remove_vertex cuando el gráfico VertexList = vecS

Tengo un Boost Graph con VertexList = vecS.remove_vertex cuando el gráfico VertexList = vecS

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

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

El problema es que cada vez que llamo remove_vertex, el iterador a los vértices en el gráfico junto con los descriptores de los vértices quedan invalidados.

Fuente

2010-07-06 Dat Chu

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

Si el parámetro VertexList plantilla de la adjacency_list era vecS, entonces todos los descriptores de vértices, descriptores de última generación, e iteradores de la gráfica son invalidadas por esta operación. < ...> Si necesita hacer un 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 no se invalidan llamando remove_vertex a menos que el iterador apunta al vértice real que fue eliminado.

Fuente

2010-07-06 04:32:07

El problema con listS es que no puedo conectar los components_components para trabajar con él. http://stackoverflow.com/questions/3183186/perform-connected-components-with-boost-adjacency-list-where-vertexlistlists –

Puede ser, antes de la iteración puede crear un vértice especial "Papelera", durante la iteración conecta todos los nodos para su eliminación a esa Trash-vertex y, después de la iteración, elimina todos los vértices "Trash-connected"?

Fuente

2011-02-15 12:34:19

Vale la pena investigar esto. – sehe

¿Pero cómo hacer un seguimiento del vértice de la papelera al eliminar sus vecinos invalida el vertex_descriptor? – leezu

Sus bordes se almacenan en un std :: vector. Si tiene N vértices, todos los vértices están numerados de 0 a N. Si elimina uno, sus vértices se renumerarán de o a N-1. Por lo tanto, su descriptor será invalidado.

Sin embargo, puede haber una obra arround: - iterar a partir de N a 0 - poner a prueba su nodo y eliminar si es necesario

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

Si realiza esta manipulación mucho, puede ser bastante lento dependiendo del tamaño de su gráfico.

Si ese enfoque no funciona, tendrás que crear un nuevo gráfico a partir del anterior (calculando cuántos vértices y bordes tendrás, esto podría ser razonablemente rápido).

Así que, lo siento, no hay una respuesta real, pero espero que consigas sacar algo de eso.

Fuente

2011-02-15 12:50:56

Esto sería bueno si solo operaras el vector. Pero 'adjacency_list' lo maneja y necesita reindexar los bordes de todos modos. Puede elegir reasignar el vector después de las eliminaciones 'n' (invalidando de nuevo _todos iteradores). Por último, no se garantiza que la iteración inversa de 'vértices (gráfico)' sea equivalente a la iteración inversa del vector interno de vértices – sehe

remove_vertex cuando el gráfico VertexList = vecS

Respuesta

Cuestiones relacionadas