Re: [Boost-Users] [BGL] dijkstra_shortest_paths and the single-pair problem
Throw an exception? Joaquín M López Muñoz Telefónica, Investigación y Desarrollo ----- Mensaje Original ----- De: Richard Jepps <yg-boost-users@m.gmane.org> Fecha: Martes, Julio 1, 2003 3:00 pm Asunto: [Boost-Users] [BGL] dijkstra_shortest_paths and the single-pair problem
I would like to use the dijkstra_shortest_paths algorithm to find the shortest path from one specified vertex to another.
The standard Boost implementation will find this, but it will continue until it has found the shortest paths to all nodes in the graph (i.e. solved the single source problem).
The BGL book (Section 5.1, pp76) says: "It turns out that there are no algorithms for solving the single-pair problem that are asymptotically faster than the algorithms that solve the single-source problem". I think this is because the single-source algorithms all have the propertythat it is possible to determine whether the shortest path to any given node has been found during the execution of the algorithm, therefore you can use the same algorithm to solve both types of problem provided that the termination criterion is appropriate to the problem.
Consider this problem: "find the shortest path from a source vertex u to a nearby destination vertex v in an infinitely large directed weighted graph G in finite time." The single-source problem can only be solved in infinite time, but the single-pair problem can be solved relatively quickly (because the two vertices are near each other).
I think that the termination criterion is quite straightforward using a DijkstraVisitor - it is when vis.finish_vertex(u, g) is called and u == destination_node. Unfortunately I can't see how to stop the algorithm in a reasonable way.
An unreasonable solution is to provide a custom graph and turn off all its edges when the termination criterion is met. This is unreasonable because the responsibility for termination belongs to the algorithm, not the data structure - I shouldn't have to modify the data structure to terminate the algorithm. It's also unreasonable because I have to customise both the graph and the algorithm to do something very simple.
Is there a better way?
Thanks
Richard
------------------------ Yahoo! Groups Sponsor -------------------- -~--> Get A Free Psychic Reading! Your Online Answer To Life's Important Questions.http://us.click.yahoo.com/Lj3uPC/Me7FAA/ySSFAA/EbFolB/TM ------------------------------------------------------------------- --~->
Info: <" target="l">http://www.boost.org> Wiki: <" target="l">http://www.crystalclearsoftware.com/cgi- bin/boost_wiki/wiki.pl>Unsubscribe: <')" >mailto:boost-users- unsubscribe@yahoogroups.com>
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
Eeek! Exceptions as flow control are, well, not exceptions. I have no solution to offer (I don't even fully understand the question), but I hope someone has a better answer. - Mark JOAQUIN LOPEZ MU?Z wrote:
Throw an exception?
Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
----- Mensaje Original ----- De: Richard Jepps <yg-boost-users@m.gmane.org> Fecha: Martes, Julio 1, 2003 3:00 pm Asunto: [Boost-Users] [BGL] dijkstra_shortest_paths and the single-pair problem
[snip]
Is there a better way?
Thanks
Richard
Joaquin, Mark, Thanks for your replies. An exception would work in this case because there is no return value, however there might be problems with resource leaks - even if version 1_30_0 doesn't leak, a later one might. If I need a quick fix I might try it - but I think a safe, clean solution will involve a small change to the algorithm - unless there is a good trick that works with visitors. Richard
Richard Jepps wrote:
An exception would work in this case because there is no return value, however there might be problems with resource leaks - even if version 1_30_0 doesn't leak, a later one might.
An exception can "return" arbitrary data, and no, a later one might not leak. That's the same as saying "even if version 1_30_0 does work, a later one might contain a bug."
Peter, "Peter Dimov" <pdimov@mmltd.net> wrote in message news:007801c34152$11ddd420$1d00a8c0@pdimov2...
Richard Jepps wrote:
An exception would work in this case because there is no return value, however there might be problems with resource leaks - even if version 1_30_0 doesn't leak, a later one might.
An exception can "return" arbitrary data, and no, a later one might not leak. That's the same as saying "even if version 1_30_0 does work, a later one might contain a bug."
If the BGL guarantees its users that it is exception safe then I agree - and looking at the Boost library guidelines: http://www.boost.org/more/lib_guide.htm "Use exceptions to report errors where appropriate, and write code that is safe in the face of exceptions. " I can reasonably expect that it is exception safe. Thanks Richard
Mark Sizer <yg-boost-users@m.gmane.org> writes:
Eeek! Exceptions as flow control are, well, not exceptions.
Playing into this little trap: If most cycles are spent doing something else, then an exception is the exception, not the rule. Beware of attractive linguistic illusions, though. Exceptions are just a programming construct. See http://www.boost.org/more/error_handling.html -- Dave Abrahams Boost Consulting www.boost-consulting.com
participants (1)
-
David Abrahams -
JOAQUIN LOPEZ MU?Z -
Mark Sizer -
Peter Dimov -
Richard Jepps