boost - 通过 BGL 的 BFS 算法使用多个访问者

Question

我是trying使用 BGL 的 BFS 算法的两个访问者:

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/visitors.hpp>

using Graph = boost::adjacency_list<>;
using Vertex = Graph::vertex_descriptor;
using Edge = Graph::edge_descriptor;

namespace boost 
{
    template <typename event_type>
    class test_visitor: public default_bfs_visitor 
    {
        public:
            using event_filter = event_type;
            void discover_vertex(Vertex, const Graph&) const 
            {
                std::cout << "vertex discovered" << std::endl;
            }
    };
}

int main() 
{

    // Initialize a test graph
    Graph graph;
    Vertex vertexFoo = boost::add_vertex(graph);
    Vertex vertexBar = boost::add_vertex(graph);
    Vertex vertexBaz = boost::add_vertex(graph);
    boost::add_edge(vertexFoo, vertexBar, graph);
    boost::add_edge(vertexBar, vertexBaz, graph);

    // Initialize parents map
    std::vector<Vertex> parents_map(boost::num_vertices(graph));
    parents_map[vertexFoo] = vertexFoo;

    // Perform BFS with two listeners
    boost::breadth_first_search(
        graph,
        vertexFoo,
        boost::visitor(
            boost::make_bfs_visitor(
                std::make_pair(
                    boost::record_predecessors(&parents_map[0], boost::on_tree_edge()),
                    boost::test_visitor<boost::on_discover_vertex()>()
                )
            )
        )
    );

    return 0;
}

由于某种原因，我的自定义访问者监听器 (discover_vertex) 未被调用。我相信这个问题与我如何将监听器传递给 breadth_first_search 有关。我无法找到有关 boost::visitor 和 boost::make_bfs_visitor 的好文档。

顺便说一句。如果我从中删除 using event_filter = event_type; 并将其包装到 boost::visitor 中而不使用 boost::make_bfs_visitor，我的自定义访问者就可以正常工作> 需要这个 typedef。

我也无法找到任何有关 event_filter 以及如何在一个事件中同时使用多个事件(例如 on_discover_vertex 和 on_examine_edge)的文档游客。 event_filter 指定访问者将处理哪些事件，我的理解正确吗？感谢有关此内容的文档链接。

Answer 1

首先，不需要在 boost 命名空间中声明访问者。这是一个坏主意，不要将您自己的东西注入(inject)到您无法控制的命名空间中。

接下来，如果您使用 make_bfs_visitor 来拼凑特定 event_filter 的访问者，则需要实现 operator() 而不是 discover_vertex :

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

    void operator()(Vertex, Graph const&) const {
        std::cout << __PRETTY_FUNCTION__ << std::endl;
    }
};

最后，event_type 参数完全错误，请删除括号:

test_visitor<boost::on_discover_vertex>()

演示

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/visitors.hpp>
#include <iostream>

using Graph  = boost::adjacency_list<>;
using Vertex = Graph::vertex_descriptor;
using Edge   = Graph::edge_descriptor;

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

    void operator()(Vertex, Graph const&) const {
        std::cout << __PRETTY_FUNCTION__ << std::endl;
    }
};

int main() {
    // Initialize a test graph
    enum { Foo, Bar, Baz, NUMVERTICES };
    Graph graph(NUMVERTICES);
    boost::add_edge(Foo, Bar, graph);
    boost::add_edge(Bar, Baz, graph);

    // Initialize parents map
    std::vector<Vertex> parents_map(boost::num_vertices(graph));
    parents_map[Foo] = Foo;

    // Perform BFS with two listeners
    boost::breadth_first_search(graph, Foo,
        boost::visitor(
            boost::make_bfs_visitor(
                std::make_pair(
                    boost::record_predecessors(&parents_map[0], boost::on_tree_edge()),
                    test_visitor<boost::on_discover_vertex>()
                )
            )
        )
    );
}