public class SumSweepUndirectedDiameterRadius
extends java.lang.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:
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.
The algorithm is exact and, although the runningtime is O( mn) in the worstcase, it is usually much faster on realworld networks.
Modifier and Type  Class and Description 

static class 
SumSweepUndirectedDiameterRadius.OutputLevel
The type of output requested: radius, diameter, radius and diameter, or
all eccentricities.

Modifier and Type  Field and Description 

protected int[] 
ecc
The array of eccentricity values.

protected int[] 
l
Lower bound on the eccentricity.

protected int[] 
u
Upper bound on the eccentricity.

Constructor and Description 

SumSweepUndirectedDiameterRadius(ImmutableGraph graph,
SumSweepUndirectedDiameterRadius.OutputLevel output,
ProgressLogger pl)
Creates a new class for computing diameter and/or radius and/or all
eccentricities.

Modifier and Type  Method and 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(java.lang.String[] arg) 
void 
sumSweepHeuristic(int start,
int iter)
Performs iter steps of the SumSweep heuristic, starting from
vertex start.

protected final int[] ecc
protected int[] l
protected int[] u
public SumSweepUndirectedDiameterRadius(ImmutableGraph graph, SumSweepUndirectedDiameterRadius.OutputLevel output, ProgressLogger pl)
graph
 a graph.pl
 a progress logger, or null
.output
 which output is requested: radius, diameter, radius and
diameter, or all eccentricities.public int getRadius()
public int getDiameter()
public int getRadialVertex()
public int getDiametralVertex()
public int getEccentricity(int v)
v
 the vertexpublic int getRadiusIterations()
public int getDiameterIterations()
public int getAllIterations()
public void sumSweepHeuristic(int start, int iter)
start
 the starting vertexiter
 the number of iterationspublic void compute()
getDiameter()
,
getRadialVertex()
and
getEccentricity(int)
.public static void main(java.lang.String[] arg) throws java.io.IOException, JSAPException
java.io.IOException
JSAPException