Detecting mulitple cycles in a cyclic directed graph

Question

I have a directed cyclic graph with more than one cycle in it and I need a way to detect (and list) each cycle present in the digraph.

The graph can be seen here: http://img412.imageshack.us/img412/3327/schematic.gif

This is a dummy graph put together for the sake of debugging my python script. It contains the cycles:

[n13, n14], [n6, n8, n15, n16, n7], [n6, n8, n9, n7]

The algorithm must detect every cycle in the digraph, not just the smallest nor the first it encounters.

Answer 1

You didn't really specify how you represent the Directed graph, but you can have a look at Neopythonic:Detecting Cycles in directed graph.

Answer 2

AFAIK, python-graph only finds one cycle, not all posible cycles. See:

http://groups.google.com/group/python-graph/browse_thread/thread/9170926f1bdd097b

This other article seems to solve the problem presented in this question:

http://www.bitformation.com/art/python_toposort.html

It's using the algorithm devised by R. E. Tarjan in 1972

Answer 3

You might want to try and use this library. It has a cycle detection algorithm.