Note
This documents the development version of NetworkX. Documentation for the current release can be found here.
networkx.algorithms.dag.topological_sort¶

topological_sort
(G)[source]¶ 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.
 Parameters
 GNetworkX digraph
A directed acyclic graph (DAG)
 Returns
 iterable
An iterable of node names in topological sorted order.
 Raises
 NetworkXError
Topological sort is defined for directed graphs only. If the graph
G
is undirected, aNetworkXError
is raised. NetworkXUnfeasible
If
G
is not a directed acyclic graph (DAG) no topological sort exists and aNetworkXUnfeasible
exception is raised. This can also be raised ifG
is changed while the returned iterator is being processed RuntimeError
If
G
is changed while the returned iterator is being processed.
Notes
This algorithm is based on a description and proof in “Introduction to Algorithms: A Creative Approach” [1] .
References
 1
Manber, U. (1989). Introduction to Algorithms  A Creative Approach. AddisonWesley.
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]
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
networkx.line_graph()
as follows:>>> list(nx.topological_sort(nx.line_graph(DG))) [(1, 2), (2, 3)]