relations (version 0.5-9)

reduction: Transitive and Reflexive Reduction

Description

Computes transitive and reflexive reduction of an endorelation.

Usage

transitive_reduction(x)
reflexive_reduction(x)
## S3 method for class 'relation':
reduction(x, operation = c("transitive", "reflexive"), ...)

Arguments

x

an Robject inheriting from class relation, representing an endorelation.

operation

character string indicating the kind of reduction.

...

currently not used.

Details

Let $R$ be an endorelation on $X$ and $n$ be the number of elements in $X$. The transitive reduction of $R$ is the smallest relation $R'$ on $X$ so that the transitive closure of $R'$ is the same than the transitive closure of $R$. The current implementation can only be used for acyclic relations. The reflexive reduction of $R$ is computed by setting the diagonal of the incidence matrix to 0.

References

S. Warshall (1962), A theorem on Boolean matrices. Journal of the ACM, 9/1, 11--12.

See Also

relation, reflexive_reduction, transitive_reduction, reduction.

Examples

R <- as.relation(1 : 5)
relation_incidence(R)

## transitive closure/reduction
RR <- transitive_reduction(R)
relation_incidence(RR)
R == transitive_closure(RR)

## same
R == closure(reduction(R))

## reflexive closure/reduction

RR <- reflexive_reduction(R)
relation_incidence(RR)
R == reflexive_closure(RR)
## same:
R == closure(reduction(R, "reflexive"), "reflexive")