rel_transitive: Transitive Binary Relations
In agop: Aggregation Operators and Preordered Sets

Description Usage Arguments Details Value References See Also

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