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