Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/approximation/distance_measures.py: 26%
31 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Distance measures approximated metrics."""
3import networkx as nx
4from networkx.utils.decorators import py_random_state
6__all__ = ["diameter"]
9@py_random_state(1)
10@nx._dispatch(name="approximate_diameter")
11def diameter(G, seed=None):
12 """Returns a lower bound on the diameter of the graph G.
14 The function computes a lower bound on the diameter (i.e., the maximum eccentricity)
15 of a directed or undirected graph G. The procedure used varies depending on the graph
16 being directed or not.
18 If G is an `undirected` graph, then the function uses the `2-sweep` algorithm [1]_.
19 The main idea is to pick the farthest node from a random node and return its eccentricity.
21 Otherwise, if G is a `directed` graph, the function uses the `2-dSweep` algorithm [2]_,
22 The procedure starts by selecting a random source node $s$ from which it performs a
23 forward and a backward BFS. Let $a_1$ and $a_2$ be the farthest nodes in the forward and
24 backward cases, respectively. Then, it computes the backward eccentricity of $a_1$ using
25 a backward BFS and the forward eccentricity of $a_2$ using a forward BFS.
26 Finally, it returns the best lower bound between the two.
28 In both cases, the time complexity is linear with respect to the size of G.
30 Parameters
31 ----------
32 G : NetworkX graph
34 seed : integer, random_state, or None (default)
35 Indicator of random number generation state.
36 See :ref:`Randomness<randomness>`.
38 Returns
39 -------
40 d : integer
41 Lower Bound on the Diameter of G
43 Raises
44 ------
45 NetworkXError
46 If the graph is empty or
47 If the graph is undirected and not connected or
48 If the graph is directed and not strongly connected.
50 See Also
51 --------
52 networkx.algorithms.distance_measures.diameter
54 References
55 ----------
56 .. [1] Magnien, Clémence, Matthieu Latapy, and Michel Habib.
57 *Fast computation of empirically tight bounds for the diameter of massive graphs.*
58 Journal of Experimental Algorithmics (JEA), 2009.
59 https://arxiv.org/pdf/0904.2728.pdf
60 .. [2] Crescenzi, Pierluigi, Roberto Grossi, Leonardo Lanzi, and Andrea Marino.
61 *On computing the diameter of real-world directed (weighted) graphs.*
62 International Symposium on Experimental Algorithms. Springer, Berlin, Heidelberg, 2012.
63 https://courses.cs.ut.ee/MTAT.03.238/2014_fall/uploads/Main/diameter.pdf
64 """
65 # if G is empty
66 if not G:
67 raise nx.NetworkXError("Expected non-empty NetworkX graph!")
68 # if there's only a node
69 if G.number_of_nodes() == 1:
70 return 0
71 # if G is directed
72 if G.is_directed():
73 return _two_sweep_directed(G, seed)
74 # else if G is undirected
75 return _two_sweep_undirected(G, seed)
78def _two_sweep_undirected(G, seed):
79 """Helper function for finding a lower bound on the diameter
80 for undirected Graphs.
82 The idea is to pick the farthest node from a random node
83 and return its eccentricity.
85 ``G`` is a NetworkX undirected graph.
87 .. note::
89 ``seed`` is a random.Random or numpy.random.RandomState instance
90 """
91 # select a random source node
92 source = seed.choice(list(G))
93 # get the distances to the other nodes
94 distances = nx.shortest_path_length(G, source)
95 # if some nodes have not been visited, then the graph is not connected
96 if len(distances) != len(G):
97 raise nx.NetworkXError("Graph not connected.")
98 # take a node that is (one of) the farthest nodes from the source
99 *_, node = distances
100 # return the eccentricity of the node
101 return nx.eccentricity(G, node)
104def _two_sweep_directed(G, seed):
105 """Helper function for finding a lower bound on the diameter
106 for directed Graphs.
108 It implements 2-dSweep, the directed version of the 2-sweep algorithm.
109 The algorithm follows the following steps.
110 1. Select a source node $s$ at random.
111 2. Perform a forward BFS from $s$ to select a node $a_1$ at the maximum
112 distance from the source, and compute $LB_1$, the backward eccentricity of $a_1$.
113 3. Perform a backward BFS from $s$ to select a node $a_2$ at the maximum
114 distance from the source, and compute $LB_2$, the forward eccentricity of $a_2$.
115 4. Return the maximum between $LB_1$ and $LB_2$.
117 ``G`` is a NetworkX directed graph.
119 .. note::
121 ``seed`` is a random.Random or numpy.random.RandomState instance
122 """
123 # get a new digraph G' with the edges reversed in the opposite direction
124 G_reversed = G.reverse()
125 # select a random source node
126 source = seed.choice(list(G))
127 # compute forward distances from source
128 forward_distances = nx.shortest_path_length(G, source)
129 # compute backward distances from source
130 backward_distances = nx.shortest_path_length(G_reversed, source)
131 # if either the source can't reach every node or not every node
132 # can reach the source, then the graph is not strongly connected
133 n = len(G)
134 if len(forward_distances) != n or len(backward_distances) != n:
135 raise nx.NetworkXError("DiGraph not strongly connected.")
136 # take a node a_1 at the maximum distance from the source in G
137 *_, a_1 = forward_distances
138 # take a node a_2 at the maximum distance from the source in G_reversed
139 *_, a_2 = backward_distances
140 # return the max between the backward eccentricity of a_1 and the forward eccentricity of a_2
141 return max(nx.eccentricity(G_reversed, a_1), nx.eccentricity(G, a_2))