Skip to main content
`Ctrl`+`K`

# all_topological_sorts

all_topological_sorts(G)

  Returns a generator of _all_ topological sorts of the directed graph G.

  A topological sort is a nonunique permutation of the nodes such that an edge from u to v implies that u appears before v in the topological sort order.

  Parameters:
    G NetworkX DiGraph

      A directed graph

  Yields:
    topological_sort_order list

      a list of nodes in `G`, representing one of the topological sort orders

  Raises:
    NetworkXNotImplemented

      If `G` is not directed

    NetworkXUnfeasible

      If `G` is not acyclic

  Notes

  Implements an iterative version of the algorithm given in [1].

  References

  [1]

  Knuth, Donald E., Szwarcfiter, Jayme L. (1974). “A Structured Program to Generate All Topological Sorting Arrangements” Information Processing Letters, Volume 2, Issue 6, 1974, Pages 153-157, ISSN 0020-0190, https://doi.org/10.1016/0020-0190(74)90001-5. Elsevier (North-Holland), Amsterdam

  Examples

  To enumerate all topological sorts of directed graph:

      >>> DG = nx.DiGraph([(1, 2), (2, 3), (2, 4)])
      >>> list(nx.all_topological_sorts(DG))
      [[1, 2, 4, 3], [1, 2, 3, 4]]