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.