[boost] "beyond graphs"

From: Gordon Woodhull (gordon_at_[hidden])
Date: 2007-05-15 01:45:23

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!

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.

My apologies if I have missed any prior discussion.  I have been lurking 
around Boost for a while but just joined the list.

Cheers!
Gordon

P.S. Extra apologies for the length of this letter.  Been thinking about 
this for a few years...