[boost] Re: graph structure interface

From: Dave Abrahams (abrahams_at_[hidden])
Date: 1999-12-07 23:53:57

> With Dietmar's interface, one would have to create a graph object
> class that basically doesn't do anything, and then pass it around in
> the algorithms.

That's perfectly natural in generic programming, and costs nothing on a good
compiler. See for example traits tags used to select algorithm
implementations.

> c) Prettiness and Encapsulation
>
> So far the main advantage of Dietmar's interface is that it makes the
> graph structure easier to implement in some situations. It does this
> by having a graph object participate in every operation. As such I
> would argue that the presense of the graph object is really an
> implementation detail for some graph types, and therefore does not
> belong in the interface used by generic graph algorithms. I think it
> is better to *encapsulate* the existence (or non-existence) of the
> graph object underneath the Vertex and Edge concepts.
>
> One nice side effect of having the Vertex and Edge concepts, and
> removing the graph object, is that the algorithms look more like the
> pseudo-code found in text books and papers, which means that it is a
> closer match to the problem domain.
>
> As Dietmar mentioned previously, the difficulty of implementation
> should be of a lessor concern than the other interfacing issues.
> Therefore I would encourage the move to the slightly more abstract
> but less easy to implement interface of GGCL.

Which do you think will be re-used more often, a particular graph
representation or a graph algorithm? In my experience, I want to re-use many
of the standard graph algorithms on different problem domains which contain
structures that can be seen as graphs. I'd be willing to pay for a little
inconvenience in writing the algorithm if I could easily plug different
graph domains into it. So far, everything I've heard argues for a structure
like Dietmar's (his proposal also resonates with many of the conclusions
I've drawn recently having tried to write generic graph stuff).

-Dave