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-10 09:02:02

> > >>> 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 with the documentation - not the code. The edge_iterator IS
invalidated after add_vertex() because the edge_iterator retains a pair ouf
out_edge_iterators that refer to the current out edge being visited of the
current vertex. The add_vertex() call may not invalidate vertex descriptors
but it will invalidate out_edge_iterators since the memory they pointed to
no longer exsts (i.e., copied and deleted). The cascading effect is that it
will also invalidate the edge_iterator. Hence, the failure of g[*i].

Andrew Sutton
andrew.n.sutton_at_[hidden]