diff options
author | Kevin Brown <github@whidit.com> | 2022-08-18 00:27:13 -0600 |
---|---|---|
committer | Jarrod Millman <jarrod.millman@gmail.com> | 2022-08-21 10:18:38 -0700 |
commit | e8b9c382dcaaebd629289486d924e52658fbe28b (patch) | |
tree | 3d1fe5c0aaeae4fcbec80066b4e33aa52863484b | |
parent | e9de98e47fb5a3be0c6a059581472abf69bae3a0 (diff) | |
download | networkx-e8b9c382dcaaebd629289486d924e52658fbe28b.tar.gz |
docstring update to lexicographical_topological_sort issue 5681 (#5930)
* docstring update to lex-topo-sort
- explain effect and purpose for lexi sort
- add hints for fixing non-sortable nodes
- add hint to exception msg
- Add examples
* Shorten the first line of the doc_string
Co-authored-by: Dan Schult <dschult@colgate.edu>
* Generalize the description of sort failures
Co-authored-by: Dan Schult <dschult@colgate.edu>
* more succinct description of key function
Co-authored-by: Dan Schult <dschult@colgate.edu>
* improve description of key function
Co-authored-by: Dan Schult <dschult@colgate.edu>
* Black'd it.
Co-authored-by: Dan Schult <dschult@colgate.edu>
-rw-r--r-- | networkx/algorithms/dag.py | 61 |
1 files changed, 52 insertions, 9 deletions
diff --git a/networkx/algorithms/dag.py b/networkx/algorithms/dag.py index c96032d4..27f1a823 100644 --- a/networkx/algorithms/dag.py +++ b/networkx/algorithms/dag.py @@ -294,12 +294,27 @@ def topological_sort(G): def lexicographical_topological_sort(G, key=None): - """Returns a generator of nodes in lexicographically topologically sorted - order. + """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. - 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 ---------- @@ -307,13 +322,13 @@ def lexicographical_topological_sort(G, key=None): 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. + 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 in lexicographical topological sort order. + Yields the nodes of G in lexicographical topological sort order. Raises ------ @@ -329,6 +344,10 @@ def lexicographical_topological_sort(G, key=None): 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. + Examples -------- >>> DG = nx.DiGraph([(2, 1), (2, 5), (1, 3), (1, 4), (5, 4)]) @@ -337,6 +356,25 @@ def lexicographical_topological_sort(G, key=None): >>> 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'] + Notes ----- This algorithm is based on a description and proof in @@ -381,7 +419,12 @@ def lexicographical_topological_sort(G, key=None): except KeyError as err: raise RuntimeError("Graph changed during iteration") from err if indegree_map[child] == 0: - heapq.heappush(zero_indegree, create_tuple(child)) + try: + heapq.heappush(zero_indegree, create_tuple(child)) + except TypeError as err: + raise TypeError( + f"{err}\nConsider using `key=` parameter to resolve ambiguities in the sort order." + ) del indegree_map[child] yield node |