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

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

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

data Rel a Source #

no invariant is ensured for relations!

Instances

Instances details

Eq a => Eq (Rel a) Source #
Instance details Defined in Common.Lib.Rel Methods (==) :: Rel a -> Rel a -> Bool (/=) :: Rel a -> Rel a -> Bool
(Data a, Ord a) => Data (Rel a) Source #
Instance details Defined in Common.Lib.Rel Methods 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) toConstr :: Rel a -> Constr 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 #
Instance details Defined in Common.Lib.Rel Methods compare :: Rel a -> Rel a -> Ordering (<) :: Rel a -> Rel a -> Bool (<=) :: Rel a -> Rel a -> Bool (>) :: Rel a -> Rel a -> Bool (>=) :: Rel a -> Rel a -> Bool max :: Rel a -> Rel a -> Rel a min :: Rel a -> Rel a -> Rel a
(Ord a, Read a) => Read (Rel a) Source #
Instance details Defined in Common.Lib.Rel Methods readsPrec :: Int -> ReadS (Rel a) readList :: ReadS [Rel a] readPrec :: ReadPrec (Rel a) readListPrec :: ReadPrec [Rel a]
Show a => Show (Rel a) Source #
Instance details Defined in Common.Lib.Rel Methods showsPrec :: Int -> Rel a -> ShowS show :: Rel a -> String showList :: [Rel a] -> ShowS
Generic (Rel a) Source #
Instance details Defined in Common.Lib.Rel Associated Types type Rep (Rel a) :: Type -> Type Methods from :: Rel a -> Rep (Rel a) x to :: Rep (Rel a) x -> Rel a
(Ord a, FromJSON a, FromJSONKey a) => FromJSON (Rel a)
Instance details Defined in Common.Json.ConvInstances Methods parseJSON :: Value -> Parser (Rel a) parseJSONList :: Value -> Parser [Rel a]
(Ord a, ToJSON a, ToJSONKey a) => ToJSON (Rel a)
Instance details Defined in Common.Json.ConvInstances Methods toJSON :: Rel a -> Value toEncoding :: Rel a -> Encoding toJSONList :: [Rel a] -> Value toEncodingList :: [Rel a] -> Encoding
(Ord a, ShATermConvertible a) => ShATermConvertible (Rel a)
Instance details Defined in Common.ATerm.ConvInstances Methods 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 #
Instance details Defined in Maude.Meta.HasSorts Methods getSorts :: Rel a -> SymbolSet Source # mapSorts :: SymbolMap -> Rel a -> Rel a Source #
type Rep (Rel a) Source #
Instance details 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)))))

empty :: Rel a Source #

the empty relation

nullKeys :: Rel a -> Bool Source #

test for empty

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

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

test for an (previously inserted) ordered pair

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

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

map the values of a relation

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

test for empty

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

insert an unrelated node

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

delete a node and all its relations

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

keysSet :: Rel a -> Set a Source #

keys of the relation

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

convert a plain node set to a relation

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

add all keys as reflexive elements

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

get entries that contain the key as element

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

union of two relations

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

intersection of two relations

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

is the first relation a sub-relation of the second

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

difference of two relations

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

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

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

delete an ordered pair

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

get direct successors

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

get direct predecessors

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

make relation irreflexive

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)

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

convert a list of ordered pairs to a relation

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

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

Restriction of a relation under a set

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

restrict to elements not in the input set

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

convert a relation to a set of ordered pairs

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

convert a set of ordered pairs to a relation

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

topologically sort a closed relation (ignore isolated cycles)

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

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

all nodes of the edges

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.

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

get transposed relation (losing unrelated keys)

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

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

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