Re: [boost] Summer of Code 2008 [Graph version 2]

From: Andrew Sutton (asutton_at_[hidden])
Date: 2008-03-07 08:37:55

>> I played with this last summer - it doesn't actually seem to solve
>> the problem. In fact, it actually makes it a little bit worse because
>> it hides (the inevitable) compiler errors behind a thick wall of
>> preprocessor code. The problem is not passing optional parameters,
>> but the fact that doing so is often used to select different versions
>> of the same algorithm. It becomes very difficult to document.
>
> Perhaps we need to draw a line between customizing an algorithm (which
> could/should(?) be done through optional parameters) and selecting
> different variants of an algorithm (which should not be done through
> optional parameters). Drawing that distinction might simplify the use
> of these algorithms.

I think that's definitely a good idea. While it's not really an  
implementation issue, documenting functions, they're types, and  
concept requirements becomes ridiculously complicated when there are  
lots of options - especially if those options actually control the  
behavior of the algorithm.

>> I don't know... maybe I'm thinking too hard. Building a version of
>> BGL2 based on the current code base (or whatever's in sandbox) is
>> just as good a summer project.
>
> I think we're just envisioning different "final products" for BGLv2,
> because we use BGL for different things. Today, I happen to be working
> with VTK, which has a new vtkGraph data type. They provide the
> appropriate graph_traits specializations, free functions, etc. so that
> a pointer to a vtkGraph (vtkGraph*) works off-the-shelf in BGL
> algorithms: no wrappers required. That's exactly the kind of thing
> that I believe the BGL excels at, and I think it's important for
> future revisions of the BGL to support that use case. There's a lot of
> cruft I'd like to eliminate---non-partial-specialization hacks, the
> property<...> class, etc.---and bits that I'd like to clean up---
> property map creation is too hard, adjacency_list has too many knobs
> only useful in rare circumstances, etc.---but I think, fundamentally,
> the Graph concepts are just about right.

I can see (from my previous comments) why you'd think we're talking  
about different final products, which probably means that I did a  
poor job communicating my ideas :) I'm starting to see the BGL as  
three distinct libraries: the generic interface (concepts), the  
algorithms (based on concepts) and some graph type implementations.

The changes to the latter two (algorithms and types) that I'm kicking  
around don't (or shouldn't) necessitate changes to the generic  
interface. It actually sounds like your cruft isn't too different  
than what I'm actually envisioning. I just want to put a little more  
focus on designing the class interface as a refinement of the generic  
interface.  After all, STL containers provide coherent, usable  
interfaces as refinements of the concepts that enable the STL  
algorithms.

I definitely agree with your list of things that need to be worked  
on... I'm not entirely sure of the best way to solve some of them.  
Maybe this summer would be a good time to experiment with some  
alternative designs since removing much of the cruft could  
potentially obsolete legacy BGL code - at least the declarations of  
graph types; probably not generic code. Getting rid of the property<>  
class will break the classes I wrote last summer :)

Besides, new designs might give the opportunity to start thinking  
formally about new concepts like subgraphs and hypergraphs.

I'll try to start making a coherent (and hopefully realistic) list of  
possible goals for the summer and their rationale. I'll try to send  
it up sometime in the next week or so to see if it anybody would be  
interested in mentoring such a proposal.

Andrew Sutton
asutton_at_[hidden]