% TOPOANC: Converts a dendrogram-type topology matrix to a cladogram-type
%           ancestor-function vector and associated branch-length vector
%
%     Usage: [anc,brlen] = topoanc(topology)
%
%         topology = [(n-1) x 4] matrix summarizing dendrogram topology:
%                       col 1 = 1st OTU/cluster being grouped at current step
%                       col 2 = 2nd OTU/cluster
%                       col 3 = ID of cluster being produced
%                       col 4 = distance at node
%         anc =      [2n-1] ancestor function
%         brlen =    corresponding lengths of branches (edges) connecting
%                      descendants with ancestors
%

% RE Strauss, 7/14/95

function [anc,brlen] = topoanc(topology)
  n = size(topology,1)+1;             % Number of terminal OTUs
  anc = zeros(1,2*n-1);               % Allocate return matrices
  brlen = anc;

  for i = 1:(n-1)
    d1 = topology(i,1);
    d2 = topology(i,2);
    a =  topology(i,3);
    nodedist = topology(i,4);

    anc(d1) = a;
    anc(d2) = a;

    prevdist = 0;
    if (d1>n)                         % If current descendant was a previous
      k = find(topology(:,3)==d1);    %   ancestor, get it's previous node distance
      prevdist = topology(k,4);
    end;
    brlen(d1) = nodedist - prevdist;

    prevdist = 0;
    if (d2>n)
      k = find(topology(:,3)==d2);
      prevdist = topology(k,4);
    end;
    brlen(d2) = nodedist - prevdist;
  end;

  return;
