%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Problema 1: Reconstrucción filogenética.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Ulises Pastor Díaz.
% Lógica computacional.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Descripción del problema: Dado un conjunto de unidades taxonómicas, un
% conjunto de caractéres, su dominio y sus expresiones en dichas
% unidades taxonómicas, queremos construir el árbol filogenético que
% maximice la compatibilidad de los caractéres dados.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%% Parte 1: Construcción del árbol binario enraizado. 2n-1 será la raiz
%% y 1..n las hojas. Las aristas serán decrecientes.
%
% Número de hojas.
numT(N) :- N = #count{L : taxa(L)}.
% Etiquetado de hojas.
leaf(1..N) :- numT(N).
% Etiquetado de nodos.
node(1..2*N-1) :- numT(N).
% Cada nodo interior tiene dos hijos (generación).
2{edge(I,J) : node(J)}2 :- node(I), not leaf(I).
% Los hijos tienen menor índice para que las aristas sean decrecientes. (CASO IGUAL).
:- node(I;J), edge(I,J), I <= J.
% Cada nodo, salvo la raiz tiene un antecesor.
1 {edge(I,J) : node(I)} 1 :- node(J), numT(N), J < 2*N-1.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%% Parte 2: Construcción de la función en los nodos internos.
%
%% Definición de h:
%
% h es una función total.
1 {h(I,C,V) : dom(C,V)} 1 :- node(I), char(C).
% h es una extensión de f.
h(I,C,V) :- leaf(I), f(I,C,V).
%% Compatibilidad:
%
% Extraemos las aristas asociadas a cada característica.
c_edge(C,V,A,B) :- node(A;B),
dom(C,V),
edge(A,B),
h(A,C,V),
h(B,C,V).
% Dividimos los nodos en cada nuevo subárbol en raíces y nodos internos.
nroot(C,V,A) :- node(A;B),
dom(C,V),
h(A,C,V),
c_edge(C,V,B,A).
root(C,V,A) :- node(A),
dom(C,V),
h(A,C,V),
not nroot(C,V,A).
% Indentificamos los valores para los que el subgrafo tiene más de una raiz.
two_roots(C,V) :- node(A;B),
A < B,
dom(C,V),
root(C,V,A),
root(C,V,B).
% Definimos la compatibilidad parcial.
par_compatible(C,V) :- dom(C,V), not two_roots(C,V).
% Definimos la compatibilidad. (Probar otra def)
-compatible(C) :- char(C), dom(C,V), not par_compatible(C,V).
compatible(C) :- not -compatible(C), char(C).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%% Parte 3: Presentación.
#show h/3.
#show compatible/1.
#show edge/2.
#show com/1.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%% Parte 4: Optimización. --opt-mode=optN
com(K) :- K = #count{C : compatible(C)}.
#maximize{1,C : compatible(C)}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%% Parte 5: Problema de decisión:
#const k = 1.
% :- com(K), K < k.
% k {compatible(C) : char(C)}.
