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?
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. 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?
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.
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. -- Jeremiah Willcock