Re: [boost] Summer of Code 2008

From: Andrew Sutton (asutton_at_[hidden])
Date: 2008-03-05 07:32:26

>> I've been thinking about Boost.Graph v2. I was hoping to finish the
>> work that I started in the fall. Of course, I was hoping for a little
>> more free reign with the interfaces for this work - source
>> compatibility won't be high on my list of priorities in my proposal.
>
> So long as Visual C++ 6/7 compatibility isn't also high on your list
> of priorities, go for it :)

I think this would be true for any library with a non-trivial  
template component.

> Half of the ugliness of the BGL implementation is in the workarounds
> needed to deal with compilers that can't handle class template partial
> specialization.

Since I'm thinking about being experimental, and SoC is a sandbox  
within a sandbox, maybe it wouldn't hurt to build the next version  
using newer C++ features (esp. variadic templates).

I also have a couple of other goals that don't align very well the  
current implementation either.
1. Making the interface a little less generic without sacrificing  
flexibility. For example, I don't know that the vertex/edge storage  
stuff actually sees much use, and it can cause terrible inefficiency  
if you're not extremely careful with it (e.g., num_vertices()/ 
num_edges() using listS storage). Also, I never did understand why  
certain functions weren't just member functions (like add_vertex()).
2. Revisit the interface and implementation for BFS/DFS, and get rid  
of the parameter passing. It's ugly and causes a lot of problems for  
people learning how to write the code. My gut feeling on this is that  
if you're using optional parameters to have the same algorithm behave  
somewhat differently, then building a new function might not be a bad  
idea. I also want to redesign the searches for "stoppability" -  
either for user-selected termination (as per Loïc's request), or in  
the case of disjoint subgraphs.

I'm also hoping to use the experience as fodder for a class I'm  
teaching in the Fall - Generic Programming and Library Design.

Obviously, it would be nearly impossible to re-implement the entirety  
of the BGL, but I think that taking a long slow look at the  
interfaces and providing a subset with some very common algorithms  
(BFS, DFS, etc...) using new C++ features could provide an  
interesting data point for how new features could be used.

Andrew Sutton
asutton_at_[hidden]