Copyright | (c) Uni Bremen 2003-2005 |
---|---|

License | GPLv2 or higher, see LICENSE.txt |

Maintainer | Christian.Maeder@dfki.de |

Stability | provisional |

Portability | portable |

Safe Haskell | Safe |

supply a simple data type for (precedence or subsort) relations. A relation is conceptually a set of (ordered) pairs, but the hidden implementation is based on a map of sets. An alternative view is that of a directed Graph possibly with isolated nodes.

`Rel`

is a directed graph with elements (Ord a) as (uniquely labelled) nodes
and (unlabelled) edges (with a multiplicity of at most one).

Usage: start with an `empty`

relation, `insert`

edges, and test for
an edge `member`

(before or after calling `transClosure`

).

It is possible to insert self edges or bigger cycles. But rather than inserting self edges and element can be mapped to the empty set.

Checking for a `path`

corresponds to checking for a member in the
transitive (possibly non-reflexive) closure. A further `insert`

, however,
may destroy the closedness property of a relation.

- data Rel a
- empty :: Rel a
- nullKeys :: Rel a -> Bool
- rmNullSets :: Ord a => Rel a -> Rel a
- insertPair :: Ord a => a -> a -> Rel a -> Rel a
- insertDiffPair :: Ord a => a -> a -> Rel a -> Rel a
- insertKeyOrPair :: Ord a => a -> a -> Rel a -> Rel a
- member :: Ord a => a -> a -> Rel a -> Bool
- toMap :: Rel a -> Map a (Set a)
- map :: (Ord a, Ord b) => (a -> b) -> Rel a -> Rel b
- noPairs :: Ord a => Rel a -> Bool
- insertKey :: Ord a => a -> Rel a -> Rel a
- deleteKey :: Ord a => a -> Rel a -> Rel a
- memberKey :: Ord a => a -> Rel a -> Bool
- keysSet :: Rel a -> Set a
- fromKeysSet :: Ord a => Set a -> Rel a
- reflexive :: Ord a => Rel a -> Rel a
- getCycles :: Ord a => Rel a -> Rel a
- union :: Ord a => Rel a -> Rel a -> Rel a
- intersection :: Ord a => Rel a -> Rel a -> Rel a
- isSubrelOf :: Ord a => Rel a -> Rel a -> Bool
- difference :: Ord a => Rel a -> Rel a -> Rel a
- path :: Ord a => a -> a -> Rel a -> Bool
- delete :: Ord a => a -> a -> Rel a -> Rel a
- succs :: Ord a => Rel a -> a -> Set a
- predecessors :: Ord a => Rel a -> a -> Set a
- irreflex :: Ord a => Rel a -> Rel a
- sccOfClosure :: Ord a => Rel a -> [Set a]
- transClosure :: Ord a => Rel a -> Rel a
- fromList :: Ord a => [(a, a)] -> Rel a
- toList :: Rel a -> [(a, a)]
- toPrecMap :: Ord a => Rel a -> (Map a Int, Int)
- intransKernel :: Ord a => Rel a -> Rel a
- mostRight :: Ord a => Rel a -> Set a
- restrict :: Ord a => Rel a -> Set a -> Rel a
- delSet :: Ord a => Set a -> Rel a -> Rel a
- toSet :: Ord a => Rel a -> Set (a, a)
- fromSet :: Ord a => Set (a, a) -> Rel a
- topSort :: Ord a => Rel a -> [Set a]
- depSort :: Ord a => Rel a -> [Set a]
- nodes :: Ord a => Rel a -> Set a
- collaps :: Ord a => [Set a] -> Rel a -> Rel a
- transpose :: Ord a => Rel a -> Rel a
- transReduce :: Ord a => Rel a -> Rel a
- fromMap :: Map a (Set a) -> Rel a
- locallyFiltered :: Ord a => Rel a -> Bool
- flatSet :: Ord a => [Set a] -> Set a
- partSet :: Ord a => (a -> a -> Bool) -> Set a -> [Set a]
- partList :: (a -> a -> Bool) -> [a] -> [[a]]
- leqClasses :: Ord a => (a -> a -> Bool) -> Set a -> [[a]]

# Documentation

no invariant is ensured for relations!

rmNullSets :: Ord a => Rel a -> Rel a Source #

insertPair :: Ord a => a -> a -> Rel a -> Rel a Source #

insert an ordered pair

insertDiffPair :: Ord a => a -> a -> Rel a -> Rel a Source #

insert a pair only if both sides are different

insertKeyOrPair :: Ord a => a -> a -> Rel a -> Rel a Source #

insert a pair only if both sides are different

fromKeysSet :: Ord a => Set a -> Rel a Source #

convert a plain node set to a relation

isSubrelOf :: Ord a => Rel a -> Rel a -> Bool Source #

is the first relation a sub-relation of the second

path :: Ord a => a -> a -> Rel a -> Bool Source #

test for `member`

or transitive membership (non-empty path)

predecessors :: Ord a => Rel a -> a -> Set a Source #

get direct predecessors

sccOfClosure :: Ord a => Rel a -> [Set a] Source #

compute strongly connected components for a transitively closed relation

transClosure :: Ord a => Rel a -> Rel a Source #

compute transitive closure (make all transitive members direct members)

toList :: Rel a -> [(a, a)] Source #

convert a relation to a list of ordered pairs (this loses isolated keys!)

toPrecMap :: Ord a => Rel a -> (Map a Int, Int) Source #

Construct a precedence map from a closed relation. Indices range between 1 and the second value that is output.

intransKernel :: Ord a => Rel a -> Rel a Source #

intransitive kernel of a reflexive and transitive closure

- precondition: (transClosure r == r)
- cycles are uniquely represented (according to Ord)

mostRight :: Ord a => Rel a -> Set a Source #

find s such that x in s => forall y . yRx or not yRx and not xRy

- precondition: (transClosure r == r)
- strongly connected components (cycles) are treated as a compound node

topSort :: Ord a => Rel a -> [Set a] Source #

topologically sort a closed relation (ignore isolated cycles)

collaps :: Ord a => [Set a] -> Rel a -> Rel a Source #

restrict strongly connected components to its minimal representative (input sets must be non-null). Direct cycles may remain.

transReduce :: Ord a => Rel a -> Rel a Source #

transitive reduction (minimal relation with the same transitive closure) of a transitively closed DAG (i.e. without cycles)!

locallyFiltered :: Ord a => Rel a -> Bool Source #

checks if a given relation is locally filtered

- precondition: the relation must already be closed by transitive closure

flatSet :: Ord a => [Set a] -> Set a Source #

flattens a list of non-empty sets and uses the minimal element of each set to represent the set

partSet :: Ord a => (a -> a -> Bool) -> Set a -> [Set a] Source #

partitions a set into a list of disjoint non-empty subsets determined by the given function as equivalence classes

partList :: (a -> a -> Bool) -> [a] -> [[a]] Source #

partitions a list into a list of disjoint non-empty lists determined by the given function as equivalence classes

leqClasses :: Ord a => (a -> a -> Bool) -> Set a -> [[a]] Source #

Divide a Set (List) into equivalence classes w.r.t. eq