Re: [boost] [metagraph]

Subject: Re: [boost] [metagraph]
From: Gordon Woodhull (gordon_at_[hidden])
Date: 2012-01-27 11:39:27

Hi Nick,

Glad to hear you're using MPL.Graph!

On Jan 27, 2012, at 11:07 AM, Kitten, Nicholas wrote:
> What's the current status of metagraph / mpl_graph?  I've been using
> msm::mpl_graph for error-checking/scheduling in a compile-time filter
> graph framework (similar to state machines, but focus is on data
> flow), and I'd certainly like to see more.  As is, I've already
> implemented a topological sort based on the BFS which doesn't yield
> errors on cyclic graphs (which I'd be happy to contribute if you don't
> already have one), and I have some thoughts on improvement.  I saw the
> BoostCon slides and the current state of the sandbox, and I was
> wondering if there's more code lurking out there somewhere,
> unchecked-in.

I made a lot of progress over the summer, but unfortunately I've been distracted with real-world concerns since then.  

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)

> 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]

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])  

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]

> The other thing is that not all of the listed visitor operations are
> called in the current implementations.  Adding things like
> "initialize_vertex" and "non_tree_edge" to BFS is an easy fix.

Yes, that certainly should be fixed too.

Cheers,
Gordon

[1] http://abel.web.elte.hu/mpllibs/metamonad/index.html
[2] https://svn.boost.org/svn/boost/sandbox/mgl
[3] http://boost.2283326.n4.nabble.com/caching-fusion-map-idea-query-td3797738.html