Detecting mulitple cycles in a cyclic directed graph (python)

Question

Hello,

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.

Thank you,

R

Answer 1

http://en.wikipedia.org/wiki/Cycle_detection

Tortoise and hare algorithm. Article contains Python samples

Answer 2

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