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

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2008-03-05 09:49:09

On Mar 5, 2008, at 7:32 AM, Andrew Sutton wrote:
>> 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 don't imagine that variadic templates would help all that much, but  
who knows?

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

These are pretty important operations... I don't think they can go  
away, even though they do require linear time for some data structures.

> Also, I never did understand why
> certain functions weren't just member functions (like add_vertex()).

It's so that people can use their own graph types with BGL  
algorithms. I guess one could have a member "add_vertex" in  
adjacency_list and also have the free function "add_vertex" that just  
forwards to the member, which might be easier for users... but I'm  
not convinced that the redundancy would help.

> 2. Revisit the interface and implementation for BFS/DFS, and get rid
> of the parameter passing.

... or use the Boost.Parameter library, which simplifies passing  
optional parameters. [*]

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

Interesting. There's a lot of internal reuse of BFS and DFS that  
would go away if they lost some of their flexibility, but perhaps  
there's a way to have both.

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

DFS supports a "TerminatorFunc" to stop early, but this might not be  
the right approach. Why does everyone dislike throwing an exception  
to terminate the search? I bet if someone went ahead and benchmarked  
the two options, the exception would be faster for graphs of non- 
trivial size.

        - Doug

[*] Now *that* is a library that could benefit from variadic templates!