Espandere in modo efficiente un set di bordi grafici

Question

Ho un set di bordi da un grafico e vorrei espanderlo con tutti i bordi che condividono un vertice con qualsiasi vantaggio. Come potrei farlo in modo efficiente con boost::graphS?

L'unico modo in cui sono stato in grado di elaborare è la soluzione ingenua per estrarre tutti i vertici di origine e target, usando boost::adjacent_vertices Per ottenere tutte le adiacenze e quindi creare tutti i nuovi bordi con boost::edge. C'è un modo migliore per farlo?

Contesto: I vertici del grafico sono centroidi di una triangolazione del terreno, i bordi collegano vertici i cui triangoli corrispondenti sono adiacenti (quindi una specie di doppio grafico). Il set di bordi che sto cercando di espandere corrisponde ai percorsi inter-triangoli che sono bloccati e l'area bloccata si sta espandendo. L'area è una specie di circolare, quindi la maggior parte dei bordi vedrò usare il mio approccio ingenuo sopra farà già parte del set.

Answer 1

Invece di considerare tutti i vertici adiacenti in ogni passaggio per generare i nuovi bordi, utilizzare una mappa della proprietà per contrassegnare i bordi già incontrati. Pertanto, è necessario considerare i bordi non contrassegnati solo in ogni passaggio. Un vertice è contrassegnato dopo aver aggiunto tutti i bordi incidenti al set.

Dato che la struttura dei dati interna utilizzata da Boost :: Graph sia un elenco di adiacenza o una matrice di adiacenza, non credo che sia possibile alcun ulteriore miglioramento.