Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
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._dispatchable(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 Examples
44 --------
45 >>> G = nx.path_graph(10) # undirected graph
46 >>> nx.diameter(G)
47 9
48 >>> G = nx.cycle_graph(3, create_using=nx.DiGraph) # directed graph
49 >>> nx.diameter(G)
50 2
52 Raises
53 ------
54 NetworkXError
55 If the graph is empty or
56 If the graph is undirected and not connected or
57 If the graph is directed and not strongly connected.
59 See Also
60 --------
61 networkx.algorithms.distance_measures.diameter
63 References
64 ----------
65 .. [1] Magnien, Clémence, Matthieu Latapy, and Michel Habib.
66 *Fast computation of empirically tight bounds for the diameter of massive graphs.*
67 Journal of Experimental Algorithmics (JEA), 2009.
68 https://arxiv.org/pdf/0904.2728.pdf
69 .. [2] Crescenzi, Pierluigi, Roberto Grossi, Leonardo Lanzi, and Andrea Marino.
70 *On computing the diameter of real-world directed (weighted) graphs.*
71 International Symposium on Experimental Algorithms. Springer, Berlin, Heidelberg, 2012.
72 https://courses.cs.ut.ee/MTAT.03.238/2014_fall/uploads/Main/diameter.pdf
73 """
74 # if G is empty
75 if not G:
76 raise nx.NetworkXError("Expected non-empty NetworkX graph!")
77 # if there's only a node
78 if G.number_of_nodes() == 1:
79 return 0
80 # if G is directed
81 if G.is_directed():
82 return _two_sweep_directed(G, seed)
83 # else if G is undirected
84 return _two_sweep_undirected(G, seed)
87def _two_sweep_undirected(G, seed):
88 """Helper function for finding a lower bound on the diameter
89 for undirected Graphs.
91 The idea is to pick the farthest node from a random node
92 and return its eccentricity.
94 ``G`` is a NetworkX undirected graph.
96 .. note::
98 ``seed`` is a random.Random or numpy.random.RandomState instance
99 """
100 # select a random source node
101 source = seed.choice(list(G))
102 # get the distances to the other nodes
103 distances = nx.shortest_path_length(G, source)
104 # if some nodes have not been visited, then the graph is not connected
105 if len(distances) != len(G):
106 raise nx.NetworkXError("Graph not connected.")
107 # take a node that is (one of) the farthest nodes from the source
108 *_, node = distances
109 # return the eccentricity of the node
110 return nx.eccentricity(G, node)
113def _two_sweep_directed(G, seed):
114 """Helper function for finding a lower bound on the diameter
115 for directed Graphs.
117 It implements 2-dSweep, the directed version of the 2-sweep algorithm.
118 The algorithm follows the following steps.
119 1. Select a source node $s$ at random.
120 2. Perform a forward BFS from $s$ to select a node $a_1$ at the maximum
121 distance from the source, and compute $LB_1$, the backward eccentricity of $a_1$.
122 3. Perform a backward BFS from $s$ to select a node $a_2$ at the maximum
123 distance from the source, and compute $LB_2$, the forward eccentricity of $a_2$.
124 4. Return the maximum between $LB_1$ and $LB_2$.
126 ``G`` is a NetworkX directed graph.
128 .. note::
130 ``seed`` is a random.Random or numpy.random.RandomState instance
131 """
132 # get a new digraph G' with the edges reversed in the opposite direction
133 G_reversed = G.reverse()
134 # select a random source node
135 source = seed.choice(list(G))
136 # compute forward distances from source
137 forward_distances = nx.shortest_path_length(G, source)
138 # compute backward distances from source
139 backward_distances = nx.shortest_path_length(G_reversed, source)
140 # if either the source can't reach every node or not every node
141 # can reach the source, then the graph is not strongly connected
142 n = len(G)
143 if len(forward_distances) != n or len(backward_distances) != n:
144 raise nx.NetworkXError("DiGraph not strongly connected.")
145 # take a node a_1 at the maximum distance from the source in G
146 *_, a_1 = forward_distances
147 # take a node a_2 at the maximum distance from the source in G_reversed
148 *_, a_2 = backward_distances
149 # return the max between the backward eccentricity of a_1 and the forward eccentricity of a_2
150 return max(nx.eccentricity(G_reversed, a_1), nx.eccentricity(G, a_2))