Использование make_bfs_visitor вместо производного посетителя с BFS в boost BGL - PullRequest
Новая
       25

Использование make_bfs_visitor вместо производного посетителя с BFS в boost BGL

0 голосов
/ 22 декабря 2018

Я (успешно) реализовал пользовательский посетитель для моей BFS:

(См. Также: Найдите все достижимые вершины в графике Boost BGL, используя BFS ) 

...
...
ListVisitor vis;
boost::breadth_first_visit(mListGraph, start, Q, vis, colormap);

Посетитель определен в моем заголовочном файле: 

class ListVisitor : public boost::default_bfs_visitor
{
public:
    template <typename Vertex, typename Graph>
    void discover_vertex(Vertex u, const Graph& /*g*/) const
    {
        std::cout << u << std::endl;
    }
};

Это работает, как и ожидалось ... так что все может быть хорошо.: -)

Однако я хотел изменить свой код на использование make_bfs_visitor вместо
и изменил свой код следующим образом: 

boost::breadth_first_visit(mListGraph, start, Q,
    boost::visitor(
        boost::make_bfs_visitor(
                ListVisitor<boost::on_discover_vertex>()
        )
    ), colormap);

и в .h: 

template <typename event_type>
struct ListVisitor : public boost::default_bfs_visitor
{
    using event_filter = event_type;

    template<typename GRAPH>
    void operator()(GRAPH::vertex_descriptor vert, const GRAPH& graph) const
    {
        std::cout << u << std::endl;
    }
};

К сожалению, это приводит к ошибке: 

Error   C2061   syntax error: identifier 'vertex_descriptor'

Я также пытался использовать реальный тип вместо шаблонных типов: 

void operator()(ListGraph_t::vertex_descriptor vert, const ListGraph_t& graph) const

, но это только изменяет ошибку: 

Error   C2039   'discover_vertex': is not a member of ...  
Error   C2039   'examine_vertex': is not a member of ...  
Error   C2039   'examine_edge': is not a member of ...  
and so on..........

Мой вопрос:

  1. Можно ли использовать make_bfs_visitor с алгоритмом breadth_first_visit?Все примеры, которые я нашел, реализованы с помощью breadth_first_search!
  2. Может ли это (один или несколько посетителей, например exam_edge, exam_vertex) быть реализовано даже с использованием лямбда-выражений?
  3. Существуют ли какие-либо причины (например, снижение производительности) использовать одно решение за другим?

1 Ответ

0 голосов
/ 22 декабря 2018

Вам нужно использовать typename, чтобы указать, что vertex_descriptor из GRAPH является типом: 

template<typename GRAPH>
void operator()(typename GRAPH::vertex_descriptor vert, const GRAPH& graph) const
                ^^^^^^^^
{
    std::cout << u << std::endl;
}

У Boost есть хорошая библиотека type_index.hpp, я использовал ее для печати двух типов:

auto v = boost::make_bfs_visitor(ListVisitor<boost::on_discover_vertex>());
cout << boost::typeindex::type_id_with_cvr<decltype(v)>().pretty_name() << endl;

в качестве вывода у нас есть 

boost::bfs_visitor<ListVisitor<boost::on_discover_vertex> >

bfs_visitor имеет методы как discover_vertex, examine_vertex и т. Д.

Теперь мы печатаемтип вашего посетителя: 

auto v2 = 
boost::visitor(boost::make_bfs_visitor(ListVisitor<boost::on_discover_vertex>()));
       ^^^            ^^^
cout << boost::typeindex::type_id_with_cvr<decltype(v2)>().pretty_name() << endl;

в качестве вывода 

boost::bgl_named_params<boost::bfs_visitor<ListVisitor<boost::on_discover_vertex> >,
              boost::graph_visitor_t, boost::no_property>

, и поэтому компилятор жалуется, что X не является членом bgl_named_params.

Так что вам нужно позвонить 

boost::breadth_first_visit(myGraph, 0, Q,
   boost::make_bfs_visitor(ListVisitor<boost::on_discover_vertex>()), colormap);

После этих двух изменений ваш код скомпилируется нормально.

...