java.lang.Object

```public class SumSweepDirectedDiameterRadius
extends Object```
Computes the radius and/or the diameter and/or all eccentricities of a graph, using the SumSweep algorithm described by Michele Borassi, Pierluigi Crescenzi, Michel Habib, Walter A. Kosters, Andrea Marino, and Frank W. Takes in “Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs—With an application to the six degrees of separation games ”, Theoretical Computer Science, 586:59−80, 2015.

We define the positive, or forward (resp., negative, or backward) eccentricity of a node v in a graph G=(V,E) as ecc +(v)=maxw reachable from v d(v,w) (resp., ecc( v)=maxw 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 vV ecc+( v), which is also equal to max vV ecc(v), while the radius is min vV' 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 out-degree 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:

• only the radius is found;
• only the diameter is found;
• radius and diameter are found;
• all forward eccentricities 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, 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.

## Performance issues

Although the running-time is O(mn) in the worst-case, the algorithm is usually much more efficient on real-world 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 breadth-first search from each node.

Author:
Michele Borassi
• ## Nested Class Summary

Nested Classes
Modifier and Type Class Description
`static class ` `SumSweepDirectedDiameterRadius.OutputLevel`
The type of output requested: radius, diameter, radius and diameter, all forward eccentricities, or all (forward and backward) eccentricities.
• ## Field Summary

Fields
Modifier and Type Field 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 Summary

Constructors
Constructor 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.
• ## Method Summary

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

### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ## Field Details

• ### lF

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

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

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

protected int[] uB
Upper bound on the backward eccentricity.
• ## Constructor Details

Creates a new class for computing diameter and/or radius and/or all eccentricities.
Parameters:
`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.
• ## Method Details

• ### argMax

public static int argMax​(double[] vec)
TODO: find better way to do it Returns the index i such that vec[i] is maximum.
Parameters:
`vec` - the vector of which we want to compute the argMax
Returns:
the value i such that vec[i] is maximum
• ### argMax

public static int argMax​(int[] vec)
Returns the index i such that vec[i] is maximum.
Parameters:
`vec` - the vector of which we want to compute the argMax
Returns:
the value i such that vec[i] is maximum
• ### argMax

public 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. In case of tie, the index maximizing tieBreak is chosen.
Parameters:
`vec` - the vector of which we want to compute the argMax
`tieBreak` - the tiebreak vector
`acc` - the vector used to decide if an index is acceptable: a negative value means that the vertex is acceptable
Returns:
the value i such that vec[i] is maximum
• ### argMin

public 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. In case of tie, the index minimizing tieBreak is chosen.
Parameters:
`vec` - the vector of which we want to compute the argMax
`tieBreak` - the tiebreak vector
`acc` - the vector used to decide if an index is acceptable: a negative value means that the vertex is acceptable
Returns:
the value i such that vec[i] is maximum

Returns the radius of the graph, if it has already been computed (otherwise, an exception is raised).
Returns:
• ### getDiameter

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

Returns a radial vertex, if it has already been computed (otherwise, an exception is raised).
Returns:
• ### 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, boolean forward)
Returns the eccentricity of a vertex, if it has already been computed (otherwise, an exception is raised).
Parameters:
`v` - the vertex
`forward` - if True, the forward eccentricity is returned, otherwise the backward eccentricity
Returns:
the eccentricity of v

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
• ### getAllForwardIterations

public int getAllForwardIterations()
Returns the number of iteration needed to compute all forward eccentricities, if they have already been computed (otherwise, an exception is raised).
Returns:
the number of iterations before all forward eccentricities are 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.
Parameters:
`start` - the starting vertex
`iter` - the number of iterations
• ### compute

public void compute()
Computes diameter, radius, and/or all eccentricities. Results can be accessed by methods such as `getDiameter()`, `getRadialVertex()` and `getEccentricity(int, boolean)`.
• ### main

public static void main​(String[] arg) throws
Throws:
`IOException`
`JSAPException`