Prolog Recursion - Satisfying Both Directions (Simple)

3
votes

I am very new to Prolog and I was given this assignment.

My code is as follows:

relatives(cindy,tanya).
relatives(tanya,alan).
relatives(alan,mike).
relatives(kerry,jay).
relatives(jay,alan).

isRelated(X,Y):-
    relatives(X,Y).
isRelated(X,Y):-
    relatives(X,Z),
    isRelated(Z,Y).

Simple enough. This shows that if:

?- isRelated(cindy,mike).

Prolog will return true. Now, I'm stuck on how to make it return true if:

?- isRelated(mike,cindy).

I've been trying to come up with ideas like if isRelated(Z,Y) returns false, then switch X and Y, and run isRelated again. But I'm not sure if Prolog even allows such an idea. Any hints or advice would be greatly appreciated. Thanks!

UPDATE:************************************

So I added:

isRelated(X,Y):-
    relatives(X,Y);
    relatives(Y,X).

That will satisfy "direct" relationships, but simply enough I found out that it doesn't satisfy indirect relationships.

I really want to do something like, if the initial query:

isRelated(mike,cindy)

fails, then try and see if the reverse is true by switching X and Y:

isRelated(cindy,mike)

That will definitely return true. I just don't know how to do this syntactically in Prolog.

3
recursionprologtransitive-closure
A hint question: if relatives(Y,X) holds, are X and Y related? - Will Ness
Yes this is for homework. I am definitely not new to this site so I know not to ask for specific advice that might give away too much answers. I have been programming in C/Java for 2 years now but I recently just got started with Prolog. It is definitely a whole different animal here. - cYn
I've added the "homework" tag to your question, that's why I asked. :) Good luck taming Prolog, I esp. recommend "The Art of Prolog". When you get to the difference lists, skip over all the hype and just remember: it's just open-ended lists with the end pointer explicitly kept at hand, so it can be set when needed. Think of logvars as of named pointers, too, which can be set only once (before backtracking). Cheers. - Will Ness

3 Answers

1
votes

Further hint to those in the comments, as I can't leave comments yet: With your original set of rules and facts, isRelated(cindy,tanya) is true, but isRelated(tanya,cindy) is not, so you need to make isRelated(X,Y) symmetric; what simple addition to isRelated would achieve that?

Also, you could try drawing a graph of the relation relatives(X,Y), with an arrow from X to Y for all your base facts, and see if that helps you think about how the Prolog interpreter is going to attempt to satisfy a query.

1
votes

So to answer your last question, you don't switch the values of X and Y in Prolog, like you would call swap(x,y) in C, say. The value held by a logic variable can not be changed explicitly, only back-tracked over. But you can easily use Y where you would use X, and vice versa:

somePred(X,Y):- is_it(X,Y).
somePred(X,Y):- is_it(Y,X).

This defines somePred predicate as a logical disjunction, an "OR". It can be written explicitly too, like

somePred(X,Y):- is_it(X,Y) ; is_it(Y,X).

Note the semicolon there. A comma , between predicates OTOH defines a conjunction, an "AND" (a comma inside a compound term just serves to delimit the term's "arguments").

1
votes

YOu're almost there, you're just trying, I think, to cram too much stuff into one predicate.

Write the problem statement in English and work from that:

A relationship exists between two people, X and Y

  • if X and Y are directly related, or
  • if any direct relative of X, P, is related to Y.

Then it gets easy. I'd approach it like this:

First, you have your set of facts about relatives.

related( cindy, tanya ).
...
related( james, alan ).

Then, a predicate describing a direct relationship is terms of those facts:

directly_related( X , Y ) :- % a direct relationship exists 
  related(X,Y)               %   if X is related to Y
  .                          % ... OR ...
directly_related( X , Y ) :- % a direct relationship exists
  related(Y,X)               %   if Y is related to X
  .                          %

Finally, a predicate describing any relationship:

is_related(X,Y) :-        % a relationship exists between X and Y
  directly_related(X,Y)   %   if a direct relationship exists between them
  .                       % ... OR ...
is_related(X,Y) :-        % a relationship exists between X and Y
  directly_related(X,P) , %   if a direct relationship exists between X and some other person P
  is_related(P,Y)         %   and [recursively] a relationship exists between P and Y.
  .                       %

The solution is actually more complicated than this:

  1. The facts about relationships describe one or more graphs. More on graphs at http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/Graphs.html. What you're doing is finding a path from node X to Node Y in the graph.

  2. If the graphs described by the facts about relationships have one or more paths between X and Y, the above solution can (and will) succeed multiple times (on backtracking), once for every such path. The solution needs to be deterministic. Normallly, having established that two people are related, we're done: just because I have two cousins doesn't mean I'm related to my aunt twice.

  3. If the graph of relationships contains cycles (almost certainly true) such that a "circular" path exists: A → B → C → A …, the solution is susceptible to unlimited recursion. That means the solution needs to detect and deal with cycles. How might that be accomplished?