function [ulmetric,ctmetric] = atreedec(prox,constant)

% ATREEDEC decomposes a given additive tree matrix into an 
% ultrametric and a centroid metric matrix (where the root is 
% half-way along the longest path).
% 
% syntax: [ulmetric,ctmetric] = atreedec(prox,constant)
%
% PROX is the input proximity matrix (with a zero main diagonal
% and a dissimilarity interpretation);
% CONSTANT is a non-negative number (less than or equal to the 
% maximum proximity value) that controls the 
% positivity of the constructed ultrametric values;
% ULMETRIC is the ultrametric component of the decomposition;
% CTMETRIC is the centroid metric component of the decomposition 
% (given by values $g_{1},...,g_{n}$ for each of the objects, 
% some of which may actually be negative depending on the input
% proximity matrix used).

n = size(prox,1);
imax = 0.0;
jmax = 0.0;
valmax = 0.0;
ctmetric = zeros(n,1);
ulmetric = zeros(n,n);

for i = 1:(n-1)
   for j = (i+1):n
      
      if(prox(i,j) > valmax)
         
         valmax = prox(i,j);
         imax = i;
         jmax = j;
         
      end
      
   end
end

for i = 1:n
   
   ctmetric(i) = max([prox(i,imax) prox(i,jmax)]) - (constant);
   
end



for i = 1:n
   for j = 1:n
      
      if(i ~= j)
         
         ulmetric(i,j) = prox(i,j) - ctmetric(i) - ctmetric(j);
         
      else
         
         ulmetric(i,j) = 0.0;
         
      end
      
   end
end
