[Boost-users] [BGL] iterator/descriptor invalidation
Julius Ziegler
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 descriptors from an
edge_iterator via source() and target() does not work (example should
compile as is):
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
using namespace boost;
typedef adjacency_list<listS, vecS, directedS > 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 )
{
std::cout << source( *ei, g ) << " " << target( *ei, g ) << "\n";
add_vertex( g ); // <- in my real application, vertex gets some
// properties that depend on source(...) and
// target(...) above
}
}
Is it the case that an edge_iterator does not store vertex_descriptors
(that should survive reallocation of the vertex storage), but iterators
to the vertex storage?
What is the proper way to accomplish something like this? My present
workaround is to postpone all add_vertex() calls after the loop, but
this costs some storage, and with my graph scaling bigger and bigger,
that begins to hurt.
Any help and explanation is really appreciated!
Regards,
Julius
_______________________________________________
Boost-users mailing list
Boost...@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Andrew Sutton
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 descriptors from an edge_iterator via source() and target() does not work (example should compile as is):
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
using namespace boost;
typedef adjacency_list<listS, vecS, directedS > 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 )
{
std::cout << source( *ei, g ) << " " << target( *ei, g ) << "\n";
add_vertex( g ); // <- in my real application, vertex gets some
// properties that depend on source(...) and
// target(...) above
}
}
Is it the case that an edge_iterator does not store vertex_descriptors (that should survive reallocation of the vertex storage), but iterators to the vertex storage?
What is the proper way to accomplish something like this? My present workaround is to postpone all add_vertex() calls after the loop, but this costs some storage, and with my graph scaling bigger and bigger, that begins to hurt.
Any help and explanation is really appreciated!
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.
andrew....@gmail.com
Dmitry Bufistov
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
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?
Andrew Sutton
andrew....@gmail.com
Julius Ziegler
> 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.
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.
So I think the documentation should be updated, should I drop a note at the
developers list?
Regards, Julius
Dmitry Bufistov
> Dmitry Bufistov <dmitry <at> lsi.upc.edu> 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
Dmitry Bufistov
Looks like everything works fine with undirected graph, i.e., this code
does not lead to segfault:
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
using namespace boost;
typedef adjacency_list<listS, vecS, undirectedS > 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,
Julius Ziegler
> > 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?
Regards, Julius
Dmitry Bufistov
> 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.
Regards,
Dmitry
Julius Ziegler
>
> 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
Andrew Sutton
> >>> 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....@gmail.com
Andrew Sutton
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.
Andrew Sutton
andrew....@gmail.com
Andrew Sutton
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:
<vecS, vecS, undirectedS> - nothing invalidated
<vecS, vecS, directedS> - edge iterators are invalidated, nothing else
<vecS, vecS, bidrectionalS> - 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....@gmail.com
Julius Ziegler
> I'm the new maintainer so I can update it.
Cool, thanks for maintaining this great lib, its such a huge achievement!
Julius Ziegler
> 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:<vecS, vecS, undirectedS> - nothing
> invalidated<vecS, vecS, directedS> - edge iterators are invalidated, nothing
> else<vecS, vecS, bidrectionalS> - nothing invliadatedThe test file is in trunk
> at libs/graphs/test/adj_list_invalidaton.cpp. It's not comprehensive, but
> will segfault as indicated above.
>
> Andrew Suttonandrew.n.sutton <at> 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.
Dmitry Bufistov
Andrew,
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?
Regards,
Dmitry
Andrew Sutton
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....@gmail.com
Andrew Sutton
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<size_t>::iterator. It's just dereferencing to integers.
andrew....@gmail.com