[net.lang.prolog] Transitive Closures

Abbott@AeroSpace@sri-unix.UUCP (09/17/83)

From:  Abbott at AeroSpace ( Russ Abbott )

The recent discussion of transitive relations has drifted somewhat
from the original question.  I thought this might be a good time to
raise it again.

Does anyone know of a good way to write a predicate in Prolog that
defines a relation to be the transitive closure of another relation.
For example:

        transitive_closure(R, T_R).

should have the side-effect of ensuring that if R(a, b) and R(b, c)
are either in the database or ( important! ) are added to the database
later, then T_R(X, Y) will succeed with (X, Y) being bound to (a, b),
(b, c), and (a, c) in turn.

One might imagine writing something like:

transitive_closure(R, T_R) :-
        assert((
                T_R(A, C) :-
                        R(A, C);
                                T_R(A, B), T_R(B, C)
                                                )).

But that leads to various difficulties involving infinite recursion.
So far, there are no clean solutions.

puder@burdvax.UUCP (09/26/83)

Here is how I define the transitive closure and avoid infinite loops, etc.

% cprolog
CProlog version 1.3
| ?- [user].
| 
| % The base relation.
| r(a,b).
| r(b,c).
| r(b,d).
| r(f,a).
| r(e,a).
| 
| % The transitive relation.
| tr(X,Y):-r(X,Y).
| % Note that the next clauses call r and tr, they do not call tr twice!
| tr(X,Y):-nonvar(X),!,r(X,Z),tr(Z,Y).
| tr(X,Y):-r(Z,Y),tr(X,Z).
| 
| user consulted 484 bytes 0.2 sec.

yes
| ?- tr(A,B).

A = a
B = b ;

A = b
B = c ;

A = b
B = d ;

A = f
B = a ;

A = e
B = a ;

A = f
B = b ;

A = e
B = b ;

A = a
B = c ;

A = f
B = c ;

A = e
B = c ;

A = a
B = d ;

A = f
B = d ;

A = e
B = d ;

no
| ?- 

-- 

Karl Puder   {sdcrdcf,presby,psuvax}!burdvax!puder   (215)648-7555