networkx.algorithms.tournament.is_reachable¶
-
is_reachable
(G, s, t)[source]¶ Decides whether there is a path from
s
tot
in the tournament.This function is more theoretically efficient than the reachability checks than the shortest path algorithms in
networkx.algorithms.shortest_paths
.The given graph must be a tournament, otherwise this function’s behavior is undefined.
- Parameters
G (NetworkX graph) – A directed graph representing a tournament.
s (node) – A node in the graph.
t (node) – A node in the graph.
- Returns
Whether there is a path from
s
tot
inG
.- Return type
Notes
Although this function is more theoretically efficient than the generic shortest path functions, a speedup requires the use of parallelism. Though it may in the future, the current implementation does not use parallelism, thus you may not see much of a speedup.
This algorithm comes from [1].
References
- 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/>