Boost logo

Boost :

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

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,

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.


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