relations (version 0.6-15)

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^{\prime }$ on $X$ so that the transitive closure of $R^{\prime }$ 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. tools:::Rd_expr_doi("10.1145/321105.321107").

J. A. La Poutré 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

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"))
  }