CODEWITHSUNDEEP
prolog
Hingusan
Hingusan

Reputation: 43

Swi-Prolog: How to write a descendant predicate?

I have the provided definition of descendent as below:

"a person who is in direct line to an ancestor. Eg: child, grandchild, great-grandchild, and forever"

and also other rules like:

...
childof(X, Y).
parent(X, Y).
grandchild(X, Y).
ancestor(X, Y).
...

So can I just simply write a rule as below,

descendant(X, Y):- ancestorof(Y, X).

or is there a better way of doing it?

Upvotes: 0

Views: 498

Answers (1)

Nicholas Carey
Nicholas Carey

Reputation: 74267

This is a problem of tree traversal or graph traversal.

I would generalize an ancestor_of/3 predicate:

ancestor(Ancestor,Generations,Descendant)

Assuming you have, say, a set of facts like

parents( mother, father, child ).

On can say that a parent is either the mother or father of a child:

% P is a parent of C if P is either the mother or father of C.
parent(P,C) :- parents(P,_,C).
parent(P,C) :- parents(_,P,C).

And given the above, the solution might look like this:

ancestor(Ancestor, Generations, Descendant) :-
  ancestor( Ancestor, 0, Generations, Descendant )
  .

ancestor( A, N, G, D ) :- % A is an ancestor of D...
  parent(A,D),            % * if A is the immediate parent of D
  G is N+1                % * in which case, tick the generation count
  .                       % Easy!
ancestor( A, N, G, D ) :- % otherwise, A is an ancestor of D...
  parent(A,X),            % * if A is the immediate parent of somebody
  X \= D,                 % * other than D
  N1 is N+1,              % * [ tick the generation count]
  ancestor( X, N1, G, D ) % and that somebody is the ancestor of D
  .                       % Also easy!

That allows us to say things like:

grandparent(A,C) :- ancestor(A,2,C).

great-grandparent(A,C) :- ancestor(A,3,C).

etc.

This will work for biological parentage, but if you are allowing non-biological parentage (e.g., step-parents and the like, then "I'm my own grandpa" is a possibility, and you will need to carry a list of visited nodes around so you can detect any cycles in the graph.

Try to figure out how to determine different degrees of kinship from this (what does a second cousin thrice removed look like?). You'll need to determine sibling status for starters.

Upvotes: 1

Related Questions