Re: [Boost-users] [BGL] vecS for vertex container and vertex index adjustments

Subject: Re: [Boost-users] [BGL] vecS for vertex container and vertex index adjustments
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-09-26 16:20:21

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