On Wed, Jun 24, 2009 at 3:21 AM, Ivan Lazar
Miljenovic
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