Algoritmi per grafico a polihedral (grafico a 3 connessi piano) isomorfismo?

Question

Ho messo qualche ricerca sull'argomento del grafico isomorfismo per i grafici Planar 3-connect, ma ci sono un'abbondanza di algoritmi di diverse restrizioni, complessità teorica e frequenza d'uso e ho problemi a trovarne uno che si trovafuori come:

.
• facile da capire
• può essere implementato con la massima chiarezza
• Buona prestazione pratica su piccoli grafici (fino ai vertici nelle dozzine)

È difficile sapere senza capire i diversi algoritmi se sto meglio con uno degli algoritmi più antichi e più specializzati per questo problema oi nuovi, più generali. Tra tutti i possibili candidati, quale è / quelli sono la migliore vestibilità?

Answer 1

Penso che l'algoritmo di Weinberg sia adatto al conto.

.

• Facile da capire: Computa Sistemi di rotazione per G e H come sottoprodotti di a Algoritmo di test di Planeria. Poiché G e H sono 3-collegati, questi sistemi di rotazione sono isomorforici fino a intercambiare in senso orario e in senso antiorario se e solo se G e H sono isomorfici. Scegli un dardo (= bordo con una direzione indicata) D in g e prova a mapparlo a tutti i frecce e in h (e ripetere per l'altro orientamento di H). Poiché G è collegato, tutti gli altri DARTS D 'possono essere raggiunti da D componendo le due operazioni del sistema di rotazione per G. Applicare le operazioni corrispondenti a E e verificare se c'è isomorfismo.

• Massima chiarezza: A parte il test di planarità, quanto sopra è una pagina del codice. Forse potresti riutilizzare il test di planarità di qualcun altro? C'è uno in aumento, per esempio. In caso contrario, penso ancora di implementare il tuo è più facile che riscrivere la nauty.

• Buone prestazioni pratiche su piccoli grafici: dopo il test di planarità, l'algoritmo di Weinberg è fondamentalmente due traversali di profondità sincronizzati per ogni dardo. Il tempo di esecuzione totale è o (| v | ^{2 ) senza costante di grandi dimensioni in agguato.}