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

Subject: Re: [Boost-users] BGL: invalidated/changing vertex_descriptor?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-11-25 20:29:24

On Fri, 25 Nov 2011, Anders Wallin wrote:

> 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?)

I don't know about the prepended 0x20.  What modifications, if any, are 
you doing to the graph before checking the edge pairs?  The invalidation 
rules are on the documentation page for adjacency_list; listS doesn't 
cause invalidations too often, though.  Can you please post a small 
example of something that breaks?  Do Valgrind and/or _GLIBCXX_DEBUG show 
anything?

-- Jeremiah Willcock