+#include "mothur.h"
#include "cluster.hpp"
/***********************************************************************/
-SingleLinkage::SingleLinkage(RAbundVector* rav, ListVector* lv, SparseMatrix* dm) :
-Cluster(rav, lv, dm)
+SingleLinkage::SingleLinkage(RAbundVector* rav, ListVector* lv, SparseMatrix* dm, float c, string s) :
+Cluster(rav, lv, dm, c, s)
{}
+
+/***********************************************************************/
+//This function returns the tag of the method.
+string SingleLinkage::getTag() {
+ return("nn");
+}
+
/***********************************************************************/
-//This function clusters based on nearest method.
-void SingleLinkage::update(){
+//This function clusters based on the single linkage method.
+void SingleLinkage::update(double& cutOFF){
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) {
- cout << "Standard Error: " << e.what() << " has occurred in the SingleLinkage class Function update. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
+ m->errorOut(e, "SingleLinkage", "update");
exit(1);
}
- catch(...) {
- cout << "An unknown error has occurred in the SingleLinkage class function update. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
- exit(1);
- }
}
+
+/***********************************************************************/
+//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) {
+ m->errorOut(e, "SingleLinkage", "updateDistance");
+ exit(1);
+ }
+}
/***********************************************************************/