Transitivity is an essential property of relations used in Decision Making. Here we provide a simple DP based facility to compute the transitive closure of an arbitrary relation on a finite set.
Let S be any non-empty set. A relation on S, say r, is a subset of SxS. Then r is said to be transitive if
Many very famous relations are transitive. For example, "descendent of" is a typical transitive relation: if "Marry" is a descendent of "Paul" and "Paul" is a descendent of "Jim" than clearly "Marry" is a descendent of "Jim". By the same token, many famous relations are not transitive: eg in general "mother of" is not a transitive relation: { "Lynn" is the mother "Marry" and "Marry" is a the mother of "Paul" } does not entail that "Lynn" is the mother of "Paul". In fact, in most cases "Lynn" will not be Paul's mother, but rather his grandma, but .... advances in medical procedures may changes this state of affairs.
The transitive closure of a relation r, denoted TC(r), is the smallest transitive relation containing r. That is, if r is a relation on S then TC(r) is the smallest transitive relation on S containing r. Of course, if r itself is transitive then TC(r)=r. Therefore we are interested only in the transitive closure of relations that are not themselves transitive.
Consider for example the relation "immediate successor of" defined on a set of nodes S associated with a given graph. Clearly, typically this is not a transitive relation. If we now consider the relation "successor of" on S, then clearly this relation is transitive and it contains the relation "immediate successor". It is not too difficult to show that in fact "successor of" is the smallest transitive relation containing "immediate successor of". Hence, "successor of" is the transitive closure of "immediate successor of".
In what follows we shall assume that set S under consideration is finite, namely it contains finitely many elements.
Observe that if R is the transitive closure of r on set S, then the following must be true: R is the smallest subset of SxS such that (a,c) is in R, if and only if either (a,c) is in r or there is some b in S such that (a,b) is in r and (b,c) is in R. We thus conclude that R is the smallest subset of SxS such satisfying the following conditions:
- R contains r
- R = {(a,c) in SxS: (a,c) in R or (a,b) is in R and (b,c) is in R, for some b in S}
We can deploy a dynamic programming successive approximation (SA) procedure to compute such an R. The procedure starts by approximating R by r, namely by setting
It then proceeds as follows:
The procedure terminates when R(k+1) = R(k), in which case R = R(k). Since we assume that S is finite, it follows that the procedure will eventually terminate. In fact, if |S| = n, namely if S contains n elements, then the procedure will terminate in no more than log2(n) iterations.
Remark:
In practice it is advisable to utilize "new" members of the transitive closure as soon as they are being discovered on the right hand side of the expression given above for R(k+1). This way they can accelerate the process as soon as they are discovered rather then only after all the operations conducted on the right hand side have been formally completed. The gain can be significant.
If this is done, then there is the question of the "best" order in which pairs (a,b) and (b,c) are tested. Our module ignores this aspect of the procedure. It tests the pairs in the order on S implied by its representation.
Since we deal only with relations on finite sets, it is convenient to represent the relations as boolean matrices where the pairs (a,b) in a relation are represented by 1's in the respective (row,column) pairs. If check boxes are available then checked boxes will represent the (row,column) pairs that are in the relation. For example,
is a non-transitive relation represented by a box diagram. Formally the relation r in this case consists of the set
Another way to interpret TC(r) is to view it as the "limit" of rk, k=0,1,2,3,... where
and
Observe that if R = rk+1 = rk then R =TC(r) and that we are assured that this holds for all k >= |S| .
We refer to this method as the Power Method.
You can interpret rm as the relation between all the descendants r generates in no more than m transitions. For instance, if r = "immediate successor of", then (a,b) in rk means that a can be reached from b along a path consisting of no more than k arcs.
So in general the successive approximation procedure should be much faster than the Power Method. However, there are situations where the latter is useful because of the intermediate results (rm, i=1,2,...,k) that it generates.
The module will enable you to compute the transitive closure of relations represented by box diagrams. Both the SA and the Power Method are on board so you can decide which one you want to use.
You have control on the progression of the computation so you can clearly see how the matrix representing the relation is updated.
For your convenience there is a facility on board to (quickly) generate pseudo-random problems.