Re: [Boost-users] [BGL] adjacency_iterator invalidation with adjacency_list<listS, listS, unorderedS>

Subject: Re: [Boost-users] [BGL] adjacency_iterator invalidation with adjacency_list<listS, listS, unorderedS>
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2010-02-24 08:20:45

> In keeping with your comments, I have tried with both out edge iterators
> and
> adjacency iterators in the below simplified examples. Both indeed exhibit
> the same behavior, but they seem to invalidate the iterators, when
> (according to the documentation) the iterators should remain valid. There
> must be a good technical reason why these iterators are invalidated. If
> anyone can explain that to me, I would greatly appreciate it. In any event,
> if someone else can confirm this, I think the documentation should be
> changed.
>

I think the problem comes from the graph being undirected, which can cause
some interesting problems.

The graph actually doubles up on out edges so that a single undirected edge
is actually two distinct edges that are stored in the out edge list of each
vertex-- one (u, v) the other (v, u). Each of these out edges refers to the
same edge stored on the graph (via a ptr or something like that). Basically,
its giving the impression that its undirected, but it's not really.

When you clear a vertex, you're removing all of the corresponding edges from
each adjacent vertex and the "globally" stored edge. What happens, when you
see the failures, is that you're actually removing a reciprical edge out
from underneath the avinext or oeinext iterator, invalidating it.

Basically, you can probably assume that clear_vertex will invalidate any
iterators referring to the vertex being cleared for an undirected graph.

Andrew Sutton
andrew.n.sutton_at_[hidden]