[BGL] Problems with remove_vertex
Hi, I have a an adjacency_list graph, which I've been using fine. I would like to remove a vertex from the graph, and I do so by calling: clear_vertex then remove_vertex If I then try a call to: adjacent_vertices on a vertex that used to have the removed vertex as a parent, my program then crashes on the line 1481 "boost::tie(first, last) = out_edges(u, g);" of adjacency_list.hpp I'm using MSVC8.0 Any advice on what might be going wrong would be much appreciated. Thanks, -Adrian
Adrian Boeing schrieb:
Hi,
I have a an adjacency_list graph, which I've been using fine. I would like to remove a vertex from the graph, and I do so by calling: clear_vertex then remove_vertex
If I then try a call to: adjacent_vertices
on a vertex that used to have the removed vertex as a parent, my program then crashes on the line 1481 "boost::tie(first, last) = out_edges(u, g);" of adjacency_list.hpp
I'm using MSVC8.0
Any advice on what might be going wrong would be much appreciated.
Can you give a small test program that crashes? Are you using vecS storage? Maybe you are using an vertex descriptor that has been invalidated by the remove operation?
Hi Jens, Unfortunately it's all part of a larger program so I can't easily provide a small example. Yes, I am using the vecS storage: typedef boost::adjacency_list<boost::vecS,boost::vecS,boost::bidirectionalS,boost::property<vertex_prop_t, T>,boost::property<edge_prop_t, U>,boost::no_property, boost::listS > graph_type; I'm not sure how to remove the property descriptor, there does not seem to be a boost::remove(vertex prop,graph) that I can find anywhere. If I remove the "remove_vertex" call, the adjacency_list call appears to succeed, however it causes my program to crash elsewhere. Thanks, -Adrian Jens Müller wrote:
Adrian Boeing schrieb:
Hi,
I have a an adjacency_list graph, which I've been using fine. I would like to remove a vertex from the graph, and I do so by calling: clear_vertex then remove_vertex
If I then try a call to: adjacent_vertices
on a vertex that used to have the removed vertex as a parent, my program then crashes on the line 1481 "boost::tie(first, last) = out_edges(u, g);" of adjacency_list.hpp
I'm using MSVC8.0
Any advice on what might be going wrong would be much appreciated.
Can you give a small test program that crashes?
Are you using vecS storage? Maybe you are using an vertex descriptor that has been invalidated by the remove operation?
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Jan 29, 2007, at 2:38 PM, Adrian Boeing wrote:
Hi Jens,
Unfortunately it's all part of a larger program so I can't easily provide a small example.
Yes, I am using the vecS storage: typedef boost::adjacency_list<boost::vecS,boost::vecS,boost::bidirectionalS,bo ost::property<vertex_prop_t, T>,boost::property<edge_prop_t, U>,boost::no_property, boost::listS > graph_type;
I'm not sure how to remove the property descriptor, there does not seem to be a boost::remove(vertex prop,graph) that I can find anywhere.
Hmmm. So, when one removes a vertex from an adjacency_list with VertexListS=vecS, it actually invalidates all of the existing vertex descriptors. So simple code like the following causes problems: graph_type::vertex_descriptor u = *vertices(g).first; graph_type::vertex_descriptor v = *(++vertices(g).first); clear_vertex(u, g); remove_vertex(u, g); adjacent_vertices(v, g); // v has been invalidated vecS is a tricky beast. I usually recommend avoiding the removal of vertices when VertexListS=vecS... it's inefficient and hard to use properly. Cheers, Doug
Hi. I had similar problems. Unfortunately, I can't remember right now what the particular situation was. I wrote the code in different ways (because of the invalidation process), but still my program crashed. Then I tried running the same code on GCC (in a debian machine). For my surprise, the problem no longer happened. Leandro Melo On 1/29/07, Doug Gregor <dgregor@cs.indiana.edu> wrote:
On Jan 29, 2007, at 2:38 PM, Adrian Boeing wrote:
Hi Jens,
Unfortunately it's all part of a larger program so I can't easily provide a small example.
Yes, I am using the vecS storage: typedef boost::adjacency_list<boost::vecS,boost::vecS,boost::bidirectionalS,bo ost::property<vertex_prop_t, T>,boost::property<edge_prop_t, U>,boost::no_property, boost::listS > graph_type;
I'm not sure how to remove the property descriptor, there does not seem to be a boost::remove(vertex prop,graph) that I can find anywhere.
Hmmm. So, when one removes a vertex from an adjacency_list with VertexListS=vecS, it actually invalidates all of the existing vertex descriptors. So simple code like the following causes problems:
graph_type::vertex_descriptor u = *vertices(g).first; graph_type::vertex_descriptor v = *(++vertices(g).first); clear_vertex(u, g); remove_vertex(u, g); adjacent_vertices(v, g); // v has been invalidated
vecS is a tricky beast. I usually recommend avoiding the removal of vertices when VertexListS=vecS... it's inefficient and hard to use properly.
Cheers, Doug
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hello, Yes, I've been finding strange problems but as Doug mentioned, it's hard to use properly, so instead of removing them I am just clearing the vertex. (ie: clear_vertex(u, g);) It makes it a bit more annoying to use the graph, but at least I get no more crashes; and programing around the empty vertices is easier than trying to remove them from the graph. Cheers, -Adrian Leandro Melo wrote:
Hi.
I had similar problems. Unfortunately, I can't remember right now what the particular situation was. I wrote the code in different ways (because of the invalidation process), but still my program crashed. Then I tried running the same code on GCC (in a debian machine). For my surprise, the problem no longer happened.
Leandro Melo
On 1/29/07, Doug Gregor <dgregor@cs.indiana.edu> wrote:
On Jan 29, 2007, at 2:38 PM, Adrian Boeing wrote:
Hi Jens,
Unfortunately it's all part of a larger program so I can't easily provide a small example.
Yes, I am using the vecS storage: typedef boost::adjacency_list<boost::vecS,boost::vecS,boost::bidirectionalS,bo ost::property<vertex_prop_t, T>,boost::property<edge_prop_t, U>,boost::no_property, boost::listS > graph_type;
I'm not sure how to remove the property descriptor, there does not seem to be a boost::remove(vertex prop,graph) that I can find anywhere. Hmmm. So, when one removes a vertex from an adjacency_list with VertexListS=vecS, it actually invalidates all of the existing vertex descriptors. So simple code like the following causes problems:
graph_type::vertex_descriptor u = *vertices(g).first; graph_type::vertex_descriptor v = *(++vertices(g).first); clear_vertex(u, g); remove_vertex(u, g); adjacent_vertices(v, g); // v has been invalidated
vecS is a tricky beast. I usually recommend avoiding the removal of vertices when VertexListS=vecS... it's inefficient and hard to use properly.
Cheers, Doug
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (4)
-
Adrian Boeing -
Doug Gregor -
Jens Müller -
Leandro Melo