Re: [Haskell-cafe] functional graphs

Thomas Hartman wrote:

I don't think this will work.

From

http://www.haskell.org/ghc/docs/latest/html/libraries/fgl/src/Data-Graph-Ind...

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 http://www.haskell.org/ghc/docs/latest/html/libraries/fgl/Data-Graph-Inducti... 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 :

...

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