lexicographical_topological_sort

lexicographical_topological_sort(G, key=None)[source]

Return 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 graph
  • key (function, optional) – This function maps nodes to keys with which to resolve ambiguities in the sort order. Defaults to the identity function.
Returns:

lexicographically_topologically_sorted_nodes – 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. http://www.amazon.com/Introduction-Algorithms-A-Creative-Approach/dp/0201120372