SumSweepDirectedDiameterRadius
/SumSweepUndirectedDiameterRadius
.@Deprecated
public class FourSweepIterativeFringeDiameter
extends java.lang.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 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.
This class uses an instance of ParallelBreadthFirstVisit
to ensure a high degree of parallelism (see its
documentation for memory requirements).
Constructor and Description 

FourSweepIterativeFringeDiameter()
Deprecated.

Modifier and Type  Method and Description 

static void 
main(java.lang.String[] arg)
Deprecated.

static int 
run(ImmutableGraph symGraph,
int threads,
ProgressLogger pl,
long seed)
Deprecated.
Computes the diameter of a symmetric graph.

public FourSweepIterativeFringeDiameter()
public static int run(ImmutableGraph symGraph, int threads, ProgressLogger pl, long seed)
symGraph
 a symmetric graph.threads
 the requested number of threads (0 for Runtime.availableProcessors()
).pl
 a progress logger, or null
.seed
 a seed for generating random starting points.public static void main(java.lang.String[] arg) throws java.lang.IllegalArgumentException, java.lang.SecurityException, java.lang.IllegalAccessException, java.lang.reflect.InvocationTargetException, java.lang.NoSuchMethodException, JSAPException, java.io.IOException, java.lang.ClassNotFoundException, java.lang.InstantiationException
java.lang.IllegalArgumentException
java.lang.SecurityException
java.lang.IllegalAccessException
java.lang.reflect.InvocationTargetException
java.lang.NoSuchMethodException
JSAPException
java.io.IOException
java.lang.ClassNotFoundException
java.lang.InstantiationException