% Deze versie werkt met iterative deepening. Het depth first
% gedeelte wordt geleverd door prolog. Je moet enkel telkens 
% maximale diepte verhogen.
%
% Werkt ongelooflijk traag...

boog(a,b,1).
boog(a,c,2).
boog(a,d,3).
boog(b,d,4).
boog(b,c,3).
boog(c,d,4).
boog(d,f,2).
boog(d,g,1).
boog(f,h,3).
boog(g,h,4).
boog(h,i,3).

mob(T, C) :-
	mob(0, T, C).

mob(N, T, C) :-
	sptree(N, T),
	allnodes(AN),
	contains_all(T, AN), !,
	cost(T, C).
mob(N, T, C) :-
	NN is N + 1,
	mob(NN, T, C).

cost([], 0).
cost([(boog(_,_,C1)|R], C) :-
	cost(R,C2),
	C is C1 + C2.

bboog(X, Y, C) :-
	boog(X, Y, C).
bboog(X, Y, C) :-
	boog(Y, X, C).

allnodes(N) :-
	findall(X, bboog(X, _, _), L),
	sort(L, N).

sptree(N, R) :-
	sptree(N, [], R).

sptree(0, R, R).
sptree(N, A, R) :-
	bboog(X,Y,C),
	(
		contains(A, X)
	;
		A == []
	),
	NN is N - C,
	NN >= 0,
	sptree(NN, [boog(X,Y,C)|A], R).

contains([boog(N,_,_)|_], N).
contains([boog(_,N,_)|_], N).
contains([_|R], N) :-
	contains(R, N).
	
contains_all(_, []).
contains_all(T, [N|Ns]) :-
	contains(T, N),
	contains_all(T, Ns).