rel_is_transitive {agop} | R Documentation |

A binary relation `R`

is *transitive*, iff
for all `x`

, `y`

, `z`

we have `xRy`

and `yRz`

`\Longrightarrow`

`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.4 Index]