From 15a3aba4408afafd1b3c3b84058a72075a6bc8ca Mon Sep 17 00:00:00 2001 From: Tim Blazytko Date: Thu, 3 Sep 2015 09:07:27 +0200 Subject: DiGraph: added regression tests for strongly connected components and natural loops --- test/core/graph.py | 30 +++++++++++++++++++++++++++++- 1 file changed, 29 insertions(+), 1 deletion(-) (limited to 'test/core/graph.py') diff --git a/test/core/graph.py b/test/core/graph.py index 5100cf8d..86175c91 100644 --- a/test/core/graph.py +++ b/test/core/graph.py @@ -163,4 +163,32 @@ assert(frontier == {7: set([9]), frontier = g2.compute_dominance_frontier(5) assert(frontier == {7: set([9]), - 8: set([9])}) \ No newline at end of file + 8: set([9])}) + +# Regression test with natural loops and irreducible loops +g3 = DiGraph() +g3.add_edge(1, 2) +g3.add_edge(1, 3) +g3.add_edge(2, 4) +g3.add_edge(2, 5) +g3.add_edge(3, 7) +g3.add_edge(3, 8) +g3.add_edge(4, 9) +g3.add_edge(5, 9) +g3.add_edge(7, 6) +g3.add_edge(8, 6) +g3.add_edge(9, 6) +g3.add_edge(9, 2) +g3.add_edge(9, 1) +g3.add_edge(7, 8) +g3.add_edge(8, 7) + +loops = set([(backedge, frozenset(body)) for backedge, body in g3.compute_natural_loops(1)]) +assert(loops == {((1, 9), frozenset({1, 2, 4, 5, 9})), + ((2, 9), frozenset({2, 4, 5, 9}))}) + +sccs = set([frozenset(scc) for scc in g3.compute_strongly_connected_components()]) +assert(sccs == {frozenset({6}), + frozenset({7, 8}), + frozenset({3}), + frozenset({1, 2, 4, 5, 9})}) -- cgit 1.4.1