Re: [boost] [gsoc] Interest in BGL v2?

Subject: Re: [boost] [gsoc] Interest in BGL v2?
From: Gordon Woodhull (gordon_at_[hidden])
Date: 2011-03-31 23:55:57

Thanks for the overview of changes, this is helpful and reassuring.

On Mar 31, 2011, at 6:23 PM, Andrew Sutton wrote:

>> It sounds to me like you are going to end up keeping the BGLv1 functional graph concepts for compatibility, and also providing STL-style OO concepts (I prefer this aesthetic too).  I'll strive to be compatible with both, if possible.
> 
> There are going to be some direct analogs, but they won't be the
> "same". Different names, (hopefully) clarified semantics, etc. For
> example, vertex_descriptor and edge_descriptor simply become vertex
> and edge and are required to be convertible to bool (so you can test
> to see if they're valid or not).

Sounds reasonable. 

> The edge function is replaced by
> get_edge, with adjacency matrices (eventually) supporting m(u, v).

Not sure what you mean here - just a rename?

> AdjacencyGraph is probably going to go away since adjacency is just an
> abstraction over incidence.

I still have to look up the difference between adjacency list and incidence list, every time; not sure why those always sound like the same thing.  

But you're talking about AdjacencyGraph - yeah, I never saw the point of iterating over adjacent vertices instead of the edges that lead there.

> Oh... we don't support "edgeless" graphs, but the BGL doesn't really
> do that either.

You mean ForwardSequence of nodes?  :-D

>> I don't see how the old graph concepts are confining in any way, if anything they are sometimes too loose, e.g. when a node object is self-sufficient and you don't need the graph to lookup its edges.  Not that I'm complaining; I understand why they are this way.
> 
> They're confining in the sense that trying to model them would
> actually constrain the design to matching those semantics. We don't
> want to follow suit. We want to reevaluate and redesign.

I still don't see it, since the BGL concepts supported all known graph interfaces.. but I'll wait and see what you come up with.

> On a side note, we actually went through a design iteration where we
> considered making nodes (and edges) self-sufficient. It ends up
> requiring avoidable overhead for vertex and edge objects in the
> general case. We didn't want to mandate the additional memory costs,
> so we're stuck with the same kinds of interface. You need the graph
> for all of your interesting calls.

Yes, my LGraph library has those annoying graph_ pointers per node/edge.  I only support the dynamic case, so it's not a big deal for me.

>> +1 on all this - I'll be watching with rapt attention, and following your lead.
> 
> Maybe we'll have a user in the future? :)

I doubt that.  The problem is still the same as a decade ago: BGL doesn't really support higher-order graphs.  BGL's sort of halfway-there subgraph support was an attempt to bring me and Dynagraph into the fold.

Now it seems that our designs are diverging even further.  Metagraph attempts to tackle the general higher-order graph problem, and that definitely requires generative programming.  And BGL is moving toward straight templated classes, it sounds like.

I'd argue it's a good thing to have some friendly competition, like Polygon vs Geometry, Statechart vs MSM, Regex vs Xpressive.  It'll keep us both honest and hopefully lead to an improved design for both libraries.

Cheers,
Gordon