singlelinkage.cpp

   1
   2 #include "mothur.h"
   3 #include "cluster.hpp"
   4
   5
   6 /***********************************************************************/
   7
   8 SingleLinkage::SingleLinkage(RAbundVector* rav, ListVector* lv, SparseMatrix* dm, float c) :
   9 Cluster(rav, lv, dm, c)
  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(){
  22         try {
  23                 getRowColCells();
  24
  25                 vector<bool> deleted(nRowCells, false);
  26                 int rowInd;
  27                 int search;
  28                 bool changed;
  29
  30                 // The vector has to be traversed in reverse order to preserve the index
  31                 // for faster removal in removeCell()
  32                 for (int i=nRowCells-1;i>=0;i--) {
  33                         if ((rowCells[i]->row == smallRow) && (rowCells[i]->column == smallCol)) {
  34                                 rowInd = i;   // The index of the smallest distance cell in rowCells
  35                         } else {
  36                                 if (rowCells[i]->row == smallRow) {
  37                                         search = rowCells[i]->column;
  38                                 } else {
  39                                         search = rowCells[i]->row;
  40                                 }
  41
  42                                 for (int j=0;j<nColCells;j++) {
  43                                         if (!((colCells[j]->row == smallRow) && (colCells[j]->column == smallCol))) {
  44                                                 if (colCells[j]->row == search || colCells[j]->column == search) {
  45                                                         changed = updateDistance(colCells[j], rowCells[i]);
  46                                                         // If the cell's distance changed and it had the same distance as
  47                                                         // the smallest distance, invalidate the mins vector in SparseMatrix
  48                                                         if (changed) {
  49                                                                 if (colCells[j]->vectorMap != NULL) {
  50                                                                         *(colCells[j]->vectorMap) = NULL;
  51                                                                         colCells[j]->vectorMap = NULL;
  52                                                                 }
  53                                                         }
  54                                                         removeCell(rowCells[i], i , -1);
  55                                                         deleted[i] = true;
  56                                                         break;
  57                                                 }
  58                                         }
  59                                 }
  60                                 if (!deleted[i]) {
  61                                         // Assign the cell to the new cluster
  62                                         // remove the old cell from seqVec and add the cell
  63                                         // with the new row and column assignment again
  64                                         removeCell(rowCells[i], i , -1, false);
  65                                         if (search < smallCol){
  66                                                 rowCells[i]->row = smallCol;
  67                                                 rowCells[i]->column = search;
  68                                         } else {
  69                                                 rowCells[i]->row = search;
  70                                                 rowCells[i]->column = smallCol;
  71                                         }
  72                                         seqVec[rowCells[i]->row].push_back(rowCells[i]);
  73                                         seqVec[rowCells[i]->column].push_back(rowCells[i]);
  74                                 }
  75                         }
  76                 }
  77                 clusterBins();
  78                 clusterNames();
  79                 // remove also the cell with the smallest distance
  80                 removeCell(rowCells[rowInd], -1 , -1);
  81         }
  82         catch(exception& e) {
  83                 errorOut(e, "SingleLinkage", "update");
  84                 exit(1);
  85         }
  86 }
  87
  88
  89 /***********************************************************************/
  90 //This function updates the distance based on the nearest neighbor method.
  91 bool SingleLinkage::updateDistance(MatData& colCell, MatData& rowCell) {
  92         try {
  93                 bool changed = false;
  94                 if (colCell->dist > rowCell->dist) {
  95                         colCell->dist = rowCell->dist;
  96                 }
  97                 return(changed);
  98         }
  99         catch(exception& e) {
 100                 errorOut(e, "SingleLinkage", "updateDistance");
 101                 exit(1);
 102         }
 103 }
 104 /***********************************************************************/