Repository: networkx/networkx
Pull request: docstring update to lexicographical_topological_sort issue 5681
Added docstring improvements to lexicographical_topological_sort as discussed in issue 5681. Partially resolves #5681 

- explains effect and purpose for lexi sort in the short and long descriptions.
- add hints for fixing un-sortable nodes
- adds hint to exception msg
- Adds example to demonstrate fixing un-sortable nodes with key function


Problem statement:
treewidth algos depend on node types
The treewidth functions appear to depend on the types of nodes in the input graph.

### Current Behavior

For example, the algos fail is there is a mix of nodes with integer and string types.

### Expected Behavior

The algos should not depend on node types, only the graph structure.

### Steps to Reproduce

```python
import networkx as nx
from networkx.algorithms.approximation import treewidth
G = nx.Graph()
G.add_nodes_from([0, 'a'])
tw, td = treewidth.treewidth_min_degree(G)
or
tw, td = treewidth.treewidth_min_fill_in(G)
```

### Environment

Python version: 3.8
NetworkX version:  2.8


### Additional context

Error:
  File "<somedir>/lib/python3.8/site-packages/networkx/algorithms/approximation/treewidth.py", line 106, in __init__
    heapify(self._degreeq)
TypeError: '<' not supported between instances of 'int' and 'str'

Hints from issue discussion:
Thanks for the report @harristeague , I can reproduce this as well.
The problem occurs while using `heapify`. So we are providing the object in `heapify` in a way that it allows comparing the nodes (perhaps only when ties on the heap priority/weight values occur. We could use some sort of unique identifier ahead of the node in the tuple put onto the heap.
The same error occurs in,
  - `lexicographical_topological_sort` in `algorithms/graphical.py`
  - `MappedQueue` in `utils/mapped_queue.py`

which also use `heapify`,

> TypeError: '<' not supported between instances of 'int' and 'str'



Thanks for those comments @brocla !!

Hmmm...  I thought the `create_tuple` function (line 375) in `dag.py` avoids the issue for `lexicographical_topological_sort`. But that is in `algorithms/dag.py` not `algorithms/graphical.py`. Perhaps I am missing something?

`MappedQueue` is a helper class that let's you put whatever you need to on the queue -- including the responsibility for the developer that is using it to make sure it is sortable.  But again, maybe I am missing the place you are referring to.

Do you have examples that don't work in those functions? Or is this comment based on looking at code?


Hello @dschult .  I should have included the examples when I had them the first time. Here is how I triggered the `TypeError`.


```
>>> G = nx.path_graph(5, create_using=nx.DiGraph)
>>> G.add_edge(2, 'a')
>>> G.edges
OutEdgeView([(0, 1), (1, 2), (2, 3), (2, 'a'), (3, 4)])
>>> list(nx.lexicographical_topological_sort(G))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/brocla/python/networkx/networkx/algorithms/dag.py", line 394, in lexicographical_topological_sort
    heapq.heappush(zero_indegree, create_tuple(child))
TypeError: '<' not supported between instances of 'str' and 'int'
```


```
>>> nx.utils.mapped_queue.MappedQueue([916, 50, 'a', 493, 237])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/brocla/python/networkx/networkx/utils/mapped_queue.py", line 132, in __init__
    self._heapify()
  File "/home/brocla/python/networkx/networkx/utils/mapped_queue.py", line 136, in _heapify
    heapq.heapify(self.heap)
TypeError: '<' not supported between instances of 'int' and 'str'
```

BTW, `heapify` is also used in these files, but I was not able to coax them into a `TypeError`.  They seem to be sorting on something besides nodes.
- `algorithms/dag.py`
- `generators/degree_seq.py`

Thanks for this! It took me a little while to recall how those two functions handle sorting. We've got it fixed so most of the time it works fine. But your examples show how our unprotected inputs can lead to problems. It would be very helpful to have better documentation; and examples to show how to handle it.

Issues:
- `lexicographical_topological_sort` has an optional second argument `key` which (just like min/max) takes a function that returns the sort value given the node. This is only needed to break ties in the lexicographical ordering. So, if a TypeError is raised due to mixed node types, the user should provide a `key` function that enables comparison of the nodes. For example:
```python
G = nx.path_graph([0, 1, 'a' ,2])
node_order = {node: i  for i, node in enumerate(G)}
nx.lexicographical_topological_sort(G, key=lambda x: node_order[x])
```
We should include an example like this one. There are many other improvements needed in that doc_string. For example, the leading paragraph description (after the one-line description) explains what a topological sort is, but not anything about a lexicographical topological sort. We should also add the TypeError as one of the exceptions that are raised, with a hint to provide a `key` input that returns values that are sortable.

- `MappingQueue` is a priority queue that sorts the items by priority. The priority values are usually provided via a dict keyed by element to the priority of that element. But you can also provide an iterator of elements as input, in which case the elements are also the priorities. To fix the example you show, the user should input a dict holding priorities rather than a list of elements. But that is not clear from the documentation. An example should be included saying that unsortable elements will cause a TypeError and showing an example of how to handle that similar to
```python
inputs = [243, 'a', 213]
node_order = {node: i for i, node in enumerate(inputs)}
M = nx.MappedQueue(node_order)
```
This doc_string does not say much at all. It should at least include a sentence that unsortable elements should have a priority assigned to them upon input via using a dict. Otherwise a TypeError will occur when the comparisons are made. And then include an example of how to make a dict to avoid this problem.

Handling `heapify` library wide:
- Each place we use heapify, we make the elements into tuples which protect the nodes from ever being compared when the tuple-elements that contain the nodes are compared. This is done by putting a unique value in the tuple before the node, e.g. `element = (priority, node_id, node)`. So long as the node_id is unique, comparing tuples will never compare the raw nodes themselves. That is why heapify doesn't lead to a TypeError in those other functions in dag.py and generators.
- In the two cases you exposed, we have provided the flexibility to use the nodes themselves. The freedom comes with responsibility to keep yourself safe. But it is hard to do that without the information about how to do that. So, we need to update the doc_strings.
Hi @dschult . Thanks for the clear explanations. It helps me understand the code and the intentions when it was written. Great.

I'd like to draft an update to the docstrings. I'll do them one at a time, `lexicographical_topological_sort` first.

#### Here is what I think I heard...
- Better explanations for the short and long descriptions. Describe lexicographical and topological without using those words.
- Add an explanation of how `key=` solves the un-sortable problem.
- Put a hint in the exception statement that points the user to the `key=` argument.
- Add an example that shows how to solve the un-sortable problem

#### A thought about the example...

Using `enumerate` to generate sortable keys also means that there won't be any lexicographic aspect to the order.
The node positions that are not determined by the topological sort will just be in the order they are stored in the Graph.


What if the example used this key?
```python
>>> sorted([2, 'c', 1, 'b', 3, 'a'], key=lambda node: (isinstance(node, str), node))
[1, 2, 3, 'a', 'b', 'c']
```
It is not general enough solve everyone's sorting problems, but good enough that the example will demonstrate lexi behavior.



That list of suggested changes looks good to me.

And I agree that the example you make by putting all strings behind every non-string works for the case of a graph with nodes that are integers or strings. I think that is good enough -- anyone with a more difficult sorting case will have to figure it out.  After all lexicographical implies that the nodes themselves are sortable somehow. :}

Commit message: 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

Patch to review:
diff --git a/networkx/algorithms/dag.py b/networkx/algorithms/dag.py
index 2b600697015..4eae4277901 100644
--- a/networkx/algorithms/dag.py
+++ b/networkx/algorithms/dag.py
@@ -304,12 +304,25 @@ def topological_sort(G):
 
 
 def lexicographical_topological_sort(G, key=None):
-    """Returns a generator of nodes in lexicographically topologically sorted
-    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
     ----------
@@ -317,13 +330,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.
+        Use to resolve 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
     ------
@@ -339,6 +352,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)])
@@ -347,6 +364,26 @@ 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 this graph because the comparison of integers 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'
+    ...
+
+    The solution is to provide a function that returns keys that do compare.
+
+    There are many ways to write a `key` function. This one returns 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
@@ -391,7 +428,12 @@ def create_tuple(node):
             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


Code review comments:
diff_hunk: @@ -304,26 +304,39 @@ def topological_sort(G):
 
 
 def lexicographical_topological_sort(G, key=None):
-    """Returns a generator of nodes in lexicographically topologically sorted
-    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.
path: networkx/algorithms/dag.py
text: @user1:
The first line should be short -- because it gets used in the docs as the text describing links to this doc_string.
I'd suggest keeping this sentence as the first part of the main description. Something like:
```suggestion
    """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.
```

diff_hunk: @@ -347,6 +364,26 @@ 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 this graph because the comparison of integers to strings
path: networkx/algorithms/dag.py
text: @user1:
```suggestion
    The sort will fail for any graph with integer and string nodes. Comparison of integer to strings
```