Re: [Haskell-cafe] Generic Graph Class

Some of us on #haskell last night (well, night for me :p) were discussing this, and we're going to start a new project to implement an extended version of my proposal. The working project name is simply "graph" (hey, we couldn't think of anything better!). If you want to join in the fun, talk to either myself (ivanm), Cale or mmorrow on #haskell. Ivan Miljenovic writes:

Yay, someone read my proposal! :p

2009/6/25 Andrew Hunter :

...

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@gmail.com IvanMiljenovic.wordpress.com