% Breadth first search

:- ensure_loaded(showPath).

bfs :- 
  bfs(Path), 
  reverse(Path,PathReversed),
  write('Best first search\n'),
  showPath(PathReversed).
	

bfs(Path) :- 
  start(S), 
  bfs(S,Path).


bfs(S,Path) :-
  bfs1([[S]],Path).

bfs1(Q,[G,S|Tail]) :-
  dequeue(Q,[S|Tail],_),
  arc(S,G),
  goal(G).

bfs1(Q1,Solution) :-
  dequeue(Q1,[S|Tail],Q2),
  findall([Succ,S|Tail], 
          (arc(S,Succ), not(member(Succ,Tail))),
          NewPaths),
  enqueueList(NewPaths,Q2,Q3),
  bfs1(Q3,Solution).


% this is a simple inplementation of a queue datastructure as a list.
% It's inefficient because its use of append, which does a lot of
% copying.  There is a clever and efficient qay to do this in Prolog.
% See the Sictus queue module.  We use this because it's so simple.

emptyQueue([]).

dequeue([X|Qout],X,Qout).

enqueueList(L,Qin,Qout) :- append(Qin,L,Qout).
enqueue(X,Qin,Qout) :- append(Qin,[X],Qout).