BGL: *** glibc detected *** free(): invalid next size
Vertexes in my graph have the distance and predecessor properties. These properties at each vertex are vectors: they store distances and predecessor of shortest paths to every other node in the graph. Below is my program. I run the program and as input I give the file also listed below, and get this run-time error: *** glibc detected *** free(): invalid next size (fast): 0x085dd110 I would appreciate your advice on what I'm doing wrong. Best, Irek ********************************************************************** #include <string> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp> #include <boost/graph/iteration_macros.hpp> #include <boost/graph/graphviz.hpp> using namespace std; using namespace boost; typedef adjacency_list_traits<vecS, vecS, undirectedS>::vertex_descriptor Vertex; typedef boost::adjacency_list <vecS, vecS, undirectedS, property<vertex_name_t, string, property<vertex_distance_t, vector<int>, property<vertex_predecessor_t, vector<Vertex> > > >, property<edge_weight_t, int, property<edge_weight2_t, int> > > Graph; int main () { Graph g; dynamic_properties dp; dp.property("node_id", get(vertex_name, g)); dp.property("distance", get(edge_weight, g)); dp.property("lambdas", get(edge_weight2, g)); read_graphviz(cin, g, dp); BGL_FORALL_VERTICES(v, g, Graph) { get(vertex_distance, g, v).resize(num_vertices(g)); get(vertex_predecessor, g, v).resize(num_vertices(g)); dijkstra_shortest_paths (g, v, predecessor_map(&get(vertex_predecessor, g, v)[0]). distance_map(&get(vertex_distance, g, v)[0])); } } ********************************************************************** Graph { a; b; c; d; e; f; a -- b [distance = "100", lambdas = "10"] b -- c [distance = "200", lambdas = "10"] c -- d [distance = "80", lambdas = "10"] b -- e [distance = "40", lambdas = "10"] c -- f [distance = "100", lambdas = "10"] a -- e [distance = "210", lambdas = "10"] e -- f [distance = "340", lambdas = "10"] f -- d [distance = "50", lambdas = "10"] }
I'm writing with an update on my problem. I'm using Fedora Core 3, Linux 2.6.10, GCC 3.4.4. The description of my error is given in the documentation of glibc:
The version of glibc provided with Red Hat Enterprise Linux 4 performs additional internal sanity checks to prevent and detect data corruption as early as possible. By default, should corruption be detected, a message similar to the following will be displayed on standard error (or logged via syslog if stderr is not open):
*** glibc detected *** double free or corruption: 0x0937d008 ***
So it seems there are problems with memory allocation. To see what's up, I ran valgrind on my code and I got many errors of this kind: ==6464== Invalid write of size 4 ==6464== at 0x805E917: void put<int, int>(int*, int, int const&) (property_map.hpp:134) ==6464== by 0x805C503: void boost::dijkstra_shortest_paths<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_name_t, std::string, boost::property<boost::vertex_distance_t, std::vector<int, std::allocator<int> >, boost::property<boost::vertex_predecessor_t, std::vector<unsigned, std::allocator<unsigned> >, boost::no_property> > >, boost::property<boost::edge_weight_t, int, boost::property<boost::edge_weight2_t, int, boost::no_property> >, boost::no_property, boost::listS>, boost::dijkstra_visitor<boost::null_visitor>, unsigned*, int*, boost::adj_list_edge_property_map<boost::undirected_tag, int, int const&, unsigned, boost::property<boost::edge_weight2_t, int, boost::no_property> const, boost::edge_weight_t>, boost::vec_adj_list_vertex_id_map<boost::property<boost::vertex_name_t, std::string, boost::property<boost::vertex_distance_t, std::vector<int, std::allocator<int> >, boost::property<boost::vertex_predecessor_t, std::vector<unsigned, std::allocator<unsigned> >, boost::no_property> > >, unsigned>, std::less<int>, boost::closed_plus<int>, int, int, boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::default_color_type*, std::vector<boost::closed_plus, std::allocator<boost::closed_plus> >
, boost::property<boost::edge_weight2_t, int, boost::no_property> const, boost::closed_plus, boost::closed_plus&> (boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_name_t, std::string, boost::property<boost::vertex_distance_t, std::vector<int, std::allocator<int> >, boost::property<boost::vertex_predecessor_t, std::vector<unsigned, std::allocator<unsigned> >, boost::no_property>
, boost::property<boost::edge_weight_t, int, boost::property<boost::edge_weight2_t, int, boost::no_property> >, boost::no_property, boost::listS> const&, boost::graph_traits<std::allocator<boost::closed_plus> ::vertex_descriptor, unsigned*, int*, boost::adj_list_edge_property_map<boost::undirected_tag, int, int const&, unsigned, boost::property<boost::edge_weight2_t, int, boost::no_property> const, boost::edge_weight_t>, boost::vec_adj_list_vertex_id_map<boost::property<boost::vertex_name_t, std::string, boost::property<boost::vertex_distance_t, std::vector<int, std::allocator<int> >, boost::property<boost::vertex_predecessor_t, std::vector<unsigned, std::allocator<unsigned> >, boost::no_property> > >, unsigned>, std::less<int>, boost::closed_plus<int>, int, int, boost::dijkstra_visitor<boost::null_visitor>, boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::default_color_type*, std::vector<boost::closed_plus, std::allocator<boost::closed_plus> > , boost::property<boost::edge_weight2_t, int, boost::no_property> const, boost::closed_plus, boost::closed_plus&>) (dijkstra_shortest_paths.hpp:250)
Unfortunately, my knowledge of BGL and its implementation techniques is modest and so I will not venture to find out what the problem exactly is. Instead, I rewrote the broken piece of code this way: vector<int> dist(num_vertices(g)); vector<Vertex> pred(num_vertices(g)); BGL_FORALL_VERTICES (v, g, Graph) { dijkstra_shortest_paths (g, v, predecessor_map(&pred[0]).distance_map(&dist[0])); put(vertex_distance, g, v, dist); put(vertex_predecessor, g, v, pred); } This works for me, and neither glibc nor valgrind complain. The complete text of my program is at the bottom of this email. I don't think there is any performance blow from using vectors as properties. Whenever I need to access these properties I write: get(vertex_distance, g, i) or get(vertex_distance, g, i)[j]. I get references so the properties (which are vectors) are not copied. Best, Irek Irek Szczesniak wrote:
Vertexes in my graph have the distance and predecessor properties. These properties at each vertex are vectors: they store distances and predecessor of shortest paths to every other node in the graph.
Below is my program. I run the program and as input I give the file also listed below, and get this run-time error:
*** glibc detected *** free(): invalid next size (fast): 0x085dd110
I would appreciate your advice on what I'm doing wrong.
Best, Irek
(...)
******************************************************************** #include <string> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp> #include <boost/graph/iteration_macros.hpp> #include <boost/graph/graphviz.hpp> using namespace std; using namespace boost; typedef adjacency_list_traits<vecS, vecS, undirectedS>::vertex_descriptor Vertex; typedef boost::adjacency_list <vecS, vecS, undirectedS, property<vertex_name_t, string, property<vertex_distance_t, vector<int>, property<vertex_predecessor_t, vector<Vertex> > > >, property<edge_weight_t, int, property<edge_weight2_t, int> > > Graph; int main () { Graph g; dynamic_properties dp; dp.property("node_id", get(vertex_name, g)); dp.property("distance", get(edge_weight, g)); dp.property("lambdas", get(edge_weight2, g)); read_graphviz(cin, g, dp); // My implementation now is this: vector<int> dist(num_vertices(g)); vector<Vertex> pred(num_vertices(g)); BGL_FORALL_VERTICES (v, g, Graph) { dijkstra_shortest_paths (g, v, predecessor_map(&pred[0]).distance_map(&dist[0])); put(vertex_distance, g, v, dist); put(vertex_predecessor, g, v, pred); } // This is what I used before: // // BGL_FORALL_VERTICES(v, g, Graph) // { // get(vertex_distance, g, v).resize(num_vertices(g)); // get(vertex_predecessor, g, v).resize(num_vertices(g)); // // dijkstra_shortest_paths // (g, v, predecessor_map(&get(vertex_predecessor, g, v)[0]). // distance_map(&get(vertex_distance, g, v)[0])); // } }
participants (1)
-
Irek Szczesniak