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

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)]

Notes

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

See also

is_directed_acyclic_graph(), lexicographical_topological_sort()

References

1

Manber, U. (1989). Introduction to Algorithms - A Creative Approach. Addison-Wesley.