Thallinger changes to cluster command.

[mothur.git] / singlelinkage.cpp

diff --git a/singlelinkage.cpp b/singlelinkage.cpp
index 5332e907d27b86d13f40c411baa4a96cbf879f40..c27b14e727057c6dcd14f2b0268cd250c4d52559 100644 (file)
--- a/singlelinkage.cpp
+++ b/singlelinkage.cpp
@@ -9,54 +9,75 @@ SingleLinkage::SingleLinkage(RAbundVector* rav, ListVector* lv, SparseMatrix* dm
 Cluster(rav, lv, dm)
 {}
 
+
 /***********************************************************************/
-//This function clusters based on nearest method.
-void SingleLinkage::update(){
+//This function returns the tag of the method.
+string SingleLinkage::getTag() {
+       return("nn");
+}
+
+/***********************************************************************/
+//This function clusters based on the single linkage method.
+void  SingleLinkage::update(){
        try {
-               getRowColCells();               
+               getRowColCells();       
        
-               for(int i=1;i<nRowCells;i++){
-               
-                       int search;
-               
-                       if(rowCells[i]->row == smallRow){
-                               search = rowCells[i]->column;
-                       }
-                       else{
-                               search = rowCells[i]->row;
-                       }
+               vector<bool> deleted(nRowCells, false);
+               int rowInd;
+               int search;
+               bool changed;
+
+               // The vector has to be traversed in reverse order to preserve the index
+               // for faster removal in removeCell()
+               for (int i=nRowCells-1;i>=0;i--) {
+                       if ((rowCells[i]->row == smallRow) && (rowCells[i]->column == smallCol)) {
+                               rowInd = i;   // The index of the smallest distance cell in rowCells
+                       } else {
+                               if (rowCells[i]->row == smallRow) {
+                                       search = rowCells[i]->column;
+                               } else {
+                                       search = rowCells[i]->row;
+                               }
                
-                       for(int j=1;j<nColCells;j++){
-                       
-                               if(colCells[j]->row == search || colCells[j]->column == search){
-                               
-                                       if(colCells[j]->dist > rowCells[i]->dist){
-                                               colCells[j]->dist = rowCells[i]->dist;
-                                       
-                                               if(colCells[j]->vectorMap != NULL){
-                                                       *(colCells[j]->vectorMap) = NULL;
-                                                       colCells[j]->vectorMap = NULL;
+                               for (int j=0;j<nColCells;j++) {
+                                       if (!((colCells[j]->row == smallRow) && (colCells[j]->column == smallCol))) {
+                                               if (colCells[j]->row == search || colCells[j]->column == search) {
+                                                       changed = updateDistance(colCells[j], rowCells[i]);
+                                                       // If the cell's distance changed and it had the same distance as 
+                                                       // the smallest distance, invalidate the mins vector in SparseMatrix
+                                                       if (changed) {
+                                                               if (colCells[j]->vectorMap != NULL) {
+                                                                       *(colCells[j]->vectorMap) = NULL;
+                                                                       colCells[j]->vectorMap = NULL;
+                                                               }
+                                                       }
+                                                       removeCell(rowCells[i], i , -1);
+                                                       deleted[i] = true;
+                                                       break;
                                                }
-                                       
                                        }
-                                       dMatrix->rmCell(rowCells[i]);
-                                       break;
                                }
-                       }                       
-               
-                       if(search < smallCol){
-                               rowCells[i]->row = smallCol;
-                               rowCells[i]->column = search;
-                       }
-                       else{
-                               rowCells[i]->row = search;
-                               rowCells[i]->column = smallCol;
-                       }
-               
-               }       
+                               if (!deleted[i]) {
+                                       // Assign the cell to the new cluster 
+                                       // remove the old cell from seqVec and add the cell
+                                       // with the new row and column assignment again
+                                       removeCell(rowCells[i], i , -1, false);
+                                       if (search < smallCol){
+                                               rowCells[i]->row = smallCol;
+                                               rowCells[i]->column = search;
+                                       } else {
+                                               rowCells[i]->row = search;
+                                               rowCells[i]->column = smallCol;
+                                       }
+                                       seqVec[rowCells[i]->row].push_back(rowCells[i]);
+                                       seqVec[rowCells[i]->column].push_back(rowCells[i]);
+                               }
+                       }       
+               }
                clusterBins();
                clusterNames();
-               dMatrix->rmCell(rowCells[0]);
+               // remove also the cell with the smallest distance
+               removeCell(rowCells[rowInd], -1 , -1);
        }
        catch(exception& e) {
                errorOut(e, "SingleLinkage", "update");
@@ -64,4 +85,20 @@ void SingleLinkage::update(){
        }
 }
 
+
+/***********************************************************************/
+//This function updates the distance based on the nearest neighbor method.
+bool SingleLinkage::updateDistance(MatData& colCell, MatData& rowCell) {
+       try {
+               bool changed = false;
+               if (colCell->dist > rowCell->dist) {
+                       colCell->dist = rowCell->dist;
+               }
+               return(changed);
+       }
+       catch(exception& e) {
+               errorOut(e, "SingleLinkage", "updateDistance");
+               exit(1);
+       }
+}
 /***********************************************************************/