Hi Gordon, On May 14, 2007, at 11:45 PM, Gordon Woodhull wrote:
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.
Great!
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. :-)
Yikes! I originally thought you wanted to take static information about C++ types and turn it into a dynamic graph for use in the BGL, but you're talking about doing this entirely statically... it would certainly be very, very interesting to try to implement some core graph algorithms in the template system.
- 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.
The notion of a "vertex" or "edge" in this case becomes a very, very abstract entity, which can have multiple different types. In the Graph library, this would probably mean that the vertex or edge is actually a variant, or an any, or some other kind of "container" type that points to an object of unknown type.
- (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!
The BGL has a notion of subgraphs, encapsulated in the "subgraph" adaptor at http://www.boost.org/libs/graph/doc/subgraph.html . The BGL "subgraph" is an induced subgraph that allows one to build a tree of such subgraphs, and it maintains those subgraphs as one makes changes to the root graph. The BGL "subgraph" is not a multi-level graph data structure, however;. Vertices in the "subgraph" are just vertices; they aren't subgraphs. We've thought about graphs at different levels of detail, because they are extremely important in a lot of applications. Layout, visualization, and partitioning were our areas of interest at the time. Although we never came up with anything concrete, we're still very interested in this notion of multi-level graphs.
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.
I'm also here in Aspen, and I'm interested in chatting about your ideas. Let's see if we can find each other among the BoostCon horde :) I'm relatively easy to find... I'll be giving the concepts talk Wednesday and Thursday morning. - Doug