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.h...