Hi everyone,
I'm having trouble with BGL's (Boost 1.33.1) topological sort. In my
source code I have this simple call:
std::vector<my_vertex> rev_topo_order;
topological_sort(*t, std::back_inserter(rev_topo_order));
Here "t" is an iterator to a list of graphs declared like this:
typedef boost::adjacency_list<
boost::setS, // Out edge list type
boost::listS, // Vertex list type
boost::bidirectionalS, // Needed for DAG, topo sort
my_property_bundle // Vertex properties
> my_graph_type;
The error trace below is mostly gobbledygook to me, but it looks like
it's running into trouble with BGL's default bgl_named_params. The call
chain runs through this curious bit of code:
template <typename VertexListGraph, typename OutputIterator>
void topological_sort(VertexListGraph& g, OutputIterator result)
{
topological_sort(g, result,
bgl_named_params<int, buffer_param_t>(0)); // bogus
}
That looks...interesting to me. What's with the "bogus" comment?
Any idea what's going on here? Any more information I can provide that
would be helpful?
The gmane archives show that Renaud Lepere ran into this problem in August
'06 but I can't find any replies to his question. He gave a small example
which I've confirmed reproduces the problem with g++ 4.1.2:
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/topological_sort.hpp>
#include <iterator>
typedef boost::adjacency_list<boost::vecS,
boost::listS,
boost::bidirectionalS,
int,
int > Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
typedef std::vector< Vertex > Vertices;
int main()
{
Graph g;
Vertices vs;
boost::topological_sort(g, back_inserter(vs));
}
Thanks for any help you can give.
-Dave
----------------------
Error trace
----------------------
./boost-1_33_1/boost/property_map.hpp: In member function 'R
boost::iterator_property_map<RandomAccessIterator, IndexMap, T,
R>::operator[](typename boost::property_traits<IndexMap>::key_type) const
[with RandomAccessIterator =
__gnu_cxx::__normal_iterator<boost::default_color_type*,
std::vector<boost::default_color_type,
std::allocator<boost::default_color_type> > >, IndexMap =
boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS,
boost::listS, boost::bidirectionalS, myclass::my_property_bundle,
boost::no_property, boost::no_property, boost::listS>,
boost::detail::error_property_not_found, const
boost::detail::error_property_not_found&, boost::vertex_index_t>, T =
boost::default_color_type, R = boost::default_color_type&]':
./boost-1_33_1/boost/property_map.hpp:319: instantiated from 'void
boost::put(const boost::put_get_helper<Reference, PropertyMap>&, K, const V&)
[with PropertyMap =
boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::default_color_type*,
std::vector<boost::default_color_type,
std::allocator<boost::default_color_type> > >,
boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS,
boost::listS, boost::bidirectionalS, myclass::my_property_bundle,
boost::no_property, boost::no_property, boost::listS>,
boost::detail::error_property_not_found, const
boost::detail::error_property_not_found&, boost::vertex_index_t>,
boost::default_color_type, boost::default_color_type&>, Reference =
boost::default_color_type&, K = void*, V = boost::default_color_type]'
./boost-1_33_1/boost/graph/depth_first_search.hpp:197: instantiated from
'void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap,
typename boost::graph_traits<G>::vertex_descriptor) [with VertexListGraph =
boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS,
myclass::my_property_bundle, boost::no_property, boost::no_property,
boost::listS>, DFSVisitor =
boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void*,
std::allocator<void*> > > >, ColorMap =
boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::default_color_type*,
std::vector<boost::default_color_type,
std::allocator<boost::default_color_type> > >,
boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS,
boost::listS, boost::bidirectionalS, myclass::my_property_bundle,
boost::no_property, boost::no_property, boost::listS>,
boost::detail::error_property_not_found, const
boost::detail::error_property_not_found&, boost::vertex_index_t>,
boost::default_color_type, boost::default_color_type&>]'
./boost-1_33_1/boost/graph/depth_first_search.hpp:246: instantiated from
'static void
boost::detail::dfs_dispatch<boost::detail::error_property_not_found>::apply(const
VertexListGraph&, DFSVisitor, Vertex, const boost::bgl_named_params<P, T,
R>&, boost::detail::error_property_not_found) [with VertexListGraph =
boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS,
myclass::my_property_bundle, boost::no_property, boost::no_property,
boost::listS>, Vertex = void*, DFSVisitor =
boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void*,
std::allocator<void*> > > >, P =
boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void*,
std::allocator<void*> > > >, T = boost::graph_visitor_t, R =
boost::bgl_named_params<int, boost::buffer_param_t, boost::no_property>]'
./boost-1_33_1/boost/graph/depth_first_search.hpp:324: instantiated from
'void boost::depth_first_search(const VertexListGraph&, const
boost::bgl_named_params<P, T, R>&) [with VertexListGraph =
boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS,
myclass::my_property_bundle, boost::no_property, boost::no_property,
boost::listS>, P =
boost::topo_sort_visitor<std::back_insert_iterator<std::vector<void*,
std::allocator<void*> > > >, T = boost::graph_visitor_t, R =
boost::bgl_named_params<int, boost::buffer_param_t, boost::no_property>]'
./boost-1_33_1/boost/graph/topological_sort.hpp:64: instantiated from 'void
boost::topological_sort(VertexListGraph&, OutputIterator, const
boost::bgl_named_params<P, T, R>&) [with VertexListGraph =
boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS,
myclass::my_property_bundle, boost::no_property, boost::no_property,
boost::listS>, OutputIterator = std::back_insert_iterator<std::vector<void*,
std::allocator<void*> > >, P = int, T = boost::buffer_param_t, R =
boost::no_property]'
./boost-1_33_1/boost/graph/topological_sort.hpp:70: instantiated from 'void
boost::topological_sort(VertexListGraph&, OutputIterator) [with
VertexListGraph = boost::adjacency_list<boost::setS, boost::listS,
boost::bidirectionalS, myclass::my_property_bundle, boost::no_property,
boost::no_property, boost::listS>, OutputIterator =
std::back_insert_iterator<std::vector<void*, std::allocator<void*> > >]'
[ User code instantiations snipped]
./boost-1_33_1/boost/property_map.hpp:349: error: no match for 'operator+' in
'((const
boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::default_color_type*,
std::vector<boost::default_color_type,
std::allocator<boost::default_color_type> > >,
boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS,
boost::listS, boost::bidirectionalS, myclass::my_property_bundle,
boost::no_property, boost::no_property, boost::listS>,
boost::detail::error_property_not_found, const
boost::detail::error_property_not_found&, boost::vertex_index_t>,
boost::default_color_type,
boost::default_color_type&>*)this)->boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::default_color_type*,
std::vector<boost::default_color_type,
std::allocator<boost::default_color_type> > >,
boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS,
boost::listS, boost::bidirectionalS, myclass::my_property_bundle,
boost::no_property, boost::no_property, boost::listS>,
boost::detail::error_property_not_found, const
boost::detail::error_property_not_found&, boost::vertex_index_t>,
boost::default_color_type, boost::default_color_type&>::iter + boost::get
[with PropertyMap =
boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS,
boost::listS, boost::bidirectionalS, myclass::my_property_bundle,
boost::no_property, boost::no_property, boost::listS>,
boost::detail::error_property_not_found, const
boost::detail::error_property_not_found&, boost::vertex_index_t>, Reference =
const boost::detail::error_property_not_found&, K = void*](((const
boost::put_get_helper<const boost::detail::error_property_not_found&,
boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS,
boost::listS, boost::bidirectionalS, myclass::my_property_bundle,
boost::no_property, boost::no_property, boost::listS>,
boost::detail::error_property_not_found, const
boost::detail::error_property_not_found&, boost::vertex_index_t> >&)((const
boost::put_get_helper<const boost::detail::error_property_not_found&,
boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS,
boost::listS, boost::bidirectionalS, myclass::my_property_bundle,
boost::no_property, boost::no_property, boost::listS>,
boost::detail::error_property_not_found, const
boost::detail::error_property_not_found&, boost::vertex_index_t> >*)(&((const
boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::default_color_type*,
std::vector<boost::default_color_type,
std::allocator<boost::default_color_type> > >,
boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS,
boost::listS, boost::bidirectionalS, myclass::my_property_bundle,
boost::no_property, boost::no_property, boost::listS>,
boost::detail::error_property_not_found, const
boost::detail::error_property_not_found&, boost::vertex_index_t>,
boost::default_color_type,
boost::default_color_type&>*)this)->boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::default_color_type*,
std::vector<boost::default_color_type,
std::allocator<boost::default_color_type> > >,
boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS,
boost::listS, boost::bidirectionalS, myclass::my_property_bundle,
boost::no_property, boost::no_property, boost::listS>,
boost::detail::error_property_not_found, const
boost::detail::error_property_not_found&, boost::vertex_index_t>,
boost::default_color_type, boost::default_color_type&>::index))), ((void*
const&)((void* const*)(& v))))'
./lib/gcc/i686-pc-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_iterator.h:703:
note: candidates are: __gnu_cxx::__normal_iterator<_Iterator, _Container>
__gnu_cxx::__normal_iterator<_Iterator, _Container>::operator+(const typename
std::iterator_traits<_Iter>::difference_type&) const [with _Iterator =
boost::default_color_type*, _Container =
std::vector<boost::default_color_type,
std::allocator<boost::default_color_type> >]
./lib/gcc/i686-pc-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_bvector.h:353:
note: std::_Bit_const_iterator std::operator+(ptrdiff_t,
const std::_Bit_const_iterator&)
./lib/gcc/i686-pc-linux-gnu/4.1.2/../../../../include/c++/4.1.2/bits/stl_bvector.h:267:
note: std::_Bit_iterator std::operator+(ptrdiff_t, const
std::_Bit_iterator&)
