% From the book
% PROLOG PROGRAMMING IN DEPTH
% by Michael A. Covington, Donald Nute, and Andre Vellino
% (Prentice Hall, 1997).
% Copyright 1997 Prentice-Hall, Inc.
% For educational use only

% FLIGHT.PL
% System for finding flight connections or flight plans.

%
% plan(+Start,+Goal,-Plan)
%   An algorithm for finding a flight plan linking the two cities
%   Start and Goal. The algorithm does not take total distance 
%   traveled into account.
% 

plan(Start,Goal,Plan) :- planner(Goal,[0,Start],Path),
                         reverse(Path,[],Plan).

%
% planner(+Goal,+PartialPlan,-CompletePlan)
%   Takes a partial flight plan and completes it all the way
%   to the destination city without regard to distances traveled.
%

planner(Goal,[Miles,Goal|Cities],[Miles,Goal|Cities]) :- !.
planner(Goal,[OldMiles,Current|Cities],Path) :-
        connected(Current,Next,MoreMiles),
        \+ member(Next,Cities),
        NewMiles is OldMiles + MoreMiles,
        planner(Goal,[NewMiles,Next,Current|Cities],Path).

%
% best_plan(+Start,+Goal,-Plan)
%   An algorithm for finding the shortest flight plan
%   linking two cities.
%

best_plan(Start,Goal,[Min|Plan]) :-   
        setof(Path,planner(Goal,[0,Start],Path),[[Min|Best]|_]),
        reverse(Best,[],Plan).

%
% good_plan(+Start,+Goal,-Plan)
%   A heuristic for quickly finding a flight plan of
%   reasonable length linking two cities.
%

good_plan(Start,Goal,[Miles|Plan]) :-
        smart_planner(Goal,[0,Start],[Miles|Good]),
        reverse(Good,[],Plan).

%
% smart_planner(+Goal,+PartialPlan,-CompletePlan)
%   Takes a partial flight plan and completes it all the way
%   to the destination city, giving priority at each step to
%   those cities which can be reached from the current city
%   that are nearest the destination city.
%   

smart_planner(Goal,[Miles,Goal|Cities],[Miles,Goal|Cities]).
smart_planner(Goal,[OldMiles,Current|Cities],Plan) :-
        setof(option(Miles,City),
	      X^(connected(Current,City,X),
		 distance(City,Goal,Miles)),
	      List),
        member(option(Min,Next),List),
	connected(Current,Next,MoreMiles),
        \+ member(Next,Cities),
        NewMiles is OldMiles + MoreMiles,
	smart_planner(Goal,[NewMiles,Next,Current|Cities],Plan).

/*smart_planner(Goal,[OldMiles,Current|Cities],Plan) :-
        findall(City,connected(City,Current,_),CityList),
        setof(Miles,distance(Goal,CityList,Miles),MilesList),
        member(Min,MilesList),
        distance(Next,[Goal],Min),
        connected(Current,Next,MoreMiles),
        \+ member(Next,Cities),
        NewMiles is OldMiles + MoreMiles,
        smart_planner(Goal,[NewMiles,Next,Current|Cities],Plan).
*/
%
% Predicates for interpreting information about the travel data.
%

connected(City1,City2,Miles) :- data(City1,City2,Miles,y).
connected(City1,City2,Miles) :- data(City2,City1,Miles,y).

distance(City,City,0).
distance(City1,City2,Miles) :- data(City1,City2,Miles,_).
distance(City1,City2,Miles) :- data(City2,City1,Miles,_).

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

reverse([],List,List).
reverse([X|Tail],SoFar,List) :-
	reverse(Tail,[X|SoFar],List).