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

Subject: Re: [Boost-users] [BGL] iterator/descriptor invalidation
From: Julius Ziegler (ziegler_at_[hidden])
Date: 2008-12-10 08:03:06

Dmitry Bufistov <dmitry <at> lsi.upc.edu> writes:

> 
> Julius Ziegler escribió:
> > Dmitry Bufistov <dmitry <at> lsi.upc.edu> writes:
> > 
> >>> It strikes to me now that the matter is not so subtle at all, since 
> >>> add_vertex()
> >>> with vecS is very likely to invalidate vertex_iterators (clearly contrary 
> >>> to 
> >>> the
> >>> documentation). In my case the issue was a bit obscured since it is not
> >>> perfectly clear that source(edge_descriptor) and target(edge_descriptor)
> >>> use
> >>> vertex_iterators. I had expected that edge_descriptor stores two
> >>> vertex_descriptors.
> >> The problem is not with edge_descriptor it is in the operator++() of the 
> >> edge_iterator class.
> > 
> > I think that edge_iterators are not directly affected, and its still save
> > to 
> > use them to access, e.g., edge properties. Its also save to use 
> > operator++(). 
> > The problem is that calling source(...) on an edge descriptor dereferences a
> > vertex_iterator, and THAT one may have been invalidated. Is that right?
> 
> Well, you can try to remove source() and target() calls from your 
> example and to see if the problem is still reproducible.

The problem is still there! To reproduce (added "double" props to vertices and
edges):

#include <iostream>
#include <boost/graph/adjacency_list.hpp>

using namespace boost;

typedef adjacency_list<listS, vecS, directedS, double, double > Graph;

int main() {
  Graph g(3);

  add_edge( 0, 1, 7.0,  g );
  add_edge( 1, 2, 2.0,  g );
  add_edge( 2, 0, 13.0, g );

  Graph::edge_iterator ei, ei_end;  

  for( tie( ei, ei_end ) = edges( g ); ei != ei_end; ++ei )
    {
      std::cout << g[*ei] << "\n";
      add_vertex( 1.0, g );             
    }  
}

Looks like things are not at all as I imagined! However, my problem is solved
well by reserving enough space for the vertices, and avoiding invalidation in
the first place, as you proposed.

Best regards, 
Julius