Re: [boost] "beyond graphs"

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2007-05-16 10:39:06

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