On Wed, Jun 24, 2009 at 3:21 AM, Ivan Lazar Miljenovic<[email protected]> 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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
