Re: [boost] "beyond graphs"

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