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 graph
Returns: topologically_sorted_nodes – An iterable of node names in topological sorted order.
Return type: 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 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] .
References
[1] Manber, U. (1989). Introduction to algorithms - a creative approach. Addison-Wesley. http://www.amazon.com/Introduction-Algorithms-A-Creative-Approach/dp/0201120372