% PATH FINDING

% the database
go(shinjuku,ikebukuro).  go(ikebukuro,tabata).   go(tabata,ueno).
go(ueno,akihabara).      go(akihabara,kanda).    go(kanda,tokyo).
go(tokyo,shinagawa).     go(shinagawa,shibuya).  go(shibuya,yoyogi).
go(yoyogi,shinjuku).
go(ikebukuro,akabane).   go(akabane,tabata).
go(yoyogi,ochanomizu).   go(ochanomizu,akihabara).
go(ochanomizu,kanda).

% depth-first version
% path(Source, Destination, List_of_stations_on_the_way)
path(S,D,Path) :-
   path(S,[],D,PathR), reverse(PathR,Path).
path(D, Visited,D,[D|Visited]).
path(S0,Visited,D,PathR) :- 
   reach(S0,S), not_in(S,Visited),
   path(S,[S0|Visited],D,PathR).

% iterative-deepening version
% path_iterative_deepening(Source, Destination, List_of_stations_on_the_way)
path_iterative_deepening(S,D,Path) :-
    path_id(S,D,PathR), reverse(PathR,Path).
path_id(D,D,[D]).
path_id(S,D,[D|PathR]) :-
   path_id(S,D0,PathR), reach(D0,D).
 
% auxiliary predicates
reach(S,D) :- go(S,D).
reach(S,D) :- go(D,S).

not_in(_,[]).
not_in(X,[Y|L]) :- dif(X,Y), not_in(X,L).

reverse(L,Lrev) :- rev1(L,[],Lrev).
rev1([],   S,S).
rev1([A|L],S,Lrev) :- rev1(L,[A|S],Lrev).