is_reachable#

is_reachable(G, s, t)[source]#

确定在比赛中是否存在从节点 s 到节点 t 的路径。

此函数在理论上比 networkx.algorithms.shortest_paths 中的最短路径算法更高效。

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

Parameters:

GNetworkX 图: 表示一个比赛的有向图。
s节点: 图中的一个节点。
t节点: 图中的一个节点。

Returns:

bool: 是否在图 G 中存在从 s 到 t 的路径。

Notes

尽管此函数在理论上比通用的最短路径函数更高效，但加速需要使用并行性。虽然未来可能会实现并行性，但当前的实现并未使用并行性，因此您可能看不到太大的加速。

此算法来自 [1]。

References

[1]

Tantau, Till. “关于比赛可达性问题复杂性的一个注记。” 计算复杂性电子研讨会。2001年。 <http://eccc.hpi-web.de/report/2001/092/>

Examples

>>> 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

Additional backends implement this function

parallelParallel backend for NetworkX algorithms

The function parallelizes the calculation of two neighborhoods of vertices in G and checks closure conditions for each neighborhood subset in parallel.

Additional parameters:

get_chunksstr, function (default = “chunks”): A function that takes in a list of all the nodes as input and returns an iterable node_chunks. The default chunking is done by slicing the nodes into n chunks, where n is the total number of CPU cores available.

[Source]