Transitive closure is one of the strong features (and also weak points, infinite computations) of Prolog. David Warren makes a good introduction to tabled transitive closure (finite) in: Link . Basically, one of the first things one learns in Prolog is the reachability relation using the dynamic database (where 'edge(X,Y)' facts are stored in the database, and a recursive 'reach(X,Y)' predicate finds all paths of any length in the given graph).
During the ICLP 2007 Prolog Net Competition probs.pdf , one of the problems required to make a transitive closure WITHOUT using the dynamic database. Please see the attached algorithm.
% transitiveClosure(+Edges,-EdgesTransitiveClosure)
transitiveClosure(Edges,EdgesTransitiveClosure):-
findall(
EdgesTransitiveClosure2,
(
select(Edge,Edges,RestEdges),
transitiveClosure(RestEdges,EdgesTransitiveClosure1),
addEdge(Edge,EdgesTransitiveClosure1,EdgesTransitiveClosure2)
),
EdgesTransitiveClosure3
),
leverage(EdgesTransitiveClosure3,EdgesTransitiveClosureDupl),
eliminateDuplicates(EdgesTransitiveClosureDupl,EdgesTransitiveClosure).
% addEdge(+Edge,+Edges,-EdgesTransitiveClosure)
addEdge(Edge,[],[Edge]):-
!.
addEdge(edge(X,Y),Edges,[edge(X,Y)|EdgesTransitiveClosure]):-
findall(
edge(X,Z),
memberListElemUnknown(edge(Y,Z),Edges),
EdgesTransitiveClosureTemp1
),
appendList(EdgesTransitiveClosureTemp1,Edges,EdgesTransitiveClosure),
!.
% leverage(+LL,-L)
leverage(LL,L):-
leverage(LL,[],L).
% leverage(+LL,+PartialL,-L).
leverage([],L,L):-
!.
leverage([H|T],PartialL,L):-
leverageOne(H,PartialL,L1),
leverage(T,PartialL,L2),
append(L1,L2,L),
!.
% leverageOne(+List,+PartialL,-L).
leverageOne([],L,L):-
!.
leverageOne([H|T],PartialL,L):-
member(H,PartialL),
!,
leverageOne(T,PartialL,L).
leverageOne([H|T],PartialL,L):-
leverageOne(T,[H|PartialL],L).
% eliminateDuplicates(+ListDupl,-List)
eliminateDuplicates([],[]):-
!.
eliminateDuplicates([H|T],List):-
member(H,T),
!,
eliminateDuplicates(T,List).
eliminateDuplicates([H|T],[H|List]):-
eliminateDuplicates(T,List).
For our submission for the ICLP207 Net contest: please see: ICLP07NetContestSBUSolutions.html .