diff options
author | Sebastian Luther <SebastianLuther@gmx.de> | 2010-06-08 13:59:41 +0200 |
---|---|---|
committer | Zac Medico <zmedico@gentoo.org> | 2010-08-18 13:22:36 -0700 |
commit | 89ae49aa43435bce34879717fffa1c470b648984 (patch) | |
tree | ab259a9f93c69687596280c4698daabd9e96acb9 | |
parent | 3268dd33bd5811f6cced00959efb390bc173f3b3 (diff) | |
download | portage-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.py | 35 |
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 |