From: Jeremy Siek (jeremy.siek_at_[hidden])
Date: 2007-05-16 19:09:05
Hi Gordon,
On May 14, 2007, at 11:59 PM, boost-request_at_[hidden] wrote:
> From: Gordon Woodhull <gordon_at_[hidden]>
> Date: May 14, 2007 11:45:23 PM MDT
> To: boost_at_[hidden]
> Subject: [boost] "beyond graphs"
> Reply-To: boost_at_[hidden]
>
>
> 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!
All very interesting stuff!
On the graphs in metadata/metaprogramming... I'm about to embark on a
project to enable the use of
normal run-time language features during compile time. Perhaps
ultimately this would mean we could use
the BGL as-is to manipulate type information at compile time. Of
course, this won't be achieved for some
years, so looking at what can be done in current C++ is also very
interesting.
> 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.
Wish I was still in Aspen to talk with you more about this!
Cheers,
Jeremy
______________________________________
Jeremy Siek <jeremy.siek_at_[hidden]>
http://www.cs.colorado.edu/~siek/
Visiting Assistant Professor
Department of Computer Science
University of Colorado at Boulder