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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
