Transitive Closure

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 finite non-empty set. A relation on S, say r, is a subset of SxS. Then r is said to be transitive if

{(a,b) in r and (b,c) in r} entails (a,c) in r

Many very famous relations are transitive. For example, "descendent of" is a typical transitive relation: if "Marry" is a decscendent 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.

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. Of interest are therefore relations that are not 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".

Observe that if R is the transitive closure of r on some set r, then the following must be true: R is the smallest set 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 set such that

R = {(a,c): (a,c) in r or (a,b) is in r and (b,c) is in R, for some b in S}

The DP procedure we shall use to compute TC(r) for a given r deploys a successive approximation procedure based on this basic property of R. The procedure starts by approximating R by r, namely by setting

R(0) := r

It then proceeds as follows:

R(k+1) := {(a,c): (a,c) in R(k) or (a,b) is in R(k) and (b,c) is in R(k), for some b in S}

The procedures terminates when R(k+1) = R(k), in which case R = R(k).

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,

[1] [2] [3] [4]
[1] [1]
[2] [2]
[3] [3]
[4] [4]

Is a non-transitive relation represented by a box diagram. Formally the relation r in this case consists of the set


Give Tranzy a try!