remove_vertex when the graph VertexList=vecS

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.

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?

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.

I don't think it is possible (in a reasonable time) with vecS as a template parameter. Look what Boost documentation says:

If the VertexList template parameter of the adjacency_list was vecS, then all vertex descriptors, edge descriptors, and iterators for the graph are invalidated by this operation. <...> If you need to make frequent use of the remove_vertex() function the listS selector is a much better choice for the VertexList template parameter.

In case of listS the iterators are not invalidated by calling remove_vertex unless the iterator is pointing to the actual vertex that was removed.