lexicographical_topological_sort#
- lexicographical_topological_sort(G, key=None)[source]#
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.
- Parameters
- GNetworkX digraph
A directed acyclic graph (DAG)
- keyfunction, optional
This function maps nodes to keys with which to resolve ambiguities in the sort order. Defaults to the identity function.
- Yields
- nodes
Yields the nodes in lexicographical topological sort 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.
See also
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.
Examples
>>> DG = nx.DiGraph([(2, 1), (2, 5), (1, 3), (1, 4), (5, 4)]) >>> list(nx.lexicographical_topological_sort(DG)) [2, 1, 3, 5, 4] >>> list(nx.lexicographical_topological_sort(DG, key=lambda x: -x)) [2, 5, 1, 4, 3]