UMinho Haskell Libraries (2004.11.10)ContentsIndex
Data.Relation.SetOfPairs
Portability portable
Stability experimental
Maintainer joost.visser@di.uminho.pt
Contents
Representation
Building relations
Basic operations
Closures
Selections (project, slice, chop)
Partitions
Integration
Description
An implementation of relations as sets of pairs.
Synopsis
type Rel a b = Set (a, b)
readSet' :: (Ord a, Read a) => ReadS (Set a)
readSet :: Read a => ReadS [a]
type Gph a = Rel a a
emptyRel :: Rel a b
mkRel :: (Ord a, Ord b) => [(a, b)] -> Rel a b
mkRelNeighbors :: (Ord a, Ord b) => a -> [b] -> Rel a b
identityRel :: Ord a => Set a -> Rel a a
totalRel :: Ord a => Set a -> Rel a a
chainRel :: (Enum n, Num n, Ord n) => n -> Rel n n
dom :: Ord a => Rel a b -> Set a
rng :: Ord b => Rel a b -> Set b
ent :: Ord a => Rel a a -> Set a
pairs :: (Ord a, Ord b) => Rel a b -> [(a, b)]
inv :: (Ord a, Ord b) => Rel a b -> Rel b a
comp :: (Ord a, Eq b, Ord c) => Rel b c -> Rel a b -> Rel a c
reflClose :: Ord a => Rel a a -> Rel a a
symmClose :: Ord a => Rel a a -> Rel a a
transClose :: Ord a => Rel a a -> Rel a a
reflTransClose :: Ord a => Rel a a -> Rel a a
equiv :: Ord b => Rel b b -> Rel b b
domWith :: (Ord a, Ord b) => Set b -> Rel a b -> Set a
rngWith :: (Ord a, Ord b) => Set a -> Rel a b -> Set b
entWith :: Ord a => Set a -> Rel a a -> Set a
removeSelfEdges :: Ord a => Gph a -> Gph a
projectWith :: (Ord a, Ord b) => (a -> b -> Bool) -> Rel a b -> Rel a b
project :: (Ord a, Ord b) => Set a -> Rel a b -> Rel a b
projectBackward :: (Ord a, Ord b) => Set b -> Rel a b -> Rel a b
slice :: Ord a => Set a -> Rel a a -> Rel a a
sliceUntil :: Ord a => Set a -> Set a -> Rel a a -> Rel a a
sliceBackward :: Ord a => Set a -> Rel a a -> Rel a a
chop :: Ord a => Set a -> Set a -> Rel a a -> Rel a a
slicesUnion :: Ord a => Set a -> Set a -> Rel a a -> Rel a a
slicesIntersect :: Ord a => Set a -> Set a -> Rel a a -> Rel a a
slicesWith :: Ord a => (Rel a a -> Rel a a -> Rel a a) -> Set a -> Set a -> Rel a a -> Rel a a
sliceOrChopWith :: Ord a => (Rel a a -> Rel a a -> Rel a a) -> [a] -> [a] -> Rel a a -> Rel a a
gobbleUntil :: Ord a => Set a -> Set a -> Rel a a -> Rel a a
weakComponents :: Ord a => Rel a a -> [Rel a a]
strongComponent :: Ord a => a -> Gph a -> Set a
strongComponentSet :: (Ord a, Ord (Set a)) => Gph a -> Set (Set a)
type Component a = (Set a, Rel a a)
strongComponent' :: Ord a => a -> Rel a a -> Component a
strongComponentRel :: (Ord a, Ord (Set a)) => Gph a -> Gph (Set a)
strongComponentRel' :: (Ord a, Ord (Set a)) => Gph a -> Gph (Component a)
integrate :: Ord a => Rel a a -> Rel a a -> Rel a a -> (Rel a a, Bool)
affectedPoints :: Ord a => Rel a a -> Rel a a -> Set a
preservedPoints :: Ord a => Rel a a -> Rel a a -> Rel a a -> Set a
Representation
type Rel a b = Set (a, b)
Type of relations
readSet' :: (Ord a, Read a) => ReadS (Set a)
readSet :: Read a => ReadS [a]
type Gph a = Rel a a
Type of graphs: relations with domain and range of the same type.
Building relations
emptyRel :: Rel a b
Build an empty relation.
mkRel :: (Ord a, Ord b) => [(a, b)] -> Rel a b
Build a relation from a list of pairs.
mkRelNeighbors :: (Ord a, Ord b) => a -> [b] -> Rel a b
Build a relation from distributing an element to a set of elements
identityRel :: Ord a => Set a -> Rel a a
Build identity relation, which contains an edge from each node to itself.
totalRel :: Ord a => Set a -> Rel a a
Build total relation, which contains an edge from each node to each other node and to itself.
chainRel :: (Enum n, Num n, Ord n) => n -> Rel n n
Build a chain relation of given number of numerals.
Basic operations
dom :: Ord a => Rel a b -> Set a
Obtain the domain of a relation
rng :: Ord b => Rel a b -> Set b
Obtain the range of a relation
ent :: Ord a => Rel a a -> Set a
Obtain all entities in a relation (union of domain and range)
pairs :: (Ord a, Ord b) => Rel a b -> [(a, b)]
Convert relation to a list of pairs.
inv :: (Ord a, Ord b) => Rel a b -> Rel b a
Take the inverse of a relation
comp :: (Ord a, Eq b, Ord c) => Rel b c -> Rel a b -> Rel a c
Compose two relations
Closures
reflClose :: Ord a => Rel a a -> Rel a a
Compute the reflective closure
symmClose :: Ord a => Rel a a -> Rel a a
Compute the symmetric closure
transClose :: Ord a => Rel a a -> Rel a a
Compute the transitive closure
reflTransClose :: Ord a => Rel a a -> Rel a a
Compute the reflexive, transitive closure
equiv :: Ord b => Rel b b -> Rel b b
Compute the reflexive, transitive, symmetric closure, i.e. the induced equivalence relation.
Selections (project, slice, chop)
domWith :: (Ord a, Ord b) => Set b -> Rel a b -> Set a
Obtain the subdomain of a relation given a subrange.
rngWith :: (Ord a, Ord b) => Set a -> Rel a b -> Set b
Obtain the subrange of a relation given a subdomain.
entWith :: Ord a => Set a -> Rel a a -> Set a
Obtain the subrange and subdomain of a relation given a subdomain.
removeSelfEdges :: Ord a => Gph a -> Gph a
Remove all edges of the form (x,x).
projectWith :: (Ord a, Ord b) => (a -> b -> Bool) -> Rel a b -> Rel a b
Retrieve a subrelation given predicates on domain and range.
project :: (Ord a, Ord b) => Set a -> Rel a b -> Rel a b
Projection of set through relation
projectBackward :: (Ord a, Ord b) => Set b -> Rel a b -> Rel a b
Projection of set backward through relation
slice :: Ord a => Set a -> Rel a a -> Rel a a
Compute forward slice starting from seeds.
sliceUntil :: Ord a => Set a -> Set a -> Rel a a -> Rel a a
Compute forward slice starting from seeds, stopping at stoppers.
sliceBackward :: Ord a => Set a -> Rel a a -> Rel a a
Compute backward slice starting from seeds.
chop :: Ord a => Set a -> Set a -> Rel a a -> Rel a a
Compute chop between seeds and sinks.
slicesUnion :: Ord a => Set a -> Set a -> Rel a a -> Rel a a
Compute union of backward and forward slice.
slicesIntersect :: Ord a => Set a -> Set a -> Rel a a -> Rel a a
Compute intersection of backward and forward slice. This is the same as the computing the chop between seeds and sinks.
slicesWith :: Ord a => (Rel a a -> Rel a a -> Rel a a) -> Set a -> Set a -> Rel a a -> Rel a a
Compute combination of backward and forward slice, where a binary operator is supplied to specify the kind of combination.
sliceOrChopWith
:: Ord a
=> (Rel a a -> Rel a a -> Rel a a)binary graph operation
-> [a]sources
-> [a]sinks
-> Rel a ainput relation
-> Rel a aoutput relation
Compute slice or chop, depending on whether the source or sink set or both are empty.
Partitions
gobbleUntil :: Ord a => Set a -> Set a -> Rel a a -> Rel a a
Compute subrelation connected to seeds, stopping at stoppers.
weakComponents :: Ord a => Rel a a -> [Rel a a]
Compute weakly connected components.
strongComponent :: Ord a => a -> Gph a -> Set a
Compute a single strong component (set of nodes).
strongComponentSet :: (Ord a, Ord (Set a)) => Gph a -> Set (Set a)
Compute the set of strong components (sets of nodes).
type Component a = (Set a, Rel a a)
Type of components: node set tupled with subrelation.
strongComponent' :: Ord a => a -> Rel a a -> Component a
Compute a single strong component (node set tupled with subrelation).
strongComponentRel :: (Ord a, Ord (Set a)) => Gph a -> Gph (Set a)
Compute the graph of strong components (node sets).
strongComponentRel' :: (Ord a, Ord (Set a)) => Gph a -> Gph (Component a)
Compute the graph of stong components (node sets tupled with subrelations).
Integration
integrate :: Ord a => Rel a a -> Rel a a -> Rel a a -> (Rel a a, Bool)
Integrate two graphs with respect to a base graph into a new graph that contains the differences of each input graph with respect to the base graph. The boolean value indicates whether the graphs are interference-free, i.e. whether the integration is valid.
affectedPoints :: Ord a => Rel a a -> Rel a a -> Set a
Points in the first graph that are affected by changes with respect to the base graph.
preservedPoints :: Ord a => Rel a a -> Rel a a -> Rel a a -> Set a
Points in the base graph that are not affected by changes in either input graph.
Produced by Haddock version 0.6