[Haskell-cafe] Re: Graph library, was: Haskell.org GSoC

[Daniel Kraft]

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!

Yours,
Daniel