% Изкуствен интелект, Факултет по математика и информатика, СУ "св. Кл. Охридски"

%--------------------------------------------------------------%

%   Uninformed Graph Searching Algorithms (Sicstus Prolog)     %

%   The graph should be represented as a set of facts          %

%   arc(Node1,Node2,Cost) loaded in the database               %

%--------------------------------------------------------------%



%--------------------------------------------------------------%

%   Depth-first search by using a stack                        %

%   call: depth_first(+[[Start]],+Goal,-Path).  %

%--------------------------------------------------------------%

depth_first([[Goal|Path]|_],Goal,FinalPath):-
		reverse([Goal|Path],FinalPath).

depth_first([Path|Stack],Goal,FinalPath) :-
    extend(Path,NewPaths), 
    append(NewPaths,Stack,NewStack),
    depth_first(NewStack,Goal,FinalPath).

extend([Node|Path],NewPaths) :-
    findall([NewNode,Node|Path],
            (arc(Node,NewNode,_), 
            \+ member(NewNode,[Node|Path])),  % for avoiding loops
            NewPaths).

        


%--------------------------------------------------------------%

%   Built-in Prolog depth-first search                         %

%   call: prolog_search(+Start,+Goal,-Path).                   %

%--------------------------------------------------------------%

prolog_search(Goal,Goal,[Goal]).

prolog_search(Node,Goal,[Node|Path]) :-

    arc(Node,NewNode,_),

    prolog_search(NewNode,Goal,Path).



%--------------------------------------------------------------%

%   Breadth-first search                                       %

%   call: breadth_first(+[[Start]],+Goal,-Path).%

%--------------------------------------------------------------%

breadth_first([[Goal|Path]|_],Goal, FinalPath):-
		reverse([Goal|Path],FinalPath).

breadth_first([Path|Queue],Goal,FinalPath) :-
    extend(Path,NewPaths), 
    append(Queue,NewPaths,NewQueue),
    breadth_first(NewQueue,Goal,FinalPath).

%--------------------------------------------------------------%

%   Depth-bound search                                         %

%   call: depth_bound(+DepthBound,+[[Start]],+Goal,-Path).     %

%--------------------------------------------------------------%

depth_bound(Depth,[[Goal|Path]|_],Goal,FinalPath):-
		reverse([Goal|Path],FinalPath).
 
depth_bound(Depth,[Path|Stack],Goal,FinalPath):-
    extend1(Depth,Path,NewPaths),
    append(NewPaths,Stack,NewStack),
    depth_bound(Depth,NewStack,Goal,FinalPath).
 
extend1(Depth,Path,NewPaths) :-
    length(Path,Len),
    Len < Depth-1, !,
    extend(Path,NewPaths).
 
extend1(_,_,[]).

%--------------------------------------------------------------%

%  Iterative Deepening search                                  %

%  call: iterative_deepening(+[[Start]],+Goal,-Path).          %

%--------------------------------------------------------------%

iterative_deepening(Stack,Goal,Path) :-
    findall(arc(X,Y,Z),arc(X,Y,Z),Graph),
  length(Graph,N),
  iterative_deepening1(1,Stack,Goal,Path,N).

iterative_deepening1(Depth,Stack,Goal,Path,Max) :- 
    nl,write(depth=Depth),
    depth_bound(Depth, Stack,Goal,Path).

iterative_deepening1(Depth,Stack,Goal,Path,Max) :- 
    Depth1 is Depth+1, Depth =< Max,!,
  iterative_deepening1(Depth1,Stack,Goal,Path,Max).
%--------------------------------------------------------------%

% Auxilliary predicates                                



member(X,[X|_]).

member(X,[_|T]) :-

    member(X,T). 



append([],L,L).

append([H|T],L,[H|V]) :-

    append(T,L,V).


reverse([],[]).
reverse([X|Rest],List):-
		reverse(Rest,NewRest),
		append(NewRest,[X],List).