[Boost-users] BGL: invalidated/changing vertex_descriptor?

Subject: [Boost-users] BGL: invalidated/changing vertex_descriptor?
From: Anders Wallin (anders.e.e.wallin_at_[hidden])
Date: 2011-11-25 16:55:13

Hi all,

I have an directed adjacency_list graph  with VertexListS=listS.
I'm using this for a DCEL/winged-edge data-structure[1] for storing a
planar graph.
In this data structure each edge (src,trg) has a "twin edge" (trg,src).

In the algorithm where I update the graph I have various
sanity-checks, one of which is that the source and target of an edge
should match the target and source of the twin edge. So if we have an
edge and the associated twin_edge we can do:
Vertex source = boost::source(edge, g);
Vertex target = boost::target(edge, g);
Vertex twin_source = boost::source(twin_edge, g);
Vertex twin_target = boost::target(twin_edge, g);
assert( source == twin_target );
assert( target == twin_source );

I have lately started seeing these asserts fail for some reason.The
output, when the assert fails, can look like this:
 edge: (0x2f88850,0x2f8a7d0)
 twin_edge: (0x202f8a7d0,0x2f88850)

Clearly this case will cause the above asserts to fail. I seem to pass
the asserts many hundreds or thousands of times in my algorithm before
at some point I get a failure. The failure always seems to happen at a
different point in the code (with fairly large input, 10s or 100s of
thousands of vertices). It is always of this same form, i.e. one
vertex-descriptor address seems to have had "20" pre-pended from
0xAAAAAAA to 0x20AAAAAAA. If I do a release build which disables
asserts I get segfaults instead when trying to access
vertex-properties with the rouge vertex-descriptor.

tested on two 64-bit ubuntu systems: (both show the behavior described above)
Boost 1.42 with gcc 4.5.2 and Boost 1.46.1 with gcc 4.6.1

thanks for any input,
(what's with the vertex_descriptors being output as seven hex-digits?
why do I see a pre-pended "20"? what, if anything causes invalidation
of vertex_descriptors?)

Anders

[1] http://en.wikipedia.org/wiki/Doubly_connected_edge_list