Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

networkx.algorithms.dag.all_topological_sorts

all_topological_sorts(G)[source]

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

All topological sorts of the digraph G
Return type:

generator
Raises:
  • NetworkXNotImplemented – If G is not directed
  • NetworkXUnfeasible – If G is not acyclic

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

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