Boost logo

Boost :

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:

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

-- Jeremiah Willcock

Boost list run by bdawes at, gregod at, cpdaniel at, john at