Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have a graph with an Eulerian cycle and no Hamiltonian cycles. I would like to divide this graph into simple cycles.
Edges may not be repeated in simple cycles.

How can this be done?

share|improve this question

migrated from stackoverflow.com Dec 24 '11 at 5:21

This question came from our site for professional and enthusiast programmers.

1  
Can you have more than one edge between two nodes in your graph? –  Thomas Ahle Dec 23 '11 at 21:54
    
Also, can the simple cycles share nodes? –  Thomas Ahle Dec 23 '11 at 21:56
    
What does 'divide' mean? I don't think the questioner intended to imply a 'partition'. I guess that it's OK for a node to be in two or more simple cycles. –  Aaron McDaid Dec 23 '11 at 22:46
    
Oh. And do you actually have the Eulerian Cycle? Or do you simply know that such a cycle exists? –  Aaron McDaid Dec 23 '11 at 22:48
    
Can you have more than one edge between two nodes in your graph? Yes Can you have more than one edge between two nodes in your graph? No What does 'divide' mean? I don't think the questioner intended to imply a 'partition'. I guess that it's OK for a node to be in two or more simple cycles. Yes, you guess correctly –  user43714 Dec 24 '11 at 13:35
add comment

3 Answers 3

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.

share|improve this answer
    
This won't work. Cutting of the first simple cycle might leave the graph in a state that is not partitionable. –  Thomas Ahle Dec 23 '11 at 22:00
    
How that? After chopping off the first simple cycle, what's left is an Eulerian cycle in the graph minus the edges used in the simple cycle, as far as I can see. –  Daniel Fischer Dec 23 '11 at 22:07
    
@ThomasAhle seeing your answer, maybe I understand. I assumed OP already has a Eulerian cycle. –  Daniel Fischer Dec 23 '11 at 22:11
    
Well it is not hard to find an Eulerian cycle iirc, but in your solution I presume you are cutting out the nodes as well? I could construct an example with 5 nodes and an Eulerian cycle, where the first simple cycle I would find takes up four nodes. Then there is just one node left. –  Thomas Ahle Dec 23 '11 at 22:13
    
Hm, actually your method probably works, if the cycles are allowed to share a vertex. –  Thomas Ahle Dec 23 '11 at 22:18
show 8 more comments

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

A -> B -> C -> D -> B -> E -> A

A ... A is a cycle, and B -> B is a cycle, but only the latter is a simple cycle

Also, two simple cycles could share many nodes and edges with each other. For example,

A -> X -> B -> Y -> A -> Z -> B

A ... A and B ... B are simple cycles which share nodes and edges with each other.

= 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 A -> B -> C -> A within this EC:

D -> A ==> B -> E -> F -> B ==> C ==> A -> D

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 A->B in your candidate simple cycle, then the next edge that you decide to include must begin at B and you can then skip over many of the following edges. This should make it easier to ignore many large parts of the search tree.

In fact, I think this algorithm is pretty much optimum efficiency for finding all simple cycles. Any thoughts?

share|improve this answer
    
In hindsight, I now think this wouldn't be a good algorithm for finding all simple cycles. (But I'm going to try to stop thinking about this as I think the original question is not very clear) –  Aaron McDaid Dec 25 '11 at 1:52
add comment

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 O(n!) algorithm: For each permutation of nodes, go through the list and see if the path you take is a partitioning in simple graphs.

But you can probably do better using dynamic programming.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.