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

Subject: Re: [Boost-users] [Boost Graph] newbie - dijkstra & external weightmap
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-12-14 17:59:29

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_map.html) 
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