7

A similar question is posted here.

I have an undirected graph with Vertex V and Edge E. I am looking for an algorithm to identify all the cycle bases in that graph. An example of such a graph is shown below:

alt text

Now, all the vertex coordinates are known ( unlike previous question, and contrary to the explanation in the above diagram), therefore it is possible to find the smallest cycles that encompass the whole graph.

In this graph, it is possible that there are edges that don't form any cycles.

What is the best algorithm to do this?

Here's another example that you can take a look at:

Assuming that e1 is the edge that gets picked first, and the arrow shows the direction of the edge.

Community
  • 1
  • 1
Graviton
  • 81,782
  • 146
  • 424
  • 602

1 Answers1

3

I haven't tried this and it is rather greedy but should work:

  1. Pick one node
  2. Go to one it's neighbors's
  3. Keep on going until you get back to your starting node, but you're not allowed to visit an old node.
  4. If you get a cycle save it if it doesn't already exist or a subset of those node make up a cycle. If the node in the cycle is a subset of the nodes in another cycle remove the larger cycle (or maybe split it in two?)
  5. Start over at 2 with a new neighbor.
  6. Start over at 1 with a new node.

Comments: At 3 you should of course do the same thing as for step 2, so take all possible paths.

Maybe that's a start? As I said, I haven't tried it so it is not optimized.

EDIT: An undocumented and not optimized version of one implementation of the algorithm can be found here: https://gist.github.com/750015. But, it doesn't solve the solution completely since it can only recognize "true" subsets.

Tomas Jansson
  • 22,767
  • 13
  • 83
  • 137
  • @Thomas, not really working. I've my own custom solution. Thanks. – Graviton Nov 29 '10 at 13:30
  • @Thomas, let's say a node is connected to multiple edges, then how do you select with edge to continue? – Graviton Dec 21 '10 at 07:10
  • @Ngu: it doesn't matter, you're supposed to visit all edges. Note that I haven't implemented it myself, it was huts something I came up with. But I think it could be implemented as somekind of recursive algorithm. Also note that the algorithm isn't optimized, it's quite greedy. – Tomas Jansson Dec 21 '10 at 08:29
  • @Thomas, my point is let's say if you are facing two edges, which one you choose will affect what kind of faces you construct, so this question is important here. – Graviton Dec 21 '10 at 08:32
  • @Ngu: that's what step 4 should take care of. The algorithm will find all the cycles in the graph, but step 4 will split those cycles that covers multiple cycles. The only difference regarding the node you choose is that you find your faces in different order. – Tomas Jansson Dec 21 '10 at 08:59
  • @Ngu: Do you have your data structure for your nodes and vertices ready? If I got that I can try to implement the algorithm... but I can't guarantee anything since I'm a little bit busy before christmas, but it's an interesting problem. – Tomas Jansson Dec 21 '10 at 09:48
  • @Tomas, yes I have. But I have a counter example that I think your algorithm couldn't work. – Graviton Dec 21 '10 at 11:14
  • @Ngu: My algorithm might be wrong. I implemented the algorithm, or some version of it here: https://gist.github.com/750015. The problem with my implementation is that it doesn't filter out large cycles like the one made of the nodes: 1, 2, 3, 4, 5, 6, 7, 8, 9, 13, 15. And that is because that cycle is not a "true" super set of any other cycle. The code is not optimized or commented and it is pretty verbose, I wrote right from the head. – Tomas Jansson Dec 21 '10 at 15:08
  • @Thomas, it is one hell of hard problem. Also, I've updated the question with another tricky example ( for me) – Graviton Dec 21 '10 at 15:17
  • @Ngu: the solution I provided gives you all "distinct" cycles, your extra example is no problem for my solution... but I thought it was an undirected graph? The implementation in the link I provided https://gist.github.com/750015 is updated with your new example and and it is also containing your first example as well as one simple one showing were my solution fail according to your spec. If you read my code you'll see that there are no edges, and that's because I don't need them :). I connect the nodes using a list defining connected nodes. – Tomas Jansson Dec 21 '10 at 15:34
  • Also, it is a hard problem... maybe adding "true" coordinates might make it easier to solve. – Tomas Jansson Dec 21 '10 at 15:34
  • @Tomas, these are the true coordinates. I'll investigate your solution tomorrow ( it's almost 12am here Malaysia time!) and let you know the result – Graviton Dec 21 '10 at 15:53
  • @Ngu, what are the true coordinates? The nodes doesn't have any coordinates. However, it's definitely harder to find if a cycle is contained inside of another one. – Tomas Jansson Dec 21 '10 at 20:47
  • @Tomas, the coordinates, although not shown, but they are reflected in the position of the nodes where I draw them. – Graviton Dec 22 '10 at 01:13
  • @Ngu: My attempt to solve might be to simple... or it is for sure. I think you need use triangulation and investigate nodes of other cycles to see if one cycle is made up of several other ones. So the algorithm will be quite complicated. But at least my algorithm find all distinct cycles if you doesn't consider coordinates :) – Tomas Jansson Dec 22 '10 at 09:01