A = importdata('grafo0.txt');

%Se debe hacer un bucle para poder calcular pisubv.
%ya que se tiene que tomar el máximo de los pesos.

maximo_vertice1 = max(A(:,1));
maximo_vertice2 = max(A(:,2))-max(A(:,1));
maximo_peso = max(A(:,3));  %No se utiliza
%Intentamos poner el valor de los pesos en forma de matriz

B = [maximo_vertice1, maximo_vertice2];
P = zeros(B(1)+2,B(2)+2);
P(1,1) = 999;
P(1, B(2)+2) = 999;
P(B(1)+2, 1) = 999;
P(B(1)+2, B(2)+2) = 999;

for i = 1: B(1)
    P(i+1, 1) = i;     %Para poner los vertices
end

for i = 1: B(2)
    P(1,i+1) = B(2)+i;
end

z = 1;
for i = 2:(B(1)+1)
    for j = 2:(B(2)+1)      %Para poner los pesos
        P(i,j) = A(z,3);
        z = z + 1;
    end
end
   

% Calculamos el maximo de los pesos. Al haber empate, se coge uno cualquiera.
 
amax = P(2,2);
for i = 2:B(1)
    for j = 2:B(2)
        if P(i,j) > amax
            amax = P(i,j); 
            filmax = i;
            colmax = j + B(1);
        end
    end
end
filmax = filmax -1;
colmax = colmax -1;
disp('El valor maximo de la matriz es');amax

disp('Se encuentra en la fila'); filmax 
disp('Se encuentra en la columna'); colmax

% Calculamos pisubv
 
 pisubv = (1/2)* amax
  
%insertamos en la matriz el valor de pisubv

 for i = 2:B(1)+1
     P(i,B(2)+2) = pisubv;
 end
 for j = 2:B(2)+1
     P(B(1)+2,j) = pisubv;
 end
 disp('La matriz de partida es'); P
 
%A continuación, realizamos la diferencia entre amax-los elementos de la matriz
% Para los pesos que se encuentran en el interior de la tabla, modificamos
% la tabla anterior.
 
C = P;
for i = 2:B(1)+1 
     for j = 2:B(2) +1
         C(i,j) = amax - P(i,j);  
     end
 end
 
disp('La matriz disminuida es'); C
 
%-------------------E D M O N D S -----------------------------------
%Realizamos una nueva tabla auxiliar que llamaremos K, que corresponde 
% al numero de emparejamientos.

%En un principio estan todos sin saturar, exceptuando aquellos que
%pertenecen al emparejamiento.
                                    
 for e = 1:sum(B)                   
     pred(e) = 0;         %Introducimos la inicialización del algoritmo 
     ex(e) = 0;           % de Edmonds para todos los vertices  
     car(e) = 0;
 end
 
K = C;
sat(1:sum(B)) = 0;
evitar(1:sum(B)) = 0;
for k = 2:B(1)+1
     for l = 2:B(2)+1
         if C(k,l) == 0 %Si es necesario añadir condicion para evitar maximos en la misma fila o columna.
             if evitar(k - 1)==0 && evitar(l + B(1) - 1)==0
                K(k,l) = 1;    
                sat(k - 1) = 1;          %Saturacion de los vertices
                sat(B(1) + l - 1) = 1;
                ex(k-1) = 1;           %Examinacion de los vertices
                ex(B(1) + l - 1) = 1;
                pred(k-1) = k-1;       %Predecesor de los vertices
                pred(B(1) + l - 1) = k-1;
                car(k-1) = 'P';        %Cardinalidad de los vertices
                car(B(1) + l - 1) = 'I';
                evitar(k-1) = 1;
                evitar(l + B(1) - 1) = 1;
                ant1 = k;
                ant2 = l;
             else
                 disp('Hay 2 posibles opciones para el emparejamiento.');
                 variable = input('Escriba 1 o 2 para elegir cual de ellas tomar: ');
                 if variable == 1
                    K(k,l) = 0;
                 elseif variable == 2
                    if ant1 == k
                        K(k,ant2) = 0;
                        K(k,l) = 1;
                        sat(B(1) + ant2 - 1) = 0;   %Saturacion de los vertices
                        sat(B(1) + l - 1) = 1;
                        ex(B(1) + ant2 - 1) = 0;    %Examinacion d elos vertices
                        ex(B(1) + l - 1) = 1;
                        pred(B(1) + ant2 - 1) = 0;  %Predecesor d elos vertices
                        pred(B(1) + l - 1) = k-1;
                        car(B(1) + ant2 - 1) = 0;   %Cardinalidad d elos vertices
                        car(B(1) + l - 1) = 'I';
                        evitar(ant2 + B(1) - 1) = 0;
                        evitar(l + B(1) - 1) = 1;
                        ant2 = l;
                    elseif ant2 == l
                        K(ant1,l) = 0;
                        K(k,l) = 1;     
                        sat(ant1 - 1) = 0;   %Saturacion de los vertices
                        sat(k-1) = 1;
                        ex(ant1 - 1) = 0;    %Examinacion d elos vertices
                        ex(k-1) = 1;
                        pred(ant1 - 1) = 0;  %Predecesor d elos vertices
                        pred(k-1) = k-1;
                        car(ant1 - 1) = 0;   %Cardinalidad d elos vertices
                        car(k-1) = 'P';
                        evitar(ant1 - 1) = 0;
                        evitar(k-1) = 1;
                        ant1 = k;
                    end
                 end
             end
         else
             K(k,l) = 0;
         end
     end
 end
 disp('El emparejamiento es'); K
  
%Hacemos un bucle para calcular el valor de R

R = []; 
numr = 0;
for k = 1:sum(B)
     if sat(k) == 0 && pred(k)== 0  %Cuenta la cantidad de vértices del grupo B(1) que tenga sat = 0 y pred = 0
         numr = numr + 1;     
         R(numr) = k ; 
     end
end
R
vuelta = 1;

%Comenzamos el algoritmo
auxpred = pred;
auxcar = car;
auxex = ex;
%auxsat=sat;

if numr >= 2
    while not (numr == 0)
        vuelta
        r = R(1)
        pause
        pred(r) = r;
        car(r) = 'P';
        NSA = [r]
        pause
        numnsa = 1;
        while  not (numnsa == 0)
            x = NSA(1)
            pause
            if (car(x) == 'P')
                Y = [];
                numy = 0;
                for j = 1:sum(B)
                    if x < B(1) + 1 && B(1) + 1 <= j
                        if pred(j) == 0 && P(x+1, j-B(1)+1) > 0
                            numy = numy + 1;
                            Y(numy) = j;
                        end
                    elseif B(1) + 1 <= x && j < B(1) + 1
                        if pred(j) == 0 && P(j+1, x-B(1)+1) > 0  
                            numy = numy + 1;
                            Y(numy) = j;
                        end
                    end
                end
                Y
                pause
                hay = 1;
                while hay <= length(Y)
                    pred(Y(hay)) = x;
                    car(Y(hay)) = 'I';
                    hay = hay + 1;
                    hay 
                    pause
                end
                ex(x) = 1;
            else
                if sat(x) == 1
                    if x < B(1)+1
                        for y = 1:B(2)
                            if K(x+1,y+1) == 1
                                candi = y + B(1);
                            end
                        end
                    else
                        for y = 1:B(1)
                            if K(y+1,x+1) == 1
                                candi = y;
                            end
                        end
                    end
                    pred(candi) = x;
                    car(candi) = 'P';
                    ex(candi) = 1;
                else
                    sat(r) = 1;
                    sat(x) = 1;
                    while not(r == x)
                        if pred(x) <= x
                            K(pred(x)+1, x+1) = 1;
                        else
                            K(x+1, pred(x)+1) = 1;
                        end
                        x = pred(x);
                        if not( x == pred(x))
                            if pred(x) <= x
                                K(pred(x)+1,x+1)=0;
                            else
                                K(x+1,pred(x)+1)=0;
                            end
                            x = pred(x);
                            K
                        end
                    end                   
                    pred = auxpred;          
                    ex = auxex;         
                    car = auxcar;
                end
            end
            NSA = [];
            numnsa = 0;
            for v = 1:sum(B)
                if ex(v) == 0 && pred(v) ~= 0  
                    numnsa = numnsa + 1;
                    NSA(numnsa) = v;
                end
            end
            NSA
            pause
        end 
        R = []; 
        numr = 0;
        for k = 1:sum(B)
            if sat(k) == 0 && pred(k)== 0  
                numr = numr + 1;     
                R(numr) = k ;
            end
        end
        R
        pause
        vuelta = vuelta + 1;
    end
end


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% % C A L C U L O   D E   D E L T A S
% 
% %Denominamos a la matriz D como la matriz auxiliar del primer cambio dual
% D = matriz_auxiliar(B, C, filmax, colmax);
% 
% 
% %Calculamos el valor delta del cambio dual
% delta = calculo_delta(B,C,D)
% 
% disp('La matriz auxiliar D es:'); D
% disp('delta es:'); delta
% 
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
% % N U E V A   I T E R A C I O N   D E  L A  T A B L A   D E   N U E V O
% 
% %Recalculamos la tabla de nuevo, para ello cuando es vértices es par,
% %disminuimos el valor de delta. Si el vértices es impar aumentamos el valor
% %de delta, y en caso contrario, se mantiene el valor de pisubv
%  
% for i = 2:B(1)+1
%      for j = 2:B(2)+1
%          if (D(i,j) == 20)
%              C(filmax +1, B(2)+2) = pisubv-delta;
%              C(B(1)+2, colmax+1) = pisubv-delta;
%          else
%              C(i,B(2)+2) = pisubv;
%              C(B(1)+2,j) = pisubv;
%          end
%      end
%  end
% 
% %En este caso, debemos disminuir a la cantidad del peso el valor de delta,
% %tantas veces, dependiendo de la fila y columna, donde se encuentre el
% %emparejameinto.
%  
%  for i = 2:B(1)+1
%      for j = 2:B(2)+1
%          if (D(i,j) == 30)
%              C(i,j) = C(i,j)-2*delta;
%          elseif (D(i,j) == 20)
%              C(i,j) = C(i,j)-1*delta;
%          else 
%              C(i,j) = C(i,j);
%          end
%      end
%  end
%  C
% % 
% % %Denominamos a la matriz E como la matriz auliar del segundo cambio dual
% % 
% % E = C;
% % for i = 2:B(1)+1
% %     for j = 2:B(2)+1
% %         if (C(i,j) == 0) & (D(i,j) == 30)
% %             fil=i-1;
% %             col=j-1;
% %             disp('El emparejamiento es:'); fil, col
% %         end
% %     end
% % end
% % disp('El emparejamiento es:'); filmax, colmax

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%