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

Subject: [Boost-users] [BGL] vecS for vertex container and vertex index adjustments
From: Sergey Mitsyn (svm_at_[hidden])
Date: 2012-05-31 08:05:09

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?

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.

------------
Sergey Mitsyn.