networkx.algorithms.dag.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:	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.
Returns:	An iterable of node names in lexicographical topological sort order.
Return type:	iterable
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” [1] .