Re: [boost] Boost Graph Library: Dijkstra Shortest Path ignores color_map in named parameters?

Subject: Re: [boost] Boost Graph Library: Dijkstra Shortest Path ignores color_map in named parameters?
From: Alex Hagen-Zanker (ahh34_at_[hidden])
Date: 2010-07-07 05:27:54

Jeremiah Willcock wrote:
> 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 
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.
> 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 
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