Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk