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 option? -- Jeremiah Willcock