Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

networkx.algorithms.approximation.distance_measures.diameter

diameter(G, seed=None)[source]

Returns a lower bound on the diameter of the graph G.

The function computes a lower bound on the diameter (i.e., the maximum eccentricity) of a directed or undirected graph G. The procedure used varies depending on the graph being directed or not.

If G is an undirected graph, then the function uses the 2-sweep algorithm [1]. The main idea is to pick the farthest node from a random node and return its eccentricity.

Otherwise, if G is a directed graph, the function uses the 2-dSweep algorithm [2], The procedure starts by selecting a random source node \(s\) from which it performs a forward and a backward BFS. Let \(a_1\) and \(a_2\) be the farthest nodes in the forward and backward cases, respectively. Then, it computes the backward eccentricity of \(a_1\) using a backward BFS and the forward eccentricity of \(a_2\) using a forward BFS. Finally, it returns the best lower bound between the two.

In both cases, the time complexity is linear with respect to the size of G.

Parameters
GNetworkX graph
seedinteger, random_state, or None (default)

Indicator of random number generation state. See Randomness.

Returns
dinteger

Lower Bound on the Diameter of G

Raises
NetworkXError

If the graph is empty or If the graph is undirected and not connected or If the graph is directed and not strongly connected.

References

1

Magnien, Clémence, Matthieu Latapy, and Michel Habib. Fast computation of empirically tight bounds for the diameter of massive graphs. Journal of Experimental Algorithmics (JEA), 2009. https://arxiv.org/pdf/0904.2728.pdf

2

Crescenzi, Pierluigi, Roberto Grossi, Leonardo Lanzi, and Andrea Marino. On computing the diameter of real-world directed (weighted) graphs. International Symposium on Experimental Algorithms. Springer, Berlin, Heidelberg, 2012. https://courses.cs.ut.ee/MTAT.03.238/2014_fall/uploads/Main/diameter.pdf