Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk