グラフエッジのセットを効率的に拡張します

Question

グラフからのエッジのセットがあり、頂点をあらゆるエッジと共有するすべてのエッジで拡張したいと考えています。どうすればこれを効率的に行うことができますか boost::graphs？

私が思いつくことができた唯一の方法は、すべてのソースとターゲットの頂点を抽出する素朴な解決策です。 boost::adjacent_vertices すべての隣接を取得してから、すべての新しいエッジを作成します boost::edge. 。これを行うより良い方法はありますか？

環境: ：グラフの頂点は地形の三角測量の重心であり、エッジは対応する三角形が隣接する頂点を接続します（したがって、デュアルグラフのようなもの）。拡張しようとしているエッジのセットは、ブロックされたトリアング間パスに対応し、ブロックされた領域が拡大しています。エリアは一種の円形であるため、上記の私の素朴なアプローチを使用するエッジのほとんどは、すでにセットの一部になります。

Answer 1

各ステップのすべての隣接する頂点を考慮する代わりに、新しいエッジを生成するために、プロパティマップを使用して、既に遭遇したエッジをマークします。したがって、各ステップでのみマークのないエッジを考慮する必要があります。頂点は、セットにすべてのエッジインシデントを追加した後にマークされます。

boost :: graphで使用される内部データ構造が隣接リストまたは隣接するマトリックスのいずれかであるという事実を考えると、私はさらなる改善が可能であるとは思わない。