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

Subject: Re: [boost] [gsoc] Interest in BGL v2?
From: Andrew Sutton (asutton.list_at_[hidden])
Date: 2011-04-01 09:47:59

>> 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?

More or less. It also allows us to syntactically differentiate
adjacency matrices from other graph models, which means you can write
a type trait for it. is_adjacency_matrix is (will be) true when m(u,
v) is a valid expression for the types of m, u, and v. This further
means that we can use enable_if to select algorithms based on that
property.

>> 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.

An IncidenceGraph gives you out_edges(g). An AdjacencyGraph gives you
adjacenct_vertices(g). This function is almost universally (within the
BGL) implemented using an iterator adaptor over an out edge iterator.
Our view is that adjacency is exactly that: an adapted view of
incidence.

You're right, though. I think there are close to 0 algorithms that
actually use adjacent_vertices.

>> Oh... we don't support "edgeless" graphs, but the BGL doesn't really
>> do that either.
>
> You mean ForwardSequence of nodes?  :-D

Yup :) I thought about what it would take integrate this kind of graph
into the library, but punted on it :) It's kind of a weird concept
when you're used to thinking about G = (V, E).

> 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.

Fair enough :) I actually don't know much about high order graphs or
their applications, so I'll have to take a look a good look at the
metagraph library. When we eventually get around to defining the
notion of subgraphs, I may ping you for some design criteria. I'm not
at all sure what motivated the BGL solution. That won't be for quite a
while.

> 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.

I like to phrase this argument as "software biodiversity" :)

On a side note, I tried to encourage this perspective with this year's
GSoC effort. I'm not sure it worked as well as I would have liked.
There seems to be a "there can be only one" mentality, and I think
that hurts both our ability to attract and retain student developers
and generate meaningful data points to drive design discussions.

Andrew