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

From: Andrew Sutton (asutton_at_[hidden])
Date: 2008-03-05 22:19:21

> I don't imagine that variadic templates would help all that much, but
> who knows?

I thought vertex/edge property specification was built using  
recursive templates. I was thinking of that as an application for  
variadic templates, but I could be way off base :)

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

I wouldn't get rid of the operations - they're pretty fundamental. I  
was just thinking about the underlying storage mechanisms for edge  
lists and vertex lists. I can certainly see arguments for using non- 
vector storage, but I don't know how often its used in practice.

> It's so that people can use their own graph types with BGL
> algorithms.

Why not just build a simple wrapper class? My concern here is that  
trying to provide a generic interface for a number of different  
implementations may actually inhibit the utility of the specific  
implementations of graph types and algorithms within the library.

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

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.

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

That's a good idea. I've always felt a little queasy about throwing  
exceptions as a means of terminating a function when no error has  
occurred, but there may not be anything /too/ wrong with it in this  
case. It would avoid the requirement to check a terminate condition  
in every iteration of the algorithm. Hiding the throw behind a  
function might not hurt either.  Something like finish() or stop().

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.

Andrew Sutton
asutton_at_[hidden]