Boost logo

Boost Users :

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?


> 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
using syntax such as the following (replacing
"weight_map(agent_weightmap)" in the code just above):

     get(vertex_index, g)))

You will need to include <boost/property_map/property_map.hpp> to get

-- Jeremiah Willcock

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at