9.10.2. networkx.algorithms.tournament.is_reachable¶

networkx.algorithms.tournament.is_reachable(G, s, t)[source]¶

Decides whether there is a path from s to t 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:	bool Whether there is a path from s to t in G.

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

[R819]

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