[Haskell-cafe] functional graphs

Christian Maeder Christian.Maeder at dfki.de
Mon Jan 21 04:49:14 EST 2008

Thomas Hartman wrote:
> I don't think this will work.
> From
> http://www.haskell.org/ghc/docs/latest/html/libraries/fgl/src/Data-Graph-Inductive-Graph.html
> the minimal implementatin for Graph is
> -- | Minimum implementation: 'empty', 'isEmpty', 'match', 'mkGraph', 'labNodes'
> ....
> -- | Decompose a 'Graph' into the 'MContext' found for the given node and the
>   -- remaining 'Graph'.
>   match     :: Node -> gr a b -> Decomp gr a b
> Basically, match given a node returns the graph minus the node, and a
> "context for the node which has ingoing edges/labels, outgoing
> edges/labels, the node itself and the node label. With the & operator
> you can compose these two things and get back your original graph.
> With the implementation you have described I can't see any way to
> implement this match function, unless per my above comment you're
> doing something weird like having no graph edges, or all possible
> graph edges. And then why use a graph?

It's a _complete_ graph, i.e. there is an edge between every two nodes.

I want to compute the minimum spanning tree using
without rewriting the FGL code and without generating the many edges
explicitly. Eventually I want to have a "proper" tree (Data.Tree.Tree)
for pre-order traversal.

Preorder traversal of a MST gives a sub-optimal solution (not worse than
twice as long as the optimum) for the travelling salesman problem (TSP).

I may be on the wrong track, though.

Thanks Christian

> Unless I'm missing something...
> Thomas.
> 2008/1/18, Christian Maeder <Christian.Maeder at dfki.de>:
>> Hi,
>> Given a complete graph as a list of nodes whose edge labels are given by
>> a function over two nodes:
>> data CGraph a b = CGraph [a] (a -> a -> b)
>> Can I define an instance for the fgl Graph class?
>> import Data.Graph.Inductive.Graph
>> instance Graph CGraph where
>>   empty = CGraph []  -- and now?
>> I had no idea how to define empty (except using undefined).
>> I thought of requiring a context for the node labels of type a, but this
>> type is not mentioned in the class header. So it looked to me like the
>> impossibility to define sets (requiring an Ord) as monads. (i.e.
>> instance Monad Data.Set.Set)
>> Any working proposals for my graph problem?
>> Cheers Christian

More information about the Haskell-Cafe mailing list