Returns a generator of nodes in lexicographically 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.
G (NetworkX digraph) – A directed acyclic graph (DAG)
key (function, optional) – This function maps nodes to keys with which to resolve ambiguities in the sort order. Defaults to the identity function.
An iterable of node names in lexicographical topological sort order.
- Return type
NetworkXError – Topological sort is defined for directed graphs only. If the graph
Gis undirected, a
NetworkXUnfeasible – If
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
RuntimeError – If
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” 1 .
Manber, U. (1989). Introduction to Algorithms - A Creative Approach. Addison-Wesley.