Simple graph search in Prolog

Question

Hi,

I'm trying to code a simple graph search in SWI-Prolog. I came up with the following program:

adjacent(1,4). adjacent(4,2). adjacent(3,6).
adjacent(6,4). adjacent(7,10). adjacent(4,9).
adjacent(5,10). adjacent(7,10). adjacent(7,12).
adjacent(6, 11). adjacent(13,11). adjacent(9,14).
adjacent(14,12). adjacent(10,15). adjacent(9,12).

connected(X,Y) :- adjacent(X,Y); adjacent(Y,X).

path(A,B,[A|B]) :- connected(A,B).

path(A,B,[A|R]) :-
    \+member(R,A),
    connected(A,C),
    A \== C,
    path(C,B,R).

But this program causes a stack overflow. What am I doing wrong and how can it be fixed?

Answer 1

The main problem here is the member test: the signature is member(Element,List); you seem to assume that the arguments are the other way 'round.

In addition, your first path predicate is meant to test a two-element list, however, B really unifies with the rest list (which then isn't connected).

If you fix these, you find that this can only work for fully instantiated variables, as the negation doesn't work well for unbound variables.

Answer 2

You are trying to use the returned path also as a check for avoiding loops. That won't work when searching for a path because the path is not yet instantiated at the negation.

The simplest solution is to add another input argument where you collect the nodes already visited and check these to avoid repetition.

Also, I think you should check A \== B instead of A \== C. You don't have loops on nodes, so the latter will never happen. The case A == B is handled in the first clause, so you don't want to do that again in the second clause.

You also got the arguments of member backwards and need to fix the list in the first clause, as Martin has written.

An advanced way to avoid infinite loops without an extra argument is to use freeze/2 on the negation.

Also take a look at how debugging works in Prolog, that might help you understand things better.