[BGL] Dijkstra visitor for examine edge event
Hi everyone, I posted this message but I haven't received any response so I decided to post it again. I am trying to store all the vertices with their respective distances from a source within the Dijkstra shortest path algorithm. For that I plan to use a std::vector<std::queue > >. I was able to have the visitor working but I don't know how to access to those values that are computed automatically by the algorithm (d_v, d_u, for example). The code I wrote is as follows: template <class Tag> struct vis : public default_dijkstra_visitor { vis() { } template <class Edge, class Graph> void edge_relaxed(Edge e, Graph& g){ cout<<"VISITOR!!!"<<endl; cout<<"Edge -> "<<e<<endl; } private: std::vector<std::queue<Vertex> > storage; }; template <class Tag> vis<Tag> target_visit(Tag) { return vis<Tag>(); } void Dijkstra() { // maps needed by the algorithm IndexMap indexmap = get(vertex_index, *gPtr); WeightMap weightmap = get(edge_weight, *gPtr); // define containers for the predecessor vertices and // for distances std::vector<Vertex> pred(num_vertices(*gPtr)); std::vector<double> dist(num_vertices(*gPtr)); // vertex to compute Dijkstra's algorithm on Vertex source = vertex(get_source(), *gPtr); // Dijkstra's algorithm dijkstra_shortest_paths(*gPtr, source, predecessor_map(&pred[0]).distance_map(&dist[0]).visitor(target_visit(on_examine_edge()))); ... Any help will be appreciated. a^2
On 2/12/07, Alejandro Marcos Aragón <aaragon2@uiuc.edu> wrote:
Hi everyone,
I posted this message but I haven't received any response so I decided to post it again. I am trying to store all the vertices with their respective distances from a source within the Dijkstra shortest path algorithm. For that I plan to use a std::vector<std::queue > >. I was able to have the visitor working but I don't know how to access to those values that are computed automatically by the algorithm (d_v, d_u, for example). The code I wrote is as follows:
Hi Alejandro, I'm not sure I understand your question - The distances from the source vertex are stored in the DistanceMap, and the shortest paths to the source vertex are stored in the PredecessorMap (I'm using the terminology from http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html.) What do you want to store in a vector of queues, i.e. what would the ith queue represent? Regards, Aaron
Aaron Windsor wrote:
On 2/12/07, Alejandro Marcos Aragón <aaragon2@uiuc.edu> wrote:
Hi everyone,
I posted this message but I haven't received any response so I decided to post it again. I am trying to store all the vertices with their respective distances from a source within the Dijkstra shortest path algorithm. For that I plan to use a std::vector<std::queue > >. I was able to have the visitor working but I don't know how to access to those values that are computed automatically by the algorithm (d_v, d_u, for example). The code I wrote is as follows:
Hi Alejandro,
I'm not sure I understand your question - The distances from the source vertex are stored in the DistanceMap, and the shortest paths to the source vertex are stored in the PredecessorMap (I'm using the terminology from http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html.) What do you want to store in a vector of queues, i.e. what would the ith queue represent?
Regards, Aaron
What I want to do is to store all the distances for a vertex i, not only the smallest distance. When an edge is relaxed, meaning that the distance from the source is less than the one before, the distance is overwritten in the DistanceMap. I would like to keep all the distances with their respective vertices. Therefore, I thought that a priority queue (min heap) would be the right data structure to use. However, I don't know how to access to this information using the visitor. Something like this: 3 B------C | / | / 2| /6 | / | / A Imagine that the A is the source and it finds first that the distance to C is 6 (A-C edge). Then, when it finds that a lower distance is obtained through A-B and B-C (5), I would like to keep the previous result as well in a priority queue. For vertex C the priority queue looks then like this: (5,B) / / / (6,A) Of course this example seems trivial but you get the idea. I also tried to understand how the algorithm works in the dijkstra_shortest_paths.hpp but I couldn't find the actual algorithm (the one for which the pseudo-code is given in http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html ). I hope you can help me. Thanks for replying, a^2
On 2/13/07, Alejandro Marcos Aragón <aaragon2@uiuc.edu> wrote: <snip>
What I want to do is to store all the distances for a vertex i, not only the smallest distance. When an edge is relaxed, meaning that the distance from the source is less than the one before, the distance is overwritten in the DistanceMap. I would like to keep all the distances with their respective vertices. Therefore, I thought that a priority queue (min heap) would be the right data structure to use. However, I don't know how to access to this information using the visitor. Something like this: 3 B------C | / | / 2| /6 | / | / A
Imagine that the A is the source and it finds first that the distance to C is 6 (A-C edge). Then, when it finds that a lower distance is obtained through A-B and B-C (5), I would like to keep the previous result as well in a priority queue. For vertex C the priority queue looks then like this:
(5,B) / / / (6,A)
Of course this example seems trivial but you get the idea. I also tried to understand how the algorithm works in the dijkstra_shortest_paths.hpp but I couldn't find the actual algorithm (the one for which the pseudo-code is given in http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html ). I hope you can help me. Thanks for replying,
Hi Alejandro, Sorry for the delay in the reply. I understand what you're asking now. First, the dijkstra visitor is passed by value, so your visitor will need to contain, say, a shared pointer to a vector instead of a vector. Although it isn't guaranteed by the documentation, the actual implementation of this algorithm in the BGL updates the same DistanceMap property map you pass in to the algorithm before calling edge_relaxed, so you could have the distance to the source available if you also store the DistanceMap in your visitor. So, what you want to do is technically possible, but I would be a little hesitant to use the fact that the actual DistanceMap is updated in the algorithm (and not some temporary.) since that's undocumented. Regards, Aaron
participants (2)
-
Aaron Windsor -
Alejandro Marcos Aragón