通过 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.

的好文档

B.t.w。如果我从中删除 using event_filter = event_type; 并将其包装到没有 boost::make_bfs_visitor 的 boost::visitor 中，我的自定义访问者工作正常，这需要这个 typedef.

我也找不到任何关于 event_filter 以及如何在一个访问者身上同时使用多个事件（例如 on_discover_vertex 和 on_examine_edge）的文档。 event_filter 指定访问者将处理哪些事件，我是否理解正确？感谢有关此文档的链接。

Answer 1

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

接下来，如果您使用 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>()
                )
            )
        )
    );
}

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

Using multiple visitors with BGL's BFS algorithm

boost

graph

breadth-first-search

boost-graph

演示