Hi, Andrew Sutton escribió:

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

[]

This is a nice, subtle problem that you've found :) Remember that an adjacency list stores a list of incident edges for each vertex.

Adding a

vertex (with VertexSet == vecS) can cause a reallocation of the underlying buffer, causing all of those incident edge lists to be reallocated and copied. The edge iterator stores actually stores a pair of iterators into the out-edge list of some vertex... The unfortunate side-effect seems to be that adding a vertex *can* in fact invalidate an edge iterator. I guess the documentation is wrong.

Note that this probably won't be the case with VertexSet != vecS since additions don't cause re-allocations.

I don't see any possible way to work around this other than deferring all of your vertex additions til after the loop.

In the provided example g.m_vertices.reserve(6) helps. --Dmitry

Andrew Sutton escribió:

In the provided example g.m_vertices.reserve(6) helps.

You're right... That should work - unless you're adding more than 6 vertices.

Maybe we should provide a reserve_vertices(g, n) function for the vertex set on adjacency lists. It's a nice optimization and apparently can help avoid some invalidation. Obviously it only applies to VertexSet == vecS || listS. Thoughts?

Looks like everything works fine with undirected graph, i.e., this code does not lead to segfault: #include <iostream> #include using namespace boost; typedef adjacency_list 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 ) { add_vertex( g ); } } Regards, Dmitry

Julius Ziegler escribió:

Dmitry Bufistov writes:

...

In the provided example g.m_vertices.reserve(6) helps.

Thanks Dimitry, that is a good idea. In my application I actually have a good upper bound on the number of vertices that will be added.

You are welcome.

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.

So I think the documentation should be updated, should I drop a note at the developers list?

Regards, Julius

Regards, Dmitry

Julius Ziegler escribió:

Dmitry Bufistov 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. Regards, Dmitry

...

...

...

...

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@gmail.com

So I think the documentation should be updated, should I drop a note at the

...

developers list?

I'm the new maintainer so I can update it.

I was going to update the documentation, but decided to test a little more thoroughly as to what is and is not actually invalidated when you add a vertex. Here are the somewhat surprising results: - nothing invalidated - edge iterators are invalidated, nothing else - nothing invliadated The test file is in trunk at libs/graphs/test/adj_list_invalidaton.cpp. It's not comprehensive, but will segfault as indicated above. Andrew Sutton andrew.n.sutton@gmail.com

For completeness: the outcome is exactly the same if you use OutEdgeList = listS. To me, the surprising thing is that vertex_iterators are so stable when adding vertices. I believe that vertex_iterator is just a vertex_descriptor in disguise, that, when dereferenced, does "normal" indexing (via operator[]) into the vertex storage.

You're right... It probably invalidates all out edge and adjacency iterators - but not descriptors! If you want to make your brain hurt, you could try to figure out why, under certain conditions for the directed graph, adjacency_iterators appear to be valid, while out_edge_iterators are not. I've been looking at it for an hour or so and can't figure it out. My guess is its just some random memory utilization artifact. You might be surprised to learn that the vertex_iterator for VertexSet == VecS is actually integer_range::iterator. It's just dereferencing to integers. Andrew Sutton andrew.n.sutton@gmail.com

Why instead of updating the documentation you'd better try to implemented directedS edge_iterator version in the way similar to the undirectedS and bidirectionalS versions?

For two reasons. First, it's not a bug, just an artifact of data type selection. Second, because solving this problem would require a large and intrusive rewrite of how adjacency lists are implemented and probably result in less efficient (time+space) graphs. The nice thing about the library being generic, is that you can create a new directed graph implementation that doesn't suffer these artifacts, and adapt it to the BGL interface. Andrew Sutton andrew.n.sutton@gmail.com

Andrew Sutton writes:

I'm the new maintainer so I can update it.

Cool, thanks for maintaining this great lib, its such a huge achievement!