BGL DF z zestawem źródeł węzłów

Question

problem

Mając wykres lista sąsiedztwa, ja jak przechodzenie jej algorytmu DF z określonym zbiorem węzłów źródłowych. Głównym problemem jest to, że mapa kolorów jest przekazywana według wartości.

Próbowałem

Do hermetyzacji mapę kolorów poprzez odniesienie do struktury:

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]; 
    } 
} 

I wreszcie Kodeksu 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); 
    } 
    } 

błąd Kompilacja

/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’ 

definicja Graph

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

Co działa

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

działa bez żadnych błędów kompilacji ...

Answer 1

Trzeba umieścić swoje get() i put() funkcje w przestrzeni nazw gdzie ref_color_map rezyduje, ponieważ można je znaleźć przez ADL. Zobacz here.