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

From: David Abrahams (dave_at_[hidden])
Date: 2003-07-04 18:45:39

"Richard Jepps" <yg-boost-users_at_[hidden]> writes:

> 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