ansaurus

Question

Algorithm to Group All the Cycles Together

Answer 1

A:

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.)

Chris Lercher 2010-04-03 12:40:44

Don't think your solution works, what about if two cycles that dont connect directly, not nevertheless still belong to the same cycle group?

Ngu Soon Hui 2010-04-03 14:46:08

@Ngu: My intention was to test two cycles first, and combine them into one, if they're connected (combining can be done easily by an OR operation). Then continue with the next cycle. I hope I understand grouping correctly, as it is used here!

Chris Lercher 2010-04-03 15:36:51

If you want to improve performance, you could also try experimenting with testing three or four cycles at once by ANDing them (depending on how likely it is, that cycles are in one group, you could tweak the performance this way). Then "drill down" to pairs of cycles only, if a match occurred. It may even be possible to start with ANDing one half of the cycles and "drilling" down recursively...

Chris Lercher 2010-04-03 15:39:36

Answer 2

+2 A:

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.

Mark Byers 2010-04-03 12:57:18

@Thanks Mark, but is there anyway to retrieve back all the cycles inside each and every cycle group?

Ngu Soon Hui 2010-04-03 13:28:32

@Mark, also I question is asking about how to tell if cycles are connected, but in your answer you say that I need to join the nodes, can be more explicitly about this?

Ngu Soon Hui 2010-04-03 13:34:18

@Ngu: I'll leave the detecting cycles part to someone else. To determine if two cycles are connected, count the number of edges they share. Once you have detected the cycles then you can create a new graph, G'. In your example G' would contain 7 nodes, one for each cycle that you have detected. Call these new nodes R1,R2,...,R7. If two cycles are connected then create an edge between them in G'. R1 should have an edge to R6 and R7. R2 should have an edge to R3 and R7, etc... Count the connected components of that graph using any standard algorithm from Wikipedia - the answer is 1.

Mark Byers 2010-04-03 13:46:01

@Mark, now it's clearer, do you have the reference on connected component counting from Wiki? Can share?

Ngu Soon Hui 2010-04-03 14:43:48

@Ngu Soon Hui: http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29#Algorithms

Mark Byers 2010-04-03 16:06:47

ansaurus

tags:

views:

answers:

Algorithm to Group All the Cycles Together

related questions