8.1.3. networkx.algorithms.dag.topological_sort¶

networkx.algorithms.dag.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 graph
Returns:	topologically_sorted_nodes : 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, 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.

See also

is_directed_acyclic_graph, lexicographical_topological_sort

Notes

This algorithm is based on a description and proof in Introduction to algorithms - a creative approach [R635] .

References

[R635]

(1, 2) Manber, U. (1989). Introduction to algorithms - a creative approach. Addison-Wesley. http://www.amazon.com/Introduction-Algorithms-A-Creative-Approach/dp/0201120372

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]