Search code examples
prologfamily-tree

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).
Solution

  • 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].