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

topological_sort

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]