% Simple international route planning example

% Is there a route from a to b?

route(A,B) :- same_country(A,B), rail([],A,B).
route(A,B) :- airport(A,C), airport(B,D), fly(C,D), rail([],A,C), rail([],D,B).

rail(_,X,X).
rail(S,X,Y) :- rail_link(Z,X), \+ member(Z,S), rail([Z|S],Z,Y).
rail(S,X,Y) :- rail_link(X,Z), \+ member(Z,S), rail([Z|S],Z,Y).

airport(X,Y) :- airport(Y), same_country(X,Y).

same_country(X,Y) :- country(X,C), country(Y,C).

country(edinburgh,scotland).
country(london,england).
country(glasgow,scotland).
country(fort_william,scotland).
country(inverness,scotland).
country(oxford,england).
country(bristol,england).
country(stirling,scotland).

fly(edinburgh,london).
fly(edinburgh,bristol).
fly(london,edinburgh).
fly(glasgow,london).
fly(london,glasgow).

airport(bristol).
airport(london).
airport(edinburgh).
airport(glasgow).

rail_link(edinburgh,glasgow).
rail_link(glasgow,fort_william).
rail_link(stirling,glasgow).
rail_link(edinburgh,inverness).
rail_link(london,oxford).
rail_link(stirling,inverness).

member(X,[X|_]).
member(X,[_|L]) :- member(X,L).

% Revised version with appropriate cuts
%
% route1(A,B) :- same_country(A,B), rail1([],A,B), !.
% route1(A,B) :- airport(A,C), airport(B,D), fly(C,D), rail1([],A,C), rail1([],D,B).
%
% rail1(_,X,X) :- !.
% rail1(S,X,Y) :- rail_link(Z,X), \+ member(Z,S), rail1([Z|S],Z,Y), !.
% rail1(S,X,Y) :- rail_link(X,Z), \+ member(Z,S), rail1([Z|S],Z,Y), !.
