path finding in prolog

Question

I need to write a program in prolog for finding paths, for example, for the graph:

edge(a, b). 
edge(a, c). 
edge(c, b).

and the test case are:

/* test case 1 */
?- path(a, b, P). 
P = [a, b] ;
P = [a, c, b] ; 
false. 

/* test case 2 */
?- path(c,b,[c,b]).
true.

and my code is

path(X,Y,[X,Y]):-
    edge(X,Y).
path(X,Z,[X|P]):-
    edge(X,Y),
    path(Y,Z,P).

However, for the test case 2, my code will show

?- path(c,b,[c,b]).
true;
false.

I know that I should add a cut in my code to remove the false in case 2, but it will remove the false in case 1 too. How can I solve this problem?

When I try this in SWI-Prolog, I get a false in the second case. — RonaldBarzell
It is because of the name of the atoms, and I have correct it. Sorry about that — Kit Yam Tse

Fyre Fyre · Accepted Answer · 2012-11-30T18:55:45

Its because both of your functions are same and i think prolog checks both....in first case it fails because only one of the function satisfies it i.e. path(c,b,P) but in second case path(c,b,[c,b]

It check both the functions

path(X,Y,[X|P] here X = c and P = b
and
path(X,Y,[X,Y]) here also X=c and Y = b

so as both the functions act same in the second case you need to modify one of your cases. for eg: for 2 vertices only you could use

path(X,Y,[X|Y|[]]):- edge(X,Y).

instead of

path(X,Y,[X,Y]):-
edge(X,Y).

it will expect only two variables and i think this should solve your problem.

path finding in prolog

1 Answers