On Tue, 6 Jul 2010, Alex Hagen-Zanker wrote:
The problem of resuming a dijkstra_shortest_path calculation is solved and I thought to share the solution here. That seems like it's a complicated workaround. Did the ideas of just doing your work in a Dijkstra visitor callback (and the algorithm then resuming automatically) or using a separate thread not work for you? Those would seem to be much simpler than what you're doing. No, it would not work for me. In my case, I have to do a large number (say 2000) of dijkstra shortest path calculations, then I do some
Those would seem to be much simpler than what you're doing. They would also be more correct. One problem with my solution is that it introduces pseudo-edges from the source to the gray vertices. It works fine for me because all my hooks are vertex-based. Edge-based hooks however would need to know about the pseude-edges somehow in order to ignore them. Otherwise, we don't have a good way to resume algorithms, although it has been on the TODO list for a long time. I might be able to put something simple together for you that works more directly for resumption. -- Jeremiah Willcock It seems that the pair of functions: algorithm() and algorithm_no_init() is ideal for resuming algorithms. The only caveat is that algorithm_no_init() should live up to its name and not do any initialization from scratch. It should be OK to initialize from
Jeremiah Willcock wrote: traffic modelling on them, and based on the results I need to go back to the 2000 dijkstra's and resume them. Doing this in a visitor call-back would (to my understanding) require a recursive approach where each visitor, except number 2000, invokes another dijkstra + visitor. It would probably be possible, but more complicated than my current solution. I have considered putting the dijkstra calculations in separate threads, but don't understand enought about threads to know if it is acceptable to create 2000 threads on a desktop computer. Another problem was that I run out of memory and one way of managing it is to store the state of the dijkstra algorithm to hard disk after a calculation and load the state from disk again upon resumption. This requires me to explicitly know the state, and to be able to clear it and overwrite it. This would not be possible in the thread solution, nor in the recursion solution. parameters that duplicate information, e.g. initialize the priority queue from the color map. It could entail the following: Initialize Q from color map in dijkstra_shortest_paths_no_init() by inserting the following after declaring Q typedef typename property_traits<ColorMap>::value_type ColorValue; typedef color_traits<ColorValue> Color; typename graph_traits<VertexListGraph>::vertex_iterator vi, vi_end; for (tie(vi, vi_end) = vertices(g); ui != vi_end; ++vi) if(get(color, *vi) == Color::gray()) Q.push(*vi); Call breadth_first_visit_no_init() instead of breadth_first_visit() from dijkstra_shortest_paths_no_init(). Create breadth_first_visit_no_init() as a copy of breadth_first_visit(), but remove the following lines. put(color, s, Color::gray()); vis.discover_vertex(s, g); Q.push(s); Also it is no longer necessary to pass the source vertex argument. If something along these lines could make it into the BGL that would be great. I would like to make my work open source some time and it would be great if it works seamlessly with boost at that point. For now, I can tolerate overly complicated workarounds. -- Alex Hagen-Zanker