Mercurial > evolve
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