Re: [boost] [BGL] Double free error (?)

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.

<snip>

> 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);
   add_edge(0,0,G);
   clear_vertex(0,G);
}

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

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
http://tinyurl.com/2rxyaw) 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?

Aaron