On Wed, 26 Sep 2012, Ed Linde wrote:
Hi Jeremiah,
I am facing a similar problem where I have to iterate through the vertices of a graph and conditionally remove a lot of vertices. With the idea you mention of keeping a VecS adjacency_list graph + some external vertex property map indexed by vertex ID. And then iterating with a for loop over "vertex IDs" instead of using the iterators, wouldn't the *remove_vertex* anyway make the descriptors on the remaining vertices of the graph invalid?
Yes, it would invalidate them.
So in the end when I want to output the remaining graph, I might have problems when I iterate through the vertices. So is there an additional step of updating these external vertex property maps every time you delete a vertex using remove_vertex? Also do you think its a good idea to process the vertices in a descending order? But I think the removal will mess up all the vertex descriptors anyway, so I cannot save the output right? Just a bit confused I guess. I also do shortest path calculations on the graph while removing vertices, so I cannot just have a flag set that can allow SP algorithms to skip these vertices ( I think). So if you have any good work arounds let me know. :)
Only vertex descriptors greater than or equal to the one being removed will be invalidated, so going in descending order will work, but you might want to use filtered_graph instead. For that, you can have a property map that represents whether a vertex is in or out of your smaller graph, then run shortest paths on that. The filtered_graph does not change vertex numbers when you mask out a vertex, so your property maps won't need to be updated. -- Jeremiah Willcock