Returns a generator of nodes in topologically sorted order.
A topological sort is a nonunique permutation of the nodes of a directed graph such that an edge from u to v implies that u appears before v in the topological sort order. This ordering is valid only if the graph has no directed cycles.
- GNetworkX digraph
A directed acyclic graph (DAG)
Yields the nodes in topological sorted order.
Topological sort is defined for directed graphs only. If the graph
Gis undirected, a
Gis not a directed acyclic graph (DAG) no topological sort exists and a
NetworkXUnfeasibleexception is raised. This can also be raised if
Gis changed while the returned iterator is being processed
Gis changed while the returned iterator is being processed.
This algorithm is based on a description and proof in “Introduction to Algorithms: A Creative Approach”  .
Manber, U. (1989). Introduction to Algorithms - A Creative Approach. Addison-Wesley.
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]
If your DiGraph naturally has the edges representing tasks/inputs and nodes representing people/processes that initiate tasks, then topological_sort is not quite what you need. You will have to change the tasks to nodes with dependence reflected by edges. The result is a kind of topological sort of the edges. This can be done with
>>> list(nx.topological_sort(nx.line_graph(DG))) [(1, 2), (2, 3)]