File size: 5,593 Bytes
6525fa6 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 |
"""Distance measures approximated metrics."""
import networkx as nx
from networkx.utils.decorators import py_random_state
__all__ = ["diameter"]
@py_random_state(1)
@nx._dispatch(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
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))
|