From: Stephen Torri (storri_at_[hidden])
Date: 2007-04-25 02:07:59
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_at_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;
}