[Boost Graph] newbie - dijkstra & external weightmap
Hi, I'm trying to write a program which considers some "agents" traversing a graph following dijkstra, from some source vertex to some destination. Each agent will have a different weightmap for the network. Therefore, I need a routine to which I pass the source & destination vertices, and a pointer or reference to the calling agents weightmap. This routine should return the next step for that agent. Alternatively, I could write a visitor which, everytime any agent calls dijkstra, overwrites the weight in the bundled edge structure, with that agent's weights array. Here below is the nuts of what I have, which works but only with the bundled edge_weight (called "transit_time"). Below that, is what I'd like to do. Anyway, the long & short of it is, I couldn't wrap my head around the syntax for either. I've looked in the books, in the lists, on the site, and I can't find any help on how to incorporate external weightmaps with dijkstra. Can anyone tell me how to proceed? Thanks, Fergal. --------------- This works, but only with the bundled weight property, identical for all agents: class road; typedef adjacency_list<setS,vecS,undirectedS,no_property,road> Graph; typedef Graph::vertex_descriptor vdest; vdest shortest_path(Graph& g, vdest src, vdest dst) { vector<vdest> parent(num_vertices(g)); dijkstra_shortest_paths(g,src,weight_map(get(&road::transit_time,g)) .predecessor_map(make_iterator_property_map(parent.begin(), get(vertex_index, g)))); vdest vd; for (vd=dst ; parent[vd]!=src ; vd=parent[vd]); // ATTN: isolated vertices return(vd); } ----------------- What I would like, where agent_weightmap is (a pointer to) the agent's weightmap: class road; typedef adjacency_list<setS,vecS,undirectedS,no_property,road> Graph; typedef Graph::vertex_descriptor vdest; vdest shortest_path(Graph& g, vdest src, vdest dst, vector<double> agent_weightmap) { vector<vdest> parent(num_vertices(g)); dijkstra_shortest_paths(g,src,weight_map(agent_weightmap)) .predecessor_map(make_iterator_property_map(parent.begin(), get(vertex_index, g)))); vdest vd; for (vd=dst ; parent[vd]!=src ; vd=parent[vd]); // ATTN: isolated vertices return(vd); }
On Mon, 14 Dec 2009, Fergal Dalton wrote:
Hi, I'm trying to write a program which considers some "agents" traversing a graph following dijkstra, from some source vertex to some destination. Each agent will have a different weightmap for the network. Therefore, I need a routine to which I pass the source & destination vertices, and a pointer or reference to the calling agents weightmap. This routine should return the next step for that agent.
Alternatively, I could write a visitor which, everytime any agent calls dijkstra, overwrites the weight in the bundled edge structure, with that agent's weights array.
Here below is the nuts of what I have, which works but only with the bundled edge_weight (called "transit_time"). Below that, is what I'd like to do.
Anyway, the long & short of it is, I couldn't wrap my head around the syntax for either. I've looked in the books, in the lists, on the site, and I can't find any help on how to incorporate external weightmaps with dijkstra. Can anyone tell me how to proceed?
(snip)
What I would like, where agent_weightmap is (a pointer to) the agent's weightmap:
class road; typedef adjacency_list<setS,vecS,undirectedS,no_property,road> Graph; typedef Graph::vertex_descriptor vdest; vdest shortest_path(Graph& g, vdest src, vdest dst, vector<double> agent_weightmap) { vector<vdest> parent(num_vertices(g));
dijkstra_shortest_paths(g,src,weight_map(agent_weightmap)) .predecessor_map(make_iterator_property_map(parent.begin(), get(vertex_index, g))));
vdest vd; for (vd=dst ; parent[vd]!=src ; vd=parent[vd]); // ATTN: isolated vertices return(vd); }
Use iterator_property_map (http://www.boost.org/doc/libs/1_41_0/libs/property_map/doc/iterator_property...) using syntax such as the following (replacing "weight_map(agent_weightmap)" in the code just above): weight_map( make_iterator_property_map( agent_weightmap.begin(), get(vertex_index, g))) You will need to include <boost/property_map/property_map.hpp> to get iterator_property_map. -- Jeremiah Willcock
participants (2)
-
Fergal Dalton
-
Jeremiah Willcock