c++ - 来自一组源节点的 BGL dfs

Question

问题

有一个邻接表图，我想用 DFS 算法从一组特定的源节点遍历它。主要问题是颜色图是按值传递的。

我试过了

通过引用将颜色映射封装到一个结构中:

class ref_color_map_wrapper
{
public:
  typedef boost::default_color_type color_type;
  typedef std::vector<color_type> color_map_type;
private:
  color_map_type &color_map;
public:
  ref_color_map_wrapper(color_map_type& color_map)
  : color_map(color_map)
  {}

  color_type& operator[](size_t i)
  {
    return color_map[i];
  }
  const color_type& operator[](size_t i) const
  {
    return color_map[i];
  }
};

namespace boost
{
  template <>
  struct property_traits<ref_color_map_wrapper>
  {
    typedef boost::read_write_property_map_tag category;
    typedef boost::default_color_type value_type;
    typedef boost::default_color_type& reference;
    typedef size_t key_type;
  };

  void put(ref_color_map_wrapper& color_map, vertex_descriptor& v, boost::default_color_type color)
  {
    color_map[v] = color;
  }

  boost::default_color_type get(ref_color_map_wrapper& color_map, vertex_descriptor& v)
  {
    return color_map[v];
  }

  void put(ref_color_map_wrapper& color_map, const vertex_descriptor& v, boost::default_color_type color)
  {
    color_map[v] = color;
  }

  boost::default_color_type get(const ref_color_map_wrapper& color_map, const vertex_descriptor& v)
  {
    return color_map[v];
  }
}

最后是 DFS 的代码:

  typedef std::vector<boost::default_color_type> color_map_type;
  color_map_type color_map(boost::num_vertices(graph), boost::white_color);

  ref_color_map_wrapper ref_color_map(color_map);
  for(auto it = root_set.begin(); it != root_set.end(); ++it)
  {
    size_t i = boost::get(boost::vertex_index_t(), graph, *it);
    if(color_map[i] == boost::white_color)
    {
      boost::depth_first_visit(graph, *it, boost::default_dfs_visitor(), ref_color_map);
    }
  }

编译错误

/usr/local/include/boost/property_map/property_map.hpp: In instantiation of ‘void boost::ReadablePropertyMapConcept<PMap, Key>::constraints() [with PMap = gc::ref_color_map_wrapper; Key = long unsigned int]’:
/usr/local/include/boost/concept/detail/has_constraints.hpp:32:14:   required by substitution of ‘template<class Model> boost::concepts::detail::yes boost::concepts::detail::has_constraints_(Model*, boost::concepts::detail::wrap_constraints<Model, (& Model:: constraints)>*) [with Model = boost::ReadablePropertyMapConcept<gc::ref_color_map_wrapper, long unsigned int>]’
/usr/local/include/boost/concept/detail/has_constraints.hpp:42:5:   required from ‘const bool boost::concepts::not_satisfied<boost::ReadablePropertyMapConcept<gc::ref_color_map_wrapper, long unsigned int> >::value’
/usr/local/include/boost/concept/detail/has_constraints.hpp:45:31:   required from ‘struct boost::concepts::not_satisfied<boost::ReadablePropertyMapConcept<gc::ref_color_map_wrapper, long unsigned int> >’
/usr/local/include/boost/mpl/if.hpp:67:11:   required from ‘struct boost::mpl::if_<boost::concepts::not_satisfied<boost::ReadablePropertyMapConcept<gc::ref_color_map_wrapper, long unsigned int> >, boost::concepts::constraint<boost::ReadablePropertyMapConcept<gc::ref_color_map_wrapper, long unsigned int> >, boost::concepts::requirement<boost::concepts::failed************ boost::ReadablePropertyMapConcept<gc::ref_color_map_wrapper, long unsigned int>::************> >’
/usr/local/include/boost/concept/detail/general.hpp:50:8:   required from ‘struct boost::concepts::requirement_<void (*)(boost::ReadablePropertyMapConcept<gc::ref_color_map_wrapper, long unsigned int>)>’
/usr/local/include/boost/concept_check.hpp:45:1:   [ skipping 4 instantiation contexts ]
/usr/local/include/boost/concept/detail/has_constraints.hpp:45:31:   required from ‘struct boost::concepts::not_satisfied<boost::ReadWritePropertyMapConcept<gc::ref_color_map_wrapper, long unsigned int> >’
/usr/local/include/boost/mpl/if.hpp:67:11:   required from ‘struct boost::mpl::if_<boost::concepts::not_satisfied<boost::ReadWritePropertyMapConcept<gc::ref_color_map_wrapper, long unsigned int> >, boost::concepts::constraint<boost::ReadWritePropertyMapConcept<gc::ref_color_map_wrapper, long unsigned int> >, boost::concepts::requirement<boost::concepts::failed************ boost::ReadWritePropertyMapConcept<gc::ref_color_map_wrapper, long unsigned int>::************> >’
/usr/local/include/boost/concept/detail/general.hpp:50:8:   required from ‘struct boost::concepts::requirement_<void (*)(boost::ReadWritePropertyMapConcept<gc::ref_color_map_wrapper, long unsigned int>)>’
/usr/local/include/boost/graph/depth_first_search.hpp:88:1:   required from ‘void boost::detail::depth_first_visit_impl(const IncidenceGraph&, typename boost::graph_traits<Graph>::vertex_descriptor, DFSVisitor&, ColorMap, TerminatorFunc) [with IncidenceGraph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, boost::variant<const void*, std::pair<void*, void*> > >; DFSVisitor = boost::dfs_visitor<>; ColorMap = gc::ref_color_map_wrapper; TerminatorFunc = boost::detail::nontruth2; typename boost::graph_traits<Graph>::vertex_descriptor = long unsigned int]’
/usr/local/include/boost/graph/depth_first_search.hpp:314:5:   required from ‘void boost::depth_first_visit(const IncidenceGraph&, typename boost::graph_traits<Graph>::vertex_descriptor, DFSVisitor, ColorMap) [with IncidenceGraph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, boost::variant<const void*, std::pair<void*, void*> > >; DFSVisitor = boost::dfs_visitor<>; ColorMap = gc::ref_color_map_wrapper; typename boost::graph_traits<Graph>::vertex_descriptor = long unsigned int]’
../include/garbage_collector.hpp:169:87:   required from here
/usr/local/include/boost/property_map/property_map.hpp:200:7: error: no matching function for call to ‘get(gc::ref_color_map_wrapper&, long unsigned int&)’
/usr/local/include/boost/property_map/property_map.hpp:200:7: note: candidates are:
In file included from /usr/local/include/boost/tuple/tuple.hpp:33:0,
                 from /usr/local/include/boost/unordered/detail/allocate.hpp:27,
                 from /usr/local/include/boost/unordered/detail/buckets.hpp:15,
                 from /usr/local/include/boost/unordered/detail/table.hpp:10,
                 from /usr/local/include/boost/unordered/detail/equivalent.hpp:14,
                 from /usr/local/include/boost/unordered/unordered_set.hpp:17,
                 from /usr/local/include/boost/unordered_set.hpp:16,
                 from /usr/local/include/boost/graph/adjacency_list.hpp:21,
                 from ../include/garbage_collector.hpp:6,
                 from main.cpp:3:
/usr/local/include/boost/tuple/detail/tuple_basic.hpp:225:1: note: template<int N, class HT, class TT> typename boost::tuples::access_traits<typename boost::tuples::element<N, boost::tuples::cons<HT, TT> >::type>::const_type boost::tuples::get(const boost::tuples::cons<HT, TT>&)
/usr/local/include/boost/tuple/detail/tuple_basic.hpp:225:1: note:   template argument deduction/substitution failed:
In file included from /usr/local/include/boost/graph/adjacency_list.hpp:36:0,
                 from ../include/garbage_collector.hpp:6,
                 from main.cpp:3:
/usr/local/include/boost/property_map/property_map.hpp:200:7: note:   ‘gc::ref_color_map_wrapper’ is not derived from ‘const boost::tuples::cons<HT, TT>’
In file included from /usr/local/include/boost/tuple/tuple.hpp:33:0,
                 from /usr/local/include/boost/unordered/detail/allocate.hpp:27,
                 from /usr/local/include/boost/unordered/detail/buckets.hpp:15,
                 from /usr/local/include/boost/unordered/detail/table.hpp:10,
                 from /usr/local/include/boost/unordered/detail/equivalent.hpp:14,
                 from /usr/local/include/boost/unordered/unordered_set.hpp:17,
                 from /usr/local/include/boost/unordered_set.hpp:16,
                 from /usr/local/include/boost/graph/adjacency_list.hpp:21,
                 from ../include/garbage_collector.hpp:6,
                 from main.cpp:3:
/usr/local/include/boost/tuple/detail/tuple_basic.hpp:211:1: note: template<int N, class HT, class TT> typename boost::tuples::access_traits<typename boost::tuples::element<N, boost::tuples::cons<HT, TT> >::type>::non_const_type boost::tuples::get(boost::tuples::cons<HT, TT>&)
/usr/local/include/boost/tuple/detail/tuple_basic.hpp:211:1: note:   template argument deduction/substitution failed:
In file included from /usr/local/include/boost/graph/adjacency_list.hpp:36:0,
                 from ../include/garbage_collector.hpp:6,
                 from main.cpp:3:
/usr/local/include/boost/property_map/property_map.hpp:200:7: note:   ‘gc::ref_color_map_wrapper’ is not derived from ‘boost::tuples::cons<HT, TT>’
/usr/local/include/boost/property_map/property_map.hpp:179:19: note: template<class T> const T& get(const T*, std::ptrdiff_t)
/usr/local/include/boost/property_map/property_map.hpp:179:19: note:   template argument deduction/substitution failed:
/usr/local/include/boost/property_map/property_map.hpp:200:7: note:   mismatched types ‘const T*’ and ‘gc::ref_color_map_wrapper’

图定义

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, vertex_info_type> graph_type;

什么在起作用

boost::get(ref_color_map, *it);
boost::put(ref_color_map, *it, boost::white_color);

没有任何编译错误……

Answer 1

您需要将 get() 和 put() 函数放在 ref_color_map 所在的命名空间中，因为它们是通过 ADL 找到的.参见 here。