Using make_bfs_visitor instead of derived visitor with BFS in boost BGL

Question

I've (successfully) implemented a custom visitor for my BFS:

(See also: Find all reachable vertices in a Boost BGL graph using BFS)

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

Visitor defined in my header file:

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

This works as expected... so everything could be fine. :-)

However I wanted to change my code to use make_bfs_visitor instead
and changed my code like this:

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

and in the .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;
    }
};

Unfortunately this produces an error:

Error   C2061   syntax error: identifier 'vertex_descriptor'

I also tried to use the real type instead of templated types:

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

but it only changes the error:

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

My question:

1. Is it possible to use make_bfs_visitor with breadth_first_visit algorithm? All examples I've found are implemented with breadth_first_search!
2. Could this (one or more visitors like examine_edge, examine_vertex) even be implemented using lambda expressions?
3. Are there any reasons (e.g. performance penalty) using one over the other solution?

Answer 1

You need to use typename to indicate that vertex_descriptor from GRAPH is a type:

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

Boost has a nice library type_index.hpp, I used it to print two types:

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

as output we have

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

bfs_visitor has methods as discover_vertex, examine_vertex, and so on.

Now we print the type of your visitor:

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;

as output

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

and that is why the compiler complains that X is not a member of bgl_named_params.

So you need to call

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

After these two changes your code compiles fine.