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