remove_vertex when the graph VertexList=vecS

Question

I have a Boost Graph with VertexList=vecS.

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

Now I want to iterate through my vertices and remove those that have a specific property. How can I do this?

The problem is whenever I call remove_vertex, the iterator to the vertices in the graph along with the vertex descriptors are invalidated.

Answer 1

May be, before iteration you can make special "Trash" vertex, during iteration you connect all nodes-for-deletion to that Trash-vertex and, after iteration, delete all "Trash-connected" vertices?

Answer 2

Your edges are stored in an std::vector. If you have N vertices, then all vertices are numbered from 0 to N. If you delete one, then your vertices will be renumbered from o to N-1. Therefor, your descriptor will be invalidated.

However, there might be a work arround : – iterate from N down to 0 – test your node and delete it if necessary

This supposes (and I'm not sure, but rather confident) that it will only renumber the vertices after the one you've just deleted.

If you do this manipulation a lot, it might be rather slow depending on your graph's size.

If that approach doesn't work, you'll have to build a new graph from the old one (by pre-computing how many vertices and edges you will have, this might actually be reasonnably fast).

So, sorry, no real answer, but I hope you'll manage to get something out of it.