Hi Nick, On Feb 2, 2012, at 1:20 PM, Kitten, Nicholas wrote:
As you can see, the sandbox version now has an iterator-based design rather than using recursion. 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
On Fri, Jan 27, 2012 at 11:39 AM, Gordon Woodhull <gordon@woodhull.com> wrote: the angly parser),
Sorry; I thought I had checked in the iterator versions. They are there now.
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?
No, MGL is a competing library by Franz Alt that I've learned a lot from. The story is that Christophe Henry badly needed a graph metaprogramming library for verifying MSMs, so he encouraged Franz to write that one. I had already written MPL.Graph but hadn't publicized it much. I think my design is better (more closely parallels BGL; tighter metafunctions) but Franz's is somewhat faster and more memory-efficient. Part of that was the iterators, which I've now adopted.
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 :)
Yep, just my made-up name for these sorts of EDSLs. :)
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.
Yes, I think it may be too expensive for everyday use until compilers catch up, though I haven't tried it yet. Note you don't need exceptions to interrupt search with an iterator-based design.
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.
This design makes more sense to me than just dying if there are cycles.
If not, you break cycles on the remaining subgraph, then continue sorting (this is exactly what I do in my own use case).
I presume you mean you build a new graph with the cycles broken, since MPL.Graph doesn't (yet?) support mutable graphs.
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.
Do you know any resources comparing iterators and recursion in TMP? The reason I switched is that MPL.Graph was *dramatically* slower on my old machine, because template recursion seems to use a lot more memory and so it ran out of physical memory. I know the Abrahams/Gurtovoy book strongly advises against deep recursion - but compilers may have changed. The new design, with an explicit stack, is more complex but I think more powerful. It's probably worthwhile to measure the performance difference. On a new machine with more RAM, I didn't really see much difference between MGL and either version of MPL.Graph, so I kind of stopped worrying about it.
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?
So far there has only been conceptual merging - his coding style is way different. I think once MPL.Graph has topo sort, strong components and/or biconnected components, and maybe something fancy like Dijkstra's shortest paths (requires a heap metadata structure), it'll be ready for review. Any help would be appreciated! Cheers, Gordon