|
Data.Relation.SetOfPairs | Portability | portable | Stability | experimental | Maintainer | joost.visser@di.uminho.pt |
|
|
|
|
|
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 a | input relation | -> Rel a a | output 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 |