src/ultrametric.c

   1 /* ultrametric.c    2011-10-11 */
   2
   3 /* Copyright 2011 Andrei-Alin Popescu */
   4
   5 /* This file is part of the R-package `ape'. */
   6 /* See the file ../COPYING for licensing issues. */
   7
   8 #include "ape.h"
   9
  10 void ultrametric(double *dd, int* np,int* mp,double *ret)//d received as dist object, -1 for missing entries
  11 {
  12     int n=*np;
  13     int m=*mp;
  14     int i=0,j=0;
  15     double max=dd[0];
  16     double d[n][n];
  17     for(i=1;i<n;i++)
  18     {d[i-1][i-1]=0;
  19      for(j=i+1;j<=n;j++)
  20       {
  21          d[i-1][j-1]=d[j-1][i-1]=dd[give_index(i,j,n)];
  22          if(dd[give_index(i,j,n)]>max)
  23           {
  24             max=dd[give_index(i,j,n)];
  25           }
  26       }
  27     }
  28     d[n-1][n-1]=0;
  29
  30   int entrCh=0;
  31    do{
  32     entrCh=0;
  33     for(i=0;i<n-1;i++)
  34      for(j=i+1;j<n;j++)
  35       {
  36          if(d[i][j]!=-1)continue;
  37          double minimax=max;
  38          int k=0;
  39          int sw=0;
  40          for(k=0;k<n;k++)
  41           {
  42              if(d[i][k]==-1 || d[j][k]==-1)continue;
  43              sw=1;
  44              double mx = d[i][k] > d[j][k] ? d[i][k] : d[j][k];
  45              if(mx<minimax){minimax=mx;}
  46           }
  47         if(sw==1)
  48           {
  49             d[i][j]=d[j][i]=minimax;
  50             m--;
  51             entrCh=1;
  52           }
  53       }
  54    }while(entrCh==1);
  55   int ij=0;
  56   for(i=0;i<n;i++)
  57    for(j=0;j<n;j++)
  58     {
  59        ret[ij++]=d[i][j];
  60     }
  61 }