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
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
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
Douglas Gregor
With listS, you'll need to create and maintain a mapping from vertices to index values, e.g., add a property
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 (4)
-
Douglas Gregor
-
Douglas Gregor
-
gast 128
-
gast128