[Haskell-cafe] Re: Graph library, was: Haskell.org GSoC
Daniel Kraft d...@domob.eu wrote: Don Stewart wrote: - Graphs. True graphs (the data structure) are still a weak point! There's no canonical graph library for Haskell. That sounds interesting... What do you mean by no canonical library? Are there already ones but just no standard one? But in this case, I don't think adding yet another one will help :D Or isn't there a real general graph library? http://hackage.haskell.org/cgi-bin/hackage-scripts/package/fgl ? -- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Graph library, was: Haskell.org GSoC
Daniel Kraft schrieb: Don Stewart wrote: - Graphs. True graphs (the data structure) are still a weak point! There's no canonical graph library for Haskell. That sounds interesting... What do you mean by no canonical library? Are there already ones but just no standard one? But in this case, I don't think adding yet another one will help :D Or isn't there a real general graph library? 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 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. - There is no single 'best' implementation (mutable vs. unmutable etc.). - Its hard to find good traversal and zipper abstractions, though fgl has some nice ones. - The complexity of algorithms varies greatly depending on the particular kind of graph. Anyway, that's why it is challenging and interesting. If so, this would be a nice thing to do :) I could look at existing ones (like Boost's graphs) to get a feeling for how an interface might look like and what functionality to implement. BTW, is there some sort of project hosting specifically for such Haskell projects? Or should I go with sourceforge (for instance) for developing this, if I gave it a try? code.haskell.org / community.haskell.org provides webspace, trac, mailing-list, darcs. benedikt ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Graph library, was: Haskell.org GSoC
Benedikt Huber benj...@gmx.net writes: I would also like to see a project working on a new graph library. [...] I think a good general purpose graph library is tricky though: And please, let us have a library that is scalable! This means there should be one (or several) benchmark application(s) that do non-trivial work on graphs of non-trivial sizes. -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Graph library, was: Haskell.org GSoC
Benedikt writes: 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. - There is no single 'best' implementation (mutable vs. unmutable etc.). - Its hard to find good traversal and zipper abstractions, though fgl has some nice ones. - The complexity of algorithms varies greatly depending on the particular kind of graph. Anyway, that's why it is challenging and interesting. Hear, hear! From what I can tell, fgl is the closest thing I've seen to a usable remotely-general-purpose graph library in any language. With all apologies to Siek, et al., the boost graph library is exceedingly complex, to the point of being unusable (one man's opinion) to all but the most ardent lovers of C++ template metaprogramming. That's no knock on its designers, it's just that the graph problem provides an exceptionally challenging tension between managing complexity and providing acceptable performance--on top of trying to achieve respectable generality. It seems to me that anyone who aspires to author a Haskell graph library that can be regarded as canonical really ought to first know fgl inside and out, and probably ought to consider extending that library, vs. starting from scratch. In fact, it was my current work with non-trivial graph problems that ultimately led me to justify switching to using Haskell for my day job a couple of months ago (after having investigated and abandoned other possible solutions in other languages that would have been a much easier sell to my higher-ups). So I have a pressing professional interest on hearing others weigh in on this topic, and particularly on the benefits/shortcomings of fgl. I'd especially like to hear from Martin Erwig on this topic. Martin? You listening? --Tracy ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Graph library, was: Haskell.org GSoC
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Graph library, was: Haskell.org GSoC
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
[Haskell-cafe] Re: Graph library, was: Haskell.org GSoC
fgl uses pretty much the most beautiful way of abstracting graphs I've seen; a brief review: type Context a b -- a collected representation of a vertex's number, label, and all information on edges going into and out of that vertex match :: Graph gr = Node - gr a b - (Maybe (Context a b), gr a b) -- if a vertex is in the graph, extracts its adjacency information in a Context and returns the graph without that vertex () :: DynGraph gr = Context a b - gr a b - gr a b -- melds a vertex and its adjacency information into the graph I've been doing a huge amount of messing around with graph algorithms recently, and this inductive style of graph querying and modification make several algorithms far more intuitive than most imperative implementations I've seen. In addition, both of these lend themselves well to use in a State monad. Take the following code to extract the connected component of a vertex in an undirected graph: extractComponentM :: DynGraph gr = gr a b - Node - State (gr a b) (gr a b) extractComponentM partialComponent v = State (match v) = maybe (return partialComponent) expandContext where expandContext cxt = liftM (cxt ) (foldM extractComponentM partialComponent (neighbors' cxt)) extractComponent :: DynGraph gr = gr a b -- the initial graph - Node -- the node whose component to find - (gr a b, gr a b) -- the original graph without the component, and the component extractComponent g v = runState (extractComponentM empty v) g That's far more compact -- and intuitive to someone familiar with both fgl and the State monad -- than a standard connected-component finder in an imperative language, speaking as someone who wrote code along these lines imperatively for several years. (Fun fact: I've been working on a nice encapsulation of priority queues as monad transformers to make other common graph algorithms both efficient and make them this pretty to read, too. Any thoughts on that would be appreciated.) I strongly feel that fgl, though it could be improved in some areas, makes a better truly general graph abstraction than anything else I've seen. Areas that could specifically be improved include the stuff that uses LRTrees, and other stuff that isn't especially intuitive, elegant, or even efficient in fgl's implementation. Louis Wasserman wasserman.lo...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
