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-insort()
. 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, aNetworkXError
is raised.- NetworkXUnfeasible
If
G
is not a directed acyclic graph (DAG) no topological sort exists and aNetworkXUnfeasible
exception is raised. This can also be raised ifG
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
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 forstr
, 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']