Applicazioni di Intelligenza Artificiale - CLP

Prof. Marco Gavanelli

19 giugno 2009

Esercizio (8 punti)

Sia dato un file graph.pl che contiene la rappresentazione di un grafo non orientato. Per ogni nodo del grafo è presente un fatto  node(N) e per ogni arco che connette i nodi I e J è presente un fatto edge(I,J), dove I < J.

Una clique è un sottoinsieme dei nodi del grafo in cui il grafo indotto è completo, cioè ogni coppia di nodi nella clique è connessa da un arco. 
Quindi per ogni coppia di nodi (I,J) appartenente alla clique, l'arco (I,J) deve appartenere al grafo.

Si scriva un programma CLP che calcola la clique di dimensione massima (ovvero contenente il massimo numero di nodi) del grafo dato.

Soluzione

:- lib(fd).
:- lib(fd_global).

:- [graph].

clique(L,Dim):-
    % Trovo il numero dei nodi N
    findall(Node,node(Node),Lnodes),
    length(Lnodes,N),
    % Costruisco la lista di variabili
    % Ogni nodo puo` entrare o no nella clique
    length(L,N),
    L::0..1,
    vincolo(L,1),
    sumlist(L,Dim),
    F #= -Dim,
    minimize(labeling(L),F).

% vincolo(L,Start)
% Impongo che gli elementi della lista L formino una clique,
% sapendo che il primo nodo della lista ha indice Start
vincolo([],_).
vincolo([X|L],N):-
    N1 is N+1,
    vincolo_loop(X,L,N,N1),
    vincolo(L,N1).

% vincolo_loop(X,L,Ix,M)
% Impone il vincolo di clique fra l'elemento X e gli elementi della lista L
% sapendo che Ix e` l'indice dell'elemento X
% ed Iy e` l'indice dell'elemento Y
vincolo_loop(_,[],_,_).
vincolo_loop(X,[_|T],Ix,Iy):-
% Se c'e` un arco, allora posso prendere entrambi i nodi X e Y nella clique
% quindi non impongo vincoli
    edge(Ix,Iy),!,
    M is Iy+1,
    vincolo_loop(X,T,Ix,M).
vincolo_loop(X,[Y|T],Ix,Iy):-
% Se non c'e` un arco, solo uno dei due nodi X e Y puo` essere nella clique
    X+Y #< 2,
    M is Iy+1,
    vincolo_loop(X,T,Ix,M).