Re: [boost] [metagraph]

Subject: Re: [boost] [metagraph]
From: Kitten, Nicholas (nkitten_at_[hidden])
Date: 2012-02-02 13:20:43

On Fri, Jan 27, 2012 at 11:39 AM, Gordon Woodhull <gordon_at_[hidden]> wrote:
> As you can see, the sandbox version now has an iterator-based design rather than using recursion.  I also implemented a parser for angly expressions like graph<node<A, edge<t, B>, edge<u, C> >, ...> but I admit that probably seems pretty esoteric to most people.  (See metagraph.info)
>

Wait, now I'm confused; the sandbox/metagraph/
<https://svn.boost.org/svn/boost/sandbox/metagraph/> (from what I can
tell, anyway) uses the original recursion-based design (but includes
the angly parser), while sandbox/mgl/ (which I hadn't seen before) has
iterator-based design, but no angly parser.  What am I missing here?
Does metagraph now consist of both folders?  As a side note, I can't
tell whether "angly expression" refers to the profusion of angle
brackets, or to some theoretician named "Angly" who works with DFAs :)

>> Anyway, the single biggest flaw I see with the current BFS and DFS
>> (and the BGL models they're based on) is that there is no way for the
>> user to specify a termination condition in the base algorithm.  It
>> seems silly that an algorithm called "Search" can't end without
>> traversing the whole connected component!  Indeed, if there were
>> simply an optional predicate determining whether a candidate vertex
>> should be added to the stack/queue, I wouldn't have needed to write a
>> separate algorithm for topo sort.
>
> Yes, that certainly makes sense.  After all we can't throw an exception as we can in BGL, at least not without Abel's creative monad-based MPL extension. [1]

Compile-time exception propagation is certainly an interesting
concept, especially considering how poorly compilers do reporting
errors for metaprogramming.  I actually stumbled across the metatest
suite from the same group of libraries not long ago, and it's good
stuff.  However, I think if we did incorporate it, we'd need a way to
make it optional, since there will likely always be people who don't
want to pay the extra cost for using exceptions.  To enable errors, I
don't see how we could get around requiring the do / let notation for
propagating monads, but perhaps a little preprocessor magic could
disable them?  I'll have to think on that.

For topological sort in particular, what I have simply returns partial
results for everything that _can_ be sorted, leaving cycles and
components lower in the ordering behind.  That makes it so you can try
to sort without doing any checks, and if all nodes are returned,
you're done.  If not, you break cycles on the remaining subgraph, then
continue sorting (this is exactly what I do in my own use case).

> If you see how to write a patch for that, I'd be glad to have a co-author.  (The iterator design is based on Franz Alt's feedback and his alternative MGL. [2])

I will write a patch, once I'm sure where the definitive home for this
library is at the moment.  My impression was that iterators and
recursion each had their pros and cons, so I'd be interested to hear
the rationale for switching.

> Topo sort is also one of the algorithms needed before this goes to review.  Josh mentioned an interesting fusion dataflow application on the Spirit mailing list. [3]

Here, I see mgl already has a simple dfs-based solution, which is
probably fine as long as find_cycles is also provided - which again
begs the question, where is the merging happening?

Best,
-Nick Kitten

Software Engineer
Center for Video Understanding Excellence
ObjectVideo, Inc.
http://www.objectvideo.com