remove_vertex cuando el gráfico VertexList = VEC

Question

Tengo un Boost Gráfico con VertexList = VEC.

typedef adjacency_list <listS, vecS, undirectedS, TrackInformation, LinkInformation> TracksConnectionGraph;

Ahora quiero para iterar a través de mis vértices y eliminar aquellas que tienen una propiedad específica. ¿Cómo puedo hacer esto?

El problema es siempre que llame remove_vertex, el iterador a los vértices en el gráfico junto con los descriptores de vértice se invalidan.

Answer 1

No creo que es posible (en un tiempo razonable) con vecS como un parámetro de plantilla. documentación mirada lo dice Boost:

Si el parámetro de plantilla VertexList de la adjacency_list era vecS, entonces todos los descriptores de vértice, los descriptores de borde, y los iteradores para el gráfico se invalidan por esta operación. <...> Si necesita hacer uso frecuente de la función remove_vertex() el selector listS es una opción mucho mejor para el parámetro de plantilla VertexList.

En caso de listS los iteradores son no invalida llamando remove_vertex a menos que el iterador está apuntando al vértice real que se ha eliminado.

Answer 2

Puede ser, antes de iteración se puede hacer especial vértice "Papelera", durante la iteración se conecta todos los nodos fines de eliminación a la Papelera-vértice y, después de la iteración, borrar todo "Trash-conectado" vértices?

Answer 3

Sus bordes son almacenados en un std :: vector. Si tiene N vértices, a continuación, todos los vértices están numerados de 0 a N. Si elimina uno, entonces sus vértices se volverán a numerar de O a N-1. Para ello, se invalidarán su descriptor.

Sin embargo, podría haber un arround de trabajo: - iterar a partir de N a 0 - prueba de su nodo y eliminar si es necesario

Esto supone (y no estoy seguro, sino más bien confianza) que sólo volverá a numerar los vértices después el que usted acaba de eliminar.

Si lo hace esta manipulación mucho, podría ser bastante lento dependiendo del tamaño de la gráfica.

Si ese enfoque no funciona, usted tiene que construir un nuevo gráfico de la anterior (por cuántos vértices pre-computación y los bordes tendrá, esto podría ser en realidad reasonnably rápido).

Así que, lo siento, hay una respuesta real, pero espero que las arreglará para obtener algo de él.