Your original question is about how boost bfs is coded internally:
http://www.boost.org/doc/libs/1_58_0/boost/graph/breadth_first_search.hpp
Maybe in boost lists is a better place to ask. But I am going to give you my best guess, based on my experience with boost’s dijkstra algorithm usage, and the knowledge of templates and C++ code:
template <class Vertex, class Graph>
graph::bfs_visitor_event_not_overridden
examine_vertex(Vertex u, Graph& g)
{
invoke_visitors(m_vis, u, g, ::boost::on_examine_vertex());
return graph::bfs_visitor_event_not_overridden();
}
Vertex is the vertex descriptor class (of the Graph type)
Graph is a boost graph type
examine_vertex is called on the algorithm
Vertex u = Q.top(); Q.pop(); vis.examine_vertex(u, g);
receives as parameters, the vertex and the graph
invoke_visitors is defined here:
http://www.boost.org/doc/libs/1_40_0/boost/graph/visitors.hpp
m_vis is the type of visitor
u is the vertex,
::boost::on_examine_vertex() is a functor that holds the code that’s to be executed when the vertex is examined
on the bfs code there is definition:
namespace graph { struct bfs_visitor_event_not_overridden {}; }
So:
return graph::bfs_visitor_event_not_overridden();
What it does its returning that empty struct.
note that the return type of the function is:
graph::bfs_visitor_event_not_overridden
Date: Tue, 25 Aug 2015 12:14:02 +0530
From: rohith.reddy@research.iiit.ac.in
To: pgrouting-dev@lists.osgeo.org
Subject: Re: [pgrouting-dev] Regarding BFS Visitor
Hey Vicky,
Thanks for your reply.I got what you said.As given in the source code,at different points of the algorithm,the different methods of the visitor class are being called.Let us consider one of the methods of bfs_visitor class(as given in the source code) > template <class Vertex, class Graph>
graph::bfs_visitor_event_not_overridden
examine_vertex(Vertex u, Graph& g)
{
invoke_visitors(m_vis, u, g, ::boost::on_examine_vertex());
return graph::bfs_visitor_event_not_overridden();
}
which is being called when a vertex is examined(popped out of the queue) in the algorithm.Please help me with the following questions: What does the function invoke_visitors() actually do? What exactly does the fourth argument of the function invoke_visitors mean? What exactly does the method(namely examine_vertex) return?
Thanks in advance.
----- Original Message -----
From: “Vicky Vergara” vicky_vergara@hotmail.com
To: “pgrouting-dev” pgrouting-dev@lists.osgeo.org
Sent: Tuesday, August 25, 2015 1:07:08 AM
Subject: Re: [pgrouting-dev] Regarding BFS Visitor
You might want to read the visitor concept of the boost libraries
http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/visitor_concepts.html
but the general idea is that an algorithm has several places that can be visited:
hope this pseudo code helps:
foo_algorithm()
1 do_a()
2 do_users_visitors_code_0()
3 if (cond) then
4 do_c()
5 do_users_visitor_code_1()
6 else
7 do_d()
8 do_users_visitor_code_2()
9 endif
Date: Mon, 24 Aug 2015 23:02:14 +0530
From: rohith.reddy@research.iiit.ac.in
To: pgrouting-dev@lists.osgeo.org
Subject: [pgrouting-dev] Regarding BFS Visitor
Hello there,
Recently I started using pgrouting,and was curious to know about how different algorithms were being implemented.While going through the source code of breadth_first_search.hpp(http://www.boost.org/doc/libs/1_58_0/boost/graph/breadth_first_search.hpp),I came across the class named bfs_visitor.In every function of the visitor class I noticed a function named invoke_visitors().I explored about this,but couldnt understand,what this function does and how it was being implemented.Can anyone help me with this?
Thanks in advance.
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev