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

[Benedikt Huber]

Daniel Kraft schrieb:
> 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 hope the following explanation is correct, apologies otherwise)
The fgl is build upon the concept of Inductive Graphs, described in
Martin Erwig's "Inductive Graphs and Functional Graph Algorithms"
(http://web.engr.oregonstate.edu/~erwig/papers/InductiveGraphs_JFP01.pdf).
The basic idea is that for traversals, you don't mark visited notes,
but decompose the graph like that:

 > (nodeContext,restGraph) = matchAny graph
 > {- or -}
 > (nodeContext,restGraph) = match nodeId graph

This is in some sense 'more functional' than relying on tables for 
marking visited nodes.
DFS e.g. is implemented as (comments for clarification)

 > xdfsWith :: Graph gr => (Context a b -> [Node]) -> -- neighbours
 >                         (Context a b -> c) ->      -- compute result
 >                         [Node] ->                  -- start
 >                         gr a b ->                  -- the graph
 >                         [c]                        -- result list
 > xdfsWith _ _ []     _             = [] -- no more nodes to visit
 > xdfsWith _ _ _      g | isEmpty g = [] -- empty graph
 > xdfsWith d f (v:vs) g =
 >   case match v g of                    -- decompose graph
 >       -- compute result, add neighbours to todo list, recursive dfs
 >       (Just c,g')  -> f c:xdfsWith d f (d c++vs) g'
 >       -- Couldn't find node, continue
 >       (Nothing,g') -> xdfsWith d f vs g'

There's certainly more to say about the fgl, just read the paper.

Now for many applications this is fine, and the fgl is indeed a fine 
library. But obviously there is some overhead in matching, and the API 
is sometimes a little difficult to understand. And it's not the only way 
to do graph algorithms in haskell.

>> 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"
Acyclic graphs are not tree-like.
The point about trees is that sometimes it is useful to view them as 
general purpose graphs, so they should also be represented in a graph 
library. However, in my opionion the library should also have a 
specialized representation of trees, as most algorithms are much simpler 
(Like containers' Data.Tree).

> 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?
 From an implementation point of view, yes, adjacency lists, as arrays 
or trees, and matrices.
But there is a wide range of possibilities for algorithms, from monadic 
implementations (using ST/UArray) to inductive graphs.
For efficient algorithms, somethink like Array's freeze/thaw seems to be 
a good idea, too.

benedikt