Prolog infinite loop

Question

I'm fairly new to Prolog and I hope this question hasn't been asked and answered but if it has I apologize, I can't make sense of any of the other similar questions and answers.

My problem is that I have 3 towns, connected by roads. Most are one way, but there are two towns connected by a two way street. i.e.

facts:  
road(a, b, 1).  
road(b, a, 1).  
road(b, c, 3). 

where a, b and c are towns, and the numbers are the distances

I need to be able to go from town a to c without getting stuck between a and b

Up to here I can solve with the predicates: (where r is a list of towns on the route)

route(A, B, R, N) :- 
  road(A, B, N), 
  R1 = [B],
  R = [A|R1],
  !.

route(A, B, R, N) :- 
  road(A, C, N1), 
  route(C, B, R1, N2), 
  \+ member(A, R1), 
  R = [A | R1], 
  N is N1+N2.

however if I add a town d like so

facts:
road(b, d, 10)

I can't get Prolog to recognize this is a second possible route. I know that this is because I have used a cut, but without the cut it doesn't stop and ends in stack overflow.

Furthermore I will then need to be able to write a new predicate that returns true when R is given as the shortest route between a and c.

Sorry for the long description. I hope someone can help me!

Answer 1

This is a problem of graph traversal. I think your problem is that you've got a cyclic graph — you find the leg a-->b and the next leg you find is b-->a where it again finds the leg a-->b and ... well, you get the picture.

I would approach the problem like this, using a helper predicate with accumulators to build my route and compute total distance. Something like this:

% ===========================================================================
% route/4: find the route(s) from Origin to Destination and compute the total distance
%
% This predicate simply invoke the helper predicate with the
% accumulator(s) variables properly seeded.
% ===========================================================================
route(Origin,Destination,Route,Distance) :-
  route(Origin,Destination,[],0,Route,Distance)
  .

% ------------------------------------------------
% route/6: helper predicate that does all the work
% ------------------------------------------------
route(D,D,V,L,R,L) :-              % special case: you're where you want to be.
  reverse([D|V],R)                 % - reverse the visited list since it get built in reverse order
  .                                % - and unify the length accumulator with the final value. 
route(O,D,V,L,Route,Length) :-     % direct connection
  road(O,D,N) ,                    % - a segment exists connecting origin and destination directly
  L1 is L+N ,                      % - increment the length accumulator
  V1 = [O|V] ,                     % - prepend the current origin to the visited accumulator
  route(D,D,V1,L1,Route,Length)    % - recurse down, indicating that we've arrived at our destination
  .                                %
route(O,D,V,L,Route,Length) :-     % indirect connection
  road(O,X,N) ,                    % - a segment exists from the current origin to some destination
  X \= D ,                         % - that destination is other than the desired destination
  not member(X,V) ,                % - and we've not yet visited that destination
  L1 is L+N ,                      % - increment the length accumulator
  V1 = [O|V] ,                     % - prepend the current origin to the visited accumulator
  route(X,D,V1,L1,Route,Length)    % - recurse down using the current destination as the new origin.