3

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!

MarryS
  • 165
  • 2
  • 10
  • @OlaviMustanoja You can have a cycle within a cycle so this won't necessarily give you all the solutions. Imagine a fully connected 4 vertex graph for example. – biziclop Jan 15 '15 at 13:34

1 Answers1

3

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.

kraskevich
  • 18,368
  • 4
  • 33
  • 45
  • Your are right. Tarjan is not made to find all cycles. I have implemented johnson's solution to solve this problem. Thanks – MarryS Apr 15 '15 at 14:07