singlelinkage.cpp

   1
   2 #include "mothur.h"
   3 #include "cluster.hpp"
   4
   5
   6 /***********************************************************************/
   7
   8 SingleLinkage::SingleLinkage(RAbundVector* rav, ListVector* lv, SparseDistanceMatrix* dm, float c, string s) :
   9 Cluster(rav, lv, dm, c, s)
  10 {}
  11
  12
  13 /***********************************************************************/
  14 //This function returns the tag of the method.
  15 string SingleLinkage::getTag() {
  16         return("nn");
  17 }
  18
  19 /***********************************************************************/
  20 //This function clusters based on the single linkage method.
  21 void SingleLinkage::update(double& cutOFF){
  22         try {
  23                 smallCol = dMatrix->getSmallestCell(smallRow);
  24         nColCells = dMatrix->seqVec[smallCol].size();
  25         nRowCells = dMatrix->seqVec[smallRow].size();
  26
  27                 vector<bool> deleted(nRowCells, false);
  28                 int rowInd;
  29                 int search;
  30                 bool changed;
  31
  32                 // The vector has to be traversed in reverse order to preserve the index
  33                 // for faster removal in removeCell()
  34                 for (int i=nRowCells-1;i>=0;i--) {
  35                 if (dMatrix->seqVec[smallRow][i].index == smallCol) {
  36                     rowInd = i;   // The index of the smallest distance cell in rowCells
  37                 } else {
  38                     search = dMatrix->seqVec[smallRow][i].index;
  39
  40                     for (int j=0;j<nColCells;j++) {
  41                         if (dMatrix->seqVec[smallCol][j].index != smallRow) { //if you are not the small cell
  42                             if (dMatrix->seqVec[smallCol][j].index == search) {
  43                                 changed = updateDistance(dMatrix->seqVec[smallCol][j], dMatrix->seqVec[smallRow][i]);
  44                                 dMatrix->updateCellCompliment(smallCol, j);
  45                                 dMatrix->rmCell(smallRow, i);
  46                                 deleted[i] = true;
  47                                 break;
  48                             }
  49                         }
  50                     }
  51                     if (!deleted[i]) {
  52                         // Assign the cell to the new cluster
  53                         // remove the old cell from seqVec and add the cell
  54                         // with the new row and column assignment again
  55                         float distance =  dMatrix->seqVec[smallRow][i].dist;
  56                         dMatrix->rmCell(smallRow, i);
  57                         if (search < smallCol){
  58                             PDistCell value(smallCol, distance);
  59                             dMatrix->addCell(search, value);
  60                         } else {
  61                             PDistCell value(search, distance);
  62                             dMatrix->addCell(smallCol, value);
  63                         }
  64                         sort(dMatrix->seqVec[smallCol].begin(), dMatrix->seqVec[smallCol].end(), compareIndexes);
  65                         sort(dMatrix->seqVec[search].begin(), dMatrix->seqVec[search].end(), compareIndexes);
  66                     }
  67                 }
  68                 }
  69                 clusterBins();
  70                 clusterNames();
  71                 // remove also the cell with the smallest distance
  72
  73                 dMatrix->rmCell(smallRow, rowInd);
  74         }
  75         catch(exception& e) {
  76                 m->errorOut(e, "SingleLinkage", "update");
  77                 exit(1);
  78         }
  79 }
  80
  81
  82 /***********************************************************************/
  83 //This function updates the distance based on the nearest neighbor method.
  84 bool SingleLinkage::updateDistance(PDistCell& colCell, PDistCell& rowCell) {
  85         try {
  86                 bool changed = false;
  87                 if (colCell.dist > rowCell.dist) {
  88                         colCell.dist = rowCell.dist;
  89                 }
  90                 return(changed);
  91         }
  92         catch(exception& e) {
  93                 m->errorOut(e, "SingleLinkage", "updateDistance");
  94                 exit(1);
  95         }
  96 }
  97 /***********************************************************************/