diff options
Diffstat (limited to 'test')
| -rw-r--r-- | test/core/graph.py | 23 |
1 files changed, 23 insertions, 0 deletions
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])) |