1N/ACopyright : (c) Christian Maeder and Uni Bremen 2003
1N/AMaintainer : maeder@tzi.de
1N/AStability : provisional
1N/APortability : portable
1N/Asupply a simple data type for (precedence or subsort) relations. A
1N/Arelation is conceptually a set of (ordered) pairs (see 'toList' and
1N/A'fromList'). But the hidden implementation is based on a map of sets.
1N/A'Rel' replaces a directed graph with unique node labels (Ord a) and
1N/Aunlabelled edges (without multiplicity higher than one).
1N/AUsage: start with an 'empty' relation, 'insert' edges, and test for
1N/Aan edge 'member' (before or after calling 'transClosure').
1N/AIt is possible to insert self edges or bigger cycles.
1N/AA transitive path can be checked by 'transMember' without computing
1N/Athe full transitive closure. A further 'insert', however,
1N/Amay destroy the closedness property of a relation.
1N/ACurrently, no further functions seem to be necessary:
1N/A- reflexive closure (for a finite domain)
1N/A- computing a minimal relation whose transitive closure
1N/A covers a given relation
1N/A , transMember, transClosure, fromList, toList
1N/A , image, restrict, toSet, fromSet) where
1N/A-- | the empty relation
1N/A-- | test for 'empty'
1N/AisEmpty :: Rel a -> Bool
1N/A-- | insert an ordered pair
1N/Ainsert :: Ord a => a -> a -> Rel a -> Rel a
1N/A-- | test for an (previously inserted) ordered pair
1N/Amember :: Ord a => a -> a -> Rel a -> Bool
1N/A-- | get direct right neighbours
1N/A-- | get right neighbours and right neighbours of right neighbours
1N/A-- transitive right neighbours
1N/AgetTAdjs r given new =
1N/A getTAdjs r (ds `
Set.union` given) (ds Set.\\ new Set.\\ given)
1N/A-- | test for 'member' or transitive membership
1N/AtransMember :: Ord a => a -> a -> Rel a -> Bool
1N/A-- | compute transitive closure (make all transitive members direct members)
1N/AtransClosure :: Ord a => Rel a -> Rel a
1N/AtransClosure r = Rel $
Map.map ( \ s -> getTAdjs r s s) $ toMap r
1N/A-- | convert a list of ordered pairs to a relation
1N/AfromList :: Ord a => [(a, a)] -> Rel a
1N/AfromList = foldr (\ (a, b) r -> insert a b r ) empty
1N/A-- | convert a relation to a list of ordered pairs
1N/AtoList :: Ord a => Rel a -> [(a, a)]
1N/AtoList = concatMap (\ (a , bs) -> map ( \ b -> (a, b) ) (
Set.toList bs))
1N/Ainstance (Show a, Ord a) => Show (Rel a) where
1N/A{--------------------------------------------------------------------
1N/A--------------------------------------------------------------------}
1N/A-- | /n/. Image of a relation under a function
1N/Aimage :: Ord b => (a -> b) -> Rel a -> Rel b
1N/A{--------------------------------------------------------------------
1N/A--------------------------------------------------------------------}
1N/A-- | /n/. Image of a relation under a function
1N/A{--------------------------------------------------------------------
1N/A--------------------------------------------------------------------}