Efficiently expand set of graph edges

Question

I have a set of edges from a graph, and would like to expand it with all edges that share a vertex with any edge. How could I do this efficiently with boost::graphs?

The only way I've been able to come up with is the naive solution of extracting all the source and target vertices, using boost::adjacent_vertices to get all adjacencies and then creating all the new edges with boost::edge. Is there a better way of doing this?

Context: The graph vertices are centroids of a terrain triangulation, the edges connect vertices whose corresponding triangles are adjacent (so sort of a dual graph). The set of edges I'm looking to expand corresponds to inter-triangle paths which are blocked, and the blocked area is expanding. The area is sort-of circular, so most of the edges I'll see using my naive approach above will already be part of the set.

Answer 1

Instead of considering all adjacent vertices in each step to generate the new edges, use a property map to mark edges already encounterd. Thus, you need to consider unmarked edges in each step only. A vertex is marked after adding all edges incident to it to your set.

Given the fact that the internal data structure used by boost::graph is either an adjacency list or an adjacency matrix, I do not think that any further improvement is possible.