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

Subject: [Boost-users] [BGL] iterator/descriptor invalidation
From: Julius Ziegler (ziegler_at_[hidden])
Date: 2008-12-09 08:37:55

Dear list,

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!

Regards,
Julius