Shortest path problem: distance between two vertices
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!
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
participants (2)
-
Gábor Szuromi
-
Pedram Pedarsani