使用 Boost::topological_sort 进行拓扑排序

Question

我正在尝试使用 boost 的 topological_sort 函数。

我使用带有 setS 和 listS 的 boost::adjacency_list 作为边和顶点的底层存储。

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"));

编译结果出错。 （g++3.4.6）

/usr/include/boost/property_map.hpp:349：错误：不匹配 '((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&>*)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 [与 PropertyMap = 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::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：错误：否 用于调用 `get_property_value(boost::no_property&, boost::vertex_index_t)

但是，使用 vecS 作为顶点的底层存储机制可以实现干净的编译。

我对顶点使用 listS 是否违反了任何概念要求？

Answer 1

这只是一个猜测，但错误消息是这样开始的：

在blah..迭代器中与“operator+”不匹配..

当您使用VecS时，您会得到一个向量 - 其迭代器是随机访问的，并且支持operator+

当您使用ListS时，您会得到一个列表 - 其迭代器是双向的，并且不支持支持运营商+