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

[Louis Wasserman]

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.louis at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090212/8461f111/attachment.htm