Find all the values ​​of the cycles on the graph, with the given coordinates of the vertices

Question

A similar question is posted here .

I have an undirected graph with vertices V and Edge E I am looking for an algorithm to determine all the loop bases in this graph. An example of such a graph is shown below:

Now all the vertex coordinates are known ( in contrast to the previous question and contrary to the explanation in the above diagram), so you can find the smallest cycles covering the entire graph.

In this graph, it is possible that there are edges that do not form any cycles.

What is the best algorithm for doing this?

Here is another example you can take a look at:

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

Answer 1

I have not tried this, and it is rather greedy, but should work:

• Choose one node
• Go to one of them
• Keep moving until you return to your node start, but you are not allowed to visit the old node.
• If you get a loop, save it if it does not already exist, or a subset of these nodes make up the loop. If the node in the loop is a subset of the nodes in another loop, delete the larger loop (or maybe split it into two?)
• Start with 2 with a new neighbor.
• Start with 1 with a new node.

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

Maybe this is the beginning? As I said, I have not 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 he does not completely solve the solution, since he can only recognize "true" subsets.