X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;ds=sidebyside;f=singlelinkage.cpp;h=c27b14e727057c6dcd14f2b0268cd250c4d52559;hb=1b9d0a66e4737f31d16824fe93944880b9edc530;hp=5332e907d27b86d13f40c411baa4a96cbf879f40;hpb=9a339a6b007b23c39b7eb20cc777af66dd2cebef;p=mothur.git

diff --git a/singlelinkage.cpp b/singlelinkage.cpp
index 5332e90..c27b14e 100644
--- 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);
+	}
+}
 /***********************************************************************/