Skip to main content

Relation TransitiveClosure

rascal-0.41.2

Synopsis​

Transitive closure on binary relation values.

Syntax​

Exp +

Types​

ExpExp +
rel[T₁, T₂]rel[T₁, T₂]

Description​

Returns the transitive closure of a binary relation. Transitive closure is defined by repeated composition of a relation. If we define for a given relation R:

  • R₁ = R
  • R₂ = R o R
  • R₃ = R o R₂
  • ...

then the transitive closure R+ can be defined as

  • R+ = R₁ + R₂ + R₃ + ...

Examples​

rascal>{<1,2>, <2,3>, <3,4>}+;
rel[int,int]: {
  <3,4>,
  <1,3>,
  <1,2>,
  <1,4>,
  <2,3>,
  <2,4>
}

We can also define transitive closure ourselves (this is not faster):

rascal>rel[int,int] tclosure(rel[int,int] R) {
|1 >>>>   tc = R;
|2 >>>>   while(true){
|3 >>>>      tc1 = tc;
|4 >>>>      tc += tc o R;
|5 >>>>      if(tc1 == tc)
|6 >>>>         return tc;
|7 >>>>   }
|8 >>>>}
rel[int,int] (rel[int,int]): function(|prompt:///|(0,149,<1,0>,<9,1>))
rascal>tclosure({<1,2>, <2,3>, <3,4>});
rel[int,int]: {
  <3,4>,
  <1,3>,
  <1,2>,
  <1,4>,
  <2,3>,
  <2,4>
}