% breadth-first search to solve a graph path problem
% example of query for initial state 
% ?- bfs(a,Solution).
% The final state (goal state) is f, for example
% graph:
%      a
%   /  |  \
%   b  c-- d
%  /\  | / | \
% e  f g h i j

:- use_module(library(lists)).

s(a,b).
s(a,c).
s(a,e).
s(b,e).
s(b,f).
s(c,d).
s(c,g).
s(d,h).
s(d,i).
s(d,j).

bfs(Initial,Final) :- solve([[Initial]],Final).

% Why does this program need a cut after goal/1 and after append/3?
solve([[N|Path]|_],[N|Path]) :- goal(N), !.
solve([Path|Paths],Solution) :-
  extend(Path,NewPaths),
  append(Paths,NewPaths,Paths1), !,
  solve(Paths1,Solution).

extend([Node|Path],NewPaths) :-
  bagof([NewNode,Node|Path],
   (s(Node,NewNode), \+ member(NewNode,[Node|Path])),
    NewPaths), !.
extend(Path,_). % node has no successor.

goal(f).