#

Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

#

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 .

See also

topological_sort()

References

1

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