Declaratieve Talen/oplossingGraafafstand

een oplossing

%korste afstand tss 2 grafen
min_distance(G1,G2,R) :-
	findall(D,distance(G1,G2,D),Ds),
	min_element(Ds,R).
	
%korste element uit rij
min_element([X],R) :- R = X.
min_element([L|List],Result) :-
	min_element(List,Rrecur),
	(Rrecur < L ->
	Result = Rrecur;
	Result = L).

%afstand graaf G1 tot G2
distance(G1,G2,R) :-
	knopen(G1,V1),
	knopen(G2,V2temp),
	permu(V2temp,V2),
	distance(G1,G2,V1,V2,R).
 
 
%afstand graaf G1 tot graaf G2 gegeven functie f:V1 -> V2
distance(_,_,[],[],R) :- R is 0.
distance(G1,G2,[V1|V1rest],[V2|V2rest],R) :-
	graad(G1,V1,Graad1),
	graad(G2,V2,Graad2),
	(Graad1 > Graad2 ->
	Verschil is Graad1 - Graad2;
	Verschil is Graad2 - Graad1),
	distance(G1,G2,V1rest,V2rest,Rrecursief),
	R is Verschil + Rrecursief.
 	

%graad van knoop V in graaf G
graad(G,V,R) :-
	findall(_,(graaf(G,V,_);graaf(G,_,V)),List),
	length(List,R).


%alle knopen van graaf 'Index'
knopen(Index, Result) :-
	findall(X,(graaf(Index,X,_);graaf(Index,_,X)),Knopen),
	list_to_set(Knopen,Result).
	
%permutaties
permu([],[]).
permu(X,[Y|Ys]) :- 
	del(Y,X,Rs),
	permu(Rs,Ys).
 
%deletes X
del(X,[X|Xs],Xs).
del(X,[Y|Ys],[Y|Zs]) :- 
 	del(X,Ys,Zs).

feedback welkom --Beau 14 jun 2006 18:07 (CEST)

Een korte alternatieve oplossing

Deze oplossing maakt volop gebruik van built-ins.

f_afstand(F,G1,G2,Res) :-
	findall(abs(Graad),(member(A,F),A=K1-K2,graad(K1,G1,Graad1),graad(K2,G2,Graad2),Graad is Graad1-Graad2),List),
	sumlist(List,Res).

graad(K,G,D) :-
	findall(_,(graaf(G,K,_);graaf(G,_,K)),L),
	length(L,D).
	
graadafstand(G1,G2,Res) :-
	findall(K,(graaf(G1,K,_);graaf(G1,_,K)),D),
	list_to_set(D,D2),
	length(D2,N),
	numlist(1,N,L),
	findall(P,permutation(P,L),Perms),
	findall(FA,(member(P,Perms),bijectie(G1,G2,P,B),f_afstand(B,G1,G2,FA)),Afstn),
	min_list(Afstn,Res).

bijectie(G1,G2,P,Res) :-
	findall(K,(graaf(G1,K,_);graaf(G1,_,K)),Dubbels1),
	list_to_set(Dubbels1,L1),
	findall(K,(graaf(G2,K,_);graaf(G2,_,K)),Dubbels2),
	list_to_set(Dubbels2,L2),
	bijectie2(L1,L2,P,Res).
	
bijectie2([],_,[],[]).
bijectie2([G|Gn],G2,[P|Pn],Res) :-
	bijectie2(Gn,G2,Pn,Res2),
	nth1(P,G2,K),
	Res = [G-K|Res2].