Boost graph problem removing last vertex
Dear all, I have a graph, but when I remove the last vertex, the edge isn't removed. This can even lead to a crash. typedef boost::adjacency_list<boost::listS, boost::vecS, //or listS, same problem boost::directedS, boost::property<boost::vertex_index_t, int, boost::property<boost::vertex_name_t, std::string> > > GraphCrash; typedef boost::graph_traits<GraphCrash>::vertex_descriptor vertex_t; typedef boost::graph_traits<GraphCrash>::edge_descriptor edge_t; typedef boost::graph_traits<GraphCrash>::vertex_iterator vertex_iterator; typedef boost::graph_traits<GraphCrash>::edge_iterator edge_iterator; GraphCrash graph; //vertices vertex_t v1 = boost::add_vertex(graph); boost::put(boost::vertex_name, graph, v1, "v1"); vertex_t v2 = boost::add_vertex(graph); boost::put(boost::vertex_name, graph, v2, "v2"); //edges boost::add_edge(v1, v2, graph); //remove last vertex boost::remove_vertex(v2, graph); //should not give any edge, however...: std::pair<edge_iterator, edge_iterator> prEdges; for (prEdges = boost::edges(graph); prEdges.first != prEdges.second; ++prEdges.first) { const edge_t e = *prEdges.first; const vertex_t u = boost::source(e, rGraph); const vertex_t v = boost::target(e, rGraph); } Do I something wrong? I use vc++ 7.1. Wkr, me (btw entering this message through gmane, it bounces back, with error that is is a top posting. Strange...) _________________________________________________________________ Talk with your online friends with MSN Messenger http://messenger.msn.nl/
On Feb 13, 2005, at 4:03 PM, gast 128 wrote:
GraphCrash graph;
//vertices vertex_t v1 = boost::add_vertex(graph); boost::put(boost::vertex_name, graph, v1, "v1");
vertex_t v2 = boost::add_vertex(graph); boost::put(boost::vertex_name, graph, v2, "v2");
//edges boost::add_edge(v1, v2, graph);
You need to call boost::clear_vertex(v2, graph) before remove_vertex.
//remove last vertex boost::remove_vertex(v2, graph);
What's happening is that there is an edge stored in the representation of "v1" that points to "v2". When you remove_vertex(v2, graph), that edge doesn't get removed. Calling clear_vertex(v2, graph) removes that all edges going out of v2 or into v2. So complete removal is a two-step process. The reason for this is that clear_vertex is an expensive operation (linear in the number of edges in the graph for directedS) whereas remove_vertex can have constant time: sometimes you know that the vertex has already been cleared, so you can skip the clear_vertex step. Doug
Douglas Gregor <dgregor <at> cs.indiana.edu> writes:
You need to call boost::clear_vertex(v2, graph) before remove_vertex.
Ok thanks. The book even mention it in the sideline. I was confused because clear_vertex(v1, graph) does automatically remove its edge. Sometimes this boost::graph stuff even suprises me from time to time. For example feeding a depth_search with a graph and vecS type vertex storage will work if the color map is not specified. However changing this to listS, and one gets a crash. But thanks. For now I will continue with playing with the serialization library. wkr, me
On Feb 15, 2005, at 5:24 PM, gast128 wrote:
Sometimes this boost::graph stuff even suprises me from time to time. For example feeding a depth_search with a graph and vecS type vertex storage will work if the color map is not specified. However changing this to listS, and one gets a crash.
With listS, you'll need to create and maintain a mapping from vertices to index values, e.g., add a property<vertex_index_t, std::size_t> to the vertex properties, and be sure to set these properties to numbers in the range [0, num_vertices(g)). For instance, with graph g of type Graph: graph_traits<Graph>::vertex_iterator vi, vi_end; std::size_t i = 0; for(tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi, ++i) put(vertex_index, g, *vi, i); Doug
Douglas Gregor <doug.gregor <at> gmail.com> writes:
With listS, you'll need to create and maintain a mapping from vertices to index values, e.g., add a property<vertex_index_t, std::size_t> to the vertex properties, and be sure to set these properties to numbers in the range [0, num_vertices(g)). For instance, with graph g of type Graph:
Thanks. I noticed it myself. Personally I don't like software constructs which do or don't work depending on some (template) parameter. I should make it work for every container (e.g. by using a std::map) or for no container. However I make this promise without deep knowledge of boost::graph internals... Wkr, me
participants (1)
-
Douglas Gregor -
Douglas Gregor -
gast 128 -
gast128