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
undirectedgraph, then the function uses the
2-sweepalgorithm . The main idea is to pick the farthest node from a random node and return its eccentricity.
Otherwise, if G is a
directedgraph, the function uses the
2-dSweepalgorithm , 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.
- GNetworkX graph
- seedinteger, random_state, or None (default)
Indicator of random number generation state. See Randomness.
Lower Bound on the Diameter of G
If the graph is empty or If the graph is undirected and not connected or If the graph is directed and not strongly connected.
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
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