% Figure 13.8: Depth-first search for AND/OR graphs. This program
% does not avoid infinite cycling. Procedure 'solve' finds a solution 
% tree, procedure 'show' displayes such a tree. 'show' assumes that 
% each node on output only takes 1 characetr.


%  Depth-first AND/OR search
%  solve( Node, SolutionTree):
%    find a solution tree for Node in an AND/OR graph

:-  op( 500, xfx, :).
:-  op( 600, xfx, ---> ).

solve( Node, Node)  :-              % Solution tree of goal node is Node itself
  goal(Node).

solve( Node, Node ---> Tree)  :-
  Node ---> or:Nodes,               % Node is an OR-node
  member( Node1, Nodes),            % Select a successor Node1 of Node
  solve( Node1, Tree).

solve( Node, Node ---> and:Trees)  :-
  Node ---> and:Nodes,              % Node is an AND-node
  solveall( Nodes, Trees).          % Solve all Node's successors

% solveall( [Node1,Node2, ...], [SolutionTree1,SolutionTree2, ...])

solveall( [], []).

solveall( [Node|Nodes], [Tree|Trees])  :-
  solve( Node, Tree),
  solveall( Nodes, Trees).

%  Displaying a solution tree

show(Tree)  :-                   % Display solution tree
  show(Tree,0), !.               % Indented by 0

% show( Tree, H): display solution tree indented by H

show( Node ---> Tree, H)  :-  !,
  write(Node), write(' ---> '),
  H1 is H + 7,
  show( Tree, H1).

show( and:[T], H)  :-  !,        % Display single AND tree
  show(T,H).

show( and:[T|Ts], H)  :-  !,     % Display AND-list of solution trees
  show( T, H),
  tab(H),
  show( and:Ts, H).

show( Node, H) :-
  write(Node), nl.