closure: Transitive and Reflexive Closure

Description

Computes transitive and reflexive closure of an endorelation.

Usage

transitive_closure(x)
reflexive_closure(x)
# S3 method for relation
closure(x, operation = c("transitive", "reflexive"), ...)

Arguments

x: an R object inheriting from class relation, representing an endorelation.
operation: character string indicating the kind of closure.
...: currently not used.

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 reflexive closure of \(R\) is computed by setting the diagonal of the incidence matrix to 1.

References

S. Warshall (1962), A theorem on Boolean matrices. Journal of the ACM, 9/1, 11--12. tools:::Rd_expr_doi("10.1145/321105.321107").

Examples

Run this code

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

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

## same
require("sets")				# closure() and reduction()
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")