Diameter, Radius and Longest Road Trips

Difficulty of diameter computation

The worst-case complexity of computing the diameter of a graph is conjectured to be quadratic in the size of the graph (more precisely the strong exponential time hypothesis (SETH) implies that diameter cannot be computed in sub-quadratic time). The basic algorithm consists in computing the distance between all pairs of nodes (and it is not known how to do better in general). This impractical for large graphs such as road networks. However, we could rely on efficient heuristics developed partly in Gang (see papers bellow).

We have implemented a variant of the heuristic presented in [2,3] that works as follows. It consists in performing successive sweeps from selected nodes of the graph. A sweep from node s is basically a Dijkstra traversal of the graph from s and returns the distance from s to any node in the graph. As the graph is oriented (road networks do have one-way links), we indeed perform two traversals per sweep: one from s providing distances from s to any node, and one to s (following arcs backwards from s) providing distances from any node to s. In particular we obtain the out-excentricity of s (that is the maximum distance from s to a node) and its in-excentricity (the maximum distance from a node to s). Each sweep also provides lower and upper bounds on the excentricities of all other nodes in the graph using triangle inequality. The main ingredient of the heuristic resides in the selection of the source node of each sweep. The basic idea is to alternatively select nodes with low (resp. high) excentricity lower (resp. upper) bound. The rationale behind this is to find central and diametral nodes, where a central node is a node with small in-/out-excentricities and a diametral node is a node with high in-/out-excentricities. The in-excentricity and out-excentricity of diametral nodes provide good lower bounds of the diameter. On the other hand, the sum of in-excentricity and out-excentricity of central nodes provide good upper bounds of the diameter. Using the known lower and upper bounds of the excentricities of each node we can further refine these bounds. If ever the two bounds match we can stop the algorithm.

This heuristic is particularly efficient when some nodes have sum of excentricities close to the diameter and few nodes are diametral. This is the case in road networks where most strongly connected components require less than 10 sweeps for the diameter computation. However, some parts of the network require more computations. This is the case for Europe that required 146 sweeps. Texas was tough also and required 198 sweeps but Corsica with 107 sweeps for fifteen thousand nodes only was more difficult compared to its size. The regions that required more than 100 sweeps are given in the table bellow. (Note that in general some graphs may require one sweep per node and the heuristic then computes all distances for all pairs of nodes.)

Most difficult diameter computations
Region	Graph size	Diameter length (travel time)	Number of sweeps used
Corsica	14916	3h 26mins	107
Wisconsin	425765	7h 17mins	110
Third largest Canary island	22519	1h 35mins	124
Taiwan	197853	6h 24mins	133
Kansas	371004	8h 51mins	136
Europe	24206021	2days 12h 49mins	146
Spain	2018009	12h 8mins	160
Texas	2003981	14h 13mins	198

We now detail the selection algorithm used as it is a variant of the one presented in [2,3]. It selects any node for the first sweep and then it selects in turn a node with: minimal lower bound of out-excentricity, maximal upper bound of in-excentricity, minimal sum of lower bounds of in- and out-excentricities, maximal upper of bound out-excentricity, minimal lower bound of in-excentricity, maximal sum of upper bounds of in- and out-excentricities. We break ties by prefering nodes with distinct lower and upper bound of excentrity and using the sum of distances to sources of sweeps performed so far.

Radius

Similar heuristic can also be used to find the radius of the network, that is the minimal out-excentricity of a node in the network. We could compute the centers of all components of the road network, that is nodes with minimal excentricities. As shown on the map bellow, the center of the largest component appears to be in Iran near Turkmenistan border. Any point in Africa, Asia or Europe can be reached within 5 days and 5 hours from that point.

Papers

• [3] Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs: With an application to the six degrees of separation games. Local version. Michele Borassi and Pierluigi Crescenzi and Michel Habib and Walter A. Kosters and Andrea Marino and Frank W. Takes. Theor. Comput. Sci., 2015.
• [2] On the Solvability of the Six Degrees of Kevin Bacon Game - A Faster Graph Diameter and Radius Computation Method. Local version. Michele Borassi and Pierluigi Crescenzi and Michel Habib and Walter A. Kosters and Andrea Marino and Frank W. Takes. 2014.
• [1] On computing the diameter of real-world undirected graphs. Local version. Pilu Crescenzi and Roberto Grossi and Michel Habib and Leonardo Lanzi and Andrea Marino. Theor. Comput. Sci., 2013.

Data

Graphs extracted from GeoFrabrik data in September 2015 (files are in 9th DIMACS format).

Acknowledgements

• Street and map information is provided by OpenStreetMap contributors.
• We used data extracted by GeoFrabrik in September 2015 from OpenStreetMap data.
• Visualization relies on OpenStreetMap, Leaflet and MapBox.
• The cluster that performed the computations is maintained by the SED team of Inria Paris.