To make it clear what this is about, I will give the simplest example.
The graph is very simple, and for this kind of graphs it is easy to come up with an algorithm that selects chordless cycles (i.e., cycles that do not have self-intersections and cannot be split into smaller ones). The problem is that graphs can be much more tricky, and all cases must be considered. Through deliberation, coding, trial and error, in the end the algorithm was born, which now works for the benefit of engineering prospectors.
Text description:
- For each vertex of the graph, we find all adjacent vertices and begin to form a cycle by moving towards each adjacent vertex in turn.
- If the number of adjacent vertices (excluding the one with which you entered) = 0, then we go back, forming a cycle ---> item 5
- If the number of adjacent vertices (excluding the one with which you entered) is equal to 1, then we go along it, forming a cycle ---> item 5
- ( , ) >=2, ( ), , ---> .5
- — ? , ---> .2
- , .
- , , , .
- , , ---> .1 ( )
- Once again we go through the cycle and look at the left branches from it. Having found such branches, we organize a breadth-first search (or depth-first, it doesn't matter) for each. If at the same time we end up at the top of the formed cycle (except for the current one), then we interrupt the formation of the cycle and go to ---> item 1
- We write down the cycle, and go to search for a new one ---> item 1
Bigger pseudocode:
At first, more and more sophisticated graphs were built to test the algorithm.
or
, in the end, it was tested on all real exploration graphs like this:
I don’t think that it is optimal, but at the moment (about 3 years already) it works without failures and complaints.
I do not quote the code, hardly anyone will be interested in it, and it will be difficult to pull out a piece, since this is just one small part of the work.