Detecting mulitple cycles in a cyclic directed graph

I开发者_JS百科 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.

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

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

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