Expandir eficientemente el conjunto de bordes de gráficos

Question

Tengo un conjunto de bordes de un gráfico, y me gustaría expandirlo con todos los bordes que comparten un vértice con cualquier borde. ¿Cómo podría hacer esto de manera eficiente con boost::graph¿s?

La única forma en que he podido encontrar es la solución ingenua de extraer todos los vértices de origen y destino, usando boost::adjacent_vertices para obtener todas las adyacencias y luego crear todos los bordes nuevos con boost::edge. ¿Hay una mejor manera de hacer esto?

Contexto: Los vértices gráficos son centroides de una triangulación de terreno, los bordes conectan los vértices cuyos triángulos correspondientes son adyacentes (así que una especie de gráfico dual). El conjunto de bordes que busco expandir corresponde a las rutas inter-triángulo que están bloqueadas, y el área bloqueada se está expandiendo. El área es una especie de circular, por lo que la mayoría de los bordes que veré con mi enfoque ingenuo anterior ya será parte del set.

Answer 1

En lugar de considerar todos los vértices adyacentes en cada paso para generar los nuevos bordes, use un mapa de propiedades para marcar los bordes ya encontrados. Por lo tanto, debe considerar solo bordes sin marcar en cada paso. Un vértice se marca después de agregarle todos los bordes incidentes a su set.

Dado el hecho de que la estructura de datos internos utilizada por Boost :: Graph es una lista de adyacencia o una matriz de adyacencia, no creo que sea posible una mejora adicional.