Re: [Boost-users] Shortest path problem: distance between two vertices

Subject: Re: [Boost-users] Shortest path problem: distance between two vertices
From: Gábor Szuromi (kukkerman_at_[hidden])
Date: 2009-11-18 11:13:43

> I am kind of new to C++ and also boost library, trying to use the bfs to
> find the distance between two vertices in a graph. As I read from previous
> posts, the easiest way would be to throw an exception once the target vertex
> has been discovered. Now the problem is that I can't figure out how to do
> this, and this is pretty urgent! Can you help me with a few lines of code
> which make the bfs_visitor and call the bfs function for this purpose?
> Thanks a lot!
>

Hi!

The visitor can be the following:

template<class Graph>
struct stop_visitor {
   // When to call operator()
   typedef on_discover_vertex             event_filter;

   // The vertex the algorithm should stop at
   typename Graph::vertex_descriptor      stop_v;

   // The visitor have to be copy constructible
   stop_visitor() { }
   stop_visitor(typename Graph::vertex_descriptor stop_v) : stop_v(stop_v) {
}

   void operator()(const typename Graph::vertex_descriptor& v, const Graph&
gr) const {
      if(v == stop_v)
         // Just throw an int when the vertex is discovered. Ugly but works
         throw 0;
   }
};

Then call breadth first search:

try {
   breadth_first_search(gr, 0,
      visitor( make_bfs_visitor(stop_visitor<graph_type>(2)) )
   );
} catch(int x) {
   cout << "Found vertex!";
}

Cheers,
   Gabe