rel_is_transitive {agop} R Documentation

## 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.

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