changeset 6234:7e2dd2159414

obshistory: rename cyclic to findcycle and correct its docstring If there's a cycle, we return a set, not a boolean. So we align the other return to be None instead of False and update doc and tests.
author Pierre-Yves David <pierre-yves.david@octobus.net>
date Fri, 13 May 2022 14:16:18 +0200
parents b829e905d36b
children 318b81560f8c
files hgext3rd/evolve/obshistory.py
diffstat 1 files changed, 12 insertions(+), 11 deletions(-) [+]
line wrap: on
line diff
--- a/hgext3rd/evolve/obshistory.py	Tue May 03 20:59:32 2022 +0400
+++ b/hgext3rd/evolve/obshistory.py	Fri May 13 14:16:18 2022 +0200
@@ -380,18 +380,19 @@
         # If we don't have it locally, it's obsolete
         return True
 
-def cyclic(graph):
-    """Return True if the directed graph has a cycle.
-    The graph must be represented as a dictionary mapping vertices to
-    iterables of neighbouring vertices. For example:
+def findcycle(graph):
+    """Return a set of vertices that form a cycle in the directed graph.
 
-    >>> cyclic({1: (2,), 2: (3,), 3: (1,)})
-    True
-    >>> cyclic({1: (2,), 2: (3,), 3: (4,)})
-    False
+    The first detected cycle is returned. If there's no cycle, this function
+    return None. The graph must be represented as a dictionary mapping vertices
+    to iterables of neighbouring vertices. For example:
+
+    >>> sorted(findcycle({1: (2,), 2: (3,), 3: (1,)}))
+    [1, 2, 3]
+    >>> print(findcycle({1: (2,), 2: (3,), 3: (4,)}))
+    None
 
     Taken from: https://codereview.stackexchange.com/a/86067
-
     """
     visited = set()
     o = object()
@@ -412,7 +413,7 @@
         else:
             path_set.remove(path.pop())
             stack.pop()
-    return False
+    return None
 
 def _obshistorywalker(repo, revs, walksuccessors=False, filternonlocal=False):
     """ Directly inspired by graphmod.dagwalker,
@@ -441,7 +442,7 @@
 
         # If we likely have a cycle
         if not validcandidates:
-            cycle = cyclic(nodesucc)
+            cycle = findcycle(nodesucc)
             assert cycle
 
             # Then choose a random node from the cycle