"Richard Jepps"
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.
I don't buy that conclusion. The visitor has many points-of-customization, each of which might signal termination. Checking at each of those points could get expensive. If you want to terminate early by force-clearing the queue, I guess that won't impose any overhead, but any check that requires *additional* cycles on each step of the algorithm can add up.
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.
That's certainly possible, providing your compiler cooperates. But most optimizers can also eliminate a call to an inline function which always returns the same boolean value and a branch which depends on that result -- so it's more than likely to be wasted optimization. I'm more concerned about the cost to performance of doing the additional termination check on each step of the algorithm.
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.
I understand the problem with comprehensibility. Furthermore, AFAIK nobody has every really measured the speed difference in the two approaches, so it may be OK to do it the "straightforward" way. I'd just like to see some numbers before anyone starts changing the BGL interfaces.
Thanks for your reply, and sorry for asking a question that's been asked before. I did look, but I didn't find.
Not a problem. -- Dave Abrahams Boost Consulting www.boost-consulting.com