diameter(G, seed=None)
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 :None:None:`undirected` graph, then the function uses the :None:None:`2-sweep` algorithm . 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 :None:None:`2-dSweep` algorithm , 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.
Indicator of random number generation state. See Randomness<randomness>
.
If the graph is empty or If the graph is undirected and not connected or If the graph is directed and not strongly connected.
Lower Bound on the Diameter of G
Returns a lower bound on the diameter of the graph G.
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them