CODEWITHSUNDEEP
boostgraphbreadth-first-searchboost-graph
Kolyunya
Kolyunya

Reputation: 6240

Using multiple visitors with BGL's BFS algorithm

I'm trying to use two visitors with BGL's BFS algorithm:

#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;
}

My custom visitor's listener (discover_vertex) is not invoked for some reason. I believe that the issue is related to how I pass listeners to the breadth_first_search. I was not able to find good docs about boost::visitor and boost::make_bfs_visitor.

B.t.w. my custom visitor works fine if I remove using event_filter = event_type; from it and pass it wrapped into just boost::visitor without boost::make_bfs_visitor which requires this typedef.

I also was not able to find any docs about event_filter and how to use multiple events (e.g. on_discover_vertex and on_examine_edge) simultaneously in one visitor. Do I get it right that event_filter specifies which events the visitor will process? Links to docs about this are appreciated.

Upvotes: 2

Views: 548

Answers (1)

sehe
sehe

Reputation: 393457

Firstly, no need to declare the visitor in the boost namespace. This is a bad idea, don't inject your own stuff into namespaces you don't control.

Next if you use make_bfs_visitor to piece together visitors for specific event_filters, you need to implement operator() not 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;
    }
};

Lastly, the event_type argument was simply wrong, drop the parentheses:

test_visitor<boost::on_discover_vertex>()

DEMO

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>()
                )
            )
        )
    );
}

Upvotes: 2

Related Questions