member(X,[X|_]).
member(X,[_|T]):- member(X,T).

delete([],_X,[]).
delete([X|T],X,T).
delete([Y|T],X,[Y|NewT]):-
	delete(T,X,NewT).

insert2(L,X,[L|X]).

add([],X,[X]).
add([Y|T],X,[Y|NewT]):-
	add(T,X,NewT).

concat([],L,L).
concat([H|T],L2,[H|NewT]):-
	concat(T,L2,NewT).


revert([],[]).
revert([H|T],Rev):-
	revert(T,RT),
	add(RT,H,Rev).

revert1(List,Rev):-
	rev(List,[],Rev).
rev([],L,L).
rev([H|T],Acc,Rev):-
	rev(T,[H|Acc],Rev).

gen(N,List):-
	(N>0 ->
	    List=[N|RestList], NewN is N-1, gen(NewN,RestList)
	;
	    List=[]
	).

sat_num(Query,_NoAnswers):-
	bb_put(counter,0),
	call(Query),
	bb_get(counter,N),
	N1 is N+1,
	bb_put(counter,N1),
	fail.
sat_num(_Query,NoAnswers):-
	bb_delete(counter,NoAnswers).


shortest_path(From,To, ShortestPath):-
	findall(Path,path(From,To,[],Path),AllPaths),
	shortest_list(AllPaths,ShortestPath).

shortest_list([List|Rest],Shortest):-
	length(List,Length),
	slist(Rest,List,Length,Shortest).
slist([],List,_,List).
slist([H|T],List,Length,Shortest):-
	length(H,LH),
	(LH<Length ->
	    slist(T,H,LH,Shortest)
	;
	    slist(T,List,Length,Shortest)
	).

	

path(From,From,Visited,Path):-!,
	revert([From|Visited],Path).
path(From,To,Visited,Path):-
	arc(From,Through),	% next node
	\+ member(Through,Visited), % prevent cycles
	path(Through,To,[From|Visited],Path).


shortest_pathBB(From,To,_Path):-
	bb_put(best,no_path),
	spathBB(From,To,[],0).
shortest_pathBB(_From,_To,Path):-
	bb_get(best,path(_,Path)).

spathBB(From,From,Visited,Length):-!,
	revert([From|Visited],Path),
	bb_put(best,path(Length,Path)), % save so-far best path
	fail.
spathBB(From,To,Visited,OldLength):-
	NewLength is OldLength+1,
	can_be_shorter(NewLength), % check the bound
	arc(From,Through),	% find the next node
	\+ member(Through,Visited), % prevent cycles
	spathBB(Through,To,[From|Visited],NewLength).

can_be_shorter(_):-
	bb_get(best,no_path).
can_be_shorter(Length):-
	bb_get(best,path(BestLength,_)),
	Length<BestLength.


shortest_pathBFS(From,To,Path):-
	spathBFS([[From]],To,Path).

spathBFS([Visited|Rest],To,Path):-
	Visited = [N|_],
	(N=To ->		% we found the path
	    revert(Visited,Path)
	;			% expand the node N
	    findall([N1|Visited],(arc(N,N1),
				  \+ member(N1,Visited),
				  \+ member([N1|_],Rest)), NewNodes),
	    concat(Rest,NewNodes, Nodes),
	    spathBFS(Nodes,To,Path)
	).

arc(a,b).
arc(a,c).
arc(b,c).
arc(b,e).
arc(c,d).
arc(d,b).
arc(d,e).