Hi Gordon, On May 14, 2007, at 11:59 PM, boost-request@lists.boost.org wrote:
From: Gordon Woodhull <gordon@woodhull.com> Date: May 14, 2007 11:45:23 PM MDT To: boost@lists.boost.org Subject: [boost] "beyond graphs" Reply-To: boost@lists.boost.org
Hullo fellow Boosters,
I am writing especially to those of you in Aspen, but also to anyone out there who is interested in, or who has already implemented, any kind of "meta" graph (network). I would like to create or contribute to some Boost libraries for graphlike structures / "metagraphs" / higher order graphs / whatchamacallits.
Below I describe some ideas simplistically/vaguely, both for lack of time and to try to grab the interest of people who have thought about these things but perhaps not in quite the same way.
So far I have thought of three general types of graphs which are beyond the scope of graph libraries I know about: - Graphs in metadata, i.e. graphs of C++ types. This seems to be pretty easy to implement using MPL and I did this a couple of years ago, though poorly. I.e. it's easy to create a BGL-like interface with angle brackets instead of parentheses. :-) - Graphlike structures which are not graphs. Actually any objects which point to other objects form a graph of sorts; what we know as "graph" happens to be the special case where an edge points to two nodes and nodes point to a bunch of edges. What if there are more types than just Node and Edge, or they don't look quite like that? This is something like a Fusion for heterogeneous/polymorphic graphs. - (Here is my root problem.) Graphs that refer to other graphs, such as subgraphs, graphs at different layers of detail (where a node/edge at one level corresponds to a subgraph at another level), constraints on graphs... I have maybe mostly figured out a system for the last, which relies on the other two. Any of the three might be generally useful; I really need the last because it's prohibitively difficult and/or inefficient to maintain correspondences between graphs, and all of my dynamic graph drawing problems keep spawning more corresponding graphs!
All very interesting stuff! On the graphs in metadata/metaprogramming... I'm about to embark on a project to enable the use of normal run-time language features during compile time. Perhaps ultimately this would mean we could use the BGL as-is to manipulate type information at compile time. Of course, this won't be achieved for some years, so looking at what can be done in current C++ is also very interesting.
Disclaimer: because I'm interested in dynamic (changing) graphs, I'm looking at the problem as a bunch of node and edge objects pointing to each other, and using intrusive containers for efficiency/locality of reference. But I'd like to generalize wherever possible.
Anyone who is here in Aspen who's interested in these ideas, please seek me out. Anyone else, please write me. I think I have some good ideas about how to proceed, and I will write up more specific descriptions, but first I would like to know what of this space has already been explored, additional requirements from similar applications, etc. My impression is that, with the reuse of MPL, Fusion, BGL, STL, and intrusive containers, none of this would require a lot of code, but there is a LOT to be designed and abstracted. I see it as at least three libraries, each depending on the last in the order above.
Wish I was still in Aspen to talk with you more about this! Cheers, Jeremy ______________________________________ Jeremy Siek <jeremy.siek@colorado.edu> http://www.cs.colorado.edu/~siek/ Visiting Assistant Professor Department of Computer Science University of Colorado at Boulder