diff options
author | Sebastian Luther <SebastianLuther@gmx.de> | 2010-08-18 21:40:26 +0200 |
---|---|---|
committer | Zac Medico <zmedico@gentoo.org> | 2010-08-18 13:22:36 -0700 |
commit | 5fef7df32495bdf0040650ee6990edf6d4a0572e (patch) | |
tree | fd882ad0c7f9d738567fd295b46fde263699e068 /pym/portage/util/digraph.py | |
parent | 1d92b35e2b24c7f0269a295ac78887132a96a643 (diff) | |
download | portage-5fef7df32495bdf0040650ee6990edf6d4a0572e.tar.gz portage-5fef7df32495bdf0040650ee6990edf6d4a0572e.tar.bz2 portage-5fef7df32495bdf0040650ee6990edf6d4a0572e.zip |
portage.util.digraph: Raise KeyError in newly added functions. Add tests.
Diffstat (limited to 'pym/portage/util/digraph.py')
-rw-r--r-- | pym/portage/util/digraph.py | 34 |
1 files changed, 21 insertions, 13 deletions
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): """ |