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-Inferred

Common.Lib.Rel

Description

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.

Synopsis

Documentation

data Rel a

no invariant is ensured for relations!

Instances

Eq a => Eq (Rel a)
(Data a, Ord a) => Data (Rel a)
Ord a => Ord (Rel a)
(Ord a, Read a) => Read (Rel a)
Show a => Show (Rel a)
(Ord a, ShATermConvertible a) => ShATermConvertible (Rel a)
(Ord a, HasSorts a) => HasSorts (Rel a)
Typeable (* -> *) Rel

empty :: Rel a

the empty relation

nullKeys :: Rel a -> Bool

test for empty

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

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

insert an ordered pair

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

insert a pair only if both sides are different

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

insert a pair only if both sides are different

member :: Ord a => a -> a -> Rel a -> Bool

test for an (previously inserted) ordered pair

toMap :: Rel a -> Map a (Set a)

map :: (Ord a, Ord b) => (a -> b) -> Rel a -> Rel b

map the values of a relation

noPairs :: Ord a => Rel a -> Bool

test for empty

insertKey :: Ord a => a -> Rel a -> Rel a

insert an unrelated node

deleteKey :: Ord a => a -> Rel a -> Rel a

delete a node and all its relations

memberKey :: Ord a => a -> Rel a -> Bool

keysSet :: Rel a -> Set a

keys of the relation

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

convert a plain node set to a relation

reflexive :: Ord a => Rel a -> Rel a

add all keys as reflexive elements

getCycles :: Ord a => Rel a -> Rel a

get entries that contain the key as element

union :: Ord a => Rel a -> Rel a -> Rel a

union of two relations

intersection :: Ord a => Rel a -> Rel a -> Rel a

intersection of two relations

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

is the first relation a sub-relation of the second

difference :: Ord a => Rel a -> Rel a -> Rel a

difference of two relations

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

test for member or transitive membership (non-empty path)

delete :: Ord a => a -> a -> Rel a -> Rel a

delete an ordered pair

succs :: Ord a => Rel a -> a -> Set a

get direct successors

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

get direct predecessors

irreflex :: Ord a => Rel a -> Rel a

make relation irreflexive

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

compute strongly connected components for a transitively closed relation

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

compute transitive closure (make all transitive members direct members)

fromList :: Ord a => [(a, a)] -> Rel a

convert a list of ordered pairs to a relation

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

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

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

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

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

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

restrict :: Ord a => Rel a -> Set a -> Rel a

Restriction of a relation under a set

delSet :: Ord a => Set a -> Rel a -> Rel a

restrict to elements not in the input set

toSet :: Ord a => Rel a -> Set (a, a)

convert a relation to a set of ordered pairs

fromSet :: Ord a => Set (a, a) -> Rel a

convert a set of ordered pairs to a relation

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

topologically sort a closed relation (ignore isolated cycles)

depSort :: Ord a => Rel a -> [Set a]

nodes :: Ord a => Rel a -> Set a

all nodes of the edges

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

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

transpose :: Ord a => Rel a -> Rel a

get transposed relation (losing unrelated keys)

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

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

fromMap :: Map a (Set a) -> Rel a

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

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

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]

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]]

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]]

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