Hi Joel, Christophe, Eric,
I think you should talk to Gordon Woodhull. He's building a metagraph
>> (among others) library, which I am going to use in msm for
>> compile-time calculations and fsm analysis. This means there will be >> temporarily a metagraph library inside msm as proof of concept until
>> there can be a review.
>> Maybe he can adapt this library for proto analysis?
>>
>Oh yeah, will save me some time indeed.
>Mayeb we shoudl invite him over here ?
I just sent him a mail. BTW the metagraph library is in the sandbox,
and a potential usage with msm was sent by Gordon on the devel list
just at the end of the BoostCon.
Sorry for the slow response - been on vacation offline.

For sure, trees are on my roadmap, as metagraph is a library that attempts to generalize all things graphlike. But I can't claim to have the best solution yet.

The tree can be thought of as a special case of the graph where each vertex has exactly one in-edge (or zero, if it's a root).

The nice thing about traversing trees is that you don't have to worry about cycles, so you don't need a color map if you know your tree is connected - way more efficient.

I wonder if Dan Marsden's Traversal library would solve this out of the box? http://boost-spirit.com/dl_docs/traversal/html/traversal/introduction.html

The way I would solve it is to create an adapter that makes a Proto tree look like a graph... Like Boost.Graph, Metagraph is designed to allow adapting any metadata that is already graphlike to have a graph API. (This wasn't the right approach for MSM because there's nothing in those tables that immediately answers "what are the edges for this vertex?")

If there is interest, I could probably pull this together pretty quickly, as Proto already has such an expressive API. Then we'd immediately have inefficient implementations of DFS & BFS and I could see if there's a good way to factor out the color map stuff to make it speedy.

The main API debate when it comes to traversals is "visitors or iterators?" Currently metagraph takes the visitor approach from Boost.Graph, which are more general and expressive, but iterators are often more convenient. Any opinions here? AFAIK we don't have coroutines or continuations in C++ metaprogramming to make the inversion of control easier. ;-)

Thoughts?

Gordon


_______________________________________________
proto mailing list
proto@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/proto

Reply via email to