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