Prolog: Tracing routes between cities falls in infinite loop

Question

I'm coding a simple Prolog program of tracing routes between different cities and returnig two things: distance, and if the cities are directly connected. I succeded partially on the first one, since it does not return if the cities are directly connected, but the worse case is when it's not possible to trace a route between the cities, and the program, instead of simply returning false falls into an infinite loop, and I just can't understand why.

The code is below:

road (city1, city2, distance).

road(campinas,valinhos,16.9).
road(campinas,paulinia,30.1).
road(campinas,hortolandia,27.6).
road(campinas,holambra,41.1).
road(valinhos,vinhedo,7.8).
road(paulinia,cosmopolis,18.5).
road(hortolandia,sumare,9.1).
road(holambra,santo_antonio_de_posse,16.7).
road(vinhedo,louveira,11.2).
road(sumare,americana,12.3).
road(sumare,santa_barbara_doeste,29.8).
road(louveira,jundiai,12.9).
road(americana,limeira,27.6).
road(limeira,cordeiropolis,14.9).
road(santa_barbara_doeste,piracicaba,28.0).
road(cordeiropolis,araras,21.4).

conects(A,B,D):-road(A,B,D).
conects(A,B,D):-road(B,A,D).

distance(A,B,0):- A == B!.
distance(A,B,D):- conects(A, B, D).
distance(A,B,D):- distance(B1,B,D2), conects(A,B1,D1), not(conects(A,B,_)), D is D1 + D2.

What am I doing wrong?

looks like there is a typo here "not(conectas(A,B,)),". it has to be not(conects(A,B,)). and introduce a cut in distance(A,B,0):- A == B,!. to avoid backtracking. — Karpak
fixed it, the outcome still is out of local stack. What's happening? — Josh C

Limmen Limmen · Accepted Answer · 2016-12-10T15:51:41

If you trace your code you will see that it goes into an infinite loop since even if it can't unify the first two distance/3 clauses, it can always unify distance(A,B,D):- distance(B1,B,D2) since B1 is unbound.

Change your code as follows:

road(campinas,valinhos,16.9).
road(campinas,paulinia,30.1).
road(campinas,hortolandia,27.6).
road(campinas,holambra,41.1).
road(valinhos,vinhedo,7.8).
road(paulinia,cosmopolis,18.5).
road(hortolandia,sumare,9.1).
road(holambra,santo_antonio_de_posse,16.7).
road(vinhedo,louveira,11.2).
road(sumare,americana,12.3).
road(sumare,santa_barbara_doeste,29.8).
road(louveira,jundiai,12.9).
road(americana,limeira,27.6).
road(limeira,cordeiropolis,14.9).
road(santa_barbara_doeste,piracicaba,28.0).
road(cordeiropolis,araras,21.4).

conects(A,B,D):-road(A,B,D).
conects(A,B,D):-road(B,A,D).

distance(A,A,0).
distance(A,B,D):- conects(A, B, D).
distance(A,B,D):- not(conects(A,B,_)), conects(A1, A, D1), A1 \= A, conects(B1, B, D2), B1 \= B, distance(A1, B1, D3),  D is D1 + D2 + D3.

Test run:

[debug]  ?- distance(campinas, test, D).
false.

[debug]  ?- distance(campinas, louveira, D).
D = 35.9

Actually it can find infinite number of distances by moving many times between same cities:

[debug]  ?- distance(campinas, louveira, D).
D = 35.9 ;
D = 95.49999999999999 ;
D = 155.09999999999997 ;
D = 214.7 ;
D = 274.3 ;
D = 333.90000000000003 ;
D = 393.50000000000006 ;
D = 453.1000000000001 ;
D = 512.7 ;
D = 572.3 ;
D = 631.8999999999999 ;
D = 691.4999999999998 ;
D = 751.0999999999997 ;
D = 810.6999999999996 ;
D = 870.2999999999995

If you don't want that you can for instance add ! as follows:

distance(A,B,D):- not(conects(A,B,_)), conects(A1, A, D1), A1 \= A, conects(B1, B, D2), B1 \= B, distance(A1, B1, D3), !, D is D1 + D2 + D3.

Test-run:

[debug]  ?- distance(campinas, louveira, D).
D = 35.9.

[debug]  ?-

Hope it helps... trace/0 is your friend.

Prolog: Tracing routes between cities falls in infinite loop

1 Answers