Why prolog fails to find a route to a vertices (in graph)?

Question

I have a question to you:

I have an exercise that says:

Let there be given edges in the directed graph arc (a, b), arc (b, c), arc (a, d), arc (d, e), arc (d, f), arc (f, a) and arc (f, g). Test go / 2, go1 / 3 predicates. I need to know why Prolog answers false for the following query:

? - go1 (a, b, X).

I have a graph illustrated below and a code pasted below.

The code is here:

arc(a,b).%these are the edges.
arc(b,c).
arc(a,d).
arc(d,e).
arc(d,f).
arc(f,a).
arc(f,g).

go(X,X).
go(X,Y):-arc(X,Z),go(Z,Y).
% without arc(f,a):
% yes ?- go(a,c).
% no  ?- go(d,c).
% no  ?- go(f,a).
% yes ?- go(a,g).
%
% with arc(f,a):
% yes ?- go(a,c).
% out of local stack ?- go(a,g).

member1(H,[H|_]).
member1(H,[_|T]):-member1(H,T).

go1(X,X,_).
go1(X,Y,T):-arc(X,Z),not(member1(Z,[X|T])),go1(Z,Y,[X|T]).
% with arc(f,a):
% yes ?- go1(a,c,[]).
% yes ?- go1(a,g,[]).

So guys, please help me to figure out why it happens? Why does Prolog answer false for the following query:

? - go1 (a, b, X).

I've tried to trace the query and I've gotten the answer that is below:

[trace]  ?- go1(a,b,X).
   Call: (8) go1(a, b, _982) ? creep
   Call: (9) arc(a, _1202) ? creep
   Exit: (9) arc(a, b) ? creep
^  Call: (9) not(member1(b, [a|_982])) ? creep
   Call: (10) member1(b, [a|_982]) ? creep
   Call: (11) member1(b, _982) ? creep
   Exit: (11) member1(b, [b|_1206]) ? creep
   Exit: (10) member1(b, [a, b|_1206]) ? creep
^  Fail: (9) not(user:member1(b, [a|_982])) ? creep
   Redo: (9) arc(a, _1202) ? creep
   Exit: (9) arc(a, d) ? creep
^  Call: (9) not(member1(d, [a|_982])) ? creep
   Call: (10) member1(d, [a|_982]) ? creep
   Call: (11) member1(d, _982) ? creep
   Exit: (11) member1(d, [d|_1206]) ? creep
   Exit: (10) member1(d, [a, d|_1206]) ? creep
^  Fail: (9) not(user:member1(d, [a|_982])) ? creep
   Fail: (8) go1(a, b, _982) ? creep
false.

Well, what I don't understand is why we have here the answer below:

 Exit: (11) member1(b, [b|_1206]) ? creep
   Exit: (10) member1(b, [a, b|_1206]) ? creep
^  Fail: (9) not(user:member1(b, [a|_982])) ? creep

Why does the Prolog not recognize that there is an edge from a to b? Why does it say that b is in the list that there is only [a] after all. Why does this call fail there? What's the reason of the query failure?

This graph illustration helps greatly, I find it always sadly missing in questions. — David Tonhofer

Willem Van Onsem Willem Van Onsem · Accepted Answer · 2020-06-04T18:45:25

You pass it a free variable X, so that means that the:

member(b, [a|X]).

call will succeed, indeed:

?- member(b, [a|X]).
X = [b|_2142] ;
X = [_2140, b|_2148] ;
X = [_2140, _2146, b|_2154]

Now not(member(Z, [X|T])) will succeed, given that the search of member(Z, [X|T]) fails, but here it will always succeed, since a free variable can always be grounded to a list that contains Z, hence it fails.

If you call it with:

go1 (a, b, [])

it will succeed, since then member(b, [a]) will indeed fail.

You can define a predicate that will reconstruct the path with:

go1(A, B, P) :-
    go1(A, B, P, []).

go1(A, A, [A], _).
go1(A, C, [A|T], V) :-
    arc(A, B),
    \+ member(B, [A|V]),
    go1(B, C, T, [A|V]).

and thus call it with go1(A, B, P) to obtain the path P.

Why prolog fails to find a route to a vertices (in graph)?

1 Answers