CODEWITHSUNDEEP
algorithmgraph
Graviton
Graviton

Reputation: 83306

Algorithm to Group All the Cycles Together

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?

Upvotes: 5

Views: 559

Answers (2)

Mark Byers
Mark Byers

Reputation: 839114

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.

Upvotes: 3

Chris Lercher
Chris Lercher

Reputation: 37798

I'm pretty sure, that this isn't the most efficient way, but this would be my initial attempt:

First exchange edges with vertices: So for your example cycles 1-2-3-4, 3-4-5-6 and 5-6-7-8, you'll need:

"12" => "A"
"23" => "B"
"34" => "C"
"45" => "D"
"56" => "E"
"67" => "F"
"78" => "G"
"41" => "H"
"63" => "I"
"85" => "J"

This gives you up to (v*(v-1))/2 vertices, but okay - it may still be good enough for a O(v^2) algorithm.

Then represent the cycles as bitfields: "1-2-3-4" becomes ABCH

ABCDEFGHIJ
1110000100

and "3-4-5-6" becomes CDEI

ABCDEFGHIJ
0011100010

So they have exactly one bit in common, which means that in the original graph, they had exactly one edge in common. This could be checked either bit by bit with O(v^2), or with binary search (first check by ANDing, if they have any bit in common, then check ANDing the first half of bits etc.)

Upvotes: 0

Related Questions