Name Rascal/Expressions/Values/Relation/TransitiveClosure

Synopsis Transitive closure on binary relation values.

Syntax Exp +

Types

Exp	Exp +
rel[T1, T2]	rel[T1, T2]

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]: {
  <1,4>,
  <2,4>,
  <1,3>,
  <2,3>,
  <1,2>,
  <3,4>
}

We can also simply (but not necessarily efficiently) define transitive closure ourselves:

rascal>rel[int,int] tclosure(rel[int,int] R) {
>>>>>>>   tc = R;
>>>>>>>   while(true){
>>>>>>>      tc1 = tc;
>>>>>>>      tc += tc o R;
>>>>>>>      if(tc1 == tc)
>>>>>>>         return tc;
>>>>>>>   }
>>>>>>>}
rel[int,int] (rel[int,int]): rel[int,int] tclosure(rel[int,int]);
rascal>tclosure({<1,2>, <2,3>, <3,4>});
rel[int,int]: {
  <1,4>,
  <2,4>,
  <1,3>,
  <2,3>,
  <1,2>,
  <3,4>
}

Questions

[Edit] | [New Subconcept] | [Recompile Course] | [Warnings]