Class SumSweepUndirectedDiameterRadius
public class SumSweepUndirectedDiameterRadius extends Object
We define the eccentricity of a node v in a graph G=(V,E) as ecc(v)=max _{w reachable from v} d(v ,w), where d(v,w) is the number of edges in a shortest path from v to w. The diameter is max_{v∈V} ecc(v), and the radius is min _{v∈ V} ecc(v).
This algorithm performs some BFSs from "clever" vertices, and uses these BFSs to bound the eccentricity of all vertices. More specifically, for each vertex v, this algorithm keeps a lower and an upper bound on the eccentricity of v, named l[v], u[ v]. Furthermore, it keeps a lower bound dL on the diameter and an upper bound rU on the radius. At each step, the algorithm performs a BFS, and it updates all these bounds: the radius is found as soon as rU is smaller than the minimum value of l, and the diameter is found as soon as dL is bigger than the maximum value of u.
More specifically, the upper bound on the radius (resp., lower bound on the diameter) is defined as the minimum (resp., maximum) eccentricity of a vertex from which we performed a BFS. Moreover, if we perform a BFS from a vertex s, we update l[v]=max(l[ v], d(s, v)), and u[v ]=max(u[v], d(v, s) + ecc(s).
To use this class, it is enough to create an instance, and then invoke
compute()
. It is possible to choose between the following stopping
conditions:
 only the radius is found;
 only the diameter is found;
 radius and diameter are found;
 all eccentricities are found.
After the method compute()
is run, the output can be obtained
through the methods getRadius()
for the radius, getRadialVertex()
for a
radial vertex, getDiameter()
for the diameter, getDiametralVertex()
for a
vertex whose (forward or backward) eccentricity equals the diameter,
getEccentricity(int)
for the eccentricity of a vertex. An exception is raised
if the field has not been computed.
Performance issues
The algorithm is exact and, although the runningtime is O( mn) in the worstcase, it is usually much faster on realworld networks.
 Author:
 Michele Borassi

Nested Class Summary
Nested Classes Modifier and Type Class Description static class
SumSweepUndirectedDiameterRadius.OutputLevel
The type of output requested: radius, diameter, radius and diameter, or all eccentricities. 
Field Summary

Constructor Summary
Constructors Constructor Description SumSweepUndirectedDiameterRadius(ImmutableGraph graph, SumSweepUndirectedDiameterRadius.OutputLevel output, ProgressLogger pl)
Creates a new class for computing diameter and/or radius and/or all eccentricities. 
Method Summary
Modifier and Type Method Description void
compute()
Computes diameter, radius, and/or all eccentricities.int
getAllIterations()
Returns the number of iteration needed to compute all eccentricities, if they have already been computed (otherwise, an exception is raised).int
getDiameter()
Returns the diameter, if it has already been computed (otherwise, an exception is raised).int
getDiameterIterations()
Returns the number of iteration needed to compute the diameter, if it has already been computed (otherwise, an exception is raised).int
getDiametralVertex()
Returns a diametral vertex, if it has already been computed (otherwise, an exception is raised).int
getEccentricity(int v)
Returns the eccentricity of a vertex, if it has already been computed (otherwise, an exception is raised).int
getRadialVertex()
Returns a radial vertex, if it has already been computed (otherwise, an exception is raised).int
getRadius()
Returns the radius of the graph, if it has already been computed (otherwise, an exception is raised).int
getRadiusIterations()
Returns the number of iteration needed to compute the radius, if it has already been computed (otherwise, an exception is raised).static void
main(String[] arg)
void
sumSweepHeuristic(int start, int iter)
Performs iter steps of the SumSweep heuristic, starting from vertex start.

Field Details

ecc
protected final int[] eccThe array of eccentricity values. 
l
protected int[] lLower bound on the eccentricity. 
u
protected int[] uUpper bound on the eccentricity.


Constructor Details

SumSweepUndirectedDiameterRadius
public SumSweepUndirectedDiameterRadius(ImmutableGraph graph, SumSweepUndirectedDiameterRadius.OutputLevel output, ProgressLogger pl)Creates a new class for computing diameter and/or radius and/or all eccentricities. Parameters:
graph
 a graph.pl
 a progress logger, ornull
.output
 which output is requested: radius, diameter, radius and diameter, or all eccentricities.


Method Details

getRadius
public int getRadius()Returns the radius of the graph, if it has already been computed (otherwise, an exception is raised). Returns:
 the radius

getDiameter
public int getDiameter()Returns the diameter, if it has already been computed (otherwise, an exception is raised). Returns:
 the diameter

getRadialVertex
public int getRadialVertex()Returns a radial vertex, if it has already been computed (otherwise, an exception is raised). Returns:
 a radial vertex

getDiametralVertex
public int getDiametralVertex()Returns a diametral vertex, if it has already been computed (otherwise, an exception is raised). Returns:
 a diametral vertex

getEccentricity
public int getEccentricity(int v)Returns the eccentricity of a vertex, if it has already been computed (otherwise, an exception is raised). Parameters:
v
 the vertex

getRadiusIterations
public int getRadiusIterations()Returns the number of iteration needed to compute the radius, if it has already been computed (otherwise, an exception is raised). Returns:
 the number of iterations before the radius is found

getDiameterIterations
public int getDiameterIterations()Returns the number of iteration needed to compute the diameter, if it has already been computed (otherwise, an exception is raised). Returns:
 the number of iterations before the diameter is found

getAllIterations
public int getAllIterations()Returns the number of iteration needed to compute all eccentricities, if they have already been computed (otherwise, an exception is raised). Returns:
 the number of iterations before all eccentricities are found

sumSweepHeuristic
public void sumSweepHeuristic(int start, int iter)Performs iter steps of the SumSweep heuristic, starting from vertex start. The SumSweep heuristic performs BFSes from vertices maximizing the sum of the distance from the starting vertices of previous BFSes, and should be considered "peripheral". This way, after few iterations, usually most lower bounds on the eccentricities are tight. Parameters:
start
 the starting vertexiter
 the number of iterations

compute
public void compute()Computes diameter, radius, and/or all eccentricities. Results can be accessed by methods such asgetDiameter()
,getRadialVertex()
andgetEccentricity(int)
. 
main
 Throws:
IOException
JSAPException
