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

Nog een oplossing:

graaf(8,a,b).
graaf(8,a,c).
graaf(8,a,d).
graaf(22,aa,bb).
graaf(22,aa,cc).
graaf(22,aa,dd).
graaf(15,x,y). 
graaf(15,y,v). 
graaf(15,x,w).
%Knoopnamen anders dan opgave. 
%Het leek mij logischer dat verschillende grafen verschillende namen hebben voor hun knopen
%Om toch met zelfde namen te werken zou je ook de graaf moeten doorgeven als argument bij sommige predicaten.

graadafstand(Graaf1, Graaf2, N):-
    findall(Bijectie, maakbijectie(Graaf1, Graaf2, Bijectie), Bijecties),
    findall(Graad, (member(Bij, Bijecties),  graadafstand(Bij, Graad)), Graden),    
    min_list(Graden, N).   

knopenvangraaf(Graaf, Knopen):-
    findall(KnoopX, graaf(Graaf, KnoopX, _Ander), KnopenX),
    findall(KnoopY, graaf(Graaf, _Ander, KnoopY), KnopenY),
    append(KnopenX, KnopenY, KnopenLijst),
    list_to_set(KnopenLijst, Knopen).

%Geeft de graad van een knoop terug
graad(Knoop, Graad):-
    findall(InKnoop, graaf(_Graaf, InKnoop, Knoop), Inkomend),
    findall(UitKnoop, graaf(_Graaf, Knoop, UitKnoop), Uitgaand),
    append(Inkomend, Uitgaand, AlleKnopen),
    list_to_set(AlleKnopen, SetVanKnopen),
    length(SetVanKnopen, Graad).

%Bijecties maken door de knopen van graaf1 in de originele volgorde te houden
%maar de volgorde van de graaf2 te permuteren. 
%Zo link je elk elementen van graaf1 op alle mogelijke manieren met elementen van graaf2.
maakbijectie(Graaf1, Graaf2, Bijectie):-
    knopenvangraaf(Graaf1, Knopen1),
    knopenvangraaf(Graaf2, Knopen2),
    permutation(Knopen2, Permutatie),
    length(Knopen1, AantalKnopen),
    numlist(1, AantalKnopen, Indices),
    findall(Knoop1-> Knoop2, (nth1(Index, Knopen1, Knoop1), nth1(Index, Permutatie, Knoop2), member(Index, Indices)), Bijectie).

graadafstand([], 0).
graadafstand([Knoop1 -> Knoop2|Rest], N):-
    graadafstand(Rest, DeelN),
    graad(Knoop1, Graad1),
    graad(Knoop2, Graad2),
    Verschil is Graad2 - Graad1,
    abs(Verschil, Graad),
    N is DeelN + Graad.

--Harm.de.weirdt 12 jan 2012 14:27 (CET)