Extraction de cycles sans accords à partir d'un graphe non dirigé

Il y a plusieurs années, j'ai dû me plonger dans ce sujet au travail. Sur Google, à ma grande surprise, je n'ai trouvé aucune solution toute faite. Et encore, en général, rien n'est visible. J'ai donc dû développer le thème à partir de zéro.



Pour clarifier de quoi il s'agit, je vais donner l'exemple le plus simple.







Le graphique est très simple, et pour ce type de graphique, il est facile de trouver un algorithme qui sélectionne les cycles sans accords (c'est-à-dire les cycles qui n'ont pas d'auto-intersections et ne peuvent pas être divisés en cycles plus petits). Le problème est que les graphiques peuvent être beaucoup plus délicats et que tous les cas doivent être prévus. Grâce à la délibération, au codage, aux essais et erreurs, à la fin est né l'algorithme, qui fonctionne maintenant au profit des prospecteurs d'ingénierie.



Description textuelle:

1. Pour chaque sommet du graphe, nous trouvons tous les sommets adjacents et commençons à former un cycle en nous déplaçant vers chaque sommet adjacent à son tour.
2. Si le nombre de sommets adjacents (à l'exclusion de celui avec lequel vous avez entré) = 0, alors nous revenons en arrière, formant un cycle ---> item 5
3. Si le nombre de sommets adjacents (à l'exclusion de celui avec lequel vous avez entré) est égal à 1, alors nous le suivons, formant un cycle ---> item 5
4. ( , ) >=2, ( ), , ---> .5
5. — ? , ---> .2
6. , .
7. , , , .
8. , , ---> .1 ( )
9. Une fois de plus, nous parcourons le cycle et examinons les branches de gauche. Après avoir trouvé de telles branches, nous organisons une recherche en largeur d'abord (ou en profondeur d'abord, peu importe) pour chacune. Si en même temps nous nous retrouvons en haut du cycle formé (à l'exception du cycle actuel), alors nous interrompons la formation du cycle et passons à ---> item 1
10. Nous notons le cycle et allons en chercher un nouveau ---> item 1

Pseudocode plus gros:





Au début, des graphiques de plus en plus sophistiqués ont été construits pour tester l'algorithme.



ou



, au final, il a été testé sur tous les graphes d'exploration réels comme celui-ci:



je ne pense pas que ce soit optimal, mais pour le moment (environ 3 ans déjà) cela fonctionne sans échecs ni plaintes.



Je ne cite pas le code, presque personne ne s'y intéressera, et il sera difficile d'en extraire un morceau, car ce n'est qu'une petite partie du travail.