is_reachable#

is_reachable(G, s, t)[源代码]#

判断在竞赛图中是否存在从节点 s 到节点 t 的路径。

与 networkx.algorithms.shortest_paths 中的最短路径算法相比，此函数在理论上进行可达性检查的效率更高。

给定的图必须是竞赛图，否则此函数的行为未定义。

参数：
GNetworkX 图

表示竞赛图的有向图。

s节点

图中的一个节点。

t节点

图中的一个节点。

返回值：
布尔值

在图 G 中是否存在从节点 s 到节点 t 的路径。

注意

尽管此函数在理论上比通用的最短路径函数更有效率，但要实现加速需要使用并行计算。虽然将来可能会，但当前的实现没有使用并行计算，因此您可能看不到明显的加速效果。

此算法来自 [1]。

参考文献

[1]

Tantau, Till. “A note on the complexity of the reachability problem for tournaments.” Electronic Colloquium on Computational Complexity. 2001. <http://eccc.hpi-web.de/report/2001/092/>

示例

>>> G = nx.DiGraph([(1, 0), (1, 3), (1, 2), (2, 3), (2, 0), (3, 0)])
>>> nx.is_tournament(G)
True
>>> nx.tournament.is_reachable(G, 1, 3)
True
>>> nx.tournament.is_reachable(G, 3, 2)
False
----

其他后端实现了此函数

parallel一个使用 joblib 并行运行图算法的 NetworkX 后端。在此处查找 nx-parallel 的配置指南 here

该函数并行计算图 G 中两个顶点的邻域，并并行检查每个邻域子集的闭包条件。

额外参数
get_chunksstr, 函数 (默认值 = “chunks”)

一个函数，接受所有节点的列表作为输入，并返回一个可迭代对象 node_chunks。默认的分块是通过将 nodes 切片成 n_jobs 块来完成的。

[Source]

在本页上