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!