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].

Een snellere oplossing

graad_afstand(Graaf1,Graaf2,Afstand):-
	knoop_bijecties(Graaf1,Graaf2,Bijecties),
	findall(Afst,(member(F,Bijecties),graad_afstand(Graaf1,Graaf2,F,Afst)),Lijst),
	sort(Lijst,[Afstand|_]).

graad_afstand(_,_,[],0).
graad_afstand(Graaf1,Graaf2,[X1-X2|Rest],Afstand):-
	graad_afstand(Graaf1,Graaf2,Rest,Afstand2),
	graad(Graaf1,X1,G1),
	graad(Graaf2,X2,G2),
	Afstand is Afstand2 + abs(G1-G2).
	
graad(Graaf,Element,Graad):-
	bagof(A,(graaf(Graaf,A,Element);graaf(Graaf,Element,A)),Lijst),
	length(Lijst,Graad).

knoop_bijecties(Graaf1,Graaf2,Lijst):-
	knopen(Graaf1,Knopen1),
	knopen(Graaf2,Knopen2),
	lijst_bijecties(Knopen1,Knopen2,Lijst).

knopen(Graaf,Lijst):-
	bagof(X,A^(graaf(Graaf,X,A);graaf(Graaf,A,X)),List),
	sort(List,Lijst).

lijst_bijecties(L1,L2,Bijecties):-
	findall(L,(permutation(L2,L3),zip(L1,L3,L)),Bijecties).

zip([],[],[]).
zip([A|As],[B|Bs],[A-B|Cs]):-
  	zip(As,Bs,Cs).