Boost topological_sort attempts to advance a dereferencable iterator 20 steps outside the valid range
I am still trying to understand why boost graph's topological_sort fails for a test program I have made to sort five vertexes. Originally I compiled this program against boost 1.33.1 on a Fedora Core 6 system using gcc-4.1.1. After receiving no response from the boost-users list that could solve this problem I read the Reporting Bug document on the boost website. I followed the CVS instructions and checked out a copy from the HEAD (reported as boost-1.35) and built it. I used the following flags: bjam -sHAVE_ICU=1 -d2 -sTOOLS=gcc -sBUILD=release -sEXPAT_INCLUDE=/usr/include -sEXPAT_LIBPATH=/usr/lib stage Afterwards I installed it and rebuilt the test program. It is still failing inside the topological_sort. The output of the program is below along with the test program source code. Stephen --------- OUTPUT ------------ [storri@localhost infrastructure]$ ./test_dag Added edge: 1 -> 20 Number of edges is 1 Added edge: 1 -> 30 Number of edges is 2 Added edge: 1 -> 40 Number of edges is 3 Added edge: 1 -> 5 Number of edges is 4 Added edge: 20 -> 5 Number of edges is 5 Added edge: 30 -> 5 Number of edges is 6 Added edge: 40 -> 5 Number of edges is 7 /usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c ++/4.1.1/debug/safe_iterator.h:277: error: attempt to advance a dereferenceable (start-of-sequence) iterator 20 steps, which falls outside its valid range. Objects involved in the operation: iterator @ 0x0xbfead0fc { type = N11__gnu_debug14_Safe_iteratorIN9__gnu_cxx17__normal_iteratorIPN5boost18default_color_typeEN10__gnu_norm6vectorIS4_SaIS4_EEEEEN15__gnu_debug_def6vectorIS4_S8_EEEE (mutable iterator); state = dereferenceable (start-of-sequence); references sequence with type `N15__gnu_debug_def6vectorIN5boost18default_color_typeESaIS2_EEE' @ 0x0xbfead0fc } Aborted ----------- CODE --------------- #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; } else { std::cout << boost::format("Added edge: %d -> %d") % parent_id % obj_ptr->get_ID() << std::endl; std::cout << "Number of edges is " << num_edges ( m_graph ) << 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; }
On Wed, 2007-04-25 at 01:07 -0500, Stephen Torri wrote:
I am still trying to understand why boost graph's topological_sort fails for a test program I have made to sort five vertexes. Originally I compiled this program against boost 1.33.1 on a Fedora Core 6 system using gcc-4.1.1. After receiving no response from the boost-users list that could solve this problem I read the Reporting Bug document on the boost website.
Ah, this is an issue with the vertex index map.
// 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();
The vertex_index property of a vertex should give each vertex a unique value in the range [0, num_vertices(m_graph)) When the vertex_index is >= the number of vertices in the graph (which happens in your test program), BGL algorithms like topological_sort will try to access memory beyond what has been allocated for their properties. If you change the last line of that snippet to ilist[node] = num_vertices (m_graph) - 1; it should work fine. The relevant part of http://www.boost.org/libs/graph/doc/topological_sort.html is the discussion of the vertex_index_map parameter. - Doug
On Thu, 2007-04-26 at 11:20 -0400, Douglas Gregor wrote:
// 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();
The vertex_index property of a vertex should give each vertex a unique value in the range
[0, num_vertices(m_graph))
When the vertex_index is >= the number of vertices in the graph (which happens in your test program), BGL algorithms like topological_sort will try to access memory beyond what has been allocated for their properties. If you change the last line of that snippet to
ilist[node] = num_vertices (m_graph) - 1;
it should work fine.
The relevant part of http://www.boost.org/libs/graph/doc/topological_sort.html is the discussion of the vertex_index_map parameter.
Ok. Now that explains why my fix works. I tried to make the vertex_index contain the unique ID that I assigned to each Component. Well that is fine but that information is also contained in the Component. So I switched my graph to have the following definition: typedef boost::property< boost::vertex_name_t, Component::ptr_t > VertexProperty_t; typedef boost::adjacency_list<boost::vecS, // OutEdgeList boost::vecS, // VertexList boost::directedS, // Directed VertexProperty_t> // VertexProperties Graph_t; Will each vertex_index will get a value assigned to it? I do not understand the way the boost::property is used by the graph library. Stephen
On Apr 26, 2007, at 9:27 PM, Stephen Torri wrote:
Ok. Now that explains why my fix works. I tried to make the vertex_index contain the unique ID that I assigned to each Component. Well that is fine but that information is also contained in the Component. So I switched my graph to have the following definition:
typedef boost::property< boost::vertex_name_t, Component::ptr_t > VertexProperty_t;
typedef boost::adjacency_list<boost::vecS, // OutEdgeList boost::vecS, // VertexList boost::directedS, // Directed VertexProperty_t> // VertexProperties Graph_t;
Will each vertex_index will get a value assigned to it?
Yes, it will. When the VertexListS template parameter is given vecS, the vertex_index is identical to the vertex's position in the vector of vertices. - Doug
My apologies for not keeping up with this discussion; I too have higher-priority duties (i.e. the ones I'm getting paid for). --- Stephen Torri wrote:
Will each vertex_index will get a value assigned to it? I do not understand the way the boost::property is used by the graph library.
Yes, if the vertex list selector is vecS, then the adjacency_list will have a built-in vertex_index property map in which each vertex has an associated index. See the "Vertex and Edge Properties" section of http://www.boost.org/libs/graph/doc/adjacency_list.html HTH, Cromwell D. Enage __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com
participants (3)
-
Cromwell Enage -
Douglas Gregor -
Stephen Torri