Skip to main content
`Ctrl`+`K`

# is_reachable

is_reachable(G, s, t)

  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

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

  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