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

From: Doug Gregor (dgregor_at_[hidden])
Date: 2008-03-06 09:31:57

On Mar 5, 2008, at 10:19 PM, Andrew Sutton wrote:

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

Ah. Well, you're right, but I'd eliminate that way of specifying  
properties. Instead, I would do everything with "bundled" properties,  
because they provide a much more solid mapping between the user's  
domain and the graph library.

> 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 one of those, "when you need it, you *really* need it" things.  
Sometimes you need to be able to add edges and vertices quickly,  
without invalidating descriptions. Non-vector containers are great for  
that.

>
>> It's so that people can use their own graph types with BGL
>> algorithms.
>
> Why not just build a simple wrapper class?

One reason not to rely on wrappers is that they must be specified  
every time one uses a BGL algorithm, e.g.,

        breadth_first_search(wrap_as_bgl_graph(mygraph), ...)

By using a traits- and free-function based approach in the BGL, merely  
including the appropriate header makes any existing data structure  
"just work" as a BGL graph.

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

I'm not sure I understand. If we're inhibiting the utility of specific  
graph types/algorithms, then our concepts are probably wrong (or, at  
least, the concept taxonomy itself isn't complete enough).

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

Perhaps we need to draw a line between customizing an algorithm (which  
could/should(?) be done through optional parameters) and selecting  
different variants of an algorithm (which should not be done through  
optional parameters). Drawing that distinction might simplify the use  
of these algorithms.

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

I think we're just envisioning different "final products" for BGLv2,  
because we use BGL for different things. Today, I happen to be working  
with VTK, which has a new vtkGraph data type. They provide the  
appropriate graph_traits specializations, free functions, etc. so that  
a pointer to a vtkGraph (vtkGraph*) works off-the-shelf in BGL  
algorithms: no wrappers required. That's exactly the kind of thing  
that I believe the BGL excels at, and I think it's important for  
future revisions of the BGL to support that use case. There's a lot of  
cruft I'd like to eliminate---non-partial-specialization hacks, the  
property<...> class, etc.---and bits that I'd like to clean up--- 
property map creation is too hard, adjacency_list has too many knobs  
only useful in rare circumstances, etc.---but I think, fundamentally,  
the Graph concepts are just about right.

        - Doug