Effizient erweitern Sie die Reihe von Graphenkanten

Question

Ich habe eine Reihe von Kanten aus einem Diagramm und möchte sie mit allen Kanten erweitern, die einen Scheitelpunkt mit jeder Kante teilen. Wie könnte ich das effizient machen boost::graphs?

Ich konnte nur die naive Lösung des Extrahierens aller Quellen- und Zielscheitelpunkte verwenden, die ich verwenden konnte. boost::adjacent_vertices um alle Angriffen zu bekommen und dann alle neuen Kanten mit zu erstellen boost::edge. Gibt es eine bessere Möglichkeit, dies zu tun?

Kontext: Die Grafikscheitelpunkte sind Zentroide einer Gelände -Triangulation, die Kanten verbinden Eckpunkte, deren entsprechende Dreiecke benachbart sind (so eine Art zweier Grafik). Die Menge der Kanten, die ich erweitern möchte, entspricht den blockierten Wegen zwischen Dreizfehlern, und der blockierte Bereich expandiert. Der Bereich ist eine Art kreisförmiger Kreis. Die meisten Kanten werden daher bereits ein Teil des Sets sein.

Answer 1

Verwenden Sie anstatt alle benachbarten Scheitelpunkte in jedem Schritt zu berücksichtigen, um die neuen Kanten zu generieren, mit einer Eigenschaftskarte, um die Kanten bereits zu markieren. Daher müssen Sie nur in jedem Schritt nicht markierte Kanten in Betracht ziehen. Ein Scheitelpunkt ist markiert, nachdem Sie alle Kanten zu Ihrem Set hinzugefügt haben.

Angesichts der Tatsache, dass die durch Boost :: Graph verwendete interne Datenstruktur entweder eine Adjazenzliste oder eine Adjazenzmatrix ist, denke ich nicht, dass eine weitere Verbesserung möglich ist.