From 77d1c6ed762dab187dc6e0df1bc410488dfd99ea Mon Sep 17 00:00:00 2001 From: serpilliere Date: Sun, 18 Jan 2015 22:59:04 +0100 Subject: DiGraph: add dominators regression test --- test/core/graph.py | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+) (limited to 'test/core/graph.py') diff --git a/test/core/graph.py b/test/core/graph.py index a419a686..eb896cfe 100644 --- a/test/core/graph.py +++ b/test/core/graph.py @@ -16,3 +16,26 @@ print [x for x in g.predecessors('a')] print [x for x in g.predecessors('b')] print [x for x in g.predecessors('c')] print [x for x in g.successors('c')] + + +""" +Test from: https://en.wikipedia.org/wiki/Dominator_(graph_theory) +""" + +g1 = DiGraph() +g1.add_edge(1, 2) +g1.add_edge(2, 3) +g1.add_edge(2, 4) +g1.add_edge(3, 5) +g1.add_edge(4, 5) +g1.add_edge(5, 2) +g1.add_edge(2, 6) + + +dominators = g1.compute_dominators() +assert(dominators[1] == set([1])) +assert(dominators[2] == set([1, 2])) +assert(dominators[3] == set([1, 2, 3])) +assert(dominators[4] == set([1, 2, 4])) +assert(dominators[5] == set([1, 2, 5])) +assert(dominators[6] == set([1, 2, 6])) -- cgit 1.4.1