how to use no_init dijkstra
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? Why doesn't it take a value for infinity? 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. Can anyone explain to me in words what I the no_init function expects me to pass to it? Thanks in advance! Fletcher
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
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? Another option would be to use a combination of a vector and a list of visited nodes. Initialize the full vector only once, and for every search re-initialize those nodes in the list and clear the list. The list can be made using the Visitor that you already use to escape
On 11/05/2011 23:40, Fletcher Foti wrote: the algorithm. The advantage is that the algorithm will find its values in a vector which is faster than a map. (AFAIK) -- Alex
participants (3)
-
Alex Hagen-Zanker -
Fletcher Foti -
Jeremiah Willcock