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.

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.

See my answer here: https://stackoverflow.com/a/60196714/1763149 — Marcin Raczyński, Feb 12 '20 at 21:36

score 2 · Answer 1 · answered Jul 28 '10 at 10:34

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.

answered Jul 28 '10 at 10:34

Yoni H

gnrfan · Answer 2 · 2011-07-22T16:38:01.587

1

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

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

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

edited Jul 22 '11 at 16:38

answered Jul 22 '11 at 16:31

gnrfan

score 0 · Answer 3 · answered Jun 19 '11 at 08:38

0

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

answered Jun 19 '11 at 08:38

the_drow

3 Answers3