ricerca di piccoli cicli in un grafico planare

Question

Ho un grafico planare non indirizzato geometrico , ovvero un grafico in cui ogni nodo ha una posizione e non ci sono 2 bordi incrociati e voglio trovare tutti i cicli che non hanno bordi che li attraversano.

Esistono buone soluzioni a questo problema?

---

Quello che sto pensando di fare è una sorta di soluzione A * :

• inserisci ogni bordo in un heap minimo come percorso
• estendi il percorso più breve con ogni opzione
• percorsi di cull che tornano indietro a quelli diversi da lì iniziano (potrebbe non essere necessario)
• percorsi di abbattimento che sarebbero i terzi a utilizzare il bordo dato

Qualcuno vede un problema con questo? Funzionerà anche?

Answer 1

Il mio primo istinto è quello di utilizzare un metodo simile a un wall follow risolutore di labirinti. In sostanza, segui i bordi e togli sempre il margine più a destra da un vertice. Tutti i cicli che incontri con questo metodo saranno i confini di una faccia. Dovrai tenere traccia di quali bordi hai attraversato in quale direzione. Dopo aver attraversato un bordo in entrambe le direzioni, hai identificato le facce che separa. Una volta che tutti i bordi sono stati attraversati in entrambe le direzioni, avrai identificato tutte le facce dai loro confini.

Answer 2

Un "bordo di attraversamento", come lo chiami tu, è generalmente noto come accordo . Pertanto, il tuo problema è trovare tutti i cicli senza accordi.

Questo documento sembra che possa aiutare.

Answer 3

Un modo semplice per farlo è semplicemente uscire ed enumerare ogni faccia. Il principio è semplice:

• Manteniamo i flag '& # 945; -visited' e '& # 946; -visited' per ogni bordo e una coppia di elenchi doppiamente collegati di bordi non visitati per ciascuno di essi. Il "& # 945;" e "& # 946;" la divisione deve corrispondere a una partizione del piano sulla linea corrispondente al bordo in questione; da che parte è & # 945; e da che parte è & # 946; è arbitrario.
• Per ogni vertice V:
  • Per ogni coppia di bordi adiacenti E = (V_1, V), E '= (V_2, V) (ovvero, ordina per angolo, accetta coppie adiacenti, nonché primo + ultimo):
  • Determina su quale lato S di E (S = & # 945; o & # 946;) V_2 si trova.
  • Cammina sulla tessera, iniziando da V, usando il lato S di E, come descritto di seguito:

Walking the tile è eseguito da:

• Lascia V = V_init
• loop:
  • V_next = il vertice di E che non è V
  • E '= Il bordo adiacente a E da V_next che si trova sul lato corrente di E
  • S '= Il lato di E' che contiene V
  • Se V_next = V, abbiamo trovato un ciclo; registra tutti i bordi che abbiamo attraversato lungo la strada e contrassegna quelle coppie di bordi come visitate.
  • Se E '= E (c'è solo un bordo), allora abbiamo raggiunto un vicolo cieco; interrompere questa passeggiata
  • Altrimenti, lascia V = V_next, E = E ', S = S' e continua.

Spero che questo abbia senso; forse ha bisogno di alcuni diagrammi per spiegare ...