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