Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at