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 .