Class FourSweepIterativeFringeDiameter
@Deprecated public class FourSweepIterativeFringeDiameter extends Object
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 realworld undirected graphs”, presented at the Workshop on Graph Algorithms and Applications (Zurich, July 3,20112014), which extends the doublesweep 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 doublesweep algorithm is the standard algorithm to compute the diameter of a tree: we take a random node and locate using a breadthfirst visit a farthest node x. Then, we perform a second breadthfirst visit, computing the eccentricity of x, which turns out to be the diameter of the tree. When applied to a general graph, the doublesweep algorithm provides a good lower bound (in general, whenever we perform a breadthfirst 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 breadthfirst 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 breadthfirst 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 foursweep 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).

Constructor Summary
Constructors Constructor Description FourSweepIterativeFringeDiameter()
Deprecated. 
Method Summary
Modifier and Type Method Description static void
main(String[] arg)
Deprecated.static int
run(ImmutableGraph symGraph, int threads, ProgressLogger pl, long seed)
Deprecated.Computes the diameter of a symmetric graph.

Constructor Details

FourSweepIterativeFringeDiameter
public FourSweepIterativeFringeDiameter()Deprecated.


Method Details

run
Deprecated.Computes the diameter of a symmetric graph. Parameters:
symGraph
 a symmetric graph.threads
 the requested number of threads (0 forRuntime.availableProcessors()
).pl
 a progress logger, ornull
.seed
 a seed for generating random starting points. Returns:
 the diameter.

main
public static void main(String[] arg) throws IllegalArgumentException, SecurityException, IllegalAccessException, InvocationTargetException, NoSuchMethodException, JSAPException, IOException, ClassNotFoundException, InstantiationExceptionDeprecated.

SumSweepDirectedDiameterRadius
/SumSweepUndirectedDiameterRadius
.