Extrahieren akkordloser Zyklen aus einem ungerichteten Diagramm

Vor einigen Jahren musste ich mich bei der Arbeit mit diesem Thema befassen. Zu meiner Überraschung habe ich beim Googeln keine vorgefertigten Lösungen gefunden. Und dennoch ist im Allgemeinen nichts sichtbar. Also musste ich das Thema von Grund auf neu entwickeln.



Um zu verdeutlichen, worum es geht, werde ich das einfachste Beispiel geben.







Der Graph ist sehr einfach, und für diese Art von Graph ist es einfach, einen Algorithmus zu entwickeln, der akkordlose Zyklen auswählt (d. H. Zyklen, die keine Selbstschnittpunkte haben und nicht in kleinere zerlegt werden können). Das Problem ist, dass Diagramme viel schwieriger sein können und alle Fälle berücksichtigt werden müssen. Durch Überlegung, Codierung, Versuch und Irrtum wurde am Ende der Algorithmus geboren, der nun zum Nutzen der technischen Prospektoren funktioniert.



Textbeschreibung:

1. Für jeden Scheitelpunkt des Graphen finden wir alle benachbarten Scheitelpunkte und beginnen, einen Zyklus zu bilden, indem wir uns nacheinander zu jedem benachbarten Scheitelpunkt bewegen.
2. Wenn die Anzahl benachbarter Eckpunkte (mit Ausnahme desjenigen, mit dem Sie eingegeben haben) = 0 ist, gehen wir zurück und bilden einen Zyklus ---> Punkt 5
3. Wenn die Anzahl benachbarter Eckpunkte (mit Ausnahme desjenigen, mit dem Sie eingegeben haben) gleich 1 ist, gehen wir daran entlang und bilden einen Zyklus ---> Punkt 5
4. ( , ) >=2, ( ), , ---> .5
5. — ? , ---> .2
6. , .
7. , , , .
8. , , ---> .1 ( )
9. Wir gehen noch einmal durch den Zyklus und schauen uns die linken Zweige davon an. Nachdem wir solche Zweige gefunden haben, organisieren wir für jeden eine Breitensuche (oder Tiefensuche, das spielt keine Rolle). Wenn wir gleichzeitig am Anfang des gebildeten Zyklus landen (mit Ausnahme des aktuellen), unterbrechen wir die Bildung des Zyklus und gehen zu ---> Punkt 1
10. Wir schreiben den Zyklus und suchen einen neuen ---> Punkt 1

Größerer Pseudocode:





Zuerst wurden immer ausgefeiltere Graphen erstellt, um den Algorithmus zu testen.



oder



am Ende wurde es auf allen realen Explorationsgraphen wie diesem getestet:



Ich denke nicht, dass es optimal ist, aber im Moment (bereits ungefähr 3 Jahre) funktioniert es ohne Fehler und Beschwerden.



Ich zitiere den Code nicht, kaum jemand wird sich dafür interessieren, und es wird schwierig sein, ein Stück herauszuholen, da dies nur ein kleiner Teil der Arbeit ist.