[Haskell-cafe] Generic Graph Class
andrewhhunter at gmail.com
Wed Jun 24 19:13:24 EDT 2009
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.
More information about the Haskell-Cafe