tree.cpp

   1 /*
   2  *  tree.cpp
   3  *  Mothur
   4  *
   5  *  Created by Sarah Westcott on 1/22/09.
   6  *  Copyright 2009 Schloss Lab UMASS Amherst. All rights reserved.
   7  *
   8  */
   9
  10 #include "tree.h"
  11
  12 /*****************************************************************/
  13 Tree::Tree(int num, TreeMap* t) : tmap(t) {
  14         try {
  15                 m = MothurOut::getInstance();
  16
  17                 numLeaves = num;
  18                 numNodes = 2*numLeaves - 1;
  19
  20                 tree.resize(numNodes);
  21         }
  22         catch(exception& e) {
  23                 m->errorOut(e, "Tree", "Tree - numNodes");
  24                 exit(1);
  25         }
  26 }
  27 /*****************************************************************/
  28 Tree::Tree(string g) { //do not use tree generated by this its just to extract the treenames, its a chicken before the egg thing that needs to be revisited.
  29         try {
  30                 m = MothurOut::getInstance();
  31
  32                 tmap = NULL;
  33
  34                 parseTreeFile();  m->runParse = false;
  35         }
  36         catch(exception& e) {
  37                 m->errorOut(e, "Tree", "Tree - just parse");
  38                 exit(1);
  39         }
  40 }
  41 /*****************************************************************/
  42 Tree::Tree(TreeMap* t) : tmap(t) {
  43         try {
  44                 m = MothurOut::getInstance();
  45
  46                 if (m->runParse == true) {  parseTreeFile();  m->runParse = false;  }
  47 //for(int i = 0; i <    globaldata->Treenames.size(); i++) { cout << i << '\t' << globaldata->Treenames[i] << endl;  }
  48                 numLeaves = m->Treenames.size();
  49                 numNodes = 2*numLeaves - 1;
  50
  51                 tree.resize(numNodes);
  52
  53                 //initialize groupNodeInfo
  54                 for (int i = 0; i < (tmap->getNamesOfGroups()).size(); i++) {
  55                         groupNodeInfo[(tmap->getNamesOfGroups())[i]].resize(0);
  56                 }
  57
  58                 //initialize tree with correct number of nodes, name and group info.
  59                 for (int i = 0; i < numNodes; i++) {
  60                         //initialize leaf nodes
  61                         if (i <= (numLeaves-1)) {
  62                                 tree[i].setName(m->Treenames[i]);
  63
  64                                 //save group info
  65                                 string group = tmap->getGroup(m->Treenames[i]);
  66
  67                                 vector<string> tempGroups; tempGroups.push_back(group);
  68                                 tree[i].setGroup(tempGroups);
  69                                 groupNodeInfo[group].push_back(i);
  70
  71                                 //set pcount and pGroup for groupname to 1.
  72                                 tree[i].pcount[group] = 1;
  73                                 tree[i].pGroups[group] = 1;
  74
  75                                 //Treemap knows name, group and index to speed up search
  76                                 tmap->setIndex(m->Treenames[i], i);
  77
  78                         //intialize non leaf nodes
  79                         }else if (i > (numLeaves-1)) {
  80                                 tree[i].setName("");
  81                                 vector<string> tempGroups;
  82                                 tree[i].setGroup(tempGroups);
  83                         }
  84                 }
  85
  86         }
  87         catch(exception& e) {
  88                 m->errorOut(e, "Tree", "Tree");
  89                 exit(1);
  90         }
  91 }
  92 /*****************************************************************/
  93 Tree::Tree(TreeMap* t, vector< vector<double> >& sims) : tmap(t) {
  94         try {
  95                 m = MothurOut::getInstance();
  96
  97                 if (m->runParse == true) {  parseTreeFile();  m->runParse = false;  }
  98         //for(int i = 0; i <    globaldata->Treenames.size(); i++) { cout << i << '\t' << globaldata->Treenames[i] << endl;  }
  99                 numLeaves = m->Treenames.size();
 100                 numNodes = 2*numLeaves - 1;
 101
 102                 tree.resize(numNodes);
 103
 104                 //initialize groupNodeInfo
 105                 for (int i = 0; i < (tmap->getNamesOfGroups()).size(); i++) {
 106                         groupNodeInfo[(tmap->getNamesOfGroups())[i]].resize(0);
 107                 }
 108
 109                 //initialize tree with correct number of nodes, name and group info.
 110                 for (int i = 0; i < numNodes; i++) {
 111                         //initialize leaf nodes
 112                         if (i <= (numLeaves-1)) {
 113                                 tree[i].setName(m->Treenames[i]);
 114
 115                                 //save group info
 116                                 string group = tmap->getGroup(m->Treenames[i]);
 117
 118                                 vector<string> tempGroups; tempGroups.push_back(group);
 119                                 tree[i].setGroup(tempGroups);
 120                                 groupNodeInfo[group].push_back(i);
 121
 122                                 //set pcount and pGroup for groupname to 1.
 123                                 tree[i].pcount[group] = 1;
 124                                 tree[i].pGroups[group] = 1;
 125
 126                                 //Treemap knows name, group and index to speed up search
 127                                 tmap->setIndex(m->Treenames[i], i);
 128
 129                 //intialize non leaf nodes
 130                         }else if (i > (numLeaves-1)) {
 131                                 tree[i].setName("");
 132                                 vector<string> tempGroups;
 133                                 tree[i].setGroup(tempGroups);
 134                         }
 135                 }
 136
 137         //build tree from matrix
 138         //initialize indexes
 139         map<int, int> indexes;  //maps row in simMatrix to vector index in the tree
 140         int numGroups = (tmap->getNamesOfGroups()).size();
 141         for (int g = 0; g < numGroups; g++) {   indexes[g] = g; }
 142
 143                 //do merges and create tree structure by setting parents and children
 144                 //there are numGroups - 1 merges to do
 145                 for (int i = 0; i < (numGroups - 1); i++) {
 146                         float largest = -1000.0;
 147
 148                         if (m->control_pressed) { break; }
 149
 150                         int row, column;
 151                         //find largest value in sims matrix by searching lower triangle
 152                         for (int j = 1; j < sims.size(); j++) {
 153                                 for (int k = 0; k < j; k++) {
 154                                         if (sims[j][k] > largest) {  largest = sims[j][k]; row = j; column = k;  }
 155                                 }
 156                         }
 157
 158                         //set non-leaf node info and update leaves to know their parents
 159                         //non-leaf
 160                         tree[numGroups + i].setChildren(indexes[row], indexes[column]);
 161
 162                         //parents
 163                         tree[indexes[row]].setParent(numGroups + i);
 164                         tree[indexes[column]].setParent(numGroups + i);
 165
 166                         //blength = distance / 2;
 167                         float blength = ((1.0 - largest) / 2);
 168
 169                         //branchlengths
 170                         tree[indexes[row]].setBranchLength(blength - tree[indexes[row]].getLengthToLeaves());
 171                         tree[indexes[column]].setBranchLength(blength - tree[indexes[column]].getLengthToLeaves());
 172
 173                         //set your length to leaves to your childs length plus branchlength
 174                         tree[numGroups + i].setLengthToLeaves(tree[indexes[row]].getLengthToLeaves() + tree[indexes[row]].getBranchLength());
 175
 176
 177                         //update index
 178                         indexes[row] = numGroups+i;
 179                         indexes[column] = numGroups+i;
 180
 181                         //remove highest value that caused the merge.
 182                         sims[row][column] = -1000.0;
 183                         sims[column][row] = -1000.0;
 184
 185                         //merge values in simsMatrix
 186                         for (int n = 0; n < sims.size(); n++)   {
 187                                 //row becomes merge of 2 groups
 188                                 sims[row][n] = (sims[row][n] + sims[column][n]) / 2;
 189                                 sims[n][row] = sims[row][n];
 190                                 //delete column
 191                                 sims[column][n] = -1000.0;
 192                                 sims[n][column] = -1000.0;
 193                         }
 194                 }
 195
 196                 //adjust tree to make sure root to tip length is .5
 197                 int root = findRoot();
 198                 tree[root].setBranchLength((0.5 - tree[root].getLengthToLeaves()));
 199         }
 200         catch(exception& e) {
 201                 m->errorOut(e, "Tree", "Tree");
 202                 exit(1);
 203         }
 204 }
 205 /*****************************************************************/
 206 Tree::~Tree() {}
 207 /*****************************************************************/
 208 void Tree::addNamesToCounts(map<string, string> nameMap) {
 209         try {
 210                 //ex. seq1      seq2,seq3,se4
 211                 //              seq1 = pasture
 212                 //              seq2 = forest
 213                 //              seq4 = pasture
 214                 //              seq3 = ocean
 215
 216                 //before this function seq1.pcount = pasture -> 1
 217                 //after                            seq1.pcount = pasture -> 2, forest -> 1, ocean -> 1
 218
 219                 //before this function seq1.pgroups = pasture -> 1
 220                 //after                            seq1.pgroups = pasture -> 1 since that is the dominant group
 221
 222
 223                 //go through each leaf and update its pcounts and pgroups
 224
 225                 //float A = clock();
 226
 227                 for (int i = 0; i < numLeaves; i++) {
 228
 229                         string name = tree[i].getName();
 230
 231                         map<string, string>::iterator itNames = nameMap.find(name);
 232
 233                         if (itNames == nameMap.end()) { m->mothurOut(name + " is not in your name file, please correct."); m->mothurOutEndLine(); exit(1);  }
 234                         else {
 235                                 vector<string> dupNames;
 236                                 m->splitAtComma(nameMap[name], dupNames);
 237
 238                                 map<string, int>::iterator itCounts;
 239                                 int maxPars = 1;
 240                                 set<string> groupsAddedForThisNode;
 241                                 for (int j = 0; j < dupNames.size(); j++) {
 242
 243                                         string group = tmap->getGroup(dupNames[j]);
 244
 245                                         if (dupNames[j] != name) {//you already added yourself in the constructor
 246
 247                                                 if (groupsAddedForThisNode.count(group) == 0)  {  groupNodeInfo[group].push_back(i);  groupsAddedForThisNode.insert(group);  } //if you have not already added this node for this group, then add it
 248
 249                                                 //update pcounts
 250                                                 itCounts = tree[i].pcount.find(group);
 251                                                 if (itCounts == tree[i].pcount.end()) { //new group, add it
 252                                                         tree[i].pcount[group] = 1;
 253                                                 }else {
 254                                                         tree[i].pcount[group]++;
 255                                                 }
 256
 257                                                 //update pgroups
 258                                                 itCounts = tree[i].pGroups.find(group);
 259                                                 if (itCounts == tree[i].pGroups.end()) { //new group, add it
 260                                                         tree[i].pGroups[group] = 1;
 261                                                 }else{
 262                                                         tree[i].pGroups[group]++;
 263                                                 }
 264
 265                                                 //keep highest group
 266                                                 if(tree[i].pGroups[group] > maxPars){
 267                                                         maxPars = tree[i].pGroups[group];
 268                                                 }
 269                                         }else {  groupsAddedForThisNode.insert(group);  } //add it so you don't add it to groupNodeInfo again
 270                                 }//end for
 271
 272                                 if (maxPars > 1) { //then we have some more dominant groups
 273                                         //erase all the groups that are less than maxPars because you found a more dominant group.
 274                                         for(it=tree[i].pGroups.begin();it!=tree[i].pGroups.end();){
 275                                                 if(it->second < maxPars){
 276                                                         tree[i].pGroups.erase(it++);
 277                                                 }else { it++; }
 278                                         }
 279                                         //set one remaining groups to 1
 280                                         for(it=tree[i].pGroups.begin();it!=tree[i].pGroups.end();it++){
 281                                                 tree[i].pGroups[it->first] = 1;
 282                                         }
 283                                 }//end if
 284
 285                                 //update groups to reflect all the groups this node represents
 286                                 vector<string> nodeGroups;
 287                                 map<string, int>::iterator itGroups;
 288                                 for (itGroups = tree[i].pcount.begin(); itGroups != tree[i].pcount.end(); itGroups++) {
 289                                         nodeGroups.push_back(itGroups->first);
 290                                 }
 291                                 tree[i].setGroup(nodeGroups);
 292
 293                         }//end else
 294                 }//end for
 295
 296                 //float B = clock();
 297                 //cout << "addNamesToCounts\t" << (B - A) / CLOCKS_PER_SEC << endl;
 298
 299         }
 300         catch(exception& e) {
 301                 m->errorOut(e, "Tree", "addNamesToCounts");
 302                 exit(1);
 303         }
 304 }
 305 /*****************************************************************/
 306 int Tree::getIndex(string searchName) {
 307         try {
 308                 //Treemap knows name, group and index to speed up search
 309                 // getIndex function will return the vector index or -1 if seq is not found.
 310                 int index = tmap->getIndex(searchName);
 311                 return index;
 312
 313         }
 314         catch(exception& e) {
 315                 m->errorOut(e, "Tree", "getIndex");
 316                 exit(1);
 317         }
 318 }
 319 /*****************************************************************/
 320
 321 void Tree::setIndex(string searchName, int index) {
 322         try {
 323                 //set index in treemap
 324                 tmap->setIndex(searchName, index);
 325         }
 326         catch(exception& e) {
 327                 m->errorOut(e, "Tree", "setIndex");
 328                 exit(1);
 329         }
 330 }
 331 /*****************************************************************/
 332 int Tree::assembleTree() {
 333         try {
 334                 //float A = clock();
 335
 336                 //if user has given a names file we want to include that info in the pgroups and pcount info.
 337                 if(m->names.size() != 0) {  addNamesToCounts(m->names);  }
 338
 339                 //build the pGroups in non leaf nodes to be used in the parsimony calcs.
 340                 for (int i = numLeaves; i < numNodes; i++) {
 341                         if (m->control_pressed) { return 1; }
 342
 343                         tree[i].pGroups = (mergeGroups(i));
 344                         tree[i].pcount = (mergeGcounts(i));
 345                 }
 346                 //float B = clock();
 347                 //cout << "assembleTree\t" << (B-A) / CLOCKS_PER_SEC << endl;
 348                 return 0;
 349         }
 350         catch(exception& e) {
 351                 m->errorOut(e, "Tree", "assembleTree");
 352                 exit(1);
 353         }
 354 }
 355 /*****************************************************************/
 356 int Tree::assembleTree(string n) {
 357         try {
 358
 359                 //build the pGroups in non leaf nodes to be used in the parsimony calcs.
 360                 for (int i = numLeaves; i < numNodes; i++) {
 361                         if (m->control_pressed) { return 1; }
 362
 363                         tree[i].pGroups = (mergeGroups(i));
 364                         tree[i].pcount = (mergeGcounts(i));
 365                 }
 366                 //float B = clock();
 367                 //cout << "assembleTree\t" << (B-A) / CLOCKS_PER_SEC << endl;
 368                 return 0;
 369         }
 370         catch(exception& e) {
 371                 m->errorOut(e, "Tree", "assembleTree");
 372                 exit(1);
 373         }
 374 }
 375 /*****************************************************************/
 376 //assumes leaf node names are in groups and no names file - used by indicator command
 377 void Tree::getSubTree(Tree* Ctree, vector<string> Groups) {
 378         try {
 379
 380         //copy Tree since we are going to destroy it
 381         Tree* copy = new Tree(tmap);
 382         copy->getCopy(Ctree);
 383         copy->assembleTree("nonames");
 384
 385                 //we want to select some of the leaf nodes to create the output tree
 386                 //go through the input Tree starting at parents of leaves
 387                 for (int i = 0; i < numNodes; i++) {
 388
 389                         //initialize leaf nodes
 390                         if (i <= (numLeaves-1)) {
 391                                 tree[i].setName(Groups[i]);
 392
 393                                 //save group info
 394                                 string group = tmap->getGroup(Groups[i]);
 395                                 vector<string> tempGroups; tempGroups.push_back(group);
 396                                 tree[i].setGroup(tempGroups);
 397                                 groupNodeInfo[group].push_back(i);
 398
 399                                 //set pcount and pGroup for groupname to 1.
 400                                 tree[i].pcount[group] = 1;
 401                                 tree[i].pGroups[group] = 1;
 402
 403                                 //Treemap knows name, group and index to speed up search
 404                                 tmap->setIndex(Groups[i], i);
 405
 406                                 //intialize non leaf nodes
 407                         }else if (i > (numLeaves-1)) {
 408                                 tree[i].setName("");
 409                                 vector<string> tempGroups;
 410                                 tree[i].setGroup(tempGroups);
 411                         }
 412                 }
 413
 414                 set<int> removedLeaves;
 415                 for (int i = 0; i < copy->getNumLeaves(); i++) {
 416
 417                         if (removedLeaves.count(i) == 0) {
 418
 419                         //am I in the group
 420                         int parent = copy->tree[i].getParent();
 421
 422                         if (parent != -1) {
 423
 424                                 if (m->inUsersGroups(copy->tree[i].getName(), Groups)) {
 425                                         //find my siblings name
 426                                         int parentRC = copy->tree[parent].getRChild();
 427                                         int parentLC = copy->tree[parent].getLChild();
 428
 429                                         //if I am the right child, then my sib is the left child
 430                                         int sibIndex = parentRC;
 431                                         if (parentRC == i) { sibIndex = parentLC; }
 432
 433                                         string sibsName = copy->tree[sibIndex].getName();
 434
 435                                         //if yes, is my sibling
 436                                         if ((m->inUsersGroups(sibsName, Groups)) || (sibsName == "")) {
 437                                                 //we both are okay no trimming required
 438                                         }else{
 439                                                 //i am, my sib is not, so remove sib by setting my parent to my grandparent
 440                                                 int grandparent = copy->tree[parent].getParent();
 441                                                 int grandparentLC = copy->tree[grandparent].getLChild();
 442                                                 int grandparentRC = copy->tree[grandparent].getRChild();
 443
 444                                                 //whichever of my granparents children was my parent now equals me
 445                                                 if (grandparentLC == parent) { grandparentLC = i; }
 446                                                 else { grandparentRC = i; }
 447
 448                                                 copy->tree[i].setParent(grandparent);
 449                                                 copy->tree[i].setBranchLength((copy->tree[i].getBranchLength()+copy->tree[parent].getBranchLength()));
 450                                                 if (grandparent != -1) {
 451                                                         copy->tree[grandparent].setChildren(grandparentLC, grandparentRC);
 452                                                 }
 453                                                 removedLeaves.insert(sibIndex);
 454                                         }
 455                                 }else{
 456                                         //find my siblings name
 457                                         int parentRC = copy->tree[parent].getRChild();
 458                                         int parentLC = copy->tree[parent].getLChild();
 459
 460                                         //if I am the right child, then my sib is the left child
 461                                         int sibIndex = parentRC;
 462                                         if (parentRC == i) { sibIndex = parentLC; }
 463
 464                                         string sibsName = copy->tree[sibIndex].getName();
 465
 466                                         //if no is my sibling
 467                                         if ((m->inUsersGroups(sibsName, Groups)) || (sibsName == "")) {
 468                                                 //i am not, but my sib is
 469                                                 int grandparent = copy->tree[parent].getParent();
 470                                                 int grandparentLC = copy->tree[grandparent].getLChild();
 471                                                 int grandparentRC = copy->tree[grandparent].getRChild();
 472
 473                                                 //whichever of my granparents children was my parent now equals my sib
 474                                                 if (grandparentLC == parent) { grandparentLC = sibIndex; }
 475                                                 else { grandparentRC = sibIndex; }
 476
 477                                                 copy->tree[sibIndex].setParent(grandparent);
 478                                                 copy->tree[sibIndex].setBranchLength((copy->tree[sibIndex].getBranchLength()+copy->tree[parent].getBranchLength()));
 479                                                 if (grandparent != -1) {
 480                                                         copy->tree[grandparent].setChildren(grandparentLC, grandparentRC);
 481                                                 }
 482                                                 removedLeaves.insert(i);
 483                                         }else{
 484                                                 //neither of us are, so we want to eliminate ourselves and our parent
 485                                                 //so set our parents sib to our great-grandparent
 486                                                 int parent = copy->tree[i].getParent();
 487                                                 int grandparent = copy->tree[parent].getParent();
 488                                                 int parentsSibIndex;
 489                                                 if (grandparent != -1) {
 490                                                         int greatgrandparent = copy->tree[grandparent].getParent();
 491                                                         int greatgrandparentLC, greatgrandparentRC;
 492                                                         if (greatgrandparent != -1) {
 493                                                                 greatgrandparentLC = copy->tree[greatgrandparent].getLChild();
 494                                                                 greatgrandparentRC = copy->tree[greatgrandparent].getRChild();
 495                                                         }
 496
 497                                                         int grandparentLC = copy->tree[grandparent].getLChild();
 498                                                         int grandparentRC = copy->tree[grandparent].getRChild();
 499
 500                                                         parentsSibIndex = grandparentLC;
 501                                                         if (grandparentLC == parent) { parentsSibIndex = grandparentRC; }
 502
 503                                                         //whichever of my greatgrandparents children was my grandparent
 504                                                         if (greatgrandparentLC == grandparent) { greatgrandparentLC = parentsSibIndex; }
 505                                                         else { greatgrandparentRC = parentsSibIndex; }
 506
 507                                                         copy->tree[parentsSibIndex].setParent(greatgrandparent);
 508                                                         copy->tree[parentsSibIndex].setBranchLength((copy->tree[parentsSibIndex].getBranchLength()+copy->tree[grandparent].getBranchLength()));
 509                                                         if (greatgrandparent != -1) {
 510                                                                 copy->tree[greatgrandparent].setChildren(greatgrandparentLC, greatgrandparentRC);
 511                                                         }
 512                                                 }else{
 513                                                         copy->tree[parent].setParent(-1);
 514                                                         //cout << "issues with making subtree" << endl;
 515                                                 }
 516                                                 removedLeaves.insert(sibIndex);
 517                                                 removedLeaves.insert(i);
 518                                         }
 519                                 }
 520                         }
 521                         }
 522                 }
 523
 524                 int root = 0;
 525                 for (int i = 0; i < copy->getNumNodes(); i++) {
 526                         //you found the root
 527                         if (copy->tree[i].getParent() == -1) { root = i; break; }
 528                 }
 529
 530                 int nextSpot = numLeaves;
 531                 populateNewTree(copy->tree, root, nextSpot);
 532
 533         delete copy;
 534         }
 535         catch(exception& e) {
 536                 m->errorOut(e, "Tree", "getSubTree");
 537                 exit(1);
 538         }
 539 }
 540 /*****************************************************************/
 541 //assumes nameMap contains unique names as key or is empty.
 542 //assumes numLeaves defined in tree constructor equals size of seqsToInclude and seqsToInclude only contains unique seqs.
 543 int Tree::getSubTree(Tree* copy, vector<string> seqsToInclude, map<string, string> nameMap) {
 544         try {
 545
 546         if (numLeaves != seqsToInclude.size()) { m->mothurOut("[ERROR]: numLeaves does not equal numUniques, cannot create subtree.\n"); m->control_pressed = true; return 0; }
 547
 548         getSubTree(copy, seqsToInclude);
 549         if (nameMap.size() != 0) {  addNamesToCounts(nameMap);  }
 550
 551         //build the pGroups in non leaf nodes to be used in the parsimony calcs.
 552                 for (int i = numLeaves; i < numNodes; i++) {
 553                         if (m->control_pressed) { return 1; }
 554
 555                         tree[i].pGroups = (mergeGroups(i));
 556                         tree[i].pcount = (mergeGcounts(i));
 557                 }
 558
 559         return 0;
 560     }
 561         catch(exception& e) {
 562                 m->errorOut(e, "Tree", "getSubTree");
 563                 exit(1);
 564         }
 565 }
 566 /*****************************************************************/
 567 int Tree::populateNewTree(vector<Node>& oldtree, int node, int& index) {
 568         try {
 569
 570                 if (oldtree[node].getLChild() != -1) {
 571                         int rc = populateNewTree(oldtree, oldtree[node].getLChild(), index);
 572                         int lc = populateNewTree(oldtree, oldtree[node].getRChild(), index);
 573
 574                         tree[index].setChildren(lc, rc);
 575                         tree[rc].setParent(index);
 576                         tree[lc].setParent(index);
 577
 578                         tree[index].setBranchLength(oldtree[node].getBranchLength());
 579                         tree[rc].setBranchLength(oldtree[oldtree[node].getLChild()].getBranchLength());
 580                         tree[lc].setBranchLength(oldtree[oldtree[node].getRChild()].getBranchLength());
 581
 582                         return (index++);
 583                 }else { //you are a leaf
 584                         int indexInNewTree = tmap->getIndex(oldtree[node].getName());
 585                         return indexInNewTree;
 586                 }
 587         }
 588         catch(exception& e) {
 589                 m->errorOut(e, "Tree", "populateNewTree");
 590                 exit(1);
 591         }
 592 }
 593 /*****************************************************************/
 594 void Tree::getCopy(Tree* copy) {
 595         try {
 596
 597                 //for each node in the tree copy its info
 598                 for (int i = 0; i < numNodes; i++) {
 599                         //copy name
 600                         tree[i].setName(copy->tree[i].getName());
 601
 602                         //copy group
 603                         tree[i].setGroup(copy->tree[i].getGroup());
 604
 605                         //copy branch length
 606                         tree[i].setBranchLength(copy->tree[i].getBranchLength());
 607
 608                         //copy parent
 609                         tree[i].setParent(copy->tree[i].getParent());
 610
 611                         //copy children
 612                         tree[i].setChildren(copy->tree[i].getLChild(), copy->tree[i].getRChild());
 613
 614                         //copy index in node and tmap
 615                         tree[i].setIndex(copy->tree[i].getIndex());
 616                         setIndex(copy->tree[i].getName(), getIndex(copy->tree[i].getName()));
 617
 618                         //copy pGroups
 619                         tree[i].pGroups = copy->tree[i].pGroups;
 620
 621                         //copy pcount
 622                         tree[i].pcount = copy->tree[i].pcount;
 623                 }
 624
 625                 groupNodeInfo = copy->groupNodeInfo;
 626
 627         }
 628         catch(exception& e) {
 629                 m->errorOut(e, "Tree", "getCopy");
 630                 exit(1);
 631         }
 632 }
 633 /*****************************************************************/
 634 //returns a map with a groupname and the number of times that group was seen in the children
 635 //for instance if your children are white and black then it would return a map with 2 entries
 636 // p[white] = 1 and p[black] = 1.  Now go up a level and merge that with a node who has p[white] = 1
 637 //and you get p[white] = 2, p[black] = 1, but you erase the p[black] because you have a p value higher than 1.
 638
 639 map<string, int> Tree::mergeGroups(int i) {
 640         try {
 641                 int lc = tree[i].getLChild();
 642                 int rc = tree[i].getRChild();
 643
 644                 //set parsimony groups to left child
 645                 map<string,int> parsimony = tree[lc].pGroups;
 646
 647                 int maxPars = 1;
 648
 649                 //look at right child groups and update maxPars if right child has something higher for that group.
 650                 for(it=tree[rc].pGroups.begin();it!=tree[rc].pGroups.end();it++){
 651                         it2 = parsimony.find(it->first);
 652                         if (it2 != parsimony.end()) {
 653                                 parsimony[it->first]++;
 654                         }else {
 655                                 parsimony[it->first] = 1;
 656                         }
 657
 658                         if(parsimony[it->first] > maxPars){
 659                                 maxPars = parsimony[it->first];
 660                         }
 661                 }
 662
 663                 // this is true if right child had a greater parsimony for a certain group
 664                 if(maxPars > 1){
 665                         //erase all the groups that are only 1 because you found something with 2.
 666                         for(it=parsimony.begin();it!=parsimony.end();){
 667                                 if(it->second == 1){
 668                                         parsimony.erase(it++);
 669                                 }else { it++; }
 670                         }
 671                         //set one remaining groups to 1
 672                         //so with our above example p[white] = 2 would be left and it would become p[white] = 1
 673                         for(it=parsimony.begin();it!=parsimony.end();it++){
 674                                 parsimony[it->first] = 1;
 675                         }
 676
 677                 }
 678
 679                 return parsimony;
 680         }
 681         catch(exception& e) {
 682                 m->errorOut(e, "Tree", "mergeGroups");
 683                 exit(1);
 684         }
 685 }
 686 /*****************************************************************/
 687 //returns a map with a groupname and the number of times that group was seen in the children
 688 //for instance if your children are white and black then it would return a map with 2 entries
 689 // p[white] = 1 and p[black] = 1.  Now go up a level and merge that with a node who has p[white] = 1
 690 //and you get p[white] = 2, p[black] = 1, but you erase the p[black] because you have a p value higher than 1.
 691
 692 map<string, int> Tree::mergeUserGroups(int i, vector<string> g) {
 693         try {
 694
 695                 int lc = tree[i].getLChild();
 696                 int rc = tree[i].getRChild();
 697
 698                 //loop through nodes groups removing the ones the user doesn't want
 699                 for(it=tree[lc].pGroups.begin();it!=tree[lc].pGroups.end();){
 700                                 if (m->inUsersGroups(it->first, g) != true) {
 701                                         tree[lc].pGroups.erase(it++);
 702                                 }else { it++; }
 703                 }
 704
 705                 //loop through nodes groups removing the ones the user doesn't want
 706                 for(it=tree[rc].pGroups.begin();it!=tree[rc].pGroups.end();){
 707                                 if (m->inUsersGroups(it->first, g) != true) {
 708                                         tree[rc].pGroups.erase(it++);
 709                                 }else { it++; }
 710                 }
 711
 712                 //set parsimony groups to left child
 713                 map<string,int> parsimony = tree[lc].pGroups;
 714
 715                 int maxPars = 1;
 716
 717                 //look at right child groups and update maxPars if right child has something higher for that group.
 718                 for(it=tree[rc].pGroups.begin();it!=tree[rc].pGroups.end();it++){
 719                         it2 = parsimony.find(it->first);
 720                         if (it2 != parsimony.end()) {
 721                                 parsimony[it->first]++;
 722                         }else {
 723                                 parsimony[it->first] = 1;
 724                         }
 725
 726                         if(parsimony[it->first] > maxPars){
 727                                 maxPars = parsimony[it->first];
 728                         }
 729                 }
 730
 731                 // this is true if right child had a greater parsimony for a certain group
 732                 if(maxPars > 1){
 733                         //erase all the groups that are only 1 because you found something with 2.
 734                         for(it=parsimony.begin();it!=parsimony.end();){
 735                                 if(it->second == 1){
 736                                         parsimony.erase(it++);
 737                                 }else { it++; }
 738                         }
 739
 740                         for(it=parsimony.begin();it!=parsimony.end();it++){
 741                                 parsimony[it->first] = 1;
 742                         }
 743                 }
 744
 745                 return parsimony;
 746         }
 747         catch(exception& e) {
 748                 m->errorOut(e, "Tree", "mergeUserGroups");
 749                 exit(1);
 750         }
 751 }
 752
 753
 754 /**************************************************************************************************/
 755
 756 map<string,int> Tree::mergeGcounts(int position) {
 757         try{
 758                 map<string,int>::iterator pos;
 759
 760                 int lc = tree[position].getLChild();
 761                 int rc = tree[position].getRChild();
 762
 763                 map<string,int> sum = tree[lc].pcount;
 764
 765                 for(it=tree[rc].pcount.begin();it!=tree[rc].pcount.end();it++){
 766                         sum[it->first] += it->second;
 767                 }
 768                 return sum;
 769         }
 770         catch(exception& e) {
 771                 m->errorOut(e, "Tree", "mergeGcounts");
 772                 exit(1);
 773         }
 774 }
 775 /**************************************************************************************************/
 776 void Tree::randomLabels(vector<string> g) {
 777         try {
 778
 779                 //initialize groupNodeInfo
 780                 for (int i = 0; i < (tmap->getNamesOfGroups()).size(); i++) {
 781                         groupNodeInfo[(tmap->getNamesOfGroups())[i]].resize(0);
 782                 }
 783
 784                 for(int i = 0; i < numLeaves; i++){
 785                         int z;
 786                         //get random index to switch with
 787                         z = int((float)(i+1) * (float)(rand()) / ((float)RAND_MAX+1.0));
 788
 789                         //you only want to randomize the nodes that are from a group the user wants analyzed, so
 790                         //if either of the leaf nodes you are about to switch are not in the users groups then you don't want to switch them.
 791                         bool treez, treei;
 792
 793                         treez = m->inUsersGroups(tree[z].getGroup(), g);
 794                         treei = m->inUsersGroups(tree[i].getGroup(), g);
 795
 796                         if ((treez == true) && (treei == true)) {
 797                                 //switches node i and node z's info.
 798                                 map<string,int> lib_hold = tree[z].pGroups;
 799                                 tree[z].pGroups = (tree[i].pGroups);
 800                                 tree[i].pGroups = (lib_hold);
 801
 802                                 vector<string> zgroup = tree[z].getGroup();
 803                                 tree[z].setGroup(tree[i].getGroup());
 804                                 tree[i].setGroup(zgroup);
 805
 806                                 string zname = tree[z].getName();
 807                                 tree[z].setName(tree[i].getName());
 808                                 tree[i].setName(zname);
 809
 810                                 map<string,int> gcount_hold = tree[z].pcount;
 811                                 tree[z].pcount = (tree[i].pcount);
 812                                 tree[i].pcount = (gcount_hold);
 813                         }
 814
 815                         for (int k = 0; k < (tree[i].getGroup()).size(); k++) {  groupNodeInfo[(tree[i].getGroup())[k]].push_back(i); }
 816                         for (int k = 0; k < (tree[z].getGroup()).size(); k++) {  groupNodeInfo[(tree[z].getGroup())[k]].push_back(z); }
 817                 }
 818         }
 819         catch(exception& e) {
 820                 m->errorOut(e, "Tree", "randomLabels");
 821                 exit(1);
 822         }
 823 }
 824 /**************************************************************************************************/
 825 void Tree::randomBlengths()  {
 826         try {
 827                 for(int i=numNodes-1;i>=0;i--){
 828                         int z = int((float)(i+1) * (float)(rand()) / ((float)RAND_MAX+1.0));
 829
 830                         float bl_hold = tree[z].getBranchLength();
 831                         tree[z].setBranchLength(tree[i].getBranchLength());
 832                         tree[i].setBranchLength(bl_hold);
 833                 }
 834         }
 835         catch(exception& e) {
 836                 m->errorOut(e, "Tree", "randomBlengths");
 837                 exit(1);
 838         }
 839 }
 840 /*************************************************************************************************/
 841 void Tree::assembleRandomUnifracTree(vector<string> g) {
 842         randomLabels(g);
 843         assembleTree("noNameCounts");
 844 }
 845 /*************************************************************************************************/
 846 void Tree::assembleRandomUnifracTree(string groupA, string groupB) {
 847
 848         vector<string> temp; temp.push_back(groupA); temp.push_back(groupB);
 849         randomLabels(temp);
 850         assembleTree("noNameCounts");
 851 }
 852
 853 /*************************************************************************************************/
 854 //for now it's just random topology but may become random labels as well later that why this is such a simple function now...
 855 void Tree::assembleRandomTree() {
 856         randomTopology();
 857         assembleTree();
 858 }
 859 /**************************************************************************************************/
 860
 861 void Tree::randomTopology() {
 862         try {
 863                 for(int i=0;i<numNodes;i++){
 864                         tree[i].setParent(-1);
 865                 }
 866                 for(int i=numLeaves;i<numNodes;i++){
 867                         tree[i].setChildren(-1, -1);
 868                 }
 869
 870                 for(int i=numLeaves;i<numNodes;i++){
 871                         int escape =0;
 872                         int rnd_index1, rnd_index2;
 873                         while(escape == 0){
 874                                 rnd_index1 = (int)(((double)rand() / (double) RAND_MAX)*i);
 875                                 if(tree[rnd_index1].getParent() == -1){escape = 1;}
 876                         }
 877
 878                         escape = 0;
 879                         while(escape == 0){
 880                                 rnd_index2 = (int)(((double)rand() / (double) RAND_MAX)*i);
 881                                 if(rnd_index2 != rnd_index1 && tree[rnd_index2].getParent() == -1){
 882                                         escape = 1;
 883                                 }
 884                         }
 885
 886                         tree[i].setChildren(rnd_index1,rnd_index2);
 887                         tree[i].setParent(-1);
 888                         tree[rnd_index1].setParent(i);
 889                         tree[rnd_index2].setParent(i);
 890                 }
 891         }
 892         catch(exception& e) {
 893                 m->errorOut(e, "Tree", "randomTopology");
 894                 exit(1);
 895         }
 896 }
 897 /*****************************************************************/
 898 void Tree::print(ostream& out) {
 899         try {
 900                 int root = findRoot();
 901                 printBranch(root, out, "branch");
 902                 out << ";" << endl;
 903         }
 904         catch(exception& e) {
 905                 m->errorOut(e, "Tree", "print");
 906                 exit(1);
 907         }
 908 }
 909 /*****************************************************************/
 910 void Tree::print(ostream& out, string mode) {
 911         try {
 912                 int root = findRoot();
 913                 printBranch(root, out, mode);
 914                 out << ";" << endl;
 915         }
 916         catch(exception& e) {
 917                 m->errorOut(e, "Tree", "print");
 918                 exit(1);
 919         }
 920 }
 921 /*****************************************************************/
 922 // This prints out the tree in Newick form.
 923 void Tree::createNewickFile(string f) {
 924         try {
 925                 int root = findRoot();
 926
 927                 filename = f;
 928
 929                 m->openOutputFile(filename, out);
 930
 931                 printBranch(root, out, "branch");
 932
 933                 // you are at the end of the tree
 934                 out << ";" << endl;
 935                 out.close();
 936         }
 937         catch(exception& e) {
 938                 m->errorOut(e, "Tree", "createNewickFile");
 939                 exit(1);
 940         }
 941 }
 942
 943 /*****************************************************************/
 944 //This function finds the index of the root node.
 945
 946 int Tree::findRoot() {
 947         try {
 948                 for (int i = 0; i < numNodes; i++) {
 949                         //you found the root
 950                         if (tree[i].getParent() == -1) { return i; }
 951                         //cout << "i = " << i << endl;
 952                         //cout << "i's parent = " << tree[i].getParent() << endl;
 953                 }
 954                 return -1;
 955         }
 956         catch(exception& e) {
 957                 m->errorOut(e, "Tree", "findRoot");
 958                 exit(1);
 959         }
 960 }
 961 /*****************************************************************/
 962 void Tree::printBranch(int node, ostream& out, string mode) {
 963 try {
 964
 965 // you are not a leaf
 966                 if (tree[node].getLChild() != -1) {
 967                         out << "(";
 968                         printBranch(tree[node].getLChild(), out, mode);
 969                         out << ",";
 970                         printBranch(tree[node].getRChild(), out, mode);
 971                         out << ")";
 972                         if (mode == "branch") {
 973                                 //if there is a branch length then print it
 974                                 if (tree[node].getBranchLength() != -1) {
 975                                         out << ":" << tree[node].getBranchLength();
 976                                 }
 977                         }else if (mode == "boot") {
 978                                 //if there is a label then print it
 979                                 if (tree[node].getLabel() != -1) {
 980                                         out << tree[node].getLabel();
 981                                 }
 982                         }else if (mode == "both") {
 983                                 if (tree[node].getLabel() != -1) {
 984                                         out << tree[node].getLabel();
 985                                 }
 986                                 //if there is a branch length then print it
 987                                 if (tree[node].getBranchLength() != -1) {
 988                                         out << ":" << tree[node].getBranchLength();
 989                                 }
 990                         }else if (mode == "deunique") {
 991                                 //if there is a branch length then print it
 992                                 if (tree[node].getBranchLength() != -1) {
 993                                         out << ":" << tree[node].getBranchLength();
 994                                 }
 995                         }
 996                 }else { //you are a leaf
 997                         string leafGroup = tmap->getGroup(tree[node].getName());
 998
 999                         if (mode == "branch") {
1000                                 out << leafGroup;
1001                                 //if there is a branch length then print it
1002                                 if (tree[node].getBranchLength() != -1) {
1003                                         out << ":" << tree[node].getBranchLength();
1004                                 }
1005                         }else if (mode == "boot") {
1006                                 out << leafGroup;
1007                                 //if there is a label then print it
1008                                 if (tree[node].getLabel() != -1) {
1009                                         out << tree[node].getLabel();
1010                                 }
1011                         }else if (mode == "both") {
1012                                 out << tree[node].getName();
1013                                 if (tree[node].getLabel() != -1) {
1014                                         out << tree[node].getLabel();
1015                                 }
1016                                 //if there is a branch length then print it
1017                                 if (tree[node].getBranchLength() != -1) {
1018                                         out << ":" << tree[node].getBranchLength();
1019                                 }
1020                         }else if (mode == "deunique") {
1021                                 map<string, string>::iterator itNames = m->names.find(tree[node].getName());
1022
1023                                 string outputString = "";
1024                                 if (itNames != m->names.end()) {
1025
1026                                         vector<string> dupNames;
1027                                         m->splitAtComma((itNames->second), dupNames);
1028
1029                                         if (dupNames.size() == 1) {
1030                                                 outputString += tree[node].getName();
1031                                                 if (tree[node].getBranchLength() != -1) {
1032                                                         outputString += ":" + toString(tree[node].getBranchLength());
1033                                                 }
1034                                         }else {
1035                                                 outputString += "(";
1036
1037                                                 for (int u = 0; u < dupNames.size()-1; u++) {
1038                                                         outputString += dupNames[u];
1039
1040                                                         if (tree[node].getBranchLength() != -1) {
1041                                                                 outputString += ":" + toString(0.0);
1042                                                         }
1043                                                         outputString += ",";
1044                                                 }
1045
1046                                                 outputString += dupNames[dupNames.size()-1];
1047                                                 if (tree[node].getBranchLength() != -1) {
1048                                                         outputString += ":" + toString(0.0);
1049                                                 }
1050
1051                                                 outputString += ")";
1052                                                 if (tree[node].getBranchLength() != -1) {
1053                                                         outputString += ":" + toString(tree[node].getBranchLength());
1054                                                 }
1055                                         }
1056                                 }else {
1057                                         outputString = tree[node].getName();
1058                                         //if there is a branch length then print it
1059                                         if (tree[node].getBranchLength() != -1) {
1060                                                 outputString += ":" + toString(tree[node].getBranchLength());
1061                                         }
1062
1063                                         m->mothurOut("[ERROR]: " + tree[node].getName() + " is not in your namefile, please correct."); m->mothurOutEndLine();
1064                                 }
1065
1066                                 out << outputString;
1067                         }
1068                 }
1069
1070         }
1071         catch(exception& e) {
1072                 m->errorOut(e, "Tree", "printBranch");
1073                 exit(1);
1074         }
1075 }
1076 /*****************************************************************/
1077 void Tree::printBranch(int node, ostream& out, string mode, vector<Node>& theseNodes) {
1078         try {
1079
1080                 // you are not a leaf
1081                 if (theseNodes[node].getLChild() != -1) {
1082                         out << "(";
1083                         printBranch(theseNodes[node].getLChild(), out, mode);
1084                         out << ",";
1085                         printBranch(theseNodes[node].getRChild(), out, mode);
1086                         out << ")";
1087                         if (mode == "branch") {
1088                                 //if there is a branch length then print it
1089                                 if (theseNodes[node].getBranchLength() != -1) {
1090                                         out << ":" << theseNodes[node].getBranchLength();
1091                                 }
1092                         }else if (mode == "boot") {
1093                                 //if there is a label then print it
1094                                 if (theseNodes[node].getLabel() != -1) {
1095                                         out << theseNodes[node].getLabel();
1096                                 }
1097                         }else if (mode == "both") {
1098                                 if (theseNodes[node].getLabel() != -1) {
1099                                         out << theseNodes[node].getLabel();
1100                                 }
1101                                 //if there is a branch length then print it
1102                                 if (theseNodes[node].getBranchLength() != -1) {
1103                                         out << ":" << theseNodes[node].getBranchLength();
1104                                 }
1105                         }
1106                 }else { //you are a leaf
1107                         string leafGroup = tmap->getGroup(theseNodes[node].getName());
1108
1109                         if (mode == "branch") {
1110                                 out << leafGroup;
1111                                 //if there is a branch length then print it
1112                                 if (theseNodes[node].getBranchLength() != -1) {
1113                                         out << ":" << theseNodes[node].getBranchLength();
1114                                 }
1115                         }else if (mode == "boot") {
1116                                 out << leafGroup;
1117                                 //if there is a label then print it
1118                                 if (theseNodes[node].getLabel() != -1) {
1119                                         out << theseNodes[node].getLabel();
1120                                 }
1121                         }else if (mode == "both") {
1122                                 out << theseNodes[node].getName();
1123                                 if (theseNodes[node].getLabel() != -1) {
1124                                         out << theseNodes[node].getLabel();
1125                                 }
1126                                 //if there is a branch length then print it
1127                                 if (theseNodes[node].getBranchLength() != -1) {
1128                                         out << ":" << theseNodes[node].getBranchLength();
1129                                 }
1130                         }
1131                 }
1132
1133         }
1134         catch(exception& e) {
1135                 m->errorOut(e, "Tree", "printBranch");
1136                 exit(1);
1137         }
1138 }
1139 /*****************************************************************/
1140
1141 void Tree::printTree() {
1142
1143         for(int i=0;i<numNodes;i++){
1144                 cout << i << '\t';
1145                 tree[i].printNode();
1146         }
1147
1148 }
1149
1150 /*****************************************************************/
1151 //this code is a mess and should be rethought...-slw
1152 void Tree::parseTreeFile() {
1153
1154         //only takes names from the first tree and assumes that all trees use the same names.
1155         try {
1156                 string filename = m->getTreeFile();
1157                 ifstream filehandle;
1158                 m->openInputFile(filename, filehandle);
1159                 int c, comment;
1160                 comment = 0;
1161                 int done = 1;
1162
1163                 //ifyou are not a nexus file
1164                 if((c = filehandle.peek()) != '#') {
1165                         while((c = filehandle.peek()) != ';') {
1166                                 while ((c = filehandle.peek()) != ';') {
1167                                         // get past comments
1168                                         if(c == '[') {
1169                                                 comment = 1;
1170                                         }
1171                                         if(c == ']'){
1172                                                 comment = 0;
1173                                         }
1174                                         if((c == '(') && (comment != 1)){ break; }
1175                                         filehandle.get();
1176                                 }
1177
1178                                 done = readTreeString(filehandle);
1179                                 if (done == 0) { break; }
1180                         }
1181                 //ifyou are a nexus file
1182                 }else if((c = filehandle.peek()) == '#') {
1183                         string holder = "";
1184
1185                         // get past comments
1186                         while(holder != "translate" && holder != "Translate"){
1187                                 if(holder == "[" || holder == "[!"){
1188                                         comment = 1;
1189                                 }
1190                                 if(holder == "]"){
1191                                         comment = 0;
1192                                 }
1193                                 filehandle >> holder;
1194
1195                                 //if there is no translate then you must read tree string otherwise use translate to get names
1196                                 if((holder == "tree") && (comment != 1)){
1197                                         //pass over the "tree rep.6878900 = "
1198                                         while (((c = filehandle.get()) != '(') && ((c = filehandle.peek()) != EOF)) {;}
1199
1200                                         if(c == EOF) { break; }
1201                                         filehandle.putback(c);  //put back first ( of tree.
1202                                         done = readTreeString(filehandle);
1203
1204                                         break;
1205                                 }
1206
1207                                 if (done == 0) { break;  }
1208                         }
1209
1210                         //use nexus translation rather than parsing tree to save time
1211                         if((holder == "translate") || (holder == "Translate")) {
1212
1213                                 string number, name, h;
1214                                 h = ""; // so it enters the loop the first time
1215                                 while((h != ";") && (number != ";")) {
1216                                         filehandle >> number;
1217                                         filehandle >> name;
1218
1219                                         //c = , until done with translation then c = ;
1220                                         h = name.substr(name.length()-1, name.length());
1221                                         name.erase(name.end()-1);  //erase the comma
1222                                         m->Treenames.push_back(number);
1223                                 }
1224                                 if(number == ";") { m->Treenames.pop_back(); }  //in case ';' from translation is on next line instead of next to last name
1225                         }
1226                 }
1227                 filehandle.close();
1228
1229                 //for (int i = 0; i < globaldata->Treenames.size(); i++) {
1230 //cout << globaldata->Treenames[i] << endl; }
1231 //cout << globaldata->Treenames.size() << endl;
1232         }
1233         catch(exception& e) {
1234                 m->errorOut(e, "Tree", "parseTreeFile");
1235                 exit(1);
1236         }
1237 }
1238 /*******************************************************/
1239
1240 /*******************************************************/
1241 int Tree::readTreeString(ifstream& filehandle)  {
1242         try {
1243                 int c;
1244                 string name;  //, k
1245
1246                 while((c = filehandle.peek()) != ';') {
1247 //k = c;
1248 //cout << " at beginning of while " <<  k << endl;
1249                         if(c == ')')  {
1250                                 //to pass over labels in trees
1251                                 c=filehandle.get();
1252                                 while((c!=',') && (c != -1) && (c!= ':') && (c!=';')){ c=filehandle.get(); }
1253                                 filehandle.putback(c);
1254                         }
1255                         if(c == ';') { return 0; }
1256                         if(c == -1) { return 0; }
1257                         //if you are a name
1258                         if((c != '(') && (c != ')') && (c != ',') && (c != ':') && (c != '\n') && (c != '\t') && (c != 32)) { //32 is space
1259                                 name = "";
1260                                 c = filehandle.get();
1261                         //k = c;
1262 //cout << k << endl;
1263                                 while ((c != '(') && (c != ')') && (c != ',') && (c != ':') && (c != '\n') && (c != 32) && (c != '\t')) {
1264                                         name += c;
1265                                         c = filehandle.get();
1266                         //k = c;
1267 //cout << " in name while " << k << endl;
1268                                 }
1269
1270 //cout << "name = " << name << endl;
1271                                 m->Treenames.push_back(name);
1272                                 filehandle.putback(c);
1273 //k = c;
1274 //cout << " after putback" <<  k << endl;
1275                         }
1276
1277                         if(c  == ':') { //read until you reach the end of the branch length
1278                                 while ((c != '(') && (c != ')') && (c != ',') && (c != ';') && (c != '\n') && (c != '\t') && (c != 32)) {
1279                                         c = filehandle.get();
1280         //k = c;
1281         //cout << " in branch while " << k << endl;
1282                                 }
1283                                 filehandle.putback(c);
1284                         }
1285
1286                         c = filehandle.get();
1287 //k = c;
1288         //cout << " here after get " << k << endl;
1289                         if(c == ';') { return 0; }
1290                         if(c == ')') { filehandle.putback(c); }
1291         //k = c;
1292 //cout << k << endl;
1293
1294                 }
1295                 return 0;
1296         }
1297         catch(exception& e) {
1298                 m->errorOut(e, "Tree", "readTreeString");
1299                 exit(1);
1300         }
1301 }
1302
1303 /*******************************************************/
1304
1305 /*******************************************************/
1306