बीजीएल DFS नोड

Question

समस्या

एक निकटता सूची ग्राफ के बाद, मैं स्रोत नोड्स का एक विशिष्ट सेट से एक डीएफएस एल्गोरिथ्म के साथ इसे पार करने के लिए करना चाहते हैं। मुख्य समस्या यह है कि रंग का नक्शा मूल्य से गुजरता है।

मैं

की कोशिश की एक संरचना में संदर्भ द्वारा रंग नक्शा संपुटित करने के लिए:

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

और अंत में डीएफएस के कोड:

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 देखें।