Prolog pathloop fail

Question

I have this program:

region(r1, 2110, [1,2]).
region(r2, 2210, [4,5,8]).
region(r3, 2310, [3,6]).
region(r4, 2410, [7,10,11,15]).
region(r5, 2510, [9,12]).
region(r6, 2610, [13,14]).

telephone(2310-6-64221, name(asd, nikos)).
telephone(2510-12-24234, name(dsa, kiki)).

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

connect(X, Y) :-
    next_to(X, Y).
connect(X, Y) :-
    next_to(Y, X).

pathloop(Start, End, _, Path) :-
    connect(Start, End),
    Path = [Start, End].
pathloop(Start, End, Visited, Path) :-
    connect(Start, Middle),
    not(member(Middle, Visited)),
    pathloop(Middle, End, [Middle|Visited], PathRest),
    Path = [Start|PathRest].

can_call(PersonA, PersonB, Route) :-
    telephone(_-Area1-_, name(PersonA, _)),
    telephone(_-Area2-_, name(PersonB, _)),
    pathloop(Area1, Area2,_, Route).

Everything runs except pathloop the base runs but the recursive one must to display a list Path which contains a path from A to B. But when i run the program and i type ?- can_call(asd, dsa, Route), it fails (returns false.). What I have to change on pathloop? i tried ?- pathloop(1, 5, [], Path). and it shows 10-20 results and then false.

Answer 1

I tried ?- pathloop(1,5,[],Path). and it shows 10-20 results and then false.

Let's look at the answers in detail and highlight any spurious parts...

?- pathloop(1,5,[],Path).
  Path = [1,4,5]                                       % ok
; Path = [1,4,5,8,5]
; Path = [1,4,5,8,9,12,15,10,7,6,3,5]
; Path = [1,4,5,3,5]
; Path = [1,4,5,3,6,7,10,15,12,9,8,5]
; Path = [1,4,8,5]                                     % ok
; Path = [1,4,8,9,12,15,10,7,6,3,5]                    % ok
; Path = [1,4,8,5,3,5]
; Path = [1,2,1,4,5]
; Path = [1,2,1,4,5,8,5]
; Path = [1,2,1,4,5,8,9,12,15,10,7,6,3,5]
; Path = [1,2,1,4,5,3,5]
; Path = [1,2,1,4,5,3,6,7,10,15,12,9,8,5]
; Path = [1,2,1,4,8,5]
; Path = [1,2,1,4,8,9,12,15,10,7,6,3,5]
; Path = [1,2,1,4,8,5,3,5]
; false.

Current status: 17 out of 20 answers are invalid!

To fix this we use meta-predicate path/4:

?- path(connect,Path,1,5).
  Path = [1,4,5]
; Path = [1,4,8,9,12,15,10,7,6,3,5]
; Path = [1,4,8,5]
; false.

Ok! Next, we adapt the definition of can_call/3 to use path/4 instead of pathloop/4:

can_call(PersonA, PersonB, Route) :-
    telephone(_-Area1-_, name(PersonA, _)),
    telephone(_-Area2-_, name(PersonB, _)),
    path(connect,Route,Area1,Area2).

But when I run [...] ?- can_call(asd,dsa,Route)., it fails (returns false.)

Let's re-run above query with the new version of can_call/3!

?- can_call(asd,dsa,Route).
  Route = [6,7,10,15,12]
; Route = [6,3, 5, 8, 9,12]
; Route = [6,3, 5, 4, 8, 9,12]
; false.

It works!

Answer 2

The problem is that when you make the call to pathloop/4 in can_call/3, you pass an ungrounded variable _ to Visited. In other words, you give an uninstantiated list. Now if you do a member check member(a,X) with X thus uninstantiated, it will say, "Yes! that's possible, simply make X=[a|_]".

So in order to fix this, rewrite can_call/3 to:

can_call(PersonA, PersonB, Route) :-
    telephone(_-Area1-_, name(PersonA, _)),
    telephone(_-Area2-_, name(PersonB, _)),
    pathloop(Area1, Area2,[Area1], Route).

Since at that moment, you have only visited Area1.

Additional advice

I think it makes more sense that the base case is defined as arriving at the destination:

pathloop(End,End, _,[End]) :-
    !.

The "cut" (!) disables the fact that once you reached the destination, you will keep searching for loops. For instance if you want to connect from 4 to 5. It will not propose a route like 4 -> 5 -> 8 -> 4 -> 5 thus looping after reaching.

Next the inductive case searches for a Next (I would not call it a Middle because it is not the node in the middle, but one that is next to the start.

pathloop(Start, End, Visited,[Start|Path]) :-
    connect(Start, Middle),
    \+ member(Middle, Visited),
    pathloop(Middle, End,[Middle|Visited],Path).

It is also better not to use unifications X=[A|B], if these can already be made at the head level. It allows faster execution, especially if you would call the predicate in the opposite direction.