rel_is_transitive {agop}

Transitive Binary Relations

Description

A binary relation R is transitive, iff for all x, y, z we have xRy and yRz \Longrightarrow xRz.

Usage

rel_is_transitive(R)

rel_closure_transitive(R)

rel_reduction_transitive(R)

Arguments

R

an object coercible to a 0-1 (logical) square matrix, representing a binary relation on a finite set.

Details

rel_is_transitive finds out if a given binary relation is transitive. The algorithm has O(n^3) time complexity, pessimistically, where n is the number of rows in R. If R contains missing values behind the diagonal, the result will be NA.

The transitive closure of a binary relation R, determined by rel_closure_transitive, is the minimal superset of R such that it is transitive. Here we use the well-known Warshall algorithm (1962), which runs in O(n^3) time.

The transitive reduction, see (Aho et al. 1972), of an acyclic binary relation R, determined by rel_reduction_transitive, is a minimal unique subset R' of R, such that the transitive closures of R and R' are equal. The implemented algorithm runs in O(n^3) time. Note that a transitive reduction of a reflexive relation is also reflexive. Moreover, some kind of transitive reduction (not necessarily minimal) is also determined in rel_reduction_hasse – it is useful for drawing Hasse diagrams.

Value

The rel_closure_transitive and rel_reduction_transitive functions return a logical square matrix. dimnames of R are preserved.

On the other hand, rel_is_transitive returns a single logical value.

References

Aho A.V., Garey M.R., Ullman J.D., The Transitive Reduction of a Directed Graph, SIAM Journal on Computing 1(2), 1972, pp. 131-137.

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

See Also

Other binary_relations: check_comonotonicity(), pord_nd(), pord_spread(), pord_weakdom(), rel_graph(), rel_is_antisymmetric(), rel_is_asymmetric(), rel_is_cyclic(), rel_is_irreflexive(), rel_is_reflexive(), rel_is_symmetric(), rel_is_total(), rel_reduction_hasse()