Graph Set Grouping

Asked Oct 28 '13 at 09:26

Active Oct 28 '13 at 11:28

Viewed 95 times

I have been trying to solve this problem in the past few days, But I don't know if this algorithm already exist.

So basically, in the image. I should be able to get 3 sets (enclosed ones)

A, C, D, B
C, D, F, E, G
A, C, F, G, E, D, B

I tried Breadth first but it seems that the "already visited" rule will not handle it, does anyone has an idea on which tree search I should look into?

The reason for this is for polygon separation.

edited Oct 28 '13 at 11:28

Bernhard Barker

54,589
14
104
138

asked Oct 28 '13 at 09:26

Albert

2

If I have understood correctly you are basically trying to count the cycles in a graph. Following link may help. http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph/ Also, isn't ACFGEDB also a group? – Abhishek Bansal Oct 28 '13 at 09:28
Could you mention explicitly WHY you should get those sets... (just to be sure solutions will really match you requirements) – subsub Oct 28 '13 at 09:29
*"already visited" rule will not handle it*. Not handle what? That's how you find a cycle, a search re-discovers a vertex. – Adam Oct 28 '13 at 09:34
@subsub, I will use it to divide a polygon. – Albert Oct 28 '13 at 09:44
2

I don't see trees here. – n. m. could be an AI Oct 28 '13 at 10:15
The problem for an arbitrary graph is NP-hard. It's called #CYCLE or #CYCLES. See e.g. [here](http://www.cs.umd.edu/~jkatz/complexity/f11/lecture23.pdf). – n. m. could be an AI Oct 28 '13 at 11:49

Graph Set Grouping

0 Answers0