Merge pull request #218 from mrphrazer/digraph_loops

Extend digraph with loop detection algorithms

1 files changed, 29 insertions, 1 deletions

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})})