Prolog: Remove circle from graph-like problem

Question

I have the following prolog program where I want to go from position a to position d. We can do that by following the path: a->b->c->d. Another path is: a->b->c->b->c->d etc. How do we remove that 'circling' path? I tried to remove it by using 'not(member(from_to(X,_),Z))' but it doesn't seem to work.

from_to(a, b).
from_to(b, c).
from_to(c, d).
from_to(d, c).
from_to(c, b).

move(X,Y,Z) :- from_to(X,Y), X \= Y, 
               Z = [from_to(X,Y)].      
move(X,Y,Z) :- from_to(X,K), K \= Y, move(K,Y,Z1), 
               Z = [from_to(X,K)|Z1],   
               not(member(from_to(X,_),Z)).

(if you remove the line 'not(member(from_to(X,_),Z))' the program works fine but outputs the circling paths)

You need to keep a list with the visited nodes (initially empty). Also, use the standard `\+/1` negation operator/predicate instead of the deprecated `not/1` predicate. — Paulo Moura, Sep 17 '18 at 18:50
`path(from_to, Path, X, Z)` using [this definition](https://stackoverflow.com/q/30328433/772868). Note that a list of visited nodes is more compact and contains the same information as a list of `from_to/2` terms. — false, Sep 17 '18 at 18:59
Thank you very much! I'll be posting the solution tomorrow (if no one else does). — Yhprums, Sep 17 '18 at 20:43

Willem Van Onsem · Accepted Answer · 2018-09-17T21:25:10.287

It is better to use an accumulator here: a variable that you update through recursive calls, and thus contains some sort of "memory". Here the accumulator can store a list of nodes that we have visited. In order to move to a new node, that node should not be in the list.

So we define a predicate move/4 instead of move/3, with:

move(X,Y,Z) :-
    move(X, Y, Z, [X]).

Now we can define the predicate move(S, D, Path, Visited) by using two rules:

in case S and D are the same, we are done, regardless what Visited is, we unify Path with [D]; and
otherwise we "walk" to another node N through the from_to/2 predicate, ensure that it is not a member of Visited, then we make a recursive call where we prepend S to the N to the visited nodes. We prepend X to the result of the recursive Z.

Like for example:

move(S, S, [S], _).
move(S, D, [S|Z], Visited) :-
    from_to(S, N),
    \+ member(N, Visited),
    move(N, D, Z, [N|Visited]).

For your sample graph:

it generates then:

?- move(a, d, Z).
Z = [a, b, c, d] ;
false.

?- move(a, D, Z).
D = a,
Z = [a] ;
D = b,
Z = [a, b] ;
D = c,
Z = [a, b, c] ;
D = d,
Z = [a, b, c, d] ;
false.

?- move(A, d, Z).
A = d,
Z = [d] ;
A = a,
Z = [a, b, c, d] ;
A = b,
Z = [b, c, d] ;
A = c,
Z = [c, d] ;
false.

?- move(A, D, Z).
A = D,
Z = [D] ;
A = a,
D = b,
Z = [a, b] ;
A = a,
D = c,
Z = [a, b, c] ;
A = a,
D = d,
Z = [a, b, c, d] ;
A = b,
D = c,
Z = [b, c] ;
A = b,
D = d,
Z = [b, c, d] ;
A = c,
D = d,
Z = [c, d] ;
A = d,
D = c,
Z = [d, c] ;
A = d,
D = b,
Z = [d, c, b] ;
A = c,
D = b,
Z = [c, b] ;
false.

In case a node is not "connected to itself" as in that we have not a path from a to a for example, we can implement move as:

move(S, D, [S|Z], V) :-
    from_to(S, N),
    \+ member(N, V),
    move2(N, D, Z, [N|V]).

move2(S, S, [S], _).
move2(N, D, [S|Z], V) :-
    move(N, D, Z, V).

Prolog: Remove circle from graph-like problem

1 Answers1