From 75ff9dea4e2bc141e53acaf7edb43f8b54fc56e5 Mon Sep 17 00:00:00 2001 From: Zac Medico Date: Sat, 12 May 2012 15:16:23 -0700 Subject: test_digraph: fix get_cycles for PYTHONHASHSEED --- pym/portage/tests/util/test_digraph.py | 7 ++++--- pym/portage/util/digraph.py | 15 +++++++++++---- 2 files changed, 15 insertions(+), 7 deletions(-) (limited to 'pym') diff --git a/pym/portage/tests/util/test_digraph.py b/pym/portage/tests/util/test_digraph.py index 4fb1f9571..4e858cf88 100644 --- a/pym/portage/tests/util/test_digraph.py +++ b/pym/portage/tests/util/test_digraph.py @@ -198,10 +198,11 @@ class DigraphTest(TestCase): self.assertEqual(x.shortest_path("C", "A"), ["C", "A"]) self.assertEqual(x.shortest_path("A", "C", ignore_priority=0), ["A", "B", "C"]) self.assertEqual(x.shortest_path("C", "A", ignore_priority=0), ["C", "A"]) - cycles = set(tuple(y) for y in x.get_cycles()) - self.assertEqual(cycles, set([("C", "A"), ("A", "B"), ("A", "C")])) + cycles = set(frozenset(y) for y in x.get_cycles()) + self.assertEqual(cycles, set([frozenset(["A", "B"]), frozenset(["A", "C"]), frozenset(["B", "C"])])) x.remove_edge("A", "B") - self.assertEqual(x.get_cycles(), [["C", "A"], ["A", "C"], ["C", "B"]]) + cycles = set(frozenset(y) for y in x.get_cycles()) + self.assertEqual(cycles, set([frozenset(["A", "C"]), frozenset(["C", "B"])])) x.difference_update(["C"]) self.assertEqual(x.all_nodes(), ["A", "B"]) portage.util.noiselimit = -2 diff --git a/pym/portage/util/digraph.py b/pym/portage/util/digraph.py index 1bbe10f61..f3ae658c9 100644 --- a/pym/portage/util/digraph.py +++ b/pym/portage/util/digraph.py @@ -317,16 +317,23 @@ class digraph(object): """ all_cycles = [] for node in self.nodes: + # If we have multiple paths of the same length, we have to + # return them all, so that we always get the same results + # even with PYTHONHASHSEED="random" enabled. shortest_path = None + candidates = [] for child in self.child_nodes(node, ignore_priority): path = self.shortest_path(child, node, ignore_priority) if path is None: continue - if not shortest_path or len(shortest_path) > len(path): + if not shortest_path or len(shortest_path) >= len(path): shortest_path = path - if shortest_path: - if not max_length or len(shortest_path) <= max_length: - all_cycles.append(shortest_path) + candidates.append(path) + if shortest_path and \ + (not max_length or len(shortest_path) <= max_length): + for path in candidates: + if len(path) == len(shortest_path): + all_cycles.append(path) return all_cycles # Backward compatibility -- cgit v1.2.3-1-g7c22