
Boost Users : 
Subject: Re: [Boostusers] [BGL] vecS for vertex container and vertex index adjustments
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 20120531 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
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