%Inefficient breadth-first search   
  %(almost identical to the depth-first search program) 

  breadth_first_search_slow(Start, GoalPred, Sol) :- 
	  bfs_slow([[Start]], [ ], GoalPred, Sol).

  bfs_slow([[Node | Path]  |   _  ],  _  , GoalPred, [Node | Path]) :- 
	  Goal =.. [GoalPred, Node], 
	  Goal. 
  bfs_slow([[Node | Path]  |  MoreOPEN], CLOSED, GoalPred, Sol) :- 
	  findall(
		  [Next,Node | Path], 
		  (
		    arc(Node, Next),  % original has lmember
		    not(member([Next |  _  ], [[Node | Path]  |  MoreOPEN])), 
		    not(member(Next, CLOSED))
		  ), 
		  NewPaths
		    ), 
	  %place the new paths at the  bottom of the queue: 
	  append(MoreOPEN, NewPaths, NewOPEN), 
	  bfs_slow(NewOPEN, [Node | CLOSED], GoalPred, Sol).


  % More efficient breadth-first search  

  breadth_first_search(Start, GoalPred, Sol) :- 
	  bfs([[Start]  |  Qtail], Qtail, [ ], GoalPred, Sol).

  %if the queue is empty, fail 
  bfs(OPEN,Qtail, _  , _  , _  ) :- 
	  OPEN==Qtail, !, 
	  fail. 
  %otherwise, as in the previous implementation: 
  bfs([[Node | Path]  |   _  ],  _  ,  _  , GoalPred, [Node | Path]) :- 
	  Goal =.. [GoalPred, Node], 
	  Goal. 
  bfs([[Node | Path]  |  MoreOPEN], Qtail, CLOSED, GoalPred, Sol) :- 
	  findall(
		  [Next,Node | Path], 
		  (
		    arc(Node, Next), %dl_member for difference lists
                    not(dlmember([Next|_], [[Node|Path]|MoreOPEN], Qtail)), 
		    not(member(Next, CLOSED))
		  ), 
		  NewPaths
		     ), 
	  %and here is where the difference list pays off:  
	  append(NewPaths, NewQtail, Qtail), 
	  bfs(MoreOPEN, NewQtail, [Node | CLOSED], GoalPred, Sol).

% membership in a difference list
dlmember( _,Head,Tail) :- Head == Tail, !, fail.
dlmember( X,[X|_],X).
dlmember( X,[_|Y],Tail) :- dlmember( X,Y,Tail).

% Graph of Figure 2.5
arc( a,b).
arc( a,c).
arc( b,d).
arc( b,e).
arc( c,f).
arc( c,g).
arc( d,i).
arc( d,h).
arc( e,d).
arc( e,j).
arc( f,b).
arc( f,j).
arc( g,k).
arc( g,l).
arc( i,a).
arc( k,c).
arc( k,f).
arc( l,k).

goal(X) :- X = l.  % l (el) is the goal node

% Try: breadth_first_search_slow( a,goal,S).
%      breadth_first_search( a,goal,S).