This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.


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.

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

An iterable of node names in lexicographical topological sort order.

Return type:


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


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


[1]Manber, U. (1989). Introduction to Algorithms - A Creative Approach. Addison-Wesley.