Re: [Boost-users] [BGL] iterator/descriptor invalidation

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]