Boost logo

Boost :

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-02-10 17:03:05

On 2/8/07, Heiko Bauke <heiko.bauke_at_[hidden]> wrote:
> Hi,
> since a day I was fighting with a strange bug in my program. Finally, I
> think, I could trace down this error to a problem in the Boost graph
> library. The following test program crashes, in a call to
> boost::clear_vertex.


> It seams to me, there is a double free error, that occurs if the
> adjacency_list has self-loops. If the if-statement is not commented
> out, the program does not crash. I am using Boost 1.33.1.

Hi Heiko,

I can verify that your code produces a segfault - in fact, an even
simpler example will produce the same results:

#include <boost/graph/adjacency_list.hpp>
using namespace boost;
typedef adjacency_list<vecS,vecS,undirectedS> graph_t;

int main()
   graph_t G(1);

The code for clear_vertex(v,G) on an undirected graph does the

for all edges (u,v) adjacent to v:
   (1) remove u from v's list of adjacent edges
   (2) remove (u,v) from the list of all edges in the graph
clear u's list of adjacent edges

And it's step 2 above that's causing the problem: in an undirected
graph, add_edge(v,v,G) creates two copies of the edge (v,v) on v's
list of adjacent edges. The second time (2) is called on the same
edge, you get a segfault.

IMO, It would be very awkward to add some logic to clear_edge to
recognize at step 2 whether or not the edge has been removed. I'd
prefer modifying add_edge so that either (a) it doesn't support self-
loops (this functionality was added in - see the thread at or (b) in the case of a self-loop, only add
the edge (v,v) once to v's list of adjacent edges.

(b) seems the most reasonable fix - and it's just a one line fix to
add_edge for undirected graphs. Does anyone else have an opinion
on this?


Boost list run by bdawes at, gregod at, cpdaniel at, john at