Package it.unimi.dsi.webgraph.algo

Class FourSweepIterativeFringeDiameter

java.lang.Object
it.unimi.dsi.webgraph.algo.FourSweepIterativeFringeDiameter
@Deprecated
public class FourSweepIterativeFringeDiameter
extends Object
Deprecated.
Superseded by SumSweepDirectedDiameterRadius/SumSweepUndirectedDiameterRadius.
Computes the diameter of a symmetric (a.k.a. undirected) graph.

This class implements a variant of the heuristic algorithm proposed by Pierluigi Crescenzi, Roberto Grossi, Michel Habib, Leonardo Lanzi and Andrea Marino in “On computing the diameter of real-world undirected graphs”, presented at the Workshop on Graph Algorithms and Applications (Zurich, July 3,2011-2014), which extends the double-sweep heuristic for bounding the diameter suggested by Clémence Magnien, Matthieu Latapy and Michel Habib in “Fast computation of empirically tight bounds for the diameter of massive graphs”, J. Exp. Algorithmics, 13:1.10:1−1.10:9, ACM, 2009.

To understand why the following algorithm works, recall that the eccentricity of a node x is the maximum distance d(x, y). The minimum eccentricity over all nodes is called the radius of the graph, and a node with minimum eccentricity is called a center. The diameter is just the maximum eccentricity, so the diameter is bounded by twice the radius (but it might not be equal: a line with an even number of nodes is a counterexample). The following two observations are obvious:

  • the eccentricity of a node is a lower bound for the diameter;
  • given a node x and an integer h, 2h maximised with the eccentricities of all nodes at distance greater than h from x is an upper bound for the diameter.

The double-sweep algorithm is the standard algorithm to compute the diameter of a tree: we take a random node and locate using a breadth-first visit a farthest node x. Then, we perform a second breadth-first visit, computing the eccentricity of x, which turns out to be the diameter of the tree. When applied to a general graph, the double-sweep algorithm provides a good lower bound (in general, whenever we perform a breadth-first visit we use the resulting eccentricity to improve the current lower bound). With some (usually few) additional visits, the iterative fringe algorithm often makes it possible to make the bounds match.

More precisely, after the second visit we find a node c that is halfway between x and a node farthest from x. The node c is a tentative center of the graph, and it certainly is if the graph is a tree.

We then perform a breadth-first visit from c and compute its eccentricity h, obtaining an upper bound 2h for the diameter.

In case our upper bound does not match the lower bound, we compute the eccentricities of the fringe, that is, the set of nodes at distance h from c, by performing a breadth-first visit from each node in the fringe. At each eccentricity computed, we update our lower bound, and stop if it matches our current upper bound. Finally, when the fringe is exhausted, assuming M is the maximum of the eccentricities computed, max(2(h − 1), M) is an improved upper bound for the diameter. We iterate the procedure with the new fringe (nodes at distance h − 1), and so on, until the lower and upper bounds do match.

The description above is a bit simplified: after finding c, we actually do a double sweep again starting from c and update c accordingly. This four-sweep procedure often improves the quality (e.g., reduces the eccentricity) of c.

Performance issues

This class uses an instance of ParallelBreadthFirstVisit to ensure a high degree of parallelism (see its documentation for memory requirements).