Name Rascal/Expressions/Values/ListRelation/TransitiveClosure

Synopsis Transitive closure on binary list relation values.

Syntax Exp +

Types

Exp	Exp +
lrel[T1, T2]	lrel[T1, T2]

Description Returns the transitive closure of a binary listrelation. 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>]+;
lrel[int,int]: [
  <1,2>,
  <2,3>,
  <3,4>,
  <1,3>,
  <2,4>,
  <1,4>
]

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

rascal>lrel[int,int] tclosure(lrel[int,int] R) {
>>>>>>>   tc = R;
>>>>>>>   while(true){
>>>>>>>      tc1 = tc;
>>>>>>>      tc += tc o R;
>>>>>>>      if(tc1 == tc)
>>>>>>>         return tc;
>>>>>>>   }
>>>>>>>}
lrel[int,int] (lrel[int,int]): lrel[int,int] tclosure(lrel[int,int]);
rascal>tclosure([<1,2>, <2,3>, <3,4>]);
interrupted:
	at tclosure(/:6,6)
	at ___SCREEN_INSTANCE___(/:1,0)

Questions

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