Re: [Boost-users] Boost graph problem removing last vertex

From: Douglas Gregor (dgregor_at_[hidden])
Date: 2005-02-15 09:06:14

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