Source code for networkx.algorithms.approximation.distance_measures
"""距离度量近似于度量标准。"""
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):
"""返回图 G 的直径下界。
该函数计算有向图或无向图 G 的直径（即最大偏心距）的下界。所使用的过程根据图是否为有向图而有所不同。
如果 G 是无向图，则函数使用 `2-sweep` 算法 [1]。其主要思想是从一个随机节点选择最远的节点并返回其偏心距。
否则，如果 G 是有向图，函数使用 `2-dSweep` 算法 [2]。该过程首先从随机选择的源节点 $s$ 开始，执行前向和后向 BFS。设 $a_1$ 和 $a_2$ 分别为前向和后向情况下的最远节点。然后，它使用后向 BFS 计算 $a_1$ 的后向偏心距，并使用前向 BFS 计算 $a_2$ 的前向偏心距。最后，返回两者之间的最佳下界。
在这两种情况下，时间复杂度与 G 的大小成线性关系。
Parameters
----------
G : NetworkX 图
seed : 整数, random_state, 或 None (默认)
随机数生成状态的指示器。
参见 :ref:`Randomness<randomness>` 。
Returns
-------
d : 整数
G 的直径下界
Examples
--------
>>> G = nx.path_graph(10) # 无向图
>>> nx.diameter(G)
9
>>> G = nx.cycle_graph(3, create_using=nx.DiGraph) # 有向图
>>> nx.diameter(G)
2
Raises
------
NetworkXError
如果图是空的，
或者图是无向图且不连通，
或者图是有向图且不强连通。
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):
"""辅助函数，用于寻找无向图直径的下界。
思路是从一个随机节点出发，找到距离最远的节点，并返回其偏心距。
``G`` 是一个 NetworkX 无向图。
.. note::
``seed`` 是一个 random.Random 或 numpy.random.RandomState 实例
"""
# 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):
"""用于寻找有向图中直径下界的辅助函数。
它实现了2-dSweep，即2-sweep算法的有向版本。该算法遵循以下步骤：
1. 随机选择一个源节点 $s$。
2. 从 $s$ 开始进行前向BFS，选择距离源节点最远的节点 $a_1$，并计算 $LB_1$，即 $a_1$ 的后向偏心距。
3. 从 $s$ 开始进行后向BFS，选择距离源节点最远的节点 $a_2$，并计算 $LB_2$，即 $a_2$ 的前向偏心距。
4. 返回 $LB_1$ 和 $LB_2$ 中的最大值。
`G` 是一个 NetworkX 有向图。
.. note::
`seed` 是一个 random.Random 或 numpy.random.RandomState 实例
"""
# 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))
