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

Subject: [Boost-users] [Boost Graph] newbie - dijkstra & external weightmap
From: Fergal Dalton (fergalish_at_[hidden])
Date: 2009-12-14 15:34:51

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);
         }