[pgrouting-dev] Regarding BFS Visitor

[Vicky Vergara]

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 at research.iiit.ac.in
> To: pgrouting-dev at 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 at hotmail.com>
> To: "pgrouting-dev" <pgrouting-dev at 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 at research.iiit.ac.in 
> > To: pgrouting-dev at 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 at lists.osgeo.org 
> > http://lists.osgeo.org/mailman/listinfo/pgrouting-dev 
> 
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

 		 	   		  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20150825/a046d32c/attachment.html>