/* Breadth-First Search                                   */
/*                                                        */
/*                DATA                                    */
/*                                                        */
/*                                   f                    */
/*                                 /                      */
/*                               e                        */
/*                             /    \                     */
/*                            b      g                    */
/*                          /                             */
/*                        a - c                           */
/*                          \     h                       */
/*                            d /                         */
/*                              - i - j                   */
/*                                                        */
e(a,b).
e(a,c).
e(a,d).
e(b,e).
e(e,f).
e(e,g).
e(d,h).
e(d,i).
e(i,j).


/***************************************************************/
/*                                                             */
/* Use breadth first search algorithm to search a graph, using */
/* the following algorithm :                                   */
/* 1. Form a one element queue consisting of the root node.    */
/* 2. Until the queue is empty or the goal has been reached,   */
/*    determine if the goal node is in the queue.              */
/*    2a. If the goal node is in the queue, do nothing.        */
/*    2b. If the goal node is not in the queue, remove the     */
/*        first element from the queue and add the first       */
/*        element's children, who have not been visited, to    */
/*        the back of the queue.                               */
/* 3. If the goal node has been found, announce success;       */
/*    otherwise announce failure.                              */
/*                                                             */
/***************************************************************/
?- list.

findall(X, G, _) :-
        asserta(found(mark)),
        call(G),
        asserta(found(X)),
        fail.
findall(_, _, L) :- collect_found([], M), !, L = M.

collect_found(S, L) :- getnext(X),
                       !,
                       collect_found([X|S], L).
collect_found(L, L).

getnext(X) :- retract(found(X)), !,
              X \== mark.

search(Start, Goal) :- seek1([Start], Goal, [Start]).

/* The [] in the next rule says that there are no more */
/* live nodes to be expanded, so just fail.            */

seek1([], _, _) :- !, fail.
seek1(Queue, Goal, _)  :- member(Goal, Queue).
seek1(Queue, Goal, Oldtail) :-
               seek2(Queue, [], Children, Oldtail, Newtail),
               seek1(Children, Goal, Newtail).

seek2([], Children, Children, Newtail, Newtail) :- !.
seek2([N|Ns], Sf, Children, Oldtail, Newtail) :-
              findall(D, (edge(N,D);edge(D,N)), Ds),
              addon(Ds, Sf, Newque, Oldtail, Temptail),
              seek2(Ns, Newque, Children, Temptail, Newtail).

addon([], L, L, Tn, Tn).
addon([N|Ns], L, M, To, Tn) :- (member(N, L);member(N, To)), !,
                               addon(Ns, L, M, To, Tn).
addon([N|Ns], L, M, To, Tn) :- addon(Ns, [N|L], M, [N|To], Tn).


member(X, [X|_]).
member(X, [_|Y]) :- member(X, Y).

edge(a,b).     edge(a,c).     edge(b,d).
edge(b,e).     edge(c,f).     edge(c,g).