test_digraph: fix get_cycles for PYTHONHASHSEED

2 files changed, 15 insertions, 7 deletions

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