Efficacement développer ensemble des arêtes du graphe

Question

J'ai un ensemble d'arêtes d'un graphe, et souhaite développer avec tous les bords qui partagent un sommet avec un bord. Comment pourrais-je faire cela efficacement avec boost::graphs?

La seule façon que je suis en mesure de trouver la solution naïve d'extraire toutes les sources et les sommets cibles, en utilisant boost::adjacent_vertices pour obtenir tous les contiguïtés et en créant ensuite tous les nouveaux bords avec boost::edge. Existe-t-il une meilleure façon de le faire?

Contexte : Les sommets du graphe sont centroïdes d'une triangulation du terrain, les bords relient les sommets dont les triangles correspondants sont adjacents (donc en quelque sorte un graphe dual). L'ensemble des arêtes je cherche à étendre correspond à des chemins inter-triangle qui sont bloqués, et la zone bloquée est en pleine expansion. La région est tri de la circulaire, de sorte que la plupart des bords je vais voir en utilisant mon approche naïve ci-dessus sera déjà partie de l'ensemble.

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.