Boost logo

Boost :

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

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.


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

Boost list run by bdawes at, gregod at, cpdaniel at, john at