Boost logo

Boost Users :

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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net