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:

GNetworkX DiGraph: A directed graph

Yields:

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