[BGL] Double free error (?)
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. #include <cstdlib> #include <boost/tuple/tuple.hpp> #include <boost/graph/adjacency_list.hpp> typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> graph_t; typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_descriptor; typedef boost::graph_traits<graph_t>::vertex_iterator vertex_iterator; int main() { graph_t G(8); vertex_iterator vi, vi_end, ui, ui_end; for (boost::tie(vi, vi_end)=boost::vertices(G); vi!=vi_end; ++vi) for (boost::tie(ui, ui_end)=boost::vertices(G); ui!=ui_end; ++ui) // if (*vi!=*ui) boost::add_edge(*vi, *ui, G); for (boost::tie(vi, vi_end)=boost::vertices(G); vi!=vi_end; ++vi) boost::clear_vertex(*vi, G); return EXIT_SUCCESS; } 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. Heiko -- -- Perfection is attained not when there is nothing more to add, but -- when there is nothing more to remove. (Antoine de Saint-Exupéry) -- Cluster Computing @ http://www.clustercomputing.de -- Heiko Bauke @ http://www.physics.ox.ac.uk/users/bauke
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
participants (2)
-
Aaron Windsor -
Heiko Bauke