I have tried out Tarjan's algorithm for cycle detection with the implementation from http://learn.yancyparedes.net/2012/03/strongly-connected-components-using-tarjans-algorithm/ .
The following graph was used for testing:
a b
a c
b a
b c
c d
d a
As an output i got the following result: Set 0: [c, b, a, d]
My problem is that i need ALL cycles, so I'm missing the Sets [a,b] and [a,c,d] in this result. Do you now if there is a way to modify the implementation to get all cycles? Or does another algorithm exists for this problem?
Thank you!
Tarjan's algorithm does not find all cycles. It finds all strongly connected components, which is not the same thing. It is not possible to find all cycles efficiently in the general case(for a full graph the size of the output is exponential. Moreover, just finding the longest cycle is already NP-hard). You can use backtracking, of course.