networkx.algorithms.dag.topological_sort¶

topological_sort(G)[source]¶

Return a generator of nodes in topologically sorted order.

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 acyclic graph (DAG)
Returns:	An iterable of node names in topological sorted order.
Return type:	iterable
Raises:	`NetworkXError` – Topological sort is defined for directed graphs only. If the graph `G` is undirected, a `NetworkXError` is raised. `NetworkXUnfeasible` – If `G` is not a directed acyclic graph (DAG) no topological sort exists and a `NetworkXUnfeasible` exception is raised. This can also be raised if `G` is changed while the returned iterator is being processed. `RuntimeError` – If `G` is changed while the returned iterator is being processed.

Examples

To get the reverse order of the topological sort:

>>> DG = nx.DiGraph([(1, 2), (2, 3)])
>>> list(reversed(list(nx.topological_sort(DG))))
[3, 2, 1]

Notes

This algorithm is based on a description and proof in “Introduction to Algorithms: A Creative Approach” [1] .