[Haskell-cafe] Generic Graph Class

[Ivan Miljenovic]

Yay, someone read my proposal! :p

2009/6/25 Andrew Hunter <andrewhhunter at gmail.com>:
> 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:

I was thinking about this, because graphviz at the moment uses the
label field of nodes to determine which cluster it belongs to, etc.
However, the problem with this is that Data.Graph doesn't have any
labels...

> a) some amount of modification--new vertex, additional edge, what have you...

Data.Graph can't really be modified in terms of adding a new vertex,
unless you go and expand the array it uses and copy everything over
(adding a new vertex, however, is indeed possible).

> b) Labeling of vertices/edges, ideally parameterized by label type.

As I said, Data.Graph doesn't have any concept of labels; besides,
this will require MultiParamTypeClasses and FunDeps AFAICT (and we
should probably try to make this compatible with Haskell98 rather than
using extensions).

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

My original thoughts (which I didn't include with the proposal) was
that algorithms _would_ use internal state.  My main impetus of
thinking about this class was graphviz and hgal, which already use an
internal state anyway (well, maybe not hgal as much; I've been trying
to work my way through it a bit at a time now and then trying to
improve its efficiency for what I need).

Admittedly, it might be nice to have these extra features; it just
might not be practical if we want the widest possible "audience" of
the class.  The other alternative is if we have a second class that
allows for updates, etc. but requires the first class as a dependency.

-- 
Ivan Lazar Miljenovic
Ivan.Miljenovic at gmail.com
IvanMiljenovic.wordpress.com
Casey Stengel  - "All right everyone, line up alphabetically according
to your height." -
http://www.brainyquote.com/quotes/authors/c/casey_stengel.html