Declaratieve Talen/Oplossing Minimale Snede

Oplossing niet volledig maar het moeilijkste stuk is er:

boog(a,b,1).
boog(a,c,1).
boog(b,c,1).
boog(c,z,3).
boog(b,z,1).


min_cut(Snede,Kost) :-
	findall((Snede,Kost),min_snede(Snede,Kost),R),
	min(R,Snede,Kost).
	
min([(Snede,Kost)],KortsteSnede,LaagsteKost) :-
	KortsteSnede = Snede,
	LaagsteKost = Kost.
	
min([(Snede,Kost)|Rest],KortsteSnede,LaagsteKost) :-
	KortsteSnede = Snede,
	LaagsteKost = Kost.


min_rnd_snede(Snede, Kost) :-
	knopen(Knopen),
	permu(Knopen, [K|PKnopen]),
	min_snede_perm([K],PKnopen,Snede,Kost).

	

%gegeven een zeker permutatie/volgorde van de knopen: ga alle snedes af 
min_snede_perm(X,[Y],KortsteSnede,Lengte) :-
	kost(snede(X,[Y]),Lengte),
	KortsteSnede = snede(X,[Y]).
min_snede_perm([X1|X1rest],[X2|X2rest], KortsteSnede, LengteKortsteSnede) :-
	min_snede_perm([X2,X1|X1rest],X2rest,KortsteSubSnede,LengteKortsteSubSnede),
	kost(snede([X1|X1rest],[X2|X2rest]),Kost),
	(Kost < LengteKortsteSubSnede ->
	LengteKortsteSnede = Kost,
	KortsteSnede = snede([X1|X1rest],[X2|X2rest]);
	KortsteSnede = KortsteSubSnede,
	LengteKortsteSnede = LengteKortsteSubSnede	
	).

%bereken de kost van een snede
kost(snede([],_),Y) :- Y = 0.
kost(snede([X|Xs],Y),Result) :-
	findall(Kost, ((boog(X,Z,Kost);boog(Z,X,Kost)),elementvan(Z,Y)),Kosten),
	sum(Kosten,TotaleKostX),
	kost(snede(Xs,Y),RecurResult),
	Result is RecurResult + TotaleKostX.

%element van
elementvan(X,[L|Lijst]) :-
	X == L;
	elementvan(X,Lijst).

%bereken de som van een rij
sum([],R) :- R = 0.
sum([X],R) :- R = X.
sum([L|List], R) :-
	sum(List, Recur),
	R is Recur + L.

%alle knopen van de graaf
knopen(Result) :-
	findall(X,(boog(_,X,_);boog(X,_,_)),Knopen),
	list_to_set(Knopen,Result).

%permutates the list
permu([],[]).
permu(X,[Y|Ys]) :- 
	del(Y,X,Rs),
	permu(Rs,Ys).
	
%deletes X from the list
del(X,[X|Xs],Xs).
del(X,[Y|Ys],[Y|Zs]) :- 
	del(X,Ys,Zs).  

--Beau 15 jun 2006 11:51 (CEST)