Il più piccolo set di anelli più piccoli

Question

Ho un grafico collegato non orientato non pesato. Generalmente, è un composto chimico con molti cicli affiancati. Il problema è comune in questo campo e viene chiamato come dice il titolo. Il buon algoritmo è quello di Horton. Tuttavia, non riesco a trovare alcuna informazione esatta sull'algoritmo, passo dopo passo.

In chiaro il mio problema è questo, Algorithm for finding minimal cycles in a graph, ma sfortunatamente il collegamento al sito è disabilitato. Ho trovato solo il codice Python dell'algoritmo di Figueras ma Figuearas non funziona in tutti i casi. A volte non trova tutti gli anelli. Il problema è simile a questo, Find all chordless cycles in an undirected graph, l'ho provato ma non ha funzionato per grafici più complessi come il mio. Ho trovato 4-5 fonti di informazioni necessarie, ma l'algoritmo non è del tutto spiegato.

Non riesco a trovare alcun algoritmo per SSSR anche se sembra un problema comune, principalmente nel campo della chimica.

Answer 1

L'algoritmo di Horton è piuttosto semplice. Lo descriverò per il tuo caso d'uso.

1. Per ogni vertice v, calcolare un albero di ricerca in ampiezza con radice v. Per ogni WX bordo tale che v, w, x sono distinti a coppie e tale che l'almeno antenato comune di x w ed è v , aggiungi un ciclo composto dal percorso da v a w, dal bordo wx e dal percorso da x indietro a v.

2. Ordinare questi cicli per dimensione non in diminuzione e considerarli in ordine. Se il ciclo corrente può essere espresso come "OR esclusivo" di cicli considerati prima di esso, allora non fa parte della base.

Il test del passaggio 2 è la parte più complessa di questo algoritmo. Quello che devi fare, in pratica, è scrivere il ciclo accettato e il ciclo candidato come una matrice di incidenza 0-1 le cui righe sono indicizzate per ciclo e le cui colonne sono indicizzate per margine, quindi eseguire l'eliminazione gaussiana su questa matrice per vedere se crea una riga tutto-zero (in tal caso, elimina il ciclo candidato).

Con un certo sforzo, è possibile risparmiare il costo di eliminare di nuovo i cicli accettati ogni volta, ma questa è un'ottimizzazione.

Ad esempio, se abbiamo un grafico

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

poi abbiamo una matrice come

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

dove sto imbrogliando un po 'perché abdca non è in realtà uno dei cicli generati Passaggio 1.

L'eliminazione procede come segue:

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 

in modo che l'insieme di cicli sia dipendente (non mantenere l'ultima riga).