relations (version 0.2-0)

transfuns: Transitive Closure and Reduction

Description

Computes transitive closure and reduction of an endorelation.

Usage

transitive_reduction(x)
transitive_closure(x)

Arguments

x

an Robject inheriting from class relation, representing an endorelation.

Details

Let $R$ be an endorelation on $X$ and $n$ be the number of elements in $X$. The transitive closure of $R$ is the smallest transitive relation on $X$ that contains $R$. The code implements Warshall's Algorithm which is of complexity $O(n^3)$.

The transitive reduction of $R$ is the smallest relation $R'$ on $X$ so that the the transitive closure of $R'$ is the same than the transitive closure of $R$. The function is implemented using a depth-first-search approach, also with complexity $O(n^3)$.

References

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

See Also

relation, reflexive_reduction.

Examples

R <- as.relation(1 : 5)
relation_incidence(R)
RR <- transitive_reduction(R)
relation_incidence(RR)
R == transitive_closure(RR)