Algorithm to Group All the Cycles Together

Question

I have a lot of cycles ( indicated by numeric values, for example, 1-2-3-4 corresponds to a cycle, with 4 edges, edge 1 is {1:2}, edge 2 is {2:3}, edge 3 is {3,4}, edge 4 is {4,1}, and so on).

A cycle is said to be connected to another cycle if they share one and only one edge.

For example, let's say I have two cycles 1-2-3-4 and 5-6-7-8, then there are two cycle groups because these two cycles are not connecting to each other. If I have two cycles 1-2-3-4 and 3-4-5-6, then I have only one cycle group because these two cycles share the same edge.

The figure below should be able to illustrate my point:

alt text http://lh5.ggpht.com/_SDci0Pf3tzU/SuBhd07xbWI/AAAAAAAAFMs/9OlMhN8uzzQ/s640/mst.jpg

The R1, R2 to R7 are what I call "cycle". In the above figure, there is only one cycle group encompassing all the R1 to R7.

What is the most efficient way to find all the cycle groups?

Answer 1

First find all the cycles in the graph and label them for example A, B, C, etc. Now make a new graph where each cycle found in the graph is converted to a single node in the new graph. Join the nodes with an edge in the new graph if the corresponding cycles are "connected" in the old graph, using your (rather unusual) definition of connected.

The number of "cycle groups" is then the number of connected components in the new graph.