Question

Я учусь использовать библиотеку Boost-graph для университетского проекта. У меня есть график, где мне нужно добавлять и удалять вершины, поэтому я объявил свой список смежности со списком в качестве списка вершин. У меня большая проблема с вызовом функции deep_first_search (): из-за listS мне нужно предоставить карту свойств Indexes, но я не понимаю, как мне нужно действовать. Вот код:

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/depth_first_search.hpp>

struct VertexProperties {
    int value;
};


typedef boost::adjacency_list<boost::vecS,            // OutEdgeList
                              boost::listS,            // VertexList
                              boost::bidirectionalS,  // Directed
                              VertexProperties     // VertexProperties
                              >
MyGraph; 

typedef boost::graph_traits<MyGraph>::vertex_descriptor MyVertex;
typedef boost::graph_traits<MyGraph>::edge_descriptor MyEdge;

class dfs_visitor : public boost::default_dfs_visitor {
    public:
        dfs_visitor();
        dfs_visitor(const dfs_visitor& other);
        void initialize_vertex(MyVertex s, MyGraph g);
        void start_vertex(MyVertex s, MyGraph g);
        void discover_vertex(MyVertex s, MyGraph g);
        void finish_vertex(MyVertex s, MyGraph g);
        void examine_edge(MyEdge e, MyGraph g);
        void tree_edge(MyEdge e, MyGraph g);
        void back_edge(MyEdge e, MyGraph g);
        void forward_or_cross_edge(MyEdge e, MyGraph g);
        void finish_edge(MyEdge e, MyGraph g);
};

dfs_visitor::dfs_visitor() {}
dfs_visitor::dfs_visitor(const dfs_visitor& other) {}
void dfs_visitor::initialize_vertex(MyVertex s, MyGraph g){
    std::cout << "Initialize: " << g[s].value << std::endl;
}
void dfs_visitor::start_vertex(MyVertex s, MyGraph g) {
    std::cout << "Start: " << g[s].value << std::endl;   
}
void dfs_visitor::discover_vertex(MyVertex s, MyGraph g) {
    std::cout << "Discover: " << g[s].value << std::endl;   
}
void dfs_visitor::finish_vertex(MyVertex s, MyGraph g) {
    std::cout << "Finished: " << g[s].value << std::endl;   
}
void dfs_visitor::examine_edge(MyEdge e, MyGraph g) {}
void dfs_visitor::tree_edge(MyEdge e, MyGraph g) {}
void dfs_visitor::back_edge(MyEdge e, MyGraph g) {}
void dfs_visitor::forward_or_cross_edge(MyEdge e, MyGraph g) {}
void dfs_visitor::finish_edge(MyEdge e, MyGraph g) {}




int main(){
    MyGraph g{};


    for(int i = 0; i < 10; i++) {
        MyVertex v = boost::add_vertex(g); 
        g[v].value = i;
    }
    MyGraph::vertex_iterator v, v_end;

    std::tie(v, v_end) = boost::vertices(g);
    auto u = v;
    u++;
    while(v != v_end && u != v_end) {
        boost::add_edge(*u, *v, g);
        u++;
        v++;
    }
    /* INDEX MAP CREATION*/
    typedef std::map<MyVertex, size_t> MyIndexMap;
    MyIndexMap i_map;
    auto ipmap = boost::make_assoc_property_map(i_map);
    std::tie(v, v_end) = boost::vertices(g);
    while(v != v_end) {
        i_map[*v] = i_map.size();
        v++; 
    }

    /* COLOR MAP CREATION */
    typedef std::map<size_t, boost::default_color_type> ColorMap;
    ColorMap c_map;
    auto cpmap = boost::make_assoc_property_map(c_map);
    std::tie(v, v_end) = boost::vertices(g);

    while(v != v_end) {
        c_map[ipmap[*v]] = boost::color_traits<boost::default_color_type>::white();
        v++; 
    }

    dfs_visitor vis{};
    boost::depth_first_search(g, 
                              boost::visitor(vis)), 
                              boost::color_map(cpmap);
                              boost::vertex_index_map(ipmap);
}

Когда я собираюсь скомпилировать это, это вывод:

In file included from /usr/include/boost/graph/adjacency_list.hpp:223,
                 from test.cpp:2:
/usr/include/boost/graph/detail/adjacency_list.hpp: In instantiation of ‘struct boost::adj_list_any_vertex_pa::bind_<boost::vertex_index_t, boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>, VertexProperties>’:
/usr/include/boost/graph/detail/adjacency_list.hpp:2618:12:   required from ‘struct boost::detail::adj_list_choose_vertex_pa<boost::vertex_index_t, boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>, VertexProperties>’
/usr/include/boost/graph/detail/adjacency_list.hpp:2755:12:   required from ‘struct boost::adj_list_vertex_property_selector::bind_<boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>, VertexProperties, boost::vertex_index_t>’
/usr/include/boost/graph/properties.hpp:201:12:   required from ‘struct boost::detail::vertex_property_map<boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>, boost::vertex_index_t>’
/usr/include/boost/graph/properties.hpp:212:10:   required from ‘struct boost::property_map<boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>, boost::vertex_index_t, void>’
/usr/include/boost/graph/named_function_params.hpp:416:69:   [ skipping 2 instantiation contexts, use -ftemplate-backtrace-limit=0 to disable ]
/usr/include/boost/graph/named_function_params.hpp:605:41:   required from ‘struct boost::detail::map_maker<boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>, boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const dfs_visitor>, boost::parameter::aux::empty_arg_list>, boost::graph::keywords::tag::color_map, boost::default_color_type>’
/usr/include/boost/graph/named_function_params.hpp:621:7:   required by substitution of ‘template<class Graph, class ArgPack> typename boost::detail::map_maker<Graph, ArgPack, boost::graph::keywords::tag::color_map, boost::default_color_type>::map_type boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::color_map, boost::default_color_type>::operator()<Graph, ArgPack>(const Graph&, const ArgPack&) const [with Graph = boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const dfs_visitor>, boost::parameter::aux::empty_arg_list>]’
/usr/include/boost/graph/depth_first_search.hpp:337:80:   required from ‘void boost::graph::detail::depth_first_search_impl<Graph>::operator()(const Graph&, const ArgPack&) const [with ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const dfs_visitor>, boost::parameter::aux::empty_arg_list>; Graph = boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>]’
/usr/include/boost/graph/depth_first_search.hpp:342:5:   required from ‘typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type boost::graph::depth_first_search_with_named_params(const Param0&, const ArgPack&) [with Param0 = boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const dfs_visitor>, boost::parameter::aux::empty_arg_list>; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type = void]’
/usr/include/boost/graph/depth_first_search.hpp:345:3:   required from ‘typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type boost::depth_first_search(const Param0&, const boost::bgl_named_params<T, Tag, Base>&) [with Param0 = boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>; P = dfs_visitor; T = boost::graph_visitor_t; R = boost::no_property; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type = void]’
test.cpp:100:50:   required from here
/usr/include/boost/graph/detail/adjacency_list.hpp:2548:29: error: forming reference to void
 2548 |         typedef value_type& reference;
      |                             ^~~~~~~~~
/usr/include/boost/graph/detail/adjacency_list.hpp:2549:35: error: forming reference to void
 2549 |         typedef const value_type& const_reference;
      |                                   ^~~~~~~~~~~~~~~
/usr/include/boost/graph/detail/adjacency_list.hpp:2552:47: error: forming reference to void
 2552 |           <Graph, value_type, reference, Tag> type;
      |                                               ^~~~
/usr/include/boost/graph/detail/adjacency_list.hpp:2554:53: error: forming reference to void
 2554 |           <Graph, value_type, const_reference, Tag> const_type;
      |                                                     ^~~~~~~~~~
In file included from /usr/include/boost/graph/graph_utility.hpp:24,
                 from test.cpp:3:
/usr/include/boost/graph/depth_first_search.hpp: In instantiation of ‘void boost::graph::detail::depth_first_search_impl<Graph>::operator()(const Graph&, const ArgPack&) const [with ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const dfs_visitor>, boost::parameter::aux::empty_arg_list>; Graph = boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>]’:
/usr/include/boost/graph/depth_first_search.hpp:342:5:   required from ‘typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type boost::graph::depth_first_search_with_named_params(const Param0&, const ArgPack&) [with Param0 = boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>; ArgPack = boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const dfs_visitor>, boost::parameter::aux::empty_arg_list>; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const ArgPack&)>::type = void]’
/usr/include/boost/graph/depth_first_search.hpp:345:3:   required from ‘typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type boost::depth_first_search(const Param0&, const boost::bgl_named_params<T, Tag, Base>&) [with Param0 = boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>; P = dfs_visitor; T = boost::graph_visitor_t; R = boost::no_property; typename boost::result_of<boost::graph::detail::depth_first_search_impl<Param0>(Param0, const typename boost::detail::convert_bgl_params_to_boost_parameter<boost::bgl_named_params<T, Tag, Base> >::type&)>::type = void]’
test.cpp:100:50:   required from here
/usr/include/boost/graph/depth_first_search.hpp:337:80: error: no match for call to ‘(const boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::color_map, boost::default_color_type>) (const boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, VertexProperties>&, const boost::parameter::aux::arg_list<boost::parameter::aux::tagged_argument<boost::graph::keywords::tag::visitor, const dfs_visitor>, boost::parameter::aux::empty_arg_list>&)’
  337 |                       boost::detail::make_color_map_from_arg_pack(g, arg_pack),
      |                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

In file included from /usr/include/boost/graph/depth_first_search.hpp:21,
                 from /usr/include/boost/graph/graph_utility.hpp:24,
                 from test.cpp:3:
/usr/include/boost/graph/named_function_params.hpp:621:7: note: candidate: ‘template<class Graph, class ArgPack> typename boost::detail::map_maker<Graph, ArgPack, MapTag, ValueType>::map_type boost::detail::make_property_map_from_arg_pack_gen<MapTag, ValueType>::operator()(const Graph&, const ArgPack&) const [with Graph = Graph; ArgPack = ArgPack; MapTag = boost::graph::keywords::tag::color_map; ValueType = boost::default_color_type]’
  621 |       operator()(const Graph& g, const ArgPack& ap) const {
      |       ^~~~~~~~
/usr/include/boost/graph/named_function_params.hpp:621:7: note:   substitution of deduced template arguments resulted in errors seen above

Я думаю, что это своего рода ошибка шаблона. Может кто-нибудь объяснить мне, где ошибка?

sehe · Answer 1 · 06 января 2020

Названные параметры указаны неправильно. Они используют Свободный синтаксис :

boost::depth_first_search(g,
         boost::visitor(vis)
        .vertex_index_map(ipmap)
        .color_map(cpmap));

Теперь вы можете значительно упростить остальную часть кода.

классы, где все публикуется c, может быть struct
упражнение Правило нуля когда это возможно
член посетителя может быть помечен const
взять график по константной ссылке на избегайте копирования графика для КАЖДОГО события
используйте псевдонимы типа c ++ (using) вместо устаревших typedef
добавьте VertexProperties с add_vertex сразу
предпочесть диапазоны парам итераторов (например, boost::make_iterator_range)
нет необходимости инициализировать значения default_color_type, std::vector или std::map уже сделали бы это

Все сразу : Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>

struct VertexProperties {
    int value;
};

using MyGraph = boost::adjacency_list<boost::vecS,           // OutEdgeList
        boost::listS,          // VertexList
        boost::bidirectionalS, // Directed
        VertexProperties       // VertexProperties
        >;

using MyVertex = boost::graph_traits<MyGraph>::vertex_descriptor;
using MyEdge = boost::graph_traits<MyGraph>::edge_descriptor;

struct dfs_visitor : boost::default_dfs_visitor {
    void initialize_vertex(MyVertex   s, MyGraph const& g) const { std::cout << "Initialize: " << g[s].value << std::endl; }
    void start_vertex(MyVertex        s, MyGraph const& g) const { std::cout << "Start:      " << g[s].value << std::endl; }
    void discover_vertex(MyVertex     s, MyGraph const& g) const { std::cout << "Discover:   " << g[s].value << std::endl; }
    void finish_vertex(MyVertex       s, MyGraph const& g) const { std::cout << "Finished:   " << g[s].value << std::endl; }
};

int main() {
    MyGraph g{};

    for (int i = 0; i < 10; i++) {
        add_vertex(VertexProperties{i}, g);
    }

    {
        boost::optional<MyVertex> prev;

        for (auto v : boost::make_iterator_range(vertices(g))) {
            if (prev)
                add_edge(v, *prev, g);
            prev = v;
        }
    }

    /* INDEX MAP CREATION*/
    std::map<MyVertex, size_t> i_map;
    for (auto v : boost::make_iterator_range(vertices(g))) {
        i_map.emplace(v, i_map.size());
    }

    auto ipmap = boost::make_assoc_property_map(i_map);

    /* COLOR MAP CREATION */
    std::vector<boost::default_color_type> c_map(num_vertices(g));
    auto cpmap = boost::make_iterator_property_map(c_map.begin(), ipmap);

    dfs_visitor vis{};
    boost::depth_first_search(g,
             boost::visitor(vis)
            .vertex_index_map(ipmap)
            .color_map(cpmap));
}

Печать

Initialize: 0
Initialize: 1
Initialize: 2
Initialize: 3
Initialize: 4
Initialize: 5
Initialize: 6
Initialize: 7
Initialize: 8
Initialize: 9
Start:      0
Discover:   0
Finished:   0
Start:      1
Discover:   1
Finished:   1
Start:      2
Discover:   2
Finished:   2
Start:      3
Discover:   3
Finished:   3
Start:      4
Discover:   4
Finished:   4
Start:      5
Discover:   5
Finished:   5
Start:      6
Discover:   6
Finished:   6
Start:      7
Discover:   7
Finished:   7
Start:      8
Discover:   8
Finished:   8
Start:      9
Discover:   9
Finished:   9

Boost-graph: как я могу вызвать глубину-первый-поиск (), когда мой график использует listS как VertexList?

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

1 Ответ

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Boost-graph: как я могу вызвать глубину-первый-поиск (), когда мой график использует listS как VertexList?

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

1 Ответ

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Похожие темы