Boost logo

Boost :

Subject: Re: [boost] Boost.Graph Metagraph project
From: Gordon Woodhull (gordon_at_[hidden])
Date: 2011-01-16 03:10:17


On Jan 15, 2011, at 11:23 PM, caustik wrote:

> This sounds relevant to my interests -- Can these meta-graphs be recursive?
> In other words, can a meta-graph contain a subgraph of itself as a node?

Those sorts of higher-order graph problems are why I started thinking about metagraphs many years ago. When I found out about MPL I realized that all kinds of - graphs at levels of detail, subgraphs, bipartite graphs, graphs within graphs, graphs of graphs - could be implemented by using graph metadata graphs to describe the structure of the runtime graphs.

The higher-order runtime graph data structure ("metagraph") is no longer simply vertices and edges, it is many types, but the way those types are connected is a compile-time graph "pattern". (Or even several overlaid patterns. For instance, a node in one pattern is also a subgraph in another pattern.)

Expect progress on this in 2011.

> Also curious if, and to what extent, the project might support MPI?

Not sure which way you mean this.

* MPL.Graph is purely compile-time (wish we could parallelize that!).

* I haven't thought about parallelizing metagraphs yet because I haven't written them yet - I'll be sure to get some ideas from Parallel BGL.

* Joel Falcou has this intriguing Quaff project to build up compile-time skeletons of data flow for parallelized algorithms and IIRC we talked at BoostCon about how it would be neat to generalize skeletons to compile-time graphs. Anywhere you know the whole contents of the graph at compile time - in that case, the contents of some expressions - you might want to consider MPL.Graph for paying the abstraction penalty upfront instead of passing it on to your users.

Thanks for the interest!
Gordon


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