# Source code for networkx.algorithms.approximation.distance_measures

```"""Distance measures approximated metrics."""

import networkx as nx
from networkx.utils.decorators import py_random_state

__all__ = ["diameter"]

[docs]
@py_random_state(1)
@nx._dispatchable(name="approximate_diameter")
def diameter(G, seed=None):
"""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
----------
G : NetworkX graph

seed : integer, random_state, or None (default)
Indicator of random number generation state.
See :ref:`Randomness<randomness>`.

Returns
-------
d : integer
Lower Bound on the Diameter of G

Examples
--------
>>> G = nx.path_graph(10)  # undirected graph
>>> nx.diameter(G)
9
>>> G = nx.cycle_graph(3, create_using=nx.DiGraph)  # directed graph
>>> nx.diameter(G)
2

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.

See Also
--------
networkx.algorithms.distance_measures.diameter

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 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
"""
# if G is empty
if not G:
raise nx.NetworkXError("Expected non-empty NetworkX graph!")
# if there's only a node
if G.number_of_nodes() == 1:
return 0
# if G is directed
if G.is_directed():
return _two_sweep_directed(G, seed)
# else if G is undirected
return _two_sweep_undirected(G, seed)

def _two_sweep_undirected(G, seed):
"""Helper function for finding a lower bound on the diameter
for undirected Graphs.

The idea is to pick the farthest node from a random node
and return its eccentricity.

``G`` is a NetworkX undirected graph.

.. note::

``seed`` is a random.Random or numpy.random.RandomState instance
"""
# select a random source node
source = seed.choice(list(G))
# get the distances to the other nodes
distances = nx.shortest_path_length(G, source)
# if some nodes have not been visited, then the graph is not connected
if len(distances) != len(G):
raise nx.NetworkXError("Graph not connected.")
# take a node that is (one of) the farthest nodes from the source
*_, node = distances
# return the eccentricity of the node
return nx.eccentricity(G, node)

def _two_sweep_directed(G, seed):
"""Helper function for finding a lower bound on the diameter
for directed Graphs.

It implements 2-dSweep, the directed version of the 2-sweep algorithm.
The algorithm follows the following steps.
1. Select a source node \$s\$ at random.
2. Perform a forward BFS from \$s\$ to select a node \$a_1\$ at the maximum
distance from the source, and compute \$LB_1\$, the backward eccentricity of \$a_1\$.
3. Perform a backward BFS from \$s\$ to select a node \$a_2\$ at the maximum
distance from the source, and compute \$LB_2\$, the forward eccentricity of \$a_2\$.
4. Return the maximum between \$LB_1\$ and \$LB_2\$.

``G`` is a NetworkX directed graph.

.. note::

``seed`` is a random.Random or numpy.random.RandomState instance
"""
# get a new digraph G' with the edges reversed in the opposite direction
G_reversed = G.reverse()
# select a random source node
source = seed.choice(list(G))
# compute forward distances from source
forward_distances = nx.shortest_path_length(G, source)
# compute backward distances  from source
backward_distances = nx.shortest_path_length(G_reversed, source)
# if either the source can't reach every node or not every node
# can reach the source, then the graph is not strongly connected
n = len(G)
if len(forward_distances) != n or len(backward_distances) != n:
raise nx.NetworkXError("DiGraph not strongly connected.")
# take a node a_1 at the maximum distance from the source in G
*_, a_1 = forward_distances
# take a node a_2 at the maximum distance from the source in G_reversed
*_, a_2 = backward_distances
# return the max between the backward eccentricity of a_1 and the forward eccentricity of a_2
return max(nx.eccentricity(G_reversed, a_1), nx.eccentricity(G, a_2))
```