public class SumSweepDirectedDiameterRadius
extends java.lang.Object
We define the positive, or forward (resp., negative, or backward) eccentricity of a node v in a graph G=(V,E) as ecc ^{+}(v)=max_{w reachable from v} d(v,w) (resp., ecc^{−}( v)=max_{w reaches v} d( w,v)), 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), which is also equal to max _{v∈ V} ecc^{−}(v), while the radius is min _{v∈V'} ecc(v), where V' is a set of vertices specified by the user. These definitions are slightly different from the standard ones due to the restriction to reachable nodes. In particular, if we simply define the radius as the minimum eccentricity, the radius of a graph containing a vertex with outdegree 0 would be 0, and this does not make much sense. For this reason, we restrict our attention only to a subset V' of the set of all vertices: by choosing a suitable V', we can specialize this definition to all definitions proposed in the literature. If V' is not specified, we include in V' all vertices from which it is possible to reach the largest strongly connected component, as suggested in the aforementioned paper.
Our 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 forward and backward eccentricity of v, named lF[v], lB[v], uF[v], and uB[ 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 lF, and the diameter is found as soon as dL is bigger than uF[v] for each v, or dL is bigger than uB[v] for each v.
More specifically, the upper bound on the radius (resp., lower bound on the diameter) is defined as the minimum forward (resp., maximum forward or backward) eccentricity of a vertex from which we performed a BFS. Moreover, if we perform a forward (resp., backward) BFS from a vertex s, we update lB[v]=max(lB[v], d( s, v)) (resp., lF[v]=max( lF[v], d(v, s)). Finally, for the upper bounds, we use a more complicated procedure that handles different strongly connected components separately.
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, boolean)
for the forward or backward eccentricities.
Similarly, one can use the methods getRadiusIterations()
An exception is raised
if the field has not been computed.
Although the runningtime is O(mn) in the worstcase, the algorithm is usually much more efficient on realworld networks, when only radius and diameter are needed. If all eccentricities are needed, the algorithm could be faster than O(mn), but in many networks it achieves performances similar to the textbook algorithm, that performs a breadthfirst search from each node.
Modifier and Type  Class and Description 

static class 
SumSweepDirectedDiameterRadius.OutputLevel
The type of output requested: radius, diameter, radius and diameter, all
forward eccentricities, or all (forward and backward) eccentricities.

Modifier and Type  Field and Description 

protected int[] 
lB
Lower bound on the backward eccentricity.

protected int[] 
lF
Lower bound on the forward eccentricity.

protected int[] 
uB
Upper bound on the backward eccentricity.

protected int[] 
uF
Upper bound on the forward eccentricity.

Constructor and Description 

SumSweepDirectedDiameterRadius(ImmutableGraph graph,
SumSweepDirectedDiameterRadius.OutputLevel output,
boolean[] accRadial,
ProgressLogger pl)
Creates a new class for computing diameter and/or radius and/or all
eccentricities.

Modifier and Type  Method and Description 

static int 
argMax(double[] vec)
TODO: find better way to do it
Returns the index i such that
vec[i] is maximum.

static int 
argMax(int[] vec)
Returns the index i such that vec[i] is
maximum.

static int 
argMax(int[] vec,
int[] tieBreak,
boolean[] acc)
Returns the index i such that vec[i] is
maximum, among all indices such that acc[i] is
true.

static int 
argMin(int[] vec,
int[] tieBreak,
boolean[] acc)
Returns the index i such that vec[i] is
minimum, among all indices such that acc[i] is
true.

void 
compute()
Computes diameter, radius, and/or all eccentricities.

int 
getAllForwardIterations()
Returns the number of iteration needed to compute all forward
eccentricities, if they have already been computed (otherwise, an
exception is raised).

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,
boolean forward)
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 int[] lF
protected int[] uF
protected int[] lB
protected int[] uB
public SumSweepDirectedDiameterRadius(ImmutableGraph graph, SumSweepDirectedDiameterRadius.OutputLevel output, boolean[] accRadial, ProgressLogger pl)
graph
 a graph.pl
 a progress logger, or null
.output
 which output is requested: radius, diameter, radius and
diameter, or all eccentricities.accRadial
 the set of vertices that can be considered radial vertices. If
null, the set is automatically chosen as the set of vertices
that are in the biggest strongly connected component, or that
are able to reach the biggest strongly connected component.public static int argMax(double[] vec)
vec
 the vector of which we want to compute the argMaxpublic static int argMax(int[] vec)
vec
 the vector of which we want to compute the argMaxpublic static int argMax(int[] vec, int[] tieBreak, boolean[] acc)
vec
 the vector of which we want to compute the argMaxtieBreak
 the tiebreak vectoracc
 the vector used to decide if an index is acceptable: a
negative value means that the vertex is acceptablepublic static int argMin(int[] vec, int[] tieBreak, boolean[] acc)
vec
 the vector of which we want to compute the argMaxtieBreak
 the tiebreak vectoracc
 the vector used to decide if an index is acceptable: a
negative value means that the vertex is acceptablepublic int getRadius()
public int getDiameter()
public int getRadialVertex()
public int getDiametralVertex()
public int getEccentricity(int v, boolean forward)
v
 the vertexforward
 if True, the forward eccentricity is returned,
otherwise the backward eccentricitypublic int getRadiusIterations()
public int getDiameterIterations()
public int getAllForwardIterations()
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, boolean)
.public static void main(java.lang.String[] arg) throws java.io.IOException, JSAPException
java.io.IOException
JSAPException