From 5fef7df32495bdf0040650ee6990edf6d4a0572e Mon Sep 17 00:00:00 2001 From: Sebastian Luther Date: Wed, 18 Aug 2010 21:40:26 +0200 Subject: portage.util.digraph: Raise KeyError in newly added functions. Add tests. --- pym/portage/util/digraph.py | 34 +++++++++++++++++++++------------- 1 file changed, 21 insertions(+), 13 deletions(-) (limited to 'pym/portage/util/digraph.py') diff --git a/pym/portage/util/digraph.py b/pym/portage/util/digraph.py index 9852bf859..97f9c99b2 100644 --- a/pym/portage/util/digraph.py +++ b/pym/portage/util/digraph.py @@ -276,21 +276,29 @@ class digraph(object): 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]) + if start not in self: + raise KeyError(start) + + 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 [] + if start not in self: + raise KeyError(start) + elif end not in self: + raise KeyError(end) + + paths = {None: []} + for parent, child in self.bfs(start, ignore_priority): + paths[child] = paths[parent] + [child] + if child == end: + return paths[child] + return None def get_cycles(self, ignore_priority=None, max_length=None): """ -- cgit v1.2.3-1-g7c22