transitive closure over a symmetric relation in prolog

Question

I am a prolog beginner and I want to create the "brother" relation.

The relation should be symmetric as in if brother(alin, alex) is true, brother(alex, alin) should be as well.

It should also be transitive as in if brother(alin, alex) and brother(alex, claudiu) are true, brother(alin, claudiu) should be as well.

Combining the to properties, if brother(alex, alin) and brother(alex, claudiu) are true, brother(alin, claudiu) should also be true.

Here is my code:

r_brother(alin, alex).
r_brother(alin, ciprian).
r_brother(alex, claudiu).

s_brother(X, Y) :- r_brother(X, Y).
s_brother(X, Y) :- r_brother(Y, X).

brother(L1, L2) :-
    t_brother(L1, L2, []).

t_brother(L1, L2, _) :-
    s_brother(L1, L2).

t_brother(L1, L2, IntermediateNodes) :-
    s_brother(L1, L3),
    \+ member(L3, IntermediateNodes),
    t_brother(L3, L2, [L3 | IntermediateNodes]).

r_brother - is the basic relation

s_brother - is the symmetric brother relation(this works well)

t_brother - this should be the transitive and symmetric relation, I keep the intermediate nodes so I don't get a loop

The problem is that the answer for:

?- brother(X, alin).

is:

X = alex ;
X = ciprian ;
X = alin ;
X = alin ;
X = alin ;
X = alin ;
X = alex ;
X = alex ;
X = alex ;
X = alex ;
X = ciprian ;
X = ciprian ;
X = claudiu ;
X = claudiu ;
false.

I looked through the trace and I understand what the problem is, but I don't know how to solve it.

alin should not be a possible answer and the others should appear a single time.

danielp · Accepted Answer · 2014-05-15T12:57:39.807

3

I think the basic problem is that you do not check if L2 is already found in the first clause of t_brother/3. And the initial L1 should be added to the list in brother/2:

brother(L1, L2) :-
  t_brother(L1, L2, [L1]).                   % <-- [L1] instead of []

t_brother(L1, L2, IntermediateNodes) :-
  s_brother(L1, L2),
  \+ member(L2, IntermediateNodes).          % <-- added this check

t_brother(L1, L2, IntermediateNodes) :-      % <-- this clause is unchanged
  s_brother(L1, L3),
  \+ member(L3, IntermediateNodes),
  t_brother(L3, L2, [L3 | IntermediateNodes]).

You can still shorten the solution by using a disjunction:

t_brother(L1, L2, IntermediateNodes) :-
  s_brother(L1, L3),
  \+ member(L3, IntermediateNodes),
  ( L2=L3
  ; t_brother(L3, L2, [L3 | IntermediateNodes])).

edited May 15 '14 at 12:57

answered May 08 '14 at 11:08

danielp

1,179
11
26

Just so I understand, in "(L2=L3 ; t_brother(L3, L2, [L3 | IntermediateNodes]))" - does this mean that if the first condition(L2=L3) is true it doesn't need to do verify the second condition? – colegu May 08 '14 at 11:55
No, it is a simple disjunction `(AlternativeA;AlternativeB)`. Either `L2` is the next brother `L3` or we find a `L2` by calling t_brother recursively. Maybe you have confused it with the `(Condition -> Then ; Else)` statement which implies a local cut? – danielp May 08 '14 at 12:00

score 1 · Answer 2 · answered May 08 '14 at 11:02

1

You can write the brother relation like this (exactly like the transitive definition)

s_brother(X, Y) :- r_brother(X, Y);r_brother(Y, X).

brother(X,Y) :- s_brother(X, Y).
brother(X,Y) :- s_brother(X, Z),s_brother(Z, Y),X\=Y.

which mean X is brother of Y if he is a symmetric brother, or they have a brother in common, and add the condition that they are different.

try adding to X\=Y to your code to get rid of "alin" as a solution.

answered May 08 '14 at 11:02

Siham

138
1
7

thanks, this is a lot shorter :), but the problem here is that if you add another fact like r_brother(claudiu, jack). you will not get "jack" as an answer. This has to be recursive to work. – colegu May 08 '14 at 11:23

transitive closure over a symmetric relation in prolog

2 Answers2

Linked

Related