it.unimi.dsi.webgraph.algo

• java.lang.Object

• ```public class SumSweepUndirectedDiameterRadius
extends java.lang.Object```
Computes the radius and/or the diameter and/or all eccentricities of an undirected 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 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 maxvV 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 running-time is O( mn) in the worst-case, it is usually much faster on real-world networks.

Author:
Michele Borassi
• ### Nested Class Summary

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

Fields
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 Summary

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

All Methods
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.
• ### Methods inherited from class java.lang.Object

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

• #### ecc

`protected final int[] ecc`
The array of eccentricity values.
• #### l

`protected int[] l`
Lower bound on the eccentricity.
• #### u

`protected int[] u`
Upper bound on the eccentricity.
• ### Constructor Detail

```public SumSweepUndirectedDiameterRadius(ImmutableGraph graph,
ProgressLogger pl)```
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.
• ### Method Detail

`public int getRadius()`
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

`public int getRadialVertex()`
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)`
Returns the eccentricity of a vertex, if it has already been computed (otherwise, an exception is raised).
Parameters:
`v` - the vertex

`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 vertex
`iter` - the number of iterations
• #### main

```public static void main(java.lang.String[] arg)
throws java.io.IOException,
JSAPException```
Throws:
`java.io.IOException`
`JSAPException`