On Tue, 7 Aug 2012, Alex Hagen-Zanker wrote:
On 04/08/2012 20:30, Jeremiah Willcock wrote:
For now, I'm only going to comment on your use cases. I'm glad that you sent them; they give a better sense of what you had in mind for the class, rather than my version which is just directly inverting the control flow from visitors to an algorithm object that suspends itself at event points.
On Fri, 4 Aug 2012, Alex Hagen-Zanker wrote:
For your information, I have the following cases at hand:
1. Calculating multiple paths on the same graph, where the graph have many vertices but the paths not. It then saves to only reset the queue and the property maps for the discovered vertices that are recorded by a visitor, instead of initializing property maps for all paths.
Does dijkstra_shortest_paths_no_init cover that use case, or do you need something other than that?
Almost. I had to create a function called dijkstra_shortest_path_no_init_at_all, which does not initialize the queue and also does not push the source vertex to the queue.
OK. Other people have asked about searching from multiple sources, which your new function would help with as well.
2. Interweavedly do many shortest paths on the same network for different sources. Iteratively do the following for each source: deserialize, update stopping criterion, expand the shortest path tree to criterion is met, serialize.
I'm not sure I understand what you're trying to do for this case.
It is part of the implementation of a traffic assignment algorithm (http://www.sciencedirect.com/science/article/pii/S0191261509000769).
OK. It looks like that algorithm is using longest paths (in DAGs) as well as shortest paths. Is that also something that you're doing?
Are you doing many independent shortest path computations with different sources and stopping criteria, but starting from scratch each time, or are you using the distance, color, and/or predecessor maps from earlier computations in later ones? I am using the distance, color and predecessor maps from earlier computations in later ones. I should also use the queue from earlier computations, but as it stands I am recreating that one from the color map.
Do you just use this to interleave computations, with the maps used to restart a shortest path search from where it left off, or are you manipulating the maps in some other way?
3. Find the nearest source, if within a given distance e.g. finding the 3-minute walking catchments for all bus-stops in a state.
There's an easier solution for that use case: use dijkstra_shortest_paths_no_color_map_no_init (from <boost/graph/dijkstra_shortest_paths_no_color_map.hpp>, with documentation at <URL:http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html>) and a combine function that does a normal saturating addition but then converts any results that are >= 3 minutes to infinity. That version of Dijkstra's algorithm stops when all vertices in the queue have infinite distances, and you should be able to just re-run it with different sources, with an empty queue each time but not changing the distance or predecessor maps between runs. The predecessor map should then give you a tree for each catchment area.
That would be easier indeed, if I did not already have the dijkstra_class for the second use case.
OK.
Originally I used exception throwing visitors, which I believe is common practice. So, I was happy to keep using visitors.
That is the common practice; the inversion of control would allow you to just use "return" and "break" instead, as well as interleave multiple searches at the same time.
Interleaving multiple searches was my critical problem in the second use case.
OK. -- Jeremiah Willcock