networkx.algorithms.dag.lexicographical_topological_sort

lexicographical_topological_sort(G, key=None)

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.

Returns

iterable

An iterable of node names 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.