%------------------------------------------------------------
% Depth - first search by Yoav Shoham
% arguments: arc function (+), start node (+), goal predicate (+),
% solution (i.e. path from start node to a node satisfying the goal predicate
%------------------------------------------------------------
depth_first_search(Arc,Start,GoalPred,Sol):-
  dfs(Arc,[[Start]],[],GoalPred,Sol).

%------------------------------------------------------------
% The second argument to dfs is the OPEN stack,
% the third argument is the CLOSED list
%------------------------------------------------------------
dfs(_,[[Node|Path]|_],_,GoalPred,[Node|Path]):-
  call(GoalPred,Node).

dfs(Arc,[[Node|Path]|MoreOPEN],CLOSED,GoalPred,Sol):-
  %  find the new neighbors of the first OPEN node
  %  and add the current path to each of them:
  findall([Next,Node|Path],
  (call(Arc,Node,Next),
   not(member([Next|_],[[Node|Path]|MoreOPEN])),
   not(member(Next,CLOSED))),
  NewPaths),
	%  place the new paths on top of the stack
  append(NewPaths,MoreOPEN,NewOPEN),
  %closing(Node),
  dfs(Arc,NewOPEN,[Node|CLOSED],GoalPred,Sol).