Find All Cycle Bases In a Graph, With the Vertex Coordinates Given

7
votes

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.

1
graph
Is this a c# question? You could probably find any general algorithm that solves your problem. – Tomas Jansson
@mastoj, I've edited the tag. – Graviton
change my alias... did you find a solution? Did my suggest algorithm work for you? – Tomas Jansson

1 Answers

3
votes

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.