[Boost-users] [BGL] topological_sort compile error

From: David A. Greene (greened_at_[hidden])
Date: 2007-06-04 12:59:11

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&)