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>

1 files changed, 52 insertions, 9 deletions

diff --git a/networkx/algorithms/dag.py b/networkx/algorithms/dag.py
index 2b600697..d1a33555 100644
--- a/networkx/algorithms/dag.py
+++ b/networkx/algorithms/dag.py
@@ -304,12 +304,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
     ----------
@@ -317,13 +332,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
     ------
@@ -339,6 +354,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 +366,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
@@ -391,7 +429,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