relations (version 0.6-8)

reduction: Transitive and Reflexive Reduction

Description

Computes transitive and reflexive reduction of an endorelation.

Usage

transitive_reduction(x)
reflexive_reduction(x)
# S3 method for relation
reduction(x, operation = c("transitive", "reflexive"), ...)

Arguments

x

an R object inheriting from class relation, representing an endorelation.

operation

character string indicating the kind of reduction.

…

currently not used.

Details

Let \(R\) be an endorelation on \(X\) and \(n\) be the number of elements in \(X\).

The transitive reduction of \(R\) is the smallest relation \(R'\) on \(X\) so that the transitive closure of \(R'\) is the same than the transitive closure of \(R\).

The transitive reduction of an acyclic relation can be obtained by subtracting from \(R\) the composition of \(R\) with its transitive closure.

The transitive reduction of a cyclic relation is the transitive reduction of the condensation, combined with the component representation of \(R\). (Note that the transitive reduction of a cyclic relation is cyclic.)

The reflexive reduction of \(R\) is computed by setting the diagonal of the incidence matrix to 0.

References

S. Warshall (1962), A theorem on Boolean matrices. Journal of the ACM, 9/1, 11--12. 10.1145/321105.321107.

J. A. La Poutr<U+00E9> and J. van Leeuwen (1988), Maintenance of Transitive Closures and Transitive Reductions of Graphs. Proceedings of the International Workshop of Graph-Theoretic Concepts in Computer Science, Springer, London, 106--120.

See Also

relation(), reflexive_reduction(), transitive_reduction(), reduction(), relation_condensation(), relation_component_representation().

Examples

# NOT RUN {
R <- as.relation(1 : 5)
relation_incidence(R)

## transitive closure/reduction
RR <- transitive_reduction(R)
relation_incidence(RR)
R == transitive_closure(RR)

## same
require("sets")				# closure() and reduction() etc.
R == closure(reduction(R))

## reflexive closure/reduction

RR <- reflexive_reduction(R)
relation_incidence(RR)
R == reflexive_closure(RR)

## same:
R == closure(reduction(R, "reflexive"), "reflexive")

## transitive reduction of a cyclic relation:
## (example from La Poutre and van Leeuwen)

require("sets")				# set(), pair() etc.
if(require("Rgraphviz")) {
  G <- set(pair(1L, 2L), pair(2L, 1L), pair(1L, 3L), pair(3L, 1L),
           pair(3L, 7L), pair(2L, 5L), pair(2L, 6L), pair(6L, 5L),
           pair(5L, 7L), pair(4L, 6L), pair(5L, 4L), pair(4L, 7L))
  R <- endorelation(graph = G)
  plot(relation_ensemble(R, R), type = c("raw", "simplified"), main =
           c("original graph", "transitive reduction"))
  }
# }