CODEWITHSUNDEEP
prologfamily-tree
CodeHunter
CodeHunter

Reputation: 2082

How to find kth generation of a family tree in Prolog?

I am trying to find a list of all the family members for the kth generation of a given family. We are given the first members of the family and the family tree as well. Below is my KB for the same and also the implementation. I am not able to figure how I can get the kth generation for this family tree? Lets say k = 4. One way of doing it is that I can find 4 times the relation like this:

4thGen(X,Y) :- parent(X,A),parent(A,B),parent(B,C),parent(C,Y)

but this is not the correct way for this I believe.

male(alex).
male(romeo).
male(oscar).
male(peter).
male(bruno).
male(georg).
male(otto).
male(pascal).
male(jean).

female(lina).
female(julia).
female(rosa).
female(eva).
female(ruth).
female(silvia).
female(ida).
female(irma).
female(olga).
female(marie).
female(tina).

parent(alex,julia).
parent(alex,rosa).
parent(lina,julia).
parent(lina,rosa).
parent(romeo,peter).
parent(julia,peter).
parent(rosa,silvia).
parent(oscar,ida).
parent(eva,ida).
parent(eva,bruno).
parent(peter,bruno).
parent(peter,georg).
parent(peter,irma).
parent(ruth,georg).
parent(ruth,irma).
parent(silvia,otto).
parent(silvia,pascal).
parent(irma,olga).
parent(irma,jean).
parent(otto,olga).
parent(otto,jean).
parent(jean,tina).
parent(marie,tina).






father(X,Y):-parent(X,Y),male(X).
grandfather(X,Y):-father(X,Z),parent(Z,Y).

Upvotes: 1

Views: 792

Answers (1)

coder
coder

Reputation: 12972

In order to make more general predicates you can use recursion:

kthGen(X,Y,1):-parent(X,Y).
kthGen(X,Y,K) :- parent(X,A),K1 is K-1,kthGen(A,Y,K1).

Here are some queries: 

?- kthGen(alex,julia,1).
true ;
false.

?- kthGen(alex,peter,2).
true ;
false.

?- kthGen(alex,bruno,2).
false.

?- kthGen(alex,bruno,3).
true ;
false.

Two important things to notice here:

  • Firstly your graph is directed (e.g if parent(A,B) you can't have parent(B,A) ), this matters because if it was undirected you could fall into cycles (e.g kthGen(alex,julia,4). would succeed due to the path alex->julia->alex->julia ,you could solve that by adding another list that keeps track persons you've visited).

  • Secondly if you try:

    ?- kthGen(alex,bruno,K). ERROR: Arguments are not sufficiently instantiated ERROR: In: ERROR: [8] kthGen(alex,bruno,_7630) ERROR: [7] <user>

So the predicate kthGen/3 does not have relational behavior. You could use library CLPFD:

:- use_module(library(clpfd)).

kthGen(X,Y,1):-parent(X,Y).
kthGen(X,Y,K) :- parent(X,A),K1 #= K-1,kthGen(A,Y,K1).

Now if you try:

?- kthGen(alex,bruno,K).
K = 3 ;
false

much better !!.

UPDATE

In order to find kth generation persons from a person X you could modify accordingly:

:- use_module(library(clpfd)).

kthGen(Y,1,[Y]).
kthGen(X,K,[X|T]) :- parent(X,A),K1 #= K-1,kthGen(A,K1,T).

Example:

?- kthGen(alex,4,L).
L = [alex, julia, peter, bruno] ;
L = [alex, julia, peter, georg] ;
L = [alex, julia, peter, irma] ;
L = [alex, rosa, silvia, otto] ;
L = [alex, rosa, silvia, pascal] ;
false.

This gives all the possible 4th generations from alex. If you want to find more complex e.g 4th gen from alex or lina you could find it separately an write another predicate that concatenates the results...

UPDATE 2

In last update I keep track of all persons until 4th generation. If you want just 4th gen simply modify like:

kthGen(Y,1,[Y]).
kthGen(X,K,L) :- parent(X,A),K1 #= K-1,kthGen(A,K1,L).

Examlpe:

?- kthGen(alex,4,L).
L = [bruno] ;
L = [georg] ;
L = [irma] ;
L = [otto] ;
L = [pascal] ;
false.

Now if you want all results in one list:

?- findall(X,kthGen(alex,4,[X]),L).
L = [bruno, georg, irma, otto, pascal].

Upvotes: 2

Related Questions