Yes, it seems to be right. Is the Daniel´s idea, when the desired vertex is permanently labeled (marked black) (you check it with the examine_vertex visitor ), you throw an exception. Sens a little crude to me, but is quite straight forward to implement. i don't know the performance overhead it will cause to call the visitor for every labeled vertex... On 3/14/06, Marcio Paim <marcio.paim@gmail.com> wrote:
Hello,
I had the same problem, after gathering some information over the net I got this modified version of dijkstra-example.cpp
#include <boost/config.hpp> #include <iostream>
#include <boost/graph/graph_traits.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp>
using namespace boost;
// define visitor for discover_vertex event
template <class Vertex, class Tag> struct target_visitor : public default_dijkstra_visitor { target_visitor(Vertex u) : v(u) { }
template <class Graph> void examine_vertex(Vertex u, Graph& g) { if( u == v ) { throw(-1); } } private: Vertex v; };
template <class Vertex, class Tag> target_visitor<Vertex, Tag> target_visit(Vertex u, Tag) { return target_visitor<Vertex, Tag>(u); }
int main(int argc, char** argv) { typedef adjacency_list < listS, vecS, directedS, no_property, property < edge_weight_t, int > > graph_t; typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor; typedef graph_traits < graph_t >::edge_descriptor edge_descriptor; typedef std::pair<int, int> Edge;
const int num_nodes = 5; enum nodes { A, B, C, D, E }; char name[] = "ABCDE"; Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E), Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B) }; int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 }; int num_arcs = sizeof(edge_array) / sizeof(Edge);
graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes); property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);
std::vector<vertex_descriptor> p(num_vertices(g)); std::vector<int> d(num_vertices(g));
// choose source and target vertex_descriptor src = vertex(A, g); vertex_descriptor targ = vertex(C, g);
try { dijkstra_shortest_paths(g, src,
predecessor_map(&p[0]).distance_map(&d[0]).visitor(target_visit(targ, on_examine_vertex()))); } catch( ... ) { }
std::cout << "distances and parents:" << std::endl; graph_traits < graph_t >::vertex_iterator vi, vend; for (tie(vi, vend) = vertices(g); vi != vend; ++vi) { std::cout << "distance(" << name[*vi] << ") = " << d[*vi] << ", "; std::cout << "parent(" << name[*vi] << ") = " << name[p[*vi]] << std::endl; }
system("PAUSE"); return EXIT_SUCCESS; } I compiled it with Dev-C++. I do not understand it in fully detail but I hopefully expect it to be right. Is it right?
m.p.a.
Is there an easy/already implemented way to stop the computation of the dijkstra_shortest_path algorithm when some target vertex is marked as black??
The recommended method is to use a visitor that throws an exception when
On 3/14/06, Daniel Mitchell <danmitchell@mail.utexas.edu> wrote: the
target is colored black.
Daniel _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users