rel_is_transitive {agop} | R Documentation |

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

rel_is_transitive(R) rel_closure_transitive(R) rel_reduction_transitive(R)

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

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

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.

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`

[Package *agop* version 0.2-3 Index]