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.