Topological Sort using Boost::topological_sort

Question

I am trying to use topological_sort function of boost.

I am using the boost::adjacency_list with setS and listS as the underlying storage for edges and vertices.

typedef boost::adjacency_list<boost::setS, boost::listS, boost::bidirectionalS > SizerGraph;  
    SizerGraph sizerGraph;  
    typedef boost::graph_traits<SizerGraph>::vertex_descriptor Vertex;  
    boost::topological_sort(sizerGraph, std::ostream_iterator<Vertex>(std::cout, "\n"));

Compilation results in errors. (g++ 3.4.6)

/usr/include/boost/property_map.hpp:349: error: no match for 'operator+' in '((const boost::iterator_property_map<__gnu_cxx::__normal_iterator > >, boost::adj_list_vertex_property_map, 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::adj_list_vertex_property_map, 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::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, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t>

&)((const boost::put_get_helper, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t> *)(((const boost::adj_list_vertex_property_map, 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::adj_list_vertex_property_map, 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)) + 8u))), ((void const&)((void* const*)(&v))))'

/usr/include/boost/graph/detail/adjacency_list.hpp:2264: error: no matching function for call to `get_property_value(boost::no_property&, boost::vertex_index_t)

However, using vecS as the underlying storage mechanism for vertices results in clean compilation.

Is my usage of listS for vertices breaking any concept requirement?

Hi, googling on the boost discussion group I found this. Need to try it. — Prasad

Marshall Clow Marshall Clow · Accepted Answer · 2011-12-24T01:20:22

This is just a guess, but the error message starts out:

No match for 'operator+' in blah .. iterator ..

When you use VecS, you get a vector - whose iterators are random access, and support operator+

When you use ListS, you get a list - whose iterators are bidirectional, and do not support operator+

Topological Sort using Boost::topological_sort

1 Answers