
Boost Users : 
Subject: [Boostusers] [BGL] vecS for vertex container and vertex index adjustments
From: Sergey Mitsyn (svm_at_[hidden])
Date: 20120531 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.
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net