0
$\begingroup$

This is the algorithm I'm using: https://stackoverflow.com/questions/12367801/finding-all-cycles-in-undirected-graphs/14115627#14115627

Specifically C#, but the linked thread has numerous languages.

Worst case time complexity should be O(|V|^{2}\log |V|+|V||E|)} https://en.wikipedia.org/wiki/Johnson%27s_algorithm

My findings running benchmarks using the first algorithm linked:

[polygons (each 3 vertices and 3 edges): milliseconds]

  • 10: 332 ms (~30 vertices, 30 edges)
  • 11: 789 ms
  • 12: 2344 ms
  • 13: 7524 ms
  • 14: 16788 ms
  • 15: 54182 ms (~45 vertices, 45 edges)

That's exponential growth!

My only question: Is this a polynomial time algorithm that I'm using to find all cycles in a graph or not?

Thanks :)

$\endgroup$
  • 2
    $\begingroup$ I'm not sure what you're trying to do. Johnson's algorithm finds shortest paths, not cycles. And, since a graph may have exponentially many cycles in it, you couldn't possibly hope to list all cycles in time polynomial in the size of the input. $\endgroup$ – David Richerby Jun 6 '16 at 18:38
  • $\begingroup$ You are clearly not using the algorithm (it has description of the usage attached, but someones code to do something not intended). $\endgroup$ – Evil Jun 6 '16 at 18:59
2
$\begingroup$

The question seems based on a faulty premise. There are multiple algorithms that Johnson invented, and you're confusing them. One of his algorithms is for finding shortest paths (that's the one Wikipedia article talks about), another is for enumerating all cycles (that's the one the Stack Overflow answer cites). They don't have the same running time.

Second, you're using some random person's code, but maybe that code sucks and isn't a good/valid implementation of the algorithm. We don't do questions about code here.

Also, as David Richerby says, you obviously can't output all cycles in polynomial time if there are exponentially many of them (where there can be). Therefore, you shouldn't expect an algorithm to enumerate all cycles with polynomial running time.

Finally, you can't disprove an asymptotic running time analysis by benchmarking it on 6 points.

I think you need to read Johnson's original paper, understand it, and implement it yourself. Sometimes there are no shortcuts.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.