On Wednesday 29 May 2002 02:58, Hal Daume III wrote:
Is there any particular reason FiniteMap (and hence Set) aren't instances
of Ord? I realize it's weird to define a map to be ordered, but even if
the Ord definition were in some sense nonsensical, being able to have,
for instance, Sets of Sets of things would be really nice.
Check this out. It was working for me last time I used it.
Comments welcome,
--
Eray Ozkural (exa) [EMAIL PROTECTED]
Comp. Sci. Dept., Bilkent University, Ankara
www: http://www.cs.bilkent.edu.tr/~erayo Malfunction: http://mp3.com/ariza
GPG public key fingerprint: 360C 852F 88B0 A745 F31B EA0F 7C07 AE16 874D 539C
module Hypergraph where
import FiniteMap
import Set
-- A hypergraph is a family of sets which are subsets of a vertex set X
-- This implementation uses an edge list representation that
-- directly corresponds to the mathematical definition
-- n index type, w weight type
-- type Hypergraph n w = Array n [(n,w)]
-- show functions for set and finitemap
instance (Show a) = Show (Set a) where
show set = show (setToList set)
instance (Show a, Show b) = Show (FiniteMap a b) where
show vs = show (fmToList vs)
type HEdges l = FiniteMap l (Set l)
data Hypergraph l = Hypergraph (HEdges l) (HEdges l) deriving Show
-- hgraph constructor
-- takes a list of edges
hgraph list = let edges = hEdges list in
Hypergraph edges (dualEdges edges)
-- hgraph edge_list
--hEdges :: [ [a] ] - HEdges a
hEdges el = listToFM (zip [1..length el] (map mkSet el))
-- = Hypergraph (listToFM . mkSet (edge_list)) (listToFM . mkSet (edge_list))
-- compute dual of a given hgraph
dualEdge (edgeIx, hEdge) = map (\x-(x, mkSet [edgeIx])) (setToList hEdge)
dualEdges hEdges = ( (addListToFM_C union emptyFM) . concat .
(map dualEdge) . fmToList )
hEdges
--hVertices el = (zip (map mkSet el) [1..length el])
-- hyper vertices are the dual of the hypergraph
--hVertices hEdges = (foldFM uni emptyFM). (mapFM dual)) hEdges
-- where uni = plusFM_C
--dual hEdges = ( listToFM . map (\(x,y)-(y,x)) . fmToList) hEdges
