Re: [boost] [gsoc] Interest in BGL v2?

Subject: Re: [boost] [gsoc] Interest in BGL v2?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-03-29 14:19:06

On Tue, 29 Mar 2011, Andrew Sutton wrote:

>> I think the original intent of algorithm objects for BGL is inversion of
>> control flow: instead of something like BFS calling visitor methods at event
>> points, you have a BFS object that suspends itself where it would have
>> called the visitor, and then is continued by surrounding code.  This makes
>> it easier to do things like interleave two BFS runs at the same time, which
>> you can't do with the existing model (without threads or coroutines).
>
> Is there a reference to that description? The algorithm objects in the
> BGL seem to be giant function objects.

There is an example at 
http://www.springerlink.com/content/20vy0y0rq5mtcqmb/ (summary also at 
http://www.cs.rpi.edu/~musser/gp/dagstuhl/gpdag_28.html).  I didn't know 
there were any algorithm objects at all in BGL, at least according to the 
definition I have in mind.

> I think our major use case was to use these objects as an alternative
> method to calling functions with large numbers of input and output
> parameters. The idea was to create an algorithm object over its
> required or optional associated data and then call it using a limited
> number of inputs (a graph, a vertex, etc.). After termination, the
> associated data is also available through the object.
>
> We've also written BFS (and soon DFS) as Range models, which offer a
> limited form of inversion. This approach also supports interleaving 2
> BF traversals. I haven't actually tried it out.
>
> Earlier designs of these classes had more control points, we weren't
> entirely sure what the use cases were, so we simplified them. It
> wouldn't be hard to bring previous designs back.
>
> One concern with this approach is that adds overhead to the of the
> algorithm. I didn't want to force users to use a slower algorithm when
> there wasn't need. Also, they're a lot harder to write, and it's not
> always straightforward to recall

Yes, they are definitely harder to write and can be slower (because of the 
state saving), so they should not be the default mode.  I think they are 
useful in special cases, though, and so that's why they are on the to-do 
list.

-- Jeremiah Willcock