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
> 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).
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk