On 2/8/07, Heiko Bauke <heiko.bauke@physics.ox.ac.uk> 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