Re: [BGL] dijkstra_shortest_paths and the single-pair problem

From: Richard Jepps (yg-boost-users_at_[hidden])
Date: 2003-07-04 11:39:15

David,

> The best (and most efficient) way to terminate graph algorithms early
> is by throwing an exception.  That's the intended way to use the
> library, and it is documented that way in the FAQ.

Thanks for pointing this out - for future readers the link is:
http://www.boost.org/libs/graph/doc/faq.html

It is also worth noting that
http://www.boost.org/libs/graph/doc/table_of_contents.html
links to a lot of information that isn't in the BGL book.

> The alternative
> would be to have every visitor explicitly checking for termination at
> every step, which would impose a high efficiency burden for large
> problems.

The algorithm already checks for termination for each node it deals with (if
Q is empty in BFS), so the performance
penalty would be very small. It might even be possible to define the test at
compile time so that there was no performance
penalty unless you explicitly ask for the check.

The main problem with using an exception is that the solution to the
single-source problem is a single function call,
the solution to the single-pair problem is to implement a visitor using an
exception - which would not be obvious
to many Boost users (the developers are in a different league). It's as if
the function has been made deliberately hard
to use for half its potential users.

Thanks for your reply, and sorry for asking a question that's been asked
before. I did look, but I didn't find.

Richard