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.

## Synopsis

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

#### Instances

Eq a => Eq (Rel a) Source # | |

(Data a, Ord a) => Data (Rel a) Source # | |

Defined in Common.Lib.Rel gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Rel a -> c (Rel a) gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Rel a) dataTypeOf :: Rel a -> DataType dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Rel a)) dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Rel a)) gmapT :: (forall b. Data b => b -> b) -> Rel a -> Rel a gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Rel a -> r gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Rel a -> r gmapQ :: (forall d. Data d => d -> u) -> Rel a -> [u] gmapQi :: Int -> (forall d. Data d => d -> u) -> Rel a -> u gmapM :: Monad m => (forall d. Data d => d -> m d) -> Rel a -> m (Rel a) gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Rel a -> m (Rel a) gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Rel a -> m (Rel a) | |

Ord a => Ord (Rel a) Source # | |

(Ord a, Read a) => Read (Rel a) Source # | |

Defined in Common.Lib.Rel | |

Show a => Show (Rel a) Source # | |

Generic (Rel a) Source # | |

(Ord a, FromJSON a, FromJSONKey a) => FromJSON (Rel a) | |

Defined in Common.Json.ConvInstances parseJSON :: Value -> Parser (Rel a) parseJSONList :: Value -> Parser [Rel a] | |

(Ord a, ToJSON a, ToJSONKey a) => ToJSON (Rel a) | |

Defined in Common.Json.ConvInstances | |

(Ord a, ShATermConvertible a) => ShATermConvertible (Rel a) | |

Defined in Common.ATerm.ConvInstances toShATermAux :: ATermTable -> Rel a -> IO (ATermTable, Int) toShATermList' :: ATermTable -> [Rel a] -> IO (ATermTable, Int) fromShATermAux :: Int -> ATermTable -> (ATermTable, Rel a) fromShATermList' :: Int -> ATermTable -> (ATermTable, [Rel a]) | |

(Ord a, HasSorts a) => HasSorts (Rel a) Source # | |

type Rep (Rel a) Source # | |

Defined in Common.Lib.Rel type Rep (Rel a) = D1 ('MetaData "Rel" "Common.Lib.Rel" "main" 'True) (C1 ('MetaCons "Rel" 'PrefixI 'True) (S1 ('MetaSel ('Just "toMap") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Map a (Set a))))) |

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