removing a frame corrupts graph structure

[niniemann]

Hello there!

After removing a frame from an EnvireGraph, calling EnvireGraph::getPath crashes depending on the order in which the frames were added. A minimal example:

#include <envire_core/graph/EnvireGraph.hpp>
using namespace envire::core;

int main(void) {
    EnvireGraph graph;

    const FrameId a = "a";
    const FrameId b = "b";

    graph.addFrame(b);
    graph.addFrame(a);

    graph.getPath(a, a, false); // this is okay
    graph.removeFrame(b);
    graph.getPath(a, a, false); // now it crashes
    return 0;
}

The above program crashes at the second graph.getPath(a, a, false); somewhere inside the breadth first search:

envire_test: /usr/include/boost/graph/two_bit_color_map.hpp:86: void boost::put(const boost::two_bit_color_map<IndexMap>&, typename boost::property_traits<PMap>::key_type, boost::two_bit_color_type) [with IndexMap
 = boost::adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS, boost::property<boost::vertex_index_t, unsigned int, envire::core::Frame>, boost::property<boost::edg
e_index_t, unsigned int, envire::core::Transform>, envire::core::Environment, boost::listS>, unsigned int, const unsigned int&, boost::vertex_index_t>; typename boost::property_traits<PMap>::key_type = void*]: Ass
ertion `(std::size_t)i < pm.n' failed.

Aborted (core dumped)

But, when changing the order of insertion from

    graph.addFrame(b);
    graph.addFrame(a);

to

    graph.addFrame(a);
    graph.addFrame(b);

everything works just fine. I guess this has something to do with how the vertex_descriptors of the graph are organized:

If the VertexList of the graph is vecS, then the graph has a builtin vertex indices accessed via the property map for the vertex_index_t property. The indices fall in the range [0, num_vertices(g)) and are contiguous. When a vertex is removed the indices are adjusted so that they retain these properties. Some care must be taken when using these indices to access exterior property storage.

(taken from here: http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/adjacency_list.html)

But I can't really say what's wrong with the EnvireGraph... Any ideas on how to fix this? :)

Best regards, Nils

[arneboe]

Is it time critical? Otherwise I ll look into it next week :)

[niniemann]

I guess next week would be okay. Thanks. :)

[arneboe]

I cannot reproduce the bug. Which boost boost version are you using?

[niniemann]

I'm working with boost 1.54 (and Ubuntu 14.04).

[Rauldg]

I am also using boost 1.54 and Ubuntu 14.04 and the above example did not trigger any error.

[niniemann]

That's really odd. Are we using the same versions of envire_core? @arneboe I see that you added my minimal example to the boost-test-cases, and my statements still hold:

Test case "getPath_test" aborted with:
    1 assertion out of 2 passed
    1 assertion out of 2 failed
 
Test case "getPath_test_2" passed with:
    2 assertions out of 2 passed

[niniemann]

Okay, another update, and a little bit of progress: I tried setting up a fresh autoproj environment containing only envire_core (plus dependencies), and what can I say -- no errors. Everything's fine, tests are passing. But a diff on envire_core in the fresh and old working directiory revealed: They are exactly the same. No differences in the sources.

The only difference (which I took quite long to notice...) is the build type! One was compiled with CMAKE_BUILD_TYPE=RelWithDebInfo, the other one with CMAKE_BUILD_TYPE=Debug. And damn it yes, the Debug fails the test, while the RelWithDebInfo passes. I guess I can work with this, but do you have any idea why this would be the case? :smirk:

Edit: Only Debug seems to fail, Release and RelWithDebInfo seem to work -- but assertions are only evaluated in Debug-mode, right? So the error might still be present, but is just ignored.

The only hint I could find is this: http://boost.2283326.n4.nabble.com/Graph-Assertion-in-two-bit-color-map-td3651787.html Same error, also during breadth-first-search, but the only comment is this:

Understood, I was passing a wrong vertex_t to dijkstra. Not an easy catch though.

Maybe this helps.

[arneboe]

I get the same error when compiling with debug. I'll look into it :)

[arneboe]

Thx :)

There are other places where search is used as well. I ll fix them.