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