Re: [Boost-users] how to use no_init dijkstra

Subject: Re: [Boost-users] how to use no_init dijkstra
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-05-11 22:30:01

On Wed, 11 May 2011, Fletcher Foti wrote:

> I'm really surprised I can't find information on this - I feel like
> I'm doing something very basic...
>
> What I want is all the nodes within a certain distance in the graph.
> I have a graph of half a million nodes and will only be visiting 20 or
> so - if you're curious, I have a graph of the street network in the
> Bay Area and will be looking at only those nodes within walking
> distance.
>
> So I read elsewhere that I need to inherit from
> default_dijkstra_visitor and throw an exception when I finalize a
> vertex beyond my search radius.  I think I have this working.
>
> Now my problem is that I have to do this search many, many times -
> performance is very important - and I don't want to initialize the
> values for a half a million nodes when I'm only going to visit 20.  I
> therefore want to use a std::map to store distances, and I want a key
> missing from that map to indicate an unvisited node, right?  I also
> want to use dijkstra_shortest_path_no_init so as to skip
> initialization, but it's very hard to find documentation on this.
>
> I could post all my code here, but I'm not yet sure if that's the most
> efficient way to get my question answered.  How does the no_init
> function work?

It does basically exactly what the normal version does, except that it 
does not initialize the distance map and allows things (such as queues) to 
be specified manually.

> Why doesn't it take a value for infinity?

The only use for the infinity parameter is to be the default value for the 
distance map, and so it is unnecessary for _no_init versions.

> I feel like
> I need to pass DistanceMap.end() as my value for infinity so that a
> node not in the distance map looks like an unvisited node.

What you want to do is to create a modified version of 
associative_property_map (from <boost/property_map/property_map.hpp>) that 
allows a user-specified value to be inserted into the std::map when the 
key is not found (rather than always default-constructing one like 
std::map::operator[] does).  The default value will work for the color 
type, so you can use a plain associative_property_map as the color map.

-- Jeremiah Willcock