Using Prolog Lists in Recursion

Question

So I am trying to use a recursive method to find a path between two people. Here is the quick background: I define some facts in(X,Y). That show who is related, ie. in(person1,project1), in(person2,project1), etc etc. Now any two people are related if they were in the same project as each other, or there is a linking path of people between them. For example p1 worked on A p2 worked on A and B and p3 worked on B therefore there is a path from p1 to p3 through p2. These paths can be any length.

I am trying to solve this recursively (don't see any other way), but there is an annoying problem:

related(A,B) :-
        in(A,X),
        in(B,X),
        not(A=B).

chain(A,B) :-
        related(A,B).
chain(A,B) :-
        related(A,Y),       
        chain(Y,B).

The issue is that the path can repeat itself. It can go from p1 to p2 back to p1 endless times. A person should not be in the path more than 1 time.

I tried to fix this with a list that I add to. If a person is already in the list, they can't be added again:

related(A,B,L) :-
        in(A,X),
        in(B,X),not(A=B).

chain(A,B,L) :-
        related(A,B,L).
chain(A,B,L) :-
        related(A,Y,L),
        not(member(Y,L)),
        append(L,[Y],Q),
        chain(Y,B,Q).

And it sort of worked, but caused a ton of random errors, repeating some people multiple times, some only once, and then failing. Does this approach look right? Am I totally using lists wrong?

Thank You.

Answer 1

Here is an alternative way, maybe less efficient but rather general, based on fixpoint computation.

connected(Found, Connected) :-
    collect(Found, [], Ext),
    (   Ext == Found
    ->  Connected = Found
    ;   connected(Ext, Connected)
    ).

collect([], Set, Set).
collect([E|Es], Set, Fix) :-
    extend(E, Set, Ext),
    collect(Es, Ext, Fix).

extend(E, Set, Ext) :-
    directly(E, DirectConn),
    ord_union(DirectConn, Set, Ext).

directly(A, DirectConn) :-
    setof(B, P^(in(A, P), in(B, P)), DirectConn).

We must call connected(Found, Connected) with a sorted list, and it loops until the set cannot be extended. For instance, with this test data

in(anna,  project1).
in(bob,   project1).
in(bob,   project2).
in(chris, project2).
in(dan,   project3).

?- connected([bob],L).
L = [anna, bob, chris].

?- connected([dan],L).
L = [dan].

I allow on purpose directly/2 get identity, i.e.

?- directly(X,Y).
X = anna,
Y = [anna, bob] ;
...
X = dan,
Y = [dan].

Answer 2

First improvement. Are you looking for all the chains of relations or do you want to check if there is one chain of relation? In the first case add a cut.

chain(A,B) :-
        related(A,B), !.
chain(A,B) :-
        related(A,Y),       
        chain(Y,B).

In the second case, Prolog does exactly what it's asked to do, that is finding all the possible chains.

Please post a query that causes problems so that we can reason together on it and improve the solution.

Answer 3

I think I was never perfectly clear enough, but I ended up solving this myself. I put the code below.

What really mattered was an effective notchain predicate and then making sure I did the appends correctly. I also created a notsame predicate to replace the not(A=B). The code is below. Most of the answer was making sure that there were [] around what was being appended to the list. Not having the correct [] around what was being appended caused errors.

notchain(X,L) :-

member(X,L),!,fail.

notchain(X,L).

And then:

chain(A,B,L) :-

related(A,B), append(L,[A],Q), append(Q,[B],Z), write(final),writeln(Z).

chain(A,B,L) :- notchain(A,L), append(L,[A],Q), related(A,Y), chain(Y,B,Q).

This was used in related:

notsame(A,B) :-
(A=B),!,fail.

notsame(A,B).