[graph] interest in resumable dijkstra?
Dear boost-list, I placed the BGL algorithm of the dijkstra_shortest_path in a class, with the creation and initialization part separate from the main algorithm. This allows interrupting, resetting and resuming the algorithm. Would this be of interest to anybody? The following function call: dijkstra_shortest_path(graph, orig, parameter_pack); is separated into: auto dijkstra = make_dijkstra(graph, parameter_pack); dijkstra.init_from_origin(orig /*, optional_visitor*/); dijkstra.expand(/*optional_visitor*/); The make_dijkstra() function reads all parameters from the parameter_pack including color_map and priority_queue Visitors interrupt the calculation using a do_intterrupt() callback instead of throwing an exception. The function expand() can be called repeatedly, each time with another visitor. The implementation requires C++11, because of auto and lambda's, it also relies on the following patch: https://svn.boost.org/trac/boost/ticket/7130. To see for yourself: http://people.pwf.cam.ac.uk/ahh34/dijkstra_test.zip I am interested to hear your opinion. With kind regards, Alex
On Fri, 13 Jul 2012, Alex Hagen-Zanker wrote:
Dear boost-list,
I placed the BGL algorithm of the dijkstra_shortest_path in a class, with the creation and initialization part separate from the main algorithm. This allows interrupting, resetting and resuming the algorithm. Would this be of interest to anybody?
Yes, definitely.
The following function call:
dijkstra_shortest_path(graph, orig, parameter_pack);
is separated into:
auto dijkstra = make_dijkstra(graph, parameter_pack); dijkstra.init_from_origin(orig /*, optional_visitor*/); dijkstra.expand(/*optional_visitor*/);
The make_dijkstra() function reads all parameters from the parameter_pack including color_map and priority_queue Visitors interrupt the calculation using a do_intterrupt() callback instead of throwing an exception. The function expand() can be called repeatedly, each time with another visitor. The implementation requires C++11, because of auto and lambda's, it also relies on the following patch: https://svn.boost.org/trac/boost/ticket/7130.
It would be nicer to have it be C++03, since nothing else in BGL requires C++11 yet.
To see for yourself: http://people.pwf.cam.ac.uk/ahh34/dijkstra_test.zip
I am interested to hear your opinion.
I haven't had a chance to look at it yet, but I'm definitely interested in putting it in when it's ready. -- Jeremiah Willcock
On 13/07/2012 19:24, Jeremiah Willcock wrote:
On Fri, 13 Jul 2012, Alex Hagen-Zanker wrote:
I placed the BGL algorithm of the dijkstra_shortest_path in a class, with the creation and initialization part separate from the main algorithm. This allows interrupting, resetting and resuming the algorithm. Would this be of interest to anybody?
Yes, definitely.
The implementation requires C++11, because of auto and lambda's, it also relies on the following patch: https://svn.boost.org/trac/boost/ticket/7130.
It would be nicer to have it be C++03, since nothing else in BGL requires C++11 yet.
There now is a new version that only requires C++03: http://people.pwf.cam.ac.uk/ahh34/dijkstra_test_v2.zip Using the class without auto takes some of the fun away, as: auto dijkstra = make_dijkstra(g, boost::distance_map(distance).vertex_index_map(indexmap).visitor(vis) ); becomes: typedef boost::bgl_named_params<DistanceMap, boost::vertex_distance_t, boost::bgl_named_params<IndexMap, boost::vertex_index_t, boost::bgl_named_params<DistanceVisitor, boost::graph_visitor_t> > >Params; typedef boost::dijkstra_traits<Graph, Params>::dijkstra_type dijkstra_type; dijkstra_type dijkstra = make_dijkstra(g, boost::distance_map(distance).vertex_index_map(indexmap).visitor(vis) );
I haven't had a chance to look at it yet, but I'm definitely interested in putting it in when it's ready.
Thanks, please let me know what you think once you have taken a look.
On Mon, 16 Jul 2012, Alex Hagen-Zanker wrote:
On 13/07/2012 19:24, Jeremiah Willcock wrote:
On Fri, 13 Jul 2012, Alex Hagen-Zanker wrote:
I placed the BGL algorithm of the dijkstra_shortest_path in a class, with the creation and initialization part separate from the main algorithm. This allows interrupting, resetting and resuming the algorithm. Would this be of interest to anybody?
Yes, definitely.
The implementation requires C++11, because of auto and lambda's, it also relies on the following patch: https://svn.boost.org/trac/boost/ticket/7130.
It would be nicer to have it be C++03, since nothing else in BGL requires C++11 yet.
There now is a new version that only requires C++03: http://people.pwf.cam.ac.uk/ahh34/dijkstra_test_v2.zip
Using the class without auto takes some of the fun away, as:
auto dijkstra = make_dijkstra(g, boost::distance_map(distance).vertex_index_map(indexmap).visitor(vis) );
becomes: typedef boost::bgl_named_params<DistanceMap, boost::vertex_distance_t, boost::bgl_named_params<IndexMap, boost::vertex_index_t, boost::bgl_named_params<DistanceVisitor, boost::graph_visitor_t> > >Params;
typedef boost::dijkstra_traits<Graph, Params>::dijkstra_type dijkstra_type;
dijkstra_type dijkstra = make_dijkstra(g, boost::distance_map(distance).vertex_index_map(indexmap).visitor(vis) );
I understand, and it will still be nicer to use with C++11, but C++03 support is necessary for now.
I haven't had a chance to look at it yet, but I'm definitely interested in putting it in when it's ready.
Thanks, please let me know what you think once you have taken a look.
OK, but please remind me early next week if I haven't sent a response by then. -- Jeremiah Willcock
I'll add a second -- this would be highly useful for some of our applications. THK On Mon, Jul 16, 2012 at 2:48 PM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Mon, 16 Jul 2012, Alex Hagen-Zanker wrote:
On 13/07/2012 19:24, Jeremiah Willcock wrote:
On Fri, 13 Jul 2012, Alex Hagen-Zanker wrote:
I placed the BGL algorithm of the dijkstra_shortest_path in a class, with the creation and initialization part separate from the main algorithm. This allows interrupting, resetting and resuming the algorithm. Would this be of interest to anybody?
<snip>
-- Timothy H. Keitt http://www.keittlab.org/
On Jul 17 2012, Klaim - Joël Lamotte wrote:
On Tue, Jul 17, 2012 at 5:36 PM, Tim Keitt <tkeitt@gmail.com> wrote:
I'll add a second -- this would be highly useful for some of our applications.
Same here.
That is great to hear. Would either of you have time to see if the implementation and interface make sense to you, and can you recommend improvements? Kind regards, Alex
On Tue, Jul 17, 2012 at 10:22 PM, Alex Hagen-Zanker <ahh34@cam.ac.uk> wrote:
That is great to hear. Would either of you have time to see if the implementation and interface make sense to you, and can you recommend improvements?
I cannot spend much time reviewing it but quickly reading the main.cpp of the test v2 don't trigger any alarm for me. I'll try to take a closer look later. Joel Lamotte
On Tue, Jul 17, 2012 at 3:22 PM, Alex Hagen-Zanker <ahh34@cam.ac.uk> wrote:
On Jul 17 2012, Klaim - Joël Lamotte wrote:
On Tue, Jul 17, 2012 at 5:36 PM, Tim Keitt <tkeitt@gmail.com> wrote:
I'll add a second -- this would be highly useful for some of our applications.
Same here.
That is great to hear. Would either of you have time to see if the implementation and interface make sense to you, and can you recommend improvements?
Kind regards, Alex
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Looks very good so far. I relies heavily on the color map, which seem appropriate from what I've seen. 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 -- Timothy H. Keitt http://www.keittlab.org/
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 Kind regards, Alex
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
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.
For now, I'm only going to comment on your use cases. I'm glad that you sent them; they give a better sense of what you had in mind for the class, rather than my version which is just directly inverting the control flow from visitors to an algorithm object that suspends itself at event points. On Fri, 4 Aug 2012, Alex Hagen-Zanker wrote:
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.
Does dijkstra_shortest_paths_no_init cover that use case, or do you need something other than that?
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.
I'm not sure I understand what you're trying to do for this case. Are you doing many independent shortest path computations with different sources and stopping criteria, but starting from scratch each time, or are you using the distance, color, and/or predecessor maps from earlier computations in later ones?
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.
There's an easier solution for that use case: use dijkstra_shortest_paths_no_color_map_no_init (from <boost/graph/dijkstra_shortest_paths_no_color_map.hpp>, with documentation at <URL:http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html>) and a combine function that does a normal saturating addition but then converts any results that are >= 3 minutes to infinity. That version of Dijkstra's algorithm stops when all vertices in the queue have infinite distances, and you should be able to just re-run it with different sources, with an empty queue each time but not changing the distance or predecessor maps between runs. The predecessor map should then give you a tree for each catchment area.
Originally I used exception throwing visitors, which I believe is common practice. So, I was happy to keep using visitors.
That is the common practice; the inversion of control would allow you to just use "return" and "break" instead, as well as interleave multiple searches at the same time. -- Jeremiah Willcock
On 04/08/2012 20:30, Jeremiah Willcock wrote:
For now, I'm only going to comment on your use cases. I'm glad that you sent them; they give a better sense of what you had in mind for the class, rather than my version which is just directly inverting the control flow from visitors to an algorithm object that suspends itself at event points.
On Fri, 4 Aug 2012, Alex Hagen-Zanker wrote:
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.
Does dijkstra_shortest_paths_no_init cover that use case, or do you need something other than that?
Almost. I had to create a function called dijkstra_shortest_path_no_init_at_all, which does not initialize the queue and also does not push the source vertex to the queue.
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.
I'm not sure I understand what you're trying to do for this case.
It is part of the implementation of a traffic assignment algorithm (http://www.sciencedirect.com/science/article/pii/S0191261509000769).
Are you doing many independent shortest path computations with different sources and stopping criteria, but starting from scratch each time, or are you using the distance, color, and/or predecessor maps from earlier computations in later ones? I am using the distance, color and predecessor maps from earlier computations in later ones. I should also use the queue from earlier computations, but as it stands I am recreating that one from the color map.
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.
There's an easier solution for that use case: use dijkstra_shortest_paths_no_color_map_no_init (from <boost/graph/dijkstra_shortest_paths_no_color_map.hpp>, with documentation at <URL:http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html>) and a combine function that does a normal saturating addition but then converts any results that are >= 3 minutes to infinity. That version of Dijkstra's algorithm stops when all vertices in the queue have infinite distances, and you should be able to just re-run it with different sources, with an empty queue each time but not changing the distance or predecessor maps between runs. The predecessor map should then give you a tree for each catchment area.
That would be easier indeed, if I did not already have the dijkstra_class for the second use case.
Originally I used exception throwing visitors, which I believe is common practice. So, I was happy to keep using visitors.
That is the common practice; the inversion of control would allow you to just use "return" and "break" instead, as well as interleave multiple searches at the same time.
Interleaving multiple searches was my critical problem in the second use case.
On Tue, 7 Aug 2012, Alex Hagen-Zanker wrote:
On 04/08/2012 20:30, Jeremiah Willcock wrote:
For now, I'm only going to comment on your use cases. I'm glad that you sent them; they give a better sense of what you had in mind for the class, rather than my version which is just directly inverting the control flow from visitors to an algorithm object that suspends itself at event points.
On Fri, 4 Aug 2012, Alex Hagen-Zanker wrote:
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.
Does dijkstra_shortest_paths_no_init cover that use case, or do you need something other than that?
Almost. I had to create a function called dijkstra_shortest_path_no_init_at_all, which does not initialize the queue and also does not push the source vertex to the queue.
OK. Other people have asked about searching from multiple sources, which your new function would help with as well.
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.
I'm not sure I understand what you're trying to do for this case.
It is part of the implementation of a traffic assignment algorithm (http://www.sciencedirect.com/science/article/pii/S0191261509000769).
OK. It looks like that algorithm is using longest paths (in DAGs) as well as shortest paths. Is that also something that you're doing?
Are you doing many independent shortest path computations with different sources and stopping criteria, but starting from scratch each time, or are you using the distance, color, and/or predecessor maps from earlier computations in later ones? I am using the distance, color and predecessor maps from earlier computations in later ones. I should also use the queue from earlier computations, but as it stands I am recreating that one from the color map.
Do you just use this to interleave computations, with the maps used to restart a shortest path search from where it left off, or are you manipulating the maps in some other way?
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.
There's an easier solution for that use case: use dijkstra_shortest_paths_no_color_map_no_init (from <boost/graph/dijkstra_shortest_paths_no_color_map.hpp>, with documentation at <URL:http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html>) and a combine function that does a normal saturating addition but then converts any results that are >= 3 minutes to infinity. That version of Dijkstra's algorithm stops when all vertices in the queue have infinite distances, and you should be able to just re-run it with different sources, with an empty queue each time but not changing the distance or predecessor maps between runs. The predecessor map should then give you a tree for each catchment area.
That would be easier indeed, if I did not already have the dijkstra_class for the second use case.
OK.
Originally I used exception throwing visitors, which I believe is common practice. So, I was happy to keep using visitors.
That is the common practice; the inversion of control would allow you to just use "return" and "break" instead, as well as interleave multiple searches at the same time.
Interleaving multiple searches was my critical problem in the second use case.
OK. -- Jeremiah Willcock
On Aug 9 2012, Jeremiah Willcock wrote:
OK. It looks like that algorithm is using longest paths (in DAGs) as well as shortest paths. Is that also something that you're doing?
Yes, but that part of the calculation does not require resumability. It is from scratch each iteration. It is based on a topological sort and does not use dijkstra shortest paths.
Do you just use this to interleave computations, with the maps used to restart a shortest path search from where it left off, or are you manipulating the maps in some other way?
I just restart where I was left. The only thing that changes is the termination criterion. (e.g. the weights on the edges remain the same)
On Thu, 10 Aug 2012, Alex Hagen-Zanker wrote:
On Aug 9 2012, Jeremiah Willcock wrote:
OK. It looks like that algorithm is using longest paths (in DAGs) as well as shortest paths. Is that also something that you're doing?
Yes, but that part of the calculation does not require resumability. It is from scratch each iteration. It is based on a topological sort and does not use dijkstra shortest paths.
Couldn't you do shortest paths in the same topological sort sweep? That would probably be faster than Dijkstra's algorithm.
Do you just use this to interleave computations, with the maps used to restart a shortest path search from where it left off, or are you manipulating the maps in some other way?
I just restart where I was left. The only thing that changes is the termination criterion. (e.g. the weights on the edges remain the same)
OK. I think either your model for suspension or the algorithm object model (what I had proposed) will work for that case. Do you need serialization to save on memory usage? -- Jeremiah Willcock
On 10/08/2012 21:12, Jeremiah Willcock wrote:
On Thu, 10 Aug 2012, Alex Hagen-Zanker wrote:
On Aug 9 2012, Jeremiah Willcock wrote:
OK. It looks like that algorithm is using longest paths (in DAGs) as well as shortest paths. Is that also something that you're doing?
Yes, but that part of the calculation does not require resumability. It is from scratch each iteration. It is based on a topological sort and does not use dijkstra shortest paths.
Couldn't you do shortest paths in the same topological sort sweep? That would probably be faster than Dijkstra's algorithm.
No that's not how the algorithm works. The Dijkstra algorithm is applied on the full transport network and the resulting tree forms the initial DAG for the rest of the algorithm.
Do you just use this to interleave computations, with the maps used to restart a shortest path search from where it left off, or are you manipulating the maps in some other way?
I just restart where I was left. The only thing that changes is the termination criterion. (e.g. the weights on the edges remain the same)
OK. I think either your model for suspension or the algorithm object model (what I had proposed) will work for that case. Do you need serialization to save on memory usage?
Yes, I also think both methods will work. I know mine is working and yours is a generalization as far as I can see. Yes, I use serialization to save on memory usage.
On 10/08/2012 21:12, Jeremiah Willcock wrote:
OK. I think either your model for suspension or the algorithm object model (what I had proposed) will work for that case.
It seems that we have established now that the proposed dijkstra_class is actually useful. It makes something possible that was not possible before: interweaving dijkstra shortest path searches. And it is making some other things easier than they were before: using dijkstra shortest path with multiple sources, re-using property maps by re-initializing properties for changed vertices only. One other improvement is that the priority queue and color map can now be set in the named parameters, making it easier to customize the algorithm. However, the algorithm object model has been long on the wish-list of the BGL and my model for suspension is not as flexible, generic, and - from your point of view - simple. The algorithm object model may be better attuned to the direction that you wish to take BGL. Perhaps you already have some working proto-type? I find it hard to imagine an efficient implementation of the algorithm object model, because there are so many potential break points in the algorithm and each time the algorithm is resumed it would have to work out where it was left. My implementation on the other hand tries to stay close to the current BGL. It uses the BGL named parameters. There is only one potential break point, which is the - from my point of view - natural outer while() loop that processes all vertices in the queue, all other events are handled using the visitors that are already supported by the BGL. How would you like to take this forward? Kind regards, Alex p.s. I put a latest version online, that uses the null_property_map and also support graphs of unknown size. http://people.pwf.cam.ac.uk/ahh34/dijkstra.zip
On 04/08/2012 00:40, Alex Hagen-Zanker wrote:
Jeremiah Willcock wrote
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.
I see now that null_property_map is also write-only. I will use that one instead.
On 16/07/2012 20:48, Jeremiah Willcock wrote:
On Mon, 16 Jul 2012, Alex Hagen-Zanker wrote:
On 13/07/2012 19:24, Jeremiah Willcock wrote:
On Fri, 13 Jul 2012, Alex Hagen-Zanker wrote:
I placed the BGL algorithm of the dijkstra_shortest_path in a class, with the creation and initialization part separate from the main algorithm. This allows interrupting, resetting and resuming the algorithm. Would this be of interest to anybody?
Yes, definitely. OK, but please remind me early next week if I haven't sent a response by then.
Hi Jeremiah, Did you have a chance to look at the code? It is now at a stage where it won't progress unless I get feedback from you or others. The latest version is here: http://people.pwf.cam.ac.uk/ahh34/dijkstra.zip Kind regards, Alex
On Tue, 24 Jul 2012, Alex Hagen-Zanker wrote:
On 16/07/2012 20:48, Jeremiah Willcock wrote:
On 13/07/2012 19:24, Jeremiah Willcock wrote:
On Fri, 13 Jul 2012, Alex Hagen-Zanker wrote:
I placed the BGL algorithm of the dijkstra_shortest_path in a class, with the creation and initialization part separate from the main algorithm. This allows interrupting, resetting and resuming the algorithm. Would this be of interest to anybody?
Yes, definitely. OK, but please remind me early next week if I haven't sent a response by
On Mon, 16 Jul 2012, Alex Hagen-Zanker wrote: then.
Hi Jeremiah,
Did you have a chance to look at the code? It is now at a stage where it won't progress unless I get feedback from you or others. The latest version is here: http://people.pwf.cam.ac.uk/ahh34/dijkstra.zip
No, I haven't been able to yet. I should have time within the next few days. -- Jeremiah Willcock
on Fri Jul 13 2012, Alex Hagen-Zanker <ahh34-AT-cam.ac.uk> wrote:
https://svn.boost.org/trac/boost/ticket/7130.
To see for yourself: http://people.pwf.cam.ac.uk/ahh34/dijkstra_test.zip
I am interested to hear your opinion.
It might make sense to consider whether Boost.Context could be used to do this job without major restructuring of the existing dijkstra code. http://lists.boost.org/boost-announce/2011/05/0310.php -- Dave Abrahams BoostPro Computing Software Development Training http://www.boostpro.com Clang/LLVM/EDG Compilers C++ Boost
On Mon, 30 Jul 2012, Dave Abrahams wrote:
on Fri Jul 13 2012, Alex Hagen-Zanker <ahh34-AT-cam.ac.uk> wrote:
https://svn.boost.org/trac/boost/ticket/7130.
To see for yourself: http://people.pwf.cam.ac.uk/ahh34/dijkstra_test.zip
I am interested to hear your opinion.
It might make sense to consider whether Boost.Context could be used to do this job without major restructuring of the existing dijkstra code. http://lists.boost.org/boost-announce/2011/05/0310.php
It would work, but I think using a lower-level, more general library like that would have a higher performance impact than doing something algorithm-specific. I think doing something like a manual translation of N3328 resumable functions or similar to get generators (with event points as yield statements) would be faster, even though it would tangle the algorithm specification more. I have written macros that help to make that kind of code cleaner for previous projects, so a variant of them might help for this use case as well. -- Jeremiah Willcock
On Jul 30 2012, Jeremiah Willcock wrote:
On Mon, 30 Jul 2012, Dave Abrahams wrote:
on Fri Jul 13 2012, Alex Hagen-Zanker <ahh34-AT-cam.ac.uk> wrote:
https://svn.boost.org/trac/boost/ticket/7130.
To see for yourself: http://people.pwf.cam.ac.uk/ahh34/dijkstra_test.zip
I am interested to hear your opinion.
It might make sense to consider whether Boost.Context could be used to do this job without major restructuring of the existing dijkstra code. http://lists.boost.org/boost-announce/2011/05/0310.php
It would work, but I think using a lower-level, more general library like that would have a higher performance impact than doing something algorithm-specific. I think doing something like a manual translation of N3328 resumable functions or similar to get generators (with event points as yield statements) would be faster, even though it would tangle the algorithm specification more. I have written macros that help to make that kind of code cleaner for previous projects, so a variant of them might help for this use case as well.
-- Jeremiah Willcock
This is beyond my knowledge, and I cannot really comment on Boost Context or N3328. But it may be relevant to point out that I use the class for more than just interupting and resuming the current dijkstra shortest path function, I also -skip initialization -serialize and deserialize the state of the algorithm -change the course of the algorithm by resuming with different visitors Best wishes, Alex
participants (5)
-
Alex Hagen-Zanker -
Dave Abrahams -
Jeremiah Willcock -
Klaim - Joël Lamotte -
Tim Keitt