Re: [Boost-users] [Boost Graph] newbie - dijkstra & external weightmap

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 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 to get iterator_property_map. -- Jeremiah Willcock