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 the2sweep
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 the2dSweep
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 realworld 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