Ich habe einen Boost Graph mit VertexList = vecS.remove_vertex wenn der Graph VertexList = vecS
Jetzt möchte ich durch meine Scheitelpunkte iterieren und diejenigen entfernen, die eine bestimmte Eigenschaft haben. Wie kann ich das machen?
Das Problem ist, wenn ich remove_vertex aufrufen, der Iterator zu den Scheitelpunkte im Diagramm zusammen mit den Scheitelpunktdeskriptoren ungültig sind.
Ich glaube nicht, dass es möglich ist (in einer angemessenen Zeit) mit vecS als Vorlage Parameter. Schauen Sie, was Boost-Dokumentation sagt:
Wenn die
VertexListTemplate-Parameter desadjacency_listvecSwar, dann sind alle Vertex-Deskriptoren, Kanten Deskriptoren und Iteratoren für die grafische Darstellung werden durch diese Operation ungültig gemacht. < ...> Wenn Sie häufig dieremove_vertex()Funktion verwenden müssen, ist derlistSSelektor eine viel bessere Wahl für denVertexListVorlagenparameter.
Bei listS werden die Iteratoren nicht durch remove_vertex Aufruf für ungültig erklärt, wenn der Iterator auf dem tatsächlichen Scheitelpunkt zeigt, der entfernt wurde.
Kann man vor der Iteration einen speziellen "Trash" -Verschluss erstellen, während der Iteration alle Knoten zum Löschen mit diesem Trash-Vertex verbinden und nach der Iteration alle "Trash-Connected" -Vertices löschen?
Ihre Kanten sind in einem std :: vector gespeichert. Wenn Sie N Scheitelpunkte haben, werden alle Scheitelpunkte von 0 bis N nummeriert. Wenn Sie einen Scheitelpunkt löschen, werden Ihre Scheitelpunkte von 0 bis N-1 neu nummeriert. Daher wird Ihr Deskriptor ungültig gemacht.
Es könnte jedoch eine Arbeit nahe sein: - von N iterieren bis 0 - testen Sie Ihre Knoten und löschen Sie es dann notwendig, wenn
Dies setzt (und ich bin nicht sicher, aber eher zuversichtlich), dass Es nummeriert nur die Vertices nach die Sie gerade gelöscht haben.
Wenn Sie diese Manipulation sehr oft machen, kann es abhängig von der Größe Ihres Diagramms ziemlich langsam sein.
Wenn dieser Ansatz nicht funktioniert, müssen Sie ein neues Diagramm aus dem alten erstellen (indem Sie vorberechnen, wie viele Scheitelpunkte und Kanten Sie haben werden, könnte dies tatsächlich sehr schnell sein).
Also, tut mir leid, keine echte Antwort, aber ich hoffe, du schaffst es, etwas daraus zu machen.
Das wäre schön, wenn Sie einfach auf dem Vektor operieren würden. Aber "adjacency_list" verwaltet es und muss die Kanten sowieso neu indizieren. Es könnte den Vektor nach "n" removals neu zuweisen (wieder invalidierende _all_ Iteratoren). Schließlich ist die umgekehrte Iteration von "Vertices (Graphen)" nicht garantiert, um eine umgekehrte Iteration des internen Vektors von Vertices zu sein – sehe
Das Problem mit listS ist, dass ich connected_components nicht bekommen kann, um damit zu arbeiten. http://stackoverflow.com/questions/3183186/perform-connected-components-with-boost-adjacency-list-where-vertexlistlists –