Najmniejszy zestaw najmniejszych pierścieni

Question

Mam nieważony, nieukierunkowany połączony wykres. Zasadniczo jest to związek chemiczny z wieloma cyklami obok siebie. Problem jest powszechny w tej dziedzinie i nazywa się tak, jak mówi tytuł. Dobry algorytm to Horton. Jednak nie wydaje mi się, aby znaleźć dokładną informację o algorytmie, krok po kroku.

Najwyraźniej mój problem polega na tym, Algorithm for finding minimal cycles in a graph, ale niestety link do strony jest wyłączony. Znalazłem tylko kod Pythona algorytmu Figueras, ale Figuearas nie działa w każdym przypadku. Czasami nie znajduje wszystkich pierścieni. Problem jest podobny do tego, Find all chordless cycles in an undirected graph, próbowałem go, ale nie działał dla bardziej złożonych wykresów, takich jak mój. Znalazłem 4-5 źródeł potrzebnych informacji, ale algorytm nie jest w pełni wyjaśniony.

Nie znalazłem żadnego algorytmu dla SSSR, chociaż wydaje się, że jest to powszechny problem, głównie w dziedzinie chemii.

Answer 1

Algorytm Hortona jest dość prosty. Opiszę to dla twojego przypadku użycia.

1. dla każdego wierzchołka v, obliczania drzewa przeszukiwanie wszerz zakorzenione w p. Dla każdego wx krawędzi w taki sposób, V, W i X mają parami różne i taki, że najmniejszy wspólny przodek W i X to V , dodaj cykl składający się z ścieżki od v do w, krawędzi wx i ścieżki od x z powrotem do v.

2. Uporządkuj te cykle według rozmiaru nieistotnego i rozważ je w kolejności. Jeśli bieżący cykl można wyrazić jako "wyłączne OR" cykli rozważanych przed nim, to nie jest on częścią podstawy.

Test w Kroku 2 jest najbardziej skomplikowaną częścią tego algorytmu. Najpierw należy zapisać akceptowany cykl i cykl kandydatów jako matrycę wypadkowości 0-1, której wiersze są indeksowane przez cykl, a kolumny są indeksowane przez krawędź, a następnie uruchomić eliminację Gaussa na tej macierzy, aby zobaczyć, czy tworzy zerowy rząd (jeśli tak, odrzuć cykl kandydatów).

Przy odrobinie wysiłku możliwe jest zaoszczędzenie kosztów ponownej eliminacji akceptowanych cykli za każdym razem, ale jest to optymalizacja.

Na przykład, jeśli mamy wykres

a---b 
| /| 
|/| 
|/ | 
c---d 

wtedy mamy matrycę jak

 ab ac bc bd cd 
abca 1 1 1 0 0 
bcdb 0 0 1 1 1 
abdca 1 1 0 1 1 

gdzie jestem oszukiwanie trochę bo abdca nie jest w rzeczywistości jednym z cykli generowanych w Krok 1.

Eliminacja przebiega w następujący sposób:

ab ac bc bd cd 
1 1 1 0 0 
0 0 1 1 1 
1 1 0 1 1 

row[2] ^= row[0]; 

ab ac bc bd cd 
1 1 1 0 0 
0 0 1 1 1 
0 0 1 1 1 

row[2] ^= row[1]; 

ab ac bc bd cd 
1 1 1 0 0 
0 0 1 1 1 
0 0 0 0 0 

tak, że zestaw cykli jest zależny (nie przechowuje ostatniego rzędu).