Re: [Boost-users] Confused by boost graph descriptor invalidation

Subject: Re: [Boost-users] Confused by boost graph descriptor invalidation
From: Chris Dellin (cdellin_at_[hidden])
Date: 2016-03-21 16:00:02

On Mon, Mar 21, 2016 at 3:25 AM, Paolo Bolzoni <
paolo.bolzoni.brown_at_[hidden]> wrote:

> The text states the table summarizes which operations cause
> descriptors and iterators to become invalid, said so what does
> "OK" means? My feeling is that iterators never become invalid,
> is that the case?
>

That's correct -- descriptors/iterators marked "OK" remain valid after the
associated function is called (besides descriptors/iterators to the removed
element itself, of course).

> And what "EL=vecS && Directed=directedS" means? It means that
> you are _fine_ only if you are working with a adjcency_list with
> OutEdgeList as vecS and Directed=directedS or the opposite
> (i.e., if you are using such adjcency_list then all iterators
> become invalid)
>

It means the latter -- if you are using such an adjacency_list, then all
descriptors/iterators become invalid.  I believe the current implementation
of adjacency_list uses vector indices as descriptors and pointers into the
vector as iterators, and since the implementation guarantees that the
vector is contiguous, removing vertex 5 in a 10-vertex graph will cause
vertices to be re-numbered, invalidating old descriptors.  If you want
descriptors/iterators to remain valid as the graph is changed, it is
therefore advisable to choose a datastructure such as a list which does not
suffer this problem.

Cheers,
- Chris