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.