aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSebastian Luther <SebastianLuther@gmx.de>2010-06-08 13:59:41 +0200
committerZac Medico <zmedico@gentoo.org>2010-08-18 13:22:36 -0700
commit89ae49aa43435bce34879717fffa1c470b648984 (patch)
treeab259a9f93c69687596280c4698daabd9e96acb9
parentTests: Make sure the ResolverPlayground doesn't ignore DEPEND (diff)
downloadportage-89ae49aa43435bce34879717fffa1c470b648984.tar.gz
portage-89ae49aa43435bce34879717fffa1c470b648984.tar.bz2
portage-89ae49aa43435bce34879717fffa1c470b648984.zip
portage.util.digraph: Add get_cycles() and its helpers shortest_path() and bfs()
-rw-r--r--pym/portage/util/digraph.py35
1 files changed, 35 insertions, 0 deletions
diff --git a/pym/portage/util/digraph.py b/pym/portage/util/digraph.py
index 4502ed582..9852bf859 100644
--- a/pym/portage/util/digraph.py
+++ b/pym/portage/util/digraph.py
@@ -3,6 +3,7 @@
__all__ = ['digraph']
+from collections import deque
from portage.util import writemsg
class digraph(object):
@@ -274,6 +275,40 @@ class digraph(object):
for child, priorities in self.nodes[node][0].items():
output(" %s (%s)\n" % (child, priorities[-1],))
+ def bfs(self, start, ignore_priority=None):
+ queue, enqueued = deque([(None, start)]), set([start])
+ while queue:
+ parent, n = queue.popleft()
+ yield parent, n
+ new = set(self.child_nodes(n, ignore_priority)) - enqueued
+ enqueued |= new
+ queue.extend([(n, child) for child in new])
+
+ def shortest_path(self, start, end, ignore_priority=None):
+ paths = {None: []}
+ for parent, child in self.bfs(start, ignore_priority):
+ paths[child] = paths[parent] + [child]
+ if child == end:
+ return paths[child]
+ return []
+
+ def get_cycles(self, ignore_priority=None, max_length=None):
+ """
+ Returns all cycles that have at most length 'max_length'.
+ If 'max_length' is 'None', all cycles are returned.
+ """
+ all_cycles = []
+ for node in self.nodes:
+ shortest_path = None
+ for child in self.child_nodes(node, ignore_priority):
+ path = self.shortest_path(child, node, ignore_priority)
+ 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)
+ return all_cycles
+
# Backward compatibility
addnode = add
allnodes = all_nodes