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

Subject: Re: [boost] [graph] interest in resumable dijkstra?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-07-26 16:15:10

On Wed, 18 Jul 2012, Alex Hagen-Zanker wrote:

> On 17/07/2012 22:42, Tim Keitt wrote:
>> Might be nice to have some simple wrappers for the most common cases (eg 
>> finding single s-t shortest path). Another useful one would be to label the 
>> vertices by nearest origin in the case of multiple origins (we encounter 
>> this all the time). THK 
> Thanks, good suggestion. I have added four wrapping functions:
>
> - for a specific maximum distance
> - reaching a specific set of targets
> - the nearest origin for multiple origins
> - plain dijkstra.
>
> They are in the dijkstra_functions.hpp file, in the following archive:
>
> http://people.pwf.cam.ac.uk/ahh34/dijkstra.zip

Here are my comments:

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

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?

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).

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?

-- Jeremiah Willcock