[Haskell-beginners] Relatively simple undirected graph library?

[Stefan Höck]

On Mon, Jan 05, 2015 at 07:51:57AM +1100, Stuart Hungerford wrote:
> Hi,
> 
> I've recently started learning Haskell and I'm looking for a library
> to create and manipulate undirected graphs for a small learning
> project.  Ideally I'd like to be able to:
> 
> - represent undirected or directed graphs with vertex type a and edge type b
> 
> - not need to manually maintain mappings between vertex values and
> vertices assumed to be integers
> 
> - be able to add and remove vertices and edges by their values with
> appropriate checks for missing vertices etc
> 
> - find the connected components of a graph
> 
> Looking on Hackage I can see some very sophisticated graph libraries
> including Data.Graph and Data.Graph.Inductive and others, but they all
> seem to need vertices to be integers or not support changing the graph
> once constructed.
> 
> This may well be my ignorance of both graph theory and Haskell but can
> someone point me to a library that meets my needs or should I extend
> the learning process and create one myself?
> 
> Thanks,
> 
> Stu

Hi Stu

I also was in need of a graph library comparable to what you describe,
which I'd like to use later on to represent molecular graphs in
cheminformatics projects. Since I did not find anything that fit my
needs on Hackage, I started writing my own implementation. The code is
not ready for anything and so far it's only unlabeled graphs. However,
adding labelings later on is - from my experience - no big thing
as most of the graph algorithms need only be implemented for unlabeled
graphs.

If you are interested, I could clean up the code and put it on github,
then we could work on it together. 

Many of the things you need like creating edge- and vertex-induced
subgraphs will require only very little work. The same goes for
extracting connected subgraphs and filtering by edge or vertex type.

Stefan