diff options
Diffstat (limited to 'pym/portage/util/digraph.py')
| -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 |