sparsedistancematrix.cpp

   1 //
   2 //  sparsedistancematrix.cpp
   3 //  Mothur
   4 //
   5 //  Created by Sarah Westcott on 7/16/12.
   6 //  Copyright (c) 2012 Schloss Lab. All rights reserved.
   7 //
   8
   9 #include "sparsedistancematrix.h"
  10
  11
  12 /***********************************************************************/
  13
  14 SparseDistanceMatrix::SparseDistanceMatrix() : numNodes(0), smallDist(1e6){  m = MothurOut::getInstance(); sorted=false; aboveCutoff = 1e6; }
  15
  16 /***********************************************************************/
  17
  18 int SparseDistanceMatrix::getNNodes(){
  19         return numNodes;
  20 }
  21 /***********************************************************************/
  22
  23 void SparseDistanceMatrix::clear(){
  24     for (int i = 0; i < seqVec.size(); i++) {  seqVec[i].clear();  }
  25     seqVec.clear();
  26 }
  27
  28 /***********************************************************************/
  29
  30 float SparseDistanceMatrix::getSmallDist(){
  31         return smallDist;
  32 }
  33 /***********************************************************************/
  34
  35 int SparseDistanceMatrix::updateCellCompliment(ull row, ull col){
  36     try {
  37
  38         ull vrow = seqVec[row][col].index;
  39         ull vcol = 0;
  40
  41         //find the columns entry for this cell as well
  42         for (int i = 0; i < seqVec[vrow].size(); i++) {
  43             if (seqVec[vrow][i].index == row) { vcol = i;  break; }
  44         }
  45
  46         seqVec[vrow][vcol].dist = seqVec[row][col].dist;
  47
  48         return 0;
  49     }
  50         catch(exception& e) {
  51                 m->errorOut(e, "SparseDistanceMatrix", "updateCellCompliment");
  52                 exit(1);
  53         }
  54 }
  55 /***********************************************************************/
  56
  57 int SparseDistanceMatrix::rmCell(ull row, ull col){
  58         try {
  59         numNodes-=2;
  60
  61         ull vrow = seqVec[row][col].index;
  62         ull vcol = 0;
  63
  64         //find the columns entry for this cell as well
  65         for (int i = 0; i < seqVec[vrow].size(); i++) {  if (seqVec[vrow][i].index == row) { vcol = i;  break; }  }
  66
  67         seqVec[vrow].erase(seqVec[vrow].begin()+vcol);
  68         seqVec[row].erase(seqVec[row].begin()+col);
  69
  70                 return(0);
  71     }
  72         catch(exception& e) {
  73                 m->errorOut(e, "SparseDistanceMatrix", "rmCell");
  74                 exit(1);
  75         }
  76 }
  77 /***********************************************************************/
  78 void SparseDistanceMatrix::addCell(ull row, PDistCell cell){
  79         try {
  80                 numNodes+=2;
  81                 if(cell.dist < smallDist){ smallDist = cell.dist; }
  82
  83         seqVec[row].push_back(cell);
  84         PDistCell temp(row, cell.dist);
  85         seqVec[cell.index].push_back(temp);
  86         }
  87         catch(exception& e) {
  88                 m->errorOut(e, "SparseDistanceMatrix", "addCell");
  89                 exit(1);
  90         }
  91 }
  92 /***********************************************************************/
  93 int SparseDistanceMatrix::addCellSorted(ull row, PDistCell cell){
  94         try {
  95                 numNodes+=2;
  96                 if(cell.dist < smallDist){ smallDist = cell.dist; }
  97
  98         seqVec[row].push_back(cell);
  99         PDistCell temp(row, cell.dist);
 100         seqVec[cell.index].push_back(temp);
 101
 102         sortSeqVec(row);
 103         sortSeqVec(cell.index);
 104
 105         int location = -1; //find location of new cell when sorted
 106         for (int i = 0; i < seqVec[row].size(); i++) {  if (seqVec[row][i].index == cell.index) { location = i; break; } }
 107
 108         return location;
 109         }
 110         catch(exception& e) {
 111                 m->errorOut(e, "SparseDistanceMatrix", "addCellSorted");
 112                 exit(1);
 113         }
 114 }
 115
 116 /***********************************************************************/
 117
 118 ull SparseDistanceMatrix::getSmallestCell(ull& row){
 119         try {
 120         if (!sorted) { sortSeqVec(); sorted = true; }
 121
 122         vector<PDistCellMin> mins;
 123         smallDist = 1e6;
 124
 125         for (int i = 0; i < seqVec.size(); i++) {
 126             for (int j = 0; j < seqVec[i].size(); j++) {
 127
 128                 if (m->control_pressed) { return smallDist; }
 129
 130                 //already checked everyone else in row
 131                 if (i < seqVec[i][j].index) {
 132
 133                     float dist = seqVec[i][j].dist;
 134
 135                     if(dist < smallDist){  //found a new smallest distance
 136                         mins.clear();
 137                         smallDist = dist;
 138                         PDistCellMin temp(i, seqVec[i][j].index);
 139                         mins.push_back(temp);
 140                     }
 141                     else if(dist == smallDist){  //if a subsequent distance is the same as mins distance add the new iterator to the mins vector
 142                         PDistCellMin temp(i, seqVec[i][j].index);
 143                         mins.push_back(temp);
 144                     }
 145                 }else { j+=seqVec[i].size(); } //stop looking
 146                         }
 147                 }
 148
 149                 //random_shuffle(mins.begin(), mins.end());  //randomize the order of the iterators in the mins vector
 150
 151         row = mins[0].row;
 152         ull col = mins[0].col;
 153
 154                 return col;
 155         }
 156         catch(exception& e) {
 157                 m->errorOut(e, "SparseDistanceMatrix", "getSmallestCell");
 158                 exit(1);
 159         }
 160 }
 161 /***********************************************************************/
 162
 163 int SparseDistanceMatrix::sortSeqVec(){
 164         try {
 165
 166         //saves time in getSmallestCell, by making it so you dont search the repeats
 167         for (int i = 0; i < seqVec.size(); i++) {  sort(seqVec[i].begin(), seqVec[i].end(), compareIndexes); }
 168
 169         return 0;
 170     }
 171         catch(exception& e) {
 172                 m->errorOut(e, "SparseDistanceMatrix", "sortSeqVec");
 173                 exit(1);
 174         }
 175 }
 176 /***********************************************************************/
 177
 178 int SparseDistanceMatrix::sortSeqVec(int index){
 179         try {
 180
 181         //saves time in getSmallestCell, by making it so you dont search the repeats
 182         sort(seqVec[index].begin(), seqVec[index].end(), compareIndexes);
 183
 184         return 0;
 185     }
 186         catch(exception& e) {
 187                 m->errorOut(e, "SparseDistanceMatrix", "sortSeqVec");
 188                 exit(1);
 189         }
 190 }
 191 /***********************************************************************/
 192