Boost C++ Libraries: Ticket #7863: Bad graph after removing named vertex and then adding it again.

attachment set

anonymous — Mon, 07 Jan 2013 05:26:59 GMT

attachment → graphing.cpp

Jeremiah Willcock — Mon, 14 Jan 2013 19:27:19 GMT

On lines 121 and 124, you are using *tv even after that vertex might have been deleted (on 121, it is known to have been deleted). Your comment about *fv being invalid after *tv has been removed is correct; in a graph with vecS vertex container, removing one vertex invalidates all other vertex descriptors.

anonymous — Mon, 14 Jan 2013 19:59:20 GMT

A bug for sure on line 121, but on 124 the vertex would still be valid as it hasn't been removed. Either way those lines are there as I was trying to figure out what was wrong, and the bug reported stands whether none, either, or both lines 121, 124 are commented out.

Final tree when connect called after disconnect: b->d

Final tree when disconnect called after connect: c->b, a->b, c->d, b->d

Jeremiah Willcock — Mon, 14 Jan 2013 20:14:23 GMT

It looks like you cannot use a vecS vertex container with a named_graph when you remove vertices; there is nothing that updates the name lookup table based on the new vertex descriptors. Because unrelated vertex descriptors might be invalidated by remove_vertex, the table might need to be entirely rebuilt in that case. Could you please try listS or setS as vertex container (the second template parameter to adjacency_list) instead of vecS?

Jeremiah Willcock — Mon, 14 Jan 2013 21:03:52 GMT

(In [82498]) Added check to prevent use of remove_vertex on named adjacency list graphs with vecS vertex container (since it does not work and could not be made to work efficiently); refs #7863

anonymous — Mon, 14 Jan 2013 22:19:11 GMT

I've since updated to listS and things work as I want...but the vecS was definitely doing things it shouldn't so reported it.

status changed; resolution set

Jeremiah Willcock — Mon, 14 Jan 2013 22:20:20 GMT

status new → closed
resolution → wontfix

You were right to report the issue; I added a check now so that other users will not get the same kind of subtle run-time error that you experienced.