[Haskell-cafe] Re: Graph library, was: Haskell.org GSoC
d at domob.eu
Thu Feb 12 10:27:06 EST 2009
Benedikt Huber wrote:
> I would also like to see a project working on a new graph library.
> Currently, there is at least Data.Graph (just one Module, package
> containers), based on Array - adjacency lists, and the functional graph
> library (package fgl).
I don't know those, but "functional graph library" suggests it is meant
to be something like what we're discussing here (and this is also what
Google returns for Haskell + graph library). What's the problem with it
or in which way is it different?
> I think a good general purpose graph library is tricky though:
> - There are lot of variants of graphs (trees, bipartite, acyclic,
> undirected, simple, edge labeled etc.), hard to find adequate and easy
> to use abstraction.
Well, while an undirected tree / acyclic graph can obviously be
represented as a "tree structure", all the others would resolve around
having nodes and for each node a list of edges to neighbouring nodes; at
least concept-wise, wouldn't they? Then one could build an abstraction
on top of this with a node class able to name neighbouring nodes or
something like that to get rid of a fixed representation (and allow
working on graphs constructed on the fly as opposed to being stored in
memory), but I think this would be the basic way to go. Everything else
(whatever could benefit from a substantial different representation)
could go in a seperate library or specialisation. Or do I miss
something here? (No expert with regards to graphs and their use-cases yet.)
> code.haskell.org / community.haskell.org
> provides webspace, trac, mailing-list, darcs.
Thanks for the pointer!
More information about the Haskell-Cafe