BOOST: 1.33.1 GCC: 4.1.1 OS: Fedora Core 6 I am receiving a abort signal from glibc when I am running the test program that is attached. You will find that the program is suppose to create a directed graph of five vertexes. I have printed out how the edges are structured so you will have a picture of the graph. I hope someone is able to help me figure out what is going wrong with this test program. So far I am stumped as to what is wrong. Figuring out the problem and its solution will help me figure out a much larger problem. So the questions I have are: 1. Is there a problem with the definition of the graph? 2. Did I fail to do something in the initialization of the graph? 3. Is this the right forum for me asking my questions? Stephen ----------------------------------------- OUTPUT ----------------------------------------- [storri@localhost infrastructure]$ ./test_dag Added edge: 1 -> 20 Added edge: 1 -> 30 Added edge: 1 -> 40 Added edge: 1 -> 5 Added edge: 20 -> 5 Added edge: 30 -> 5 Added edge: 40 -> 5 *** glibc detected *** ./test_dag: free(): invalid next size (fast): 0x09f08780 *** ======= Backtrace: ========= /lib/libc.so.6[0x47c1709d] /lib/libc.so.6(cfree+0x90)[0x47c1a6f0] /usr/lib/libstdc++.so.6(_ZdlPv+0x21)[0x48058ef1] ./test_dag[0x8053357] ./test_dag[0x8053381] ./test_dag[0x80533bb] ./test_dag[0x8053db1] ./test_dag[0x805f2bd] ./test_dag[0x805f3e9] ./test_dag[0x805f434] ./test_dag[0x805f468] ./test_dag[0x804a858] /lib/libc.so.6(__libc_start_main+0xdc)[0x47bc6f2c] ./test_dag(_ZNSt15basic_streambufIcSt11char_traitsIcEE6xsputnEPKci +0x7d)[0x804a251] ======= Memory map: ======== 003e3000-003e4000 r-xp 003e3000 00:00 0 [vdso] 08048000-08068000 r-xp 00000000 fd:00 3178562 /home/storri/src/libreverse/src/infrastructure/test_dag 08068000-08069000 rwxp 0001f000 fd:00 3178562 /home/storri/src/libreverse/src/infrastructure/test_dag 09f08000-09f29000 rwxp 09f08000 00:00 0 47b94000-47bad000 r-xp 00000000 fd:00 458769 /lib/ld-2.5.so 47bad000-47bae000 r-xp 00018000 fd:00 458769 /lib/ld-2.5.so 47bae000-47baf000 rwxp 00019000 fd:00 458769 /lib/ld-2.5.so 47bb1000-47ce8000 r-xp 00000000 fd:00 458776 /lib/libc-2.5.so 47ce8000-47cea000 r-xp 00137000 fd:00 458776 /lib/libc-2.5.so 47cea000-47ceb000 rwxp 00139000 fd:00 458776 /lib/libc-2.5.so 47ceb000-47cee000 rwxp 47ceb000 00:00 0 47cf0000-47d15000 r-xp 00000000 fd:00 458802 /lib/libm-2.5.so 47d15000-47d16000 r-xp 00024000 fd:00 458802 /lib/libm-2.5.so 47d16000-47d17000 rwxp 00025000 fd:00 458802 /lib/libm-2.5.so 47f97000-47fa2000 r-xp 00000000 fd:00 458837 /lib/libgcc_s-4.1.1-20070105.so.1 47fa2000-47fa3000 rwxp 0000a000 fd:00 458837 /lib/libgcc_s-4.1.1-20070105.so.1 47fa5000-48085000 r-xp 00000000 fd:00 12363696 /usr/lib/libstdc ++.so.6.0.8 48085000-48088000 r-xp 000e0000 fd:00 12363696 /usr/lib/libstdc ++.so.6.0.8 48088000-4808a000 rwxp 000e3000 fd:00 12363696 /usr/lib/libstdc ++.so.6.0.8 4808a000-48090000 rwxp 4808a000 00:00 0 b7e00000-b7e21000 rw-p b7e00000 00:00 0 b7e21000-b7f00000 ---p b7e21000 00:00 0 b7f4c000-b7f4e000 rw-p b7f4c000 00:00 0 b7f60000-b7f62000 rw-p b7f60000 00:00 0 bfa5e000-bfa73000 rw-p bfa5e000 00:00 0 [stack] Aborted ----------------------------------------- GDB OUTPUT ----------------------------------------- (gdb) bt #0 0x009af402 in __kernel_vsyscall () #1 0x47bd9d40 in raise () from /lib/libc.so.6 #2 0x47bdb591 in abort () from /lib/libc.so.6 #3 0x47c0f33b in __libc_message () from /lib/libc.so.6 #4 0x47c1709d in _int_free () from /lib/libc.so.6 #5 0x47c1a6f0 in free () from /lib/libc.so.6 #6 0x48058ef1 in operator delete () from /usr/lib/libstdc++.so.6 #7 0x08053357 in __gnu_cxx::new_allocator<boost::default_color_type>::deallocate (this=0xbfcf7974, __p=0x97fe780) at /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/ext/new_allocator.h:94 #8 0x08053381 in std::_Vector_base<boost::default_color_type, std::allocator<boost::default_color_type> >::_M_deallocate (this=0xbfcf7974, __p=0x97fe780, __n=5) at /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_vector.h:133 #9 0x080533bb in ~_Vector_base (this=0xbfcf7974) at /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_vector.h:119 #10 0x08053db1 in ~vector (this=0xbfcf7974) at /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_vector.h:272 #11 0x0805f2bd in boost::detail::dfs_dispatch<boost::detail::error_property_not_found>::apply<boost::adjacency_list<boost::setS, boost::setS, boost::directedS, boost::property<boost::vertex_index_t, unsigned int, boost::property<boost::vertex_name_t, boost::shared_ptr<Component>, boost::no_property> >, boost::no_property, boost::no_property, boost::listS>, void*, boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void*, std::allocator<void*> > > >, boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void*, std::allocator<void*> > > >, boost::graph_visitor_t, boost::bgl_named_params<int, boost::buffer_param_t, boost::no_property> > (g=@0xbfcf7ac4, vis= {<boost::dfs_visitor<boost::null_visitor>> = {m_vis = {<> = {<No data fields>}, <No data fields>}}, m_iter = {<std::iterator<std::output_iterator_tag,void,void,void,void>> = {<No data fields>}, container = 0xbfcf7b0c}}, start_vertex=0x97fe220, params=@0xbfcf7a34) at /usr/include/boost/graph/depth_first_search.hpp:246 #12 0x0805f3e9 in boost::depth_first_search<boost::adjacency_list<boost::setS, boost::setS, boost::directedS, boost::property<boost::vertex_index_t, unsigned int, boost::property<boost::vertex_name_t, boost::shared_ptr<Component>, boost::no_property> >, boost::no_property, boost::no_property, boost::listS>, boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void*, std::allocator<void*> > > >, boost::graph_visitor_t, boost::bgl_named_params<int, boost::buffer_param_t, boost::no_property> > (g=@0xbfcf7ac4, params=@0xbfcf7a34) at /usr/include/boost/graph/depth_first_search.hpp:324 #13 0x0805f434 in boost::topological_sort<boost::adjacency_list<boost::setS, boost::setS, boost::directedS, boost::property<boost::vertex_index_t, unsigned int, boost::property<boost::vertex_name_t, boost::shared_ptr<Component>, boost::no_property> >, boost::no_property, boost::no_property, boost::listS> const, std::back_insert_iterator<std::vector<void*, std::allocator<void*> > >, int, boost::buffer_param_t, boost::no_property> ( g=@0xbfcf7ac4, result= {<std::iterator<std::output_iterator_tag,void,void,void,void>> = {<No data fields>}, container = 0xbfcf7b0c}, params=@0xbfcf7a74) at /usr/include/boost/graph/topological_sort.hpp:64 #14 0x0805f468 in boost::topological_sort<boost::adjacency_list<boost::setS, boost::setS, boost::directedS, boost::property<boost::vertex_index_t, unsigned int, boost::property<boost::vertex_name_t, boost::shared_ptr<Component>, boost::no_property> >, boost::no_property, boost::no_property, boost::listS> const, std::back_insert_iterator<std::vector<void*, std::allocator<void*> > > > (g=@0xbfcf7ac4, result= {<std::iterator<std::output_iterator_tag,void,void,void,void>> = {<No data fields>}, container = 0xbfcf7b0c}) at /usr/include/boost/graph/topological_sort.hpp:70 #15 0x0804a858 in main () at test_dag.cpp:256 ------------------------------- TEST PROGRAM -------------------------------- #include <boost/graph/adjacency_list.hpp> #include <boost/shared_ptr.hpp> #include <boost/cstdint.hpp> #include <boost/format.hpp> #include <boost/graph/topological_sort.hpp> #include <iostream> #include <map> class Component; class Graph_Base { public: typedef boost::property< boost::vertex_index_t, boost::uint32_t, boost::property< boost::vertex_name_t, boost::shared_ptr<Component> > > VertexProperty_t; typedef boost::adjacency_list< boost::setS, // OutEdgeList boost::setS, // VertexList boost::directedS, // Directed VertexProperty_t > // VertexProperties Graph_t; typedef boost::adj_list_vertex_property_map<Graph_Base::Graph_t, boost::shared_ptr<Component>, const boost::shared_ptr<Component>&, boost::vertex_name_t> Property_Map_const_t; }; class Component { public: typedef boost::shared_ptr<Component> ptr_t; Component ( boost::uint32_t id ) : m_id ( id ) {} ~Component () { m_source_list.clear(); } // Now part of Component_Data void set_Data_Source ( uint32_t id ) { if ( ! m_source_list.insert ( std::make_pair ( id, false ) ).second ) { std::cerr << "WARNING: Attempted to add a duplicate component id."; std::cerr << std::endl; std::cerr << "Ignoring component id." << std::endl; } } std::map<boost::uint32_t, bool>::const_iterator get_Source_List_Begin() const { return m_source_list.begin(); } std::map<boost::uint32_t, bool>::const_iterator get_Source_List_End() const { return m_source_list.end(); } boost::uint32_t get_ID (void) const { return m_id; } private: boost::uint32_t m_id; std::map<boost::uint32_t, bool> m_source_list; }; class Component_Graph { public: typedef boost::graph_traits<Graph_Base::Graph_t>::vertex_descriptor Vertex_t; typedef boost::graph_traits<Graph_Base::Graph_t>::edge_descriptor Edge_t; typedef std::map<uint32_t, Vertex_t> IdVertexMap_t; Component_Graph () {} void add_Component ( Component::ptr_t obj_ptr ) { bool no_duplicate; IdVertexMap_t::iterator pos; Vertex_t node; if ( obj_ptr.get() == 0 ) { std::cerr << boost::format("Exception throw in %s at line %d") % __FILE__ % __LINE__ << std::endl; return; } boost::tie (pos, no_duplicate) = m_index.insert (std::make_pair(obj_ptr->get_ID(), node)); if ( no_duplicate ) { // Insertion was successful // Make a new vertex and return handle to 'node' node = add_vertex(m_graph); // Get list of Components boost::property_map<Graph_Base::Graph_t, boost::vertex_name_t>::type clist = boost::get(boost::vertex_name, m_graph); // Assign component to vertex position clist[node] = obj_ptr; // Add vertex handle to map position pos->second = node; // Get list of indexes boost::property_map<Graph_Base::Graph_t, boost::vertex_index_t>::type ilist = get(boost::vertex_index, m_graph); ilist[node] = obj_ptr->get_ID(); for ( std::map<boost::uint32_t,bool>::const_iterator cpos = obj_ptr->get_Source_List_Begin(); cpos != obj_ptr->get_Source_List_End(); ++cpos ) { this->add_Child ( (*cpos).first, obj_ptr ); } } else { std::cerr << "ERROR: Duplicate source found. Skipping Component" << std::endl; return; } } void add_Child ( uint32_t parent_id, Component::ptr_t obj_ptr ) { IdVertexMap_t::iterator pos; IdVertexMap_t::iterator cpos; if ( obj_ptr.get() == 0 ) { std::cerr << boost::format("Exception throw in %s at line %d") % __FILE__ % __LINE__ << std::endl; return; } pos = m_index.find (parent_id); cpos = m_index.find ( obj_ptr->get_ID() ); if (pos == m_index.end()) { std::cerr << "ERROR: Cannot find parent. Skipping adding component #" << obj_ptr->get_ID() << std::endl; return; } // Add edge from parent to child Edge_t link; if (! (add_edge ( pos->second, cpos->second, m_graph).second)) { std::cerr << "ERROR: Duplicate edge exists from " << parent_id << " to " << obj_ptr->get_ID() << std::endl; return; } else { std::cout << boost::format("Added edge: %d -> %d") % parent_id % obj_ptr->get_ID() << std::endl; } } Graph_Base::Graph_t const& get_Graph () const { return m_graph; } Component::ptr_t get_Component (const Vertex_t& node) const { Graph_Base::Property_Map_const_t clist = get(boost::vertex_name, m_graph); return clist[node]; } private: Graph_Base::Graph_t m_graph; IdVertexMap_t m_index; }; int main (int, char**) { // CREATE Component_Graph Component_Graph m_graph; // Create Components Component::ptr_t node_one ( new Component ( 1 ) ); Component::ptr_t node_twenty ( new Component ( 20 ) ); node_twenty->set_Data_Source ( 1 ); Component::ptr_t node_thirty ( new Component ( 30 ) ); node_thirty->set_Data_Source ( 1 ); Component::ptr_t node_forty ( new Component ( 40 ) ); node_forty->set_Data_Source ( 1 ); Component::ptr_t node_five ( new Component ( 5 ) ); node_five->set_Data_Source ( 1 ); node_five->set_Data_Source ( 20 ); node_five->set_Data_Source ( 30 ); node_five->set_Data_Source ( 40 ); // Add Components to Graph m_graph.add_Component ( node_one ); m_graph.add_Component ( node_twenty ); m_graph.add_Component ( node_thirty ); m_graph.add_Component ( node_forty ); m_graph.add_Component ( node_five ); // Call topological_sort on graph typedef std::vector<Component_Graph::Vertex_t> m_container; m_container comp_list; boost::topological_sort ( m_graph.get_Graph(), std::back_inserter ( comp_list ) ); std::cout << "A topological ordering: "; for ( m_container::reverse_iterator ii = comp_list.rbegin(); ii != comp_list.rend(); ++ii ) { Component::ptr_t comp_ptr = m_graph.get_Component ( *ii ); std::cout << comp_ptr->get_ID() << " "; } std::cout << std::endl; return 0; }