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/tests/util/test_digraph.py | 201 +++++++++++++++++++++++++++++++++ pym/portage/util/digraph.py | 34 +++--- 2 files changed, 222 insertions(+), 13 deletions(-) create mode 100644 pym/portage/tests/util/test_digraph.py diff --git a/pym/portage/tests/util/test_digraph.py b/pym/portage/tests/util/test_digraph.py new file mode 100644 index 000000000..9b95a596f --- /dev/null +++ b/pym/portage/tests/util/test_digraph.py @@ -0,0 +1,201 @@ +# Copyright 2010 Gentoo Foundation +# Distributed under the terms of the GNU General Public License v2 + +from portage.tests import TestCase +from portage.util.digraph import digraph +#~ from portage.util import noiselimit +import portage.util + +class DigraphTest(TestCase): + + def testBackwardCompatibility(self): + g = digraph() + f = g.copy() + g.addnode("A", None) + self.assertEqual("A" in g, True) + self.assertEqual(g.empty(), False) + self.assertEqual(g.allnodes(), ["A"]) + self.assertEqual(g.allzeros(), ["A"]) + self.assertEqual(g.hasnode("A"), True) + + def testDigraphEmptyGraph(self): + g = digraph() + f = g.clone() + for x in g, f: + self.assertEqual(x.is_empty(), True) + self.assertEqual(x.contains("A"), False) + self.assertEqual(x.firstzero(), None) + self.assertRaises(KeyError, x.remove, "A") + x.delnode("A") + self.assertEqual(list(x), []) + self.assertEqual(x.get("A"), None) + self.assertEqual(x.get("A", "default"), "default") + self.assertEqual(x.all_nodes(), []) + self.assertEqual(x.leaf_nodes(), []) + self.assertEqual(x.root_nodes(), []) + self.assertRaises(KeyError, x.child_nodes, "A") + self.assertRaises(KeyError, x.parent_nodes, "A") + self.assertEqual(x.hasallzeros(), True) + self.assertRaises(KeyError, list, x.bfs("A")) + self.assertRaises(KeyError, x.shortest_path, "A", "B") + self.assertRaises(KeyError, x.remove_edge, "A", "B") + self.assertEqual(x.get_cycles(), []) + x.difference_update("A") + portage.util.noiselimit = -2 + x.debug_print() + portage.util.noiselimit = 0 + + def testDigraphCircle(self): + g = digraph() + g.add("A", "B", -1) + g.add("B", "C", 0) + g.add("C", "D", 1) + g.add("D", "A", 2) + + f = g.clone() + for x in g, f: + self.assertEqual(x.is_empty(), False) + self.assertEqual(x.contains("A"), True) + self.assertEqual(x.firstzero(), None) + self.assertRaises(KeyError, x.remove, "Z") + x.delnode("Z") + self.assertEqual(list(x), ["A", "B", "C", "D"]) + self.assertEqual(x.get("A"), "A") + self.assertEqual(x.get("A", "default"), "A") + self.assertEqual(x.all_nodes(), ["A", "B", "C", "D"]) + self.assertEqual(x.leaf_nodes(), []) + self.assertEqual(x.root_nodes(), []) + self.assertEqual(x.child_nodes("A"), ["D"]) + self.assertEqual(x.child_nodes("A", ignore_priority=2), []) + self.assertEqual(x.parent_nodes("A"), ["B"]) + self.assertEqual(x.parent_nodes("A", ignore_priority=-2), ["B"]) + self.assertEqual(x.parent_nodes("A", ignore_priority=-1), []) + self.assertEqual(x.hasallzeros(), False) + self.assertEqual(list(x.bfs("A")), [(None, "A"), ("A", "D"), ("D", "C"), ("C", "B")]) + self.assertEqual(x.shortest_path("A", "D"), ["A", "D"]) + self.assertEqual(x.shortest_path("D", "A"), ["D", "C", "B", "A"]) + self.assertEqual(x.shortest_path("A", "D", ignore_priority=2), None) + self.assertEqual(x.shortest_path("D", "A", ignore_priority=-2), ["D", "C", "B", "A"]) + cycles = set(tuple(y) for y in x.get_cycles()) + self.assertEqual(cycles, set([("D", "C", "B", "A"), ("C", "B", "A", "D"), ("B", "A", "D", "C"), \ + ("A", "D", "C", "B")])) + x.remove_edge("A", "B") + self.assertEqual(x.get_cycles(), []) + x.difference_update(["D"]) + self.assertEqual(x.all_nodes(), ["A", "B", "C"]) + portage.util.noiselimit = -2 + x.debug_print() + portage.util.noiselimit = 0 + + def testDigraphTree(self): + g = digraph() + g.add("B", "A", -1) + g.add("C", "A", 0) + g.add("D", "C", 1) + g.add("E", "C", 2) + + f = g.clone() + for x in g, f: + self.assertEqual(x.is_empty(), False) + self.assertEqual(x.contains("A"), True) + self.assertEqual(x.firstzero(), "B") + self.assertRaises(KeyError, x.remove, "Z") + x.delnode("Z") + self.assertEqual(set(x), set(["A", "B", "C", "D", "E"])) + self.assertEqual(x.get("A"), "A") + self.assertEqual(x.get("A", "default"), "A") + self.assertEqual(set(x.all_nodes()), set(["A", "B", "C", "D", "E"])) + self.assertEqual(set(x.leaf_nodes()), set(["B", "D", "E"])) + self.assertEqual(set(x.leaf_nodes(ignore_priority=0)), set(["A", "B", "D", "E"])) + self.assertEqual(x.root_nodes(), ["A"]) + self.assertEqual(set(x.root_nodes(ignore_priority=0)), set(["A", "B", "C"])) + self.assertEqual(set(x.child_nodes("A")), set(["B", "C"])) + self.assertEqual(x.child_nodes("A", ignore_priority=2), []) + self.assertEqual(x.parent_nodes("B"), ["A"]) + self.assertEqual(x.parent_nodes("B", ignore_priority=-2), ["A"]) + self.assertEqual(x.parent_nodes("B", ignore_priority=-1), []) + self.assertEqual(x.hasallzeros(), False) + self.assertEqual(list(x.bfs("A")), [(None, "A"), ("A", "C"), ("A", "B"), ("C", "E"), ("C", "D")]) + self.assertEqual(x.shortest_path("A", "D"), ["A", "C", "D"]) + self.assertEqual(x.shortest_path("D", "A"), None) + self.assertEqual(x.shortest_path("A", "D", ignore_priority=2), None) + cycles = set(tuple(y) for y in x.get_cycles()) + self.assertEqual(cycles, set()) + x.remove("D") + self.assertEqual(set(x.all_nodes()), set(["A", "B", "C", "E"])) + x.remove("C") + self.assertEqual(set(x.all_nodes()), set(["A", "B", "E"])) + portage.util.noiselimit = -2 + x.debug_print() + portage.util.noiselimit = 0 + self.assertRaises(KeyError, x.remove_edge, "A", "E") + + def testDigraphCompleteGraph(self): + g = digraph() + g.add("A", "B", -1) + g.add("B", "A", 1) + g.add("A", "C", 1) + g.add("C", "A", -1) + g.add("C", "B", 1) + g.add("B", "C", 1) + + f = g.clone() + for x in g, f: + self.assertEqual(x.is_empty(), False) + self.assertEqual(x.contains("A"), True) + self.assertEqual(x.firstzero(), None) + self.assertRaises(KeyError, x.remove, "Z") + x.delnode("Z") + self.assertEqual(list(x), ["A", "B", "C"]) + self.assertEqual(x.get("A"), "A") + self.assertEqual(x.get("A", "default"), "A") + self.assertEqual(x.all_nodes(), ["A", "B", "C"]) + self.assertEqual(x.leaf_nodes(), []) + self.assertEqual(x.root_nodes(), []) + self.assertEqual(set(x.child_nodes("A")), set(["B", "C"])) + self.assertEqual(x.child_nodes("A", ignore_priority=0), ["B"]) + self.assertEqual(set(x.parent_nodes("A")), set(["B", "C"])) + self.assertEqual(x.parent_nodes("A", ignore_priority=0), ["C"]) + self.assertEqual(x.parent_nodes("A", ignore_priority=1), []) + self.assertEqual(x.hasallzeros(), False) + self.assertEqual(list(x.bfs("A")), [(None, "A"), ("A", "C"), ("A", "B")]) + self.assertEqual(x.shortest_path("A", "C"), ["A", "C"]) + self.assertEqual(x.shortest_path("C", "A"), ["C", "A"]) + self.assertEqual(x.shortest_path("A", "C", ignore_priority=0), ["A", "B", "C"]) + self.assertEqual(x.shortest_path("C", "A", ignore_priority=0), ["C", "A"]) + cycles = set(tuple(y) for y in x.get_cycles()) + self.assertEqual(cycles, set([("C", "A"), ("A", "B"), ("A", "C")])) + x.remove_edge("A", "B") + self.assertEqual(x.get_cycles(), [["C", "A"], ["A", "C"], ["C", "B"]]) + x.difference_update(["C"]) + self.assertEqual(x.all_nodes(), ["A", "B"]) + portage.util.noiselimit = -2 + x.debug_print() + portage.util.noiselimit = 0 + + def testDigraphIgnorePriority(self): + + def always_true(dummy): + return True + + def always_false(dummy): + return False + + g = digraph() + g.add("A", "B") + + self.assertEqual(g.parent_nodes("A"), ["B"]) + self.assertEqual(g.parent_nodes("A", ignore_priority=always_false), ["B"]) + self.assertEqual(g.parent_nodes("A", ignore_priority=always_true), []) + + self.assertEqual(g.child_nodes("B"), ["A"]) + self.assertEqual(g.child_nodes("B", ignore_priority=always_false), ["A"]) + self.assertEqual(g.child_nodes("B", ignore_priority=always_true), []) + + self.assertEqual(g.leaf_nodes(), ["A"]) + self.assertEqual(g.leaf_nodes(ignore_priority=always_false), ["A"]) + self.assertEqual(g.leaf_nodes(ignore_priority=always_true), ["A", "B"]) + + self.assertEqual(g.root_nodes(), ["B"]) + self.assertEqual(g.root_nodes(ignore_priority=always_false), ["B"]) + self.assertEqual(g.root_nodes(ignore_priority=always_true), ["A", "B"]) 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