Re: [boost] [graph] interest in resumable dijkstra?

Subject: Re: [boost] [graph] interest in resumable dijkstra?
From: Alex Hagen-Zanker (ahh34_at_[hidden])
Date: 2012-08-03 19:40:24

> Jeremiah Willcock wrote

>Here are my comments:

Thank you, much appreciated.

>
>1. You don't need dummy_write_only_property_map; use null_property_map 
>from boost/graph/property_maps/ instead.

Yes, I could use that and it would be fine. My consideration for using the 
write only map was to pre-empt mistakes where this class is used for 
getting values.

>
>2. What is the requirement for patch #7130 for?  Couldn't your class own 
>the d_ary_heap object?  Is that the only change you made to d_ary_heap.hpp 
>in your zip file?

Yes, it is the only change. It allows the heap object to store its data 
behind a smart pointer. The heap object parameter can then be passed by 
value just like the other parameters. The dijkstra object itself can then 
also be copied at low cost.

I suppose the class could own the heap object instead of its data. But then 
the heap object would become a heap-holding object instead, and be used 
with one more indirection.

>
>3. A lot of the parameter-handling stuff in dijkstra_maker.hpp duplicates 
>functionality in boost/graph/named_function_params.hpp; you might want to 
>use Boost.Parameter anyway now (BGL is slowly moving in that direction).
>

I tried to stay close to what is already there. I duplicated stuff mainly 
from dijkstra_shortest_path.hpp and not from named_function_params.hpp. The 
selection mechanism for using either the default parameter or the parameter 
from the parameter pack is similar to that in named_function_params, but 
different. Instead of the default parameter, a functor to make the default 
parameter is passed. This avoids creating default parameter objects when 
they are not required.

>4. I think there might be a simpler way to write the code and have a 
>simpler, more general interface.  However, it might not fit well with your 
>use case.  Here's what I have in mind (pseudocode):
>
> enum dijkstra_event_kind {event_init_vertex, event_discover_vertex, ..., 
> event_finished}; // or use separate classes and Boost.Variant template 
> <...> struct dijkstra_state {
>   dijkstra_state(const Graph& g, ...);
>   struct event {
>     dijkstra_event_kind get_kind() const;
>     vertex_descriptor get_vertex() const;
>     edge_descriptor get_edge() const; // Assumes dummy_edge() function
>   };
>   event operator() {...}
>};
>
>template <...>
>dijkstra_state<...> make_dijkstra(const Graph& g, ...) {
>   return dijkstra_state<...>(g, ...);
>}
>
>Then you'd use it by:
>
>auto d = make_dijkstra(g, s, ...);
>decltype(d)::event e;
>do {
>   e = d();
>} while (e.get_kind() != event_finished);
>
>or similar.  Would that kind of interface make sense for you, with 
>wrappers for common use cases that hide the use of raw events?  There 
>would probably also be a compile-time event mask to prevent the function 
>from returning unnecessarily, and maybe dijkstra_state would own the event 
>object and just return a const reference to it.  What do you think of that 
>option?
>

I see that this is certainly more general, but not necessarily that it is 
simpler. The main difference is that in your interface the operator () 
would give the user an opportunity to interrupt the algorithm at any event. 
In my implementation it is only possible to interrupt at one particular 
event, which is just before the next vertex in the queue gets processed.

It seems to me that your suggestion requires more overhead and a more 
complex dijkstra state in order to pick-up where it last stopped. For 
instance it needs to store current and end iterator over the out-edges. I 
suppose the compile time mask could solve that and make both methods 
equally efficient, but I am not familiar with that technique.

I am not sure how well your suggestion would work with my use cases because 
some bits are not clear to me. Does the dijkstra_state object own the 
property maps, the queue and the visitor? Who initializes the property 
maps, queue and visitor, is that the make_dijksta function or the 
operator(), if it is the make_dijkstra function I would require quite a few 
overloads: to initialize the property maps fully, only the source 
vertices(one or more), or not at all. If it is the operator() then I would 
need to be able to tell it to skip particular stages in the initialization 
(and the source vertices would need to become members of the state class to 
carry this information from the make_dijkstra function to the operator() , 
which would be a problem if there are many sources. (it could be a range, 
but then the user is responsible for keeping it valid).

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.

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.

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.

Originally I used exception throwing visitors, which I believe is common 
practice. So, I was happy to keep using visitors.

>