lexicographical_topological_sort#

lexicographical_topological_sort(G, key=None)[source]#

Generate the nodes in the unique lexicographical topological sort order.

Generates a unique ordering of nodes by first sorting topologically (for which there are often multiple valid orderings) and then additionally by sorting lexicographically.

A topological sort arranges the nodes of a directed graph so that the upstream node of each directed edge precedes the downstream node. It is always possible to find a solution for directed graphs that have no cycles. There may be more than one valid solution.

Lexicographical sorting is just sorting alphabetically. It is used here to break ties in the topological sort and to determine a single, unique ordering. This can be useful in comparing sort results.

The lexicographical order can be customized by providing a function to the key= parameter. The definition of the key function is the same as used in python’s built-in sort(). The function takes a single argument and returns a key to use for sorting purposes.

Lexicographical sorting can fail if the node names are un-sortable. See the example below. The solution is to provide a function to the key= argument that returns sortable keys.

Parameters:

GNetworkX digraph: A directed acyclic graph (DAG)
keyfunction, optional: A function of one argument that converts a node name to a comparison key. It defines and resolves ambiguities in the sort order. Defaults to the identity function.

Yields:

nodes: Yields the nodes of G in lexicographical topological sort order.

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.
TypeError: Results from un-sortable node names. Consider using key= parameter to resolve ambiguities in the sort order.

See also

topological_sort

Notes

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

References

[1]

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

Examples

>>> DG = nx.DiGraph([(2, 1), (2, 5), (1, 3), (1, 4), (5, 4)])
>>> list(nx.lexicographical_topological_sort(DG))
[2, 1, 3, 5, 4]
>>> list(nx.lexicographical_topological_sort(DG, key=lambda x: -x))
[2, 5, 1, 4, 3]

The sort will fail for any graph with integer and string nodes. Comparison of integer to strings is not defined in python. Is 3 greater or less than ‘red’?

>>> DG = nx.DiGraph([(1, "red"), (3, "red"), (1, "green"), (2, "blue")])
>>> list(nx.lexicographical_topological_sort(DG))
Traceback (most recent call last):
...
TypeError: '<' not supported between instances of 'str' and 'int'
...

Incomparable nodes can be resolved using a key function. This example function allows comparison of integers and strings by returning a tuple where the first element is True for str, False otherwise. The second element is the node name. This groups the strings and integers separately so they can be compared only among themselves.

>>> key = lambda node: (isinstance(node, str), node)
>>> list(nx.lexicographical_topological_sort(DG, key=key))
[1, 2, 3, 'blue', 'green', 'red']