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
> 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
> 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
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-
[*] Now *that* is a library that could benefit from variadic templates!
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk