Subject: Re: [Boost-users] [BGL] iterator/descriptor invalidation
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2008-12-09 09:27:32
>
> the documentation of adjacency_list states, that a call to add_vertex()
> does not invalidate any iterators nor descriptors. However, following code
> segfaults, because retrieving vertex descriptors from an edge_iterator via
> source() and target() does not work (example should compile as is):
>
> #include <iostream>
> #include <boost/graph/adjacency_list.hpp>
>
> using namespace boost;
>
> typedef adjacency_list<listS, vecS, directedS > Graph;
>
> int main() {
> Graph g(3);
>
> add_edge( 0, 1, g );
> add_edge( 1, 2, g );
> add_edge( 2, 0, g );
>
> Graph::edge_iterator ei, ei_end;
>
> for( tie( ei, ei_end ) = edges( g ); ei != ei_end; ++ei )
> {
> std::cout << source( *ei, g ) << " " << target( *ei, g ) << "\n";
> add_vertex( g ); // <- in my real application, vertex gets some
> // properties that depend on source(...) and
> // target(...) above
> }
> }
>
> Is it the case that an edge_iterator does not store vertex_descriptors
> (that should survive reallocation of the vertex storage), but iterators to
> the vertex storage?
>
> What is the proper way to accomplish something like this? My present
> workaround is to postpone all add_vertex() calls after the loop, but this
> costs some storage, and with my graph scaling bigger and bigger, that begins
> to hurt.
>
> Any help and explanation is really appreciated!
>
This is a nice, subtle problem that you've found :) Remember that an
adjacency list stores a list of incident edges for each vertex. Adding a
vertex (with VertexSet == vecS) can cause a reallocation of the underlying
buffer, causing all of those incident edge lists to be reallocated and
copied. The edge iterator stores actually stores a pair of iterators into
the out-edge list of some vertex... The unfortunate side-effect seems to be
that adding a vertex *can* in fact invalidate an edge iterator. I guess the
documentation is wrong.
Note that this probably won't be the case with VertexSet != vecS since
additions don't cause re-allocations.
I don't see any possible way to work around this other than deferring all of
your vertex additions til after the loop.
Andrew Sutton
andrew.n.sutton_at_[hidden]