/* PLAN - program znajdowania trasy polaczen miedzy miastami */
%%% Przeszukiwanie wgłąb z nawrotami


     droga(krakow,katowice).
     droga(katowice,opole).
     droga(wroclaw,opole).
     droga(krakow,zakopane).
     droga(krakow,kielce).
     droga(krakow,tarnow).
     droga(kielce,radom).
     droga(radom,warszawa).
     droga(warszawa,poznan).
     droga(warszawa,gdansk).
     droga(warszawa,lodz).
     droga(poznan,szczecin).
     droga(poznan,wroclaw).
     droga(tarnow,rzeszow).
     droga(rzeszow,lublin).
     droga(lublin,bialystok).
     droga(warszawa,bialystok).
     droga(szczecin,koszalin).
     droga(koszalin,gdansk).

%%% domknięcie symetryczne relacji droga/2
     
     przejazd(X,Y):- droga(X,Y).
     przejazd(X,Y):- droga(Y,X).
     
     p(X,Y):- przejazd(X,Y).

%%% Depth-First Strategy with calculating the depth

    path(F,F,T,T,D,D).                %%% A path from F to F is defined the current working path T
    path(I,F,Path,T,L,D):-            %%% A path from I to F where Path is the current path
       p(I,N), %write(N), nl,      %%% Find a new node N
       not(member(N,Path)),         %%% Check for ne cycle
       L1 is L+1,     
       path(N,F,[N|Path],T,L1,D).      %%% A Path from N to F - the last before F

%%% Breadth-First Strategy:

    %%%   Instead of a single path, the solution and the state of the search is represented as a set of paths
    %%%   Technically: this is a list of lists

   bf(F,[[F|Path]|_],[F|Path]).
   bf(F,[Path|SetOfPaths],T):-
      extend(Path,NewPaths),
      append(SetOfPaths,NewPaths,NewSetOfPaths),
      bf(F,NewSetOfPaths,T).

   extend([N|Path],NewPaths):-
      bagof([NextN,N|Path],(p(N,NextN),not(member(NextN,[N|Path]))),NewPaths),!.
   extend(_,[]).

   go(I,F,Path):- 
      bf(F,[[I]],Path).
      
      
      
 %%% Breadth-First Strategy with depth calculating

    %%%   Instead of a single path, the solution and the state of the search is represented as a set of paths
    %%%   Technically: this is a list of lists

 
   godc(I,F,Path,D):- 
      bf(F,[[I]],Path),
      length(Path,D).