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 => 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`