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 http://www.haskell.org/ghc/docs/latest/html/libraries/fgl/Data-Graph-Inductive-Query-MST.html 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 <[EMAIL PROTECTED]>: >> 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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
