# 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.

Notes

This algorithm is based on a description and proof in “Introduction to Algorithms: A Creative Approach”  .

References



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]
```