c++ - 在 boost BGL 中使用 make_bfs_visitor 而不是带有 BFS 的派生访问者

Question

我已经(成功地)为我的 BFS 实现了一个自定义访问者:

(另请参阅:Find all reachable vertices in a Boost BGL graph using 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. 这(一个或多个访问者，如 examine_edge、examine_vertex)甚至可以使用 lambda 表达式来实现吗？
3. 是否有任何理由(例如性能损失)使用一个解决方案而不是另一个解决方案？

Answer 1

您需要使用typename 来表明GRAPH 中的vertex_descriptor 是一种类型:

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_pa​​rams 成员的原因。

所以你需要调用

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

在这两个更改之后，您的代码可以正常编译。