CODEWITHSUNDEEP
prologtransitive-closure
Gavin
Gavin

Reputation: 2824

Ancestor to all reachable node

I wrote it as such. But it only succeed in finding till the grandparent, and not any further. How do I write it in such a way that it finds all possible ancestor. That is, finding greatgrandparent and even further if there exist such fact? 

 ancestor(X, Y) :- parent(X, Y); parent(X,Z), parent(Z,Y).

Given

parent(greatgrand_parent, grand_parent).
parent(grand_parent, parent).
parent(parent, child).

Returns only

?- ancestor(What, child).
What = parent ;
What = grand_parent ;
false.

Upvotes: 2

Views: 677

Answers (2)

CapelliC
CapelliC

Reputation: 60014

you forget the recursive call: try

ancestor(X, Y) :- parent(X, Y) ; parent(X,Z), ancestor(Z,Y).

and you get

?- ancestor(X,child).
   X = parent
;  X = greatgrand_parent
;  X = grand_parent
;  false.

Upvotes: 2

false
false

Reputation: 10102

Transitive closure is a frequently recurring problem in Prolog. So why not separate the specific - in your case the relation parent/2 from the general - a relation closure/3.

| ?- closure(parent, What, child).
What = greatgrand_parent ? ;
What = grand_parent ? ;
What = parent ? ;
no

Upvotes: 2

Related Questions