How can this be done?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
migrated from stackoverflow.com Dec 24 '11 at 5:21
This question came from our site for professional and enthusiast programmers.
Follow your Eulerian cycle. Whenever you arrive at a vertex you've been at before, the part between the two visits is a simple cycle. Chop that off and store it in the list of simple cycles, mark all vertices used in that, except the one you are at now, as unvisited. Continue until all edges have been used.
To find a Eulerian cycle, Hierholzer's method is efficient.
If you don't already know the Eulerian cycle, use Hierholzer's algorithm.
(Edited to show how to find every simple cycle in the network, not just those contained within the EC. Is this what the questioner wanted?)
Assuming that you actually already know a Eulerian cycle, then simply follow the Eulerian cycle. Every time you visit a node that you have already visited, then you have found a cycle. You should check that it is a simple cycle by making sure that there are no other repeats within this cycle. For example
Also, two simple cycles could share many nodes and edges with each other. For example,
= Finding every simple cycle in the graph =
Every simple cycle will either be contained with the Eulerian Cycle (EC), or will be spread out throughout the EC. For example of what I mean by 'spread out', we can see the simple cycle
where I've highlighted some edges by making them longer. Those edges form part of the simple cycle. So, given and EC and the goal to find every simple cycle, it's a question of enumerating all subsets of the edges in the EC.
But you can speed things up considerably with a simple observation. If you decide to include
In fact, I think this algorithm is pretty much optimum efficiency for finding all simple cycles. Any thoughts?
This problem is just as hard as finding a Hamiltonian cycle. I don't think you can use the fact that the graph has an Eulerian Cycle.
You can use the obvious
But you can probably do better using dynamic programming.