[Haskell-cafe] Generic Graph Class

[Andrew Hunter]

On Wed, Jun 24, 2009 at 3:21 AM, Ivan Lazar
Miljenovic<ivan.miljenovic at gmail.com> wrote:
> there, each of which uses one of the above approaches.  However, for the
> more "generic" packages that operate _on_ graphs (rather than using
> graphs as an internal data structure),
>
> ...
>
> I thus propose that we work out a generic graph class that can be used
> by the various libraries we have and use, to avoid this duplication of
> effort (I have already proposed that I intended to add such
> functionality to the graphviz library, but I'm throwing open the design
> of such a class to the general community).  This means that even if you
> have to use some custom graph-like data structure in your program, you
> can take advantage of one of the libraries available (e.g. graphviz)
> without having to write your own graph functions for common tasks.
>

This is a good idea and one I support.  (I think I've been told before
that this has been tried w/o a lot of success, but, well...)  My
primary concern is this: you built your class for things that operate
"on" graphs...but there isn't a great distinction.  There are too many
useful graph algorithms that require modification, or at least marking
of vertices/edges (as taken, seen, by distance, color...think and
you'll notice this happens everywhere.)  Thus, it'd be very nice if
the Graph class could have a concept of:

a) some amount of modification--new vertex, additional edge, what have you...
b) Labeling of vertices/edges, ideally parameterized by label type.
c) some amount of modification of those marks, so we can run, say,
DFS, Floyd-Warshall, Dijsktra, Prims without cumbersome external
management of secondary data structures.  This might require the
definition of a GraphAlgorithm monad, which I've been toying with for
a while--I'll see if I can dig up the code if there's desire.

AHH