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-05-31 12:38:00

On Thu, 31 May 2012, Sergey Mitsyn wrote:

> Hi all,
>
> I know that while using vecS for vertices one has no vertex iterator 
> stability upon removing vertices. But I have a question if there exists 
> something like vertex _index_ stability. The documentation says that indices 
> for vertices are automatically adjusted so that they are still in contiguous 
> range, but it is not specified how it is done. Is it okay to assume that if a 
> vertex with an index I is removed, then vertices with indices < I have their 
> indices unchanged, while vertices with indices > I have their indices 
> decreased by one?

Yes, that is how it works internally, but that is not documented behavior; 
it probably should be, however. It also does not apply to vertex 
iterators; those can change to completely unrelated values on any vertex 
insertion/deletion.

> The actual problem is removing all vertices meeting some condition. Is the 
> following code ok?
>
> // traverse all vertices and remove those for which predicate
> // condition_to_remove_vertex returns true.
>
> // graph is adjacency_list<.., vecS, ...>
>
> vertex_iterator vi = vertices(graph).first, vi_end = vertices(graph).second;
>
> while (vi != vi_end)
> {
>    if (condition_to_remove_vertex(vi, graph))
>    {
>        vertices_size_type end_index = vertex_index[*vi_end]
>            , vi_index = vertex_index[*vi];
>
>        remove_vertex_f(*vi, graph);
>        // vi and vi_end are invalid
>
>        --end_index;
>
>        vi = vertices(graph).first + vi_index;
>        vi_end = vertices(graph).first + end_index;
>        // now vi and vi_end are valid again
>    }
>    else
>        ++vi;
> }
>
>
>
> This way seems to be more effective than to start iteration again every time 
> a vertex is removed.

Yes, that should work. Rather than using vertices(graph).first + vi_index, 
use vertex(vi_index, graph); I believe the order is guaranteed to be the 
same between those, and it is in practice.  You might also want to have 
the loop be over the vertex numbers:

for (vertices_size_type i = 0; i < num_vertices(graph); /*Incremented in loop*/) {
   vertex_descriptor v = vertex(i, graph);
   if (condition(v, graph) {
     remove_vertex(v, graph);
   } else {
     ++i;
   }
}

Depending on what you are doing, you might also want to consider using 
filtered_graph with a bitmap representing which vertices are deleted. 
That will keep everything valid (even for vecS), including external 
property maps based on the vertex index numbers.

-- Jeremiah Willcock