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 /*****************************************************************/
  14 Tree::Tree() {
  15         try {
  16                 globaldata = GlobalData::getInstance();
  17
  18                 if (globaldata->runParse == true) {  parseTreeFile();  globaldata->runParse = false;  }
  19
  20                 numLeaves = globaldata->Treenames.size();
  21                 numNodes = 2*numLeaves - 1;
  22
  23                 tree.resize(numNodes);
  24
  25                 //initialize tree with correct number of nodes, name and group info.
  26                 for (int i = 0; i < numNodes; i++) {
  27                         //initialize leaf nodes
  28                         if (i <= (numLeaves-1)) {
  29                                 tree[i].setName(globaldata->Treenames[i]);
  30                                 tree[i].setGroup(globaldata->gTreemap->getGroup(globaldata->Treenames[i]));
  31                                 //set pcount and pGroup for groupname to 1.
  32                                 tree[i].pcount[globaldata->gTreemap->getGroup(globaldata->Treenames[i])] = 1;
  33                                 tree[i].pGroups[globaldata->gTreemap->getGroup(globaldata->Treenames[i])] = 1;
  34                                 //Treemap knows name, group and index to speed up search
  35                                 globaldata->gTreemap->setIndex(globaldata->Treenames[i], i);
  36
  37                         //intialize non leaf nodes
  38                         }else if (i > (numLeaves-1)) {
  39                                 tree[i].setName("");
  40                                 tree[i].setGroup("");
  41                         }
  42                 }
  43         }
  44         catch(exception& e) {
  45                 cout << "Standard Error: " << e.what() << " has occurred in the Tree class Function Tree. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
  46                 exit(1);
  47         }
  48         catch(...) {
  49                 cout << "An unknown error has occurred in the Tree class function Tree. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
  50                 exit(1);
  51         }
  52 }
  53
  54 /*****************************************************************/
  55 Tree::~Tree() {}
  56 /*****************************************************************/
  57 int Tree::getIndex(string searchName) {
  58         try {
  59                 //Treemap knows name, group and index to speed up search
  60                 // getIndex function will return the vector index or -1 if seq is not found.
  61                 int index = globaldata->gTreemap->getIndex(searchName);
  62                 return index;
  63
  64         }
  65         catch(exception& e) {
  66                 cout << "Standard Error: " << e.what() << " has occurred in the Tree class Function getIndex. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
  67                 exit(1);
  68         }
  69         catch(...) {
  70                 cout << "An unknown error has occurred in the Tree class function getIndex. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
  71                 exit(1);
  72         }
  73 }
  74 /*****************************************************************/
  75
  76 void Tree::setIndex(string searchName, int index) {
  77         try {
  78                 //set index in treemap
  79                 globaldata->gTreemap->setIndex(searchName, index);
  80         }
  81         catch(exception& e) {
  82                 cout << "Standard Error: " << e.what() << " has occurred in the Tree class Function setIndex. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
  83                 exit(1);
  84         }
  85         catch(...) {
  86                 cout << "An unknown error has occurred in the Tree class function setIndex. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
  87                 exit(1);
  88         }
  89 }
  90 /*****************************************************************/
  91 void Tree::assembleTree() {
  92         try {
  93                 //build the pGroups in non leaf nodes to be used in the parsimony calcs.
  94                 for (int i = numLeaves; i < numNodes; i++) {
  95                         tree[i].pGroups = (mergeGroups(i));
  96                         tree[i].pcount = (mergeGcounts(i));
  97                 }
  98         }
  99         catch(exception& e) {
 100                 cout << "Standard Error: " << e.what() << " has occurred in the Tree class Function assembleTree. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 101                 exit(1);
 102         }
 103         catch(...) {
 104                 cout << "An unknown error has occurred in the Tree class function assembleTree. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 105                 exit(1);
 106         }
 107 }
 108 /*****************************************************************/
 109 void Tree::getCopy(Tree* copy) {
 110         try {
 111
 112                 //for each node in the tree copy its info
 113                 for (int i = 0; i < numNodes; i++) {
 114                         //copy name
 115                         tree[i].setName(copy->tree[i].getName());
 116
 117                         //copy group
 118                         tree[i].setGroup(copy->tree[i].getGroup());
 119
 120                         //copy branch length
 121                         tree[i].setBranchLength(copy->tree[i].getBranchLength());
 122
 123                         //copy parent
 124                         tree[i].setParent(copy->tree[i].getParent());
 125
 126                         //copy children
 127                         tree[i].setChildren(copy->tree[i].getLChild(), copy->tree[i].getRChild());
 128
 129                         //copy index in node and tmap
 130                         tree[i].setIndex(copy->tree[i].getIndex());
 131                         setIndex(copy->tree[i].getName(), getIndex(copy->tree[i].getName()));
 132
 133                         //copy pGroups
 134                         tree[i].pGroups = copy->tree[i].pGroups;
 135
 136                         //copy pcount
 137                         tree[i].pcount = copy->tree[i].pcount;
 138                 }
 139         }
 140         catch(exception& e) {
 141                 cout << "Standard Error: " << e.what() << " has occurred in the Tree class Function getCopy. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 142                 exit(1);
 143         }
 144         catch(...) {
 145                 cout << "An unknown error has occurred in the Tree class function getCopy. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 146                 exit(1);
 147         }
 148 }
 149 /*****************************************************************/
 150 //returns a map with a groupname and the number of times that group was seen in the children
 151 //for instance if your children are white and black then it would return a map with 2 entries
 152 // p[white] = 1 and p[black] = 1.  Now go up a level and merge that with a node who has p[white] = 1
 153 //and you get p[white] = 2, p[black] = 1, but you erase the p[black] because you have a p value higher than 1.
 154
 155 map<string, int> Tree::mergeGroups(int i) {
 156         try {
 157                 int lc = tree[i].getLChild();
 158                 int rc = tree[i].getRChild();
 159
 160                 //set parsimony groups to left child
 161                 map<string,int> parsimony = tree[lc].pGroups;
 162
 163                 int maxPars = 1;
 164
 165                 //look at right child groups and update maxPars if right child has something higher for that group.
 166                 for(it=tree[rc].pGroups.begin();it!=tree[rc].pGroups.end();it++){
 167                         it2 = parsimony.find(it->first);
 168                         if (it2 != parsimony.end()) {
 169                                 parsimony[it->first]++;
 170                         }else {
 171                                 parsimony[it->first] = 1;
 172                         }
 173
 174                         if(parsimony[it->first] > maxPars){
 175                                 maxPars = parsimony[it->first];
 176                         }
 177                 }
 178
 179                 // this is true if right child had a greater parsimony for a certain group
 180                 if(maxPars > 1){
 181                         //erase all the groups that are only 1 because you found something with 2.
 182                         for(it=parsimony.begin();it!=parsimony.end();it++){
 183                                 if(it->second == 1){
 184                                         parsimony.erase(it->first);
 185 //                                      it--;
 186                                 }
 187                         }
 188                         //set one remaining groups to 1
 189                         //so with our above example p[white] = 2 would be left and it would become p[white] = 1
 190                         for(it=parsimony.begin();it!=parsimony.end();it++){
 191                                 parsimony[it->first] = 1;
 192                         }
 193
 194                 }
 195
 196                 return parsimony;
 197         }
 198         catch(exception& e) {
 199                 cout << "Standard Error: " << e.what() << " has occurred in the Tree class Function mergeGroups. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 200                 exit(1);
 201         }
 202         catch(...) {
 203                 cout << "An unknown error has occurred in the Tree class function mergeGroups. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 204                 exit(1);
 205         }
 206 }
 207 /*****************************************************************/
 208 //returns a map with a groupname and the number of times that group was seen in the children
 209 //for instance if your children are white and black then it would return a map with 2 entries
 210 // p[white] = 1 and p[black] = 1.  Now go up a level and merge that with a node who has p[white] = 1
 211 //and you get p[white] = 2, p[black] = 1, but you erase the p[black] because you have a p value higher than 1.
 212
 213 map<string, int> Tree::mergeUserGroups(int i, vector<string> g) {
 214         try {
 215
 216                 int lc = tree[i].getLChild();
 217                 int rc = tree[i].getRChild();
 218
 219                 //loop through nodes groups removing the ones the user doesn't want
 220                 for (it = tree[lc].pGroups.begin(); it != tree[lc].pGroups.end(); it++) {
 221                         if (inUsersGroups(it->first, g) != true) { tree[lc].pGroups.erase(it->first); }
 222                 }
 223
 224                 //loop through nodes groups removing the ones the user doesn't want
 225                 for (it = tree[rc].pGroups.begin(); it != tree[rc].pGroups.end(); it++) {
 226                         if (inUsersGroups(it->first, g) != true) { tree[rc].pGroups.erase(it->first); }
 227                 }
 228
 229                 //set parsimony groups to left child
 230                 map<string,int> parsimony = tree[lc].pGroups;
 231
 232                 int maxPars = 1;
 233
 234                 //look at right child groups and update maxPars if right child has something higher for that group.
 235                 for(it=tree[rc].pGroups.begin();it!=tree[rc].pGroups.end();it++){
 236                         it2 = parsimony.find(it->first);
 237                         if (it2 != parsimony.end()) {
 238                                 parsimony[it->first]++;
 239                         }else {
 240                                 parsimony[it->first] = 1;
 241                         }
 242
 243                         if(parsimony[it->first] > maxPars){
 244                                 maxPars = parsimony[it->first];
 245                         }
 246                 }
 247
 248                 // this is true if right child had a greater parsimony for a certain group
 249                 if(maxPars > 1){
 250                         //erase all the groups that are only 1 because you found something with 2.
 251                         for(it=parsimony.begin();it!=parsimony.end();it++){
 252                                 if(it->second == 1){
 253                                         parsimony.erase(it->first);
 254                                 }
 255                         }
 256                         for(it=parsimony.begin();it!=parsimony.end();it++){
 257                                 parsimony[it->first] = 1;
 258                         }
 259                 }
 260
 261                 return parsimony;
 262         }
 263         catch(exception& e) {
 264                 cout << "Standard Error: " << e.what() << " has occurred in the Tree class Function mergeGroups. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 265                 exit(1);
 266         }
 267         catch(...) {
 268                 cout << "An unknown error has occurred in the Tree class function mergeGroups. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 269                 exit(1);
 270         }
 271 }
 272
 273
 274 /**************************************************************************************************/
 275
 276 map<string,int> Tree::mergeGcounts(int position) {
 277         try{
 278                 map<string,int>::iterator pos;
 279
 280                 int lc = tree[position].getLChild();
 281                 int rc = tree[position].getRChild();
 282
 283                 map<string,int> sum = tree[lc].pcount;
 284
 285                 for(it=tree[rc].pcount.begin();it!=tree[rc].pcount.end();it++){
 286                         sum[it->first] += it->second;
 287                 }
 288                 return sum;
 289         }
 290         catch(exception& e) {
 291                 cout << "Standard Error: " << e.what() << " has occurred in the Tree class Function mergeGcounts. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 292                 exit(1);
 293         }
 294         catch(...) {
 295                 cout << "An unknown error has occurred in the Tree class function mergeGcounts. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 296                 exit(1);
 297         }
 298 }
 299 /**************************************************************************************************/
 300
 301 void Tree::randomLabels(vector<string> g) {
 302         try {
 303
 304                 for(int i = 0; i < numLeaves; i++){
 305                         int z;
 306                         //get random index to switch with
 307                         z = int((float)(i+1) * (float)(rand()) / ((float)RAND_MAX+1.0));
 308
 309                         //you only want to randomize the nodes that are from a group the user wants analyzed, so
 310                         //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.
 311                         bool treez, treei;
 312
 313                         treez = inUsersGroups(tree[z].getGroup(), g);
 314                         treei = inUsersGroups(tree[i].getGroup(), g);
 315
 316                         if ((treez == true) && (treei == true)) {
 317                                 //switches node i and node z's info.
 318                                 map<string,int> lib_hold = tree[z].pGroups;
 319                                 tree[z].pGroups = (tree[i].pGroups);
 320                                 tree[i].pGroups = (lib_hold);
 321
 322                                 string zgroup = tree[z].getGroup();
 323                                 tree[z].setGroup(tree[i].getGroup());
 324                                 tree[i].setGroup(zgroup);
 325
 326                                 string zname = tree[z].getName();
 327                                 tree[z].setName(tree[i].getName());
 328                                 tree[i].setName(zname);
 329
 330                                 map<string,int> gcount_hold = tree[z].pcount;
 331                                 tree[z].pcount = (tree[i].pcount);
 332                                 tree[i].pcount = (gcount_hold);
 333                         }
 334                 }
 335         }
 336         catch(exception& e) {
 337                 cout << "Standard Error: " << e.what() << " has occurred in the Tree class Function randomLabels. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 338                 exit(1);
 339         }
 340         catch(...) {
 341                 cout << "An unknown error has occurred in the Tree class function randomLabels. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 342                 exit(1);
 343         }
 344 }
 345 /**************************************************************************************************/
 346
 347 void Tree::randomLabels(string groupA, string groupB) {
 348         try {
 349                 int numSeqsA = globaldata->gTreemap->seqsPerGroup[groupA];
 350                 int numSeqsB = globaldata->gTreemap->seqsPerGroup[groupB];
 351
 352                 vector<string> randomGroups(numSeqsA+numSeqsB, groupA);
 353                 for(int i=numSeqsA;i<randomGroups.size();i++){
 354                         randomGroups[i] = groupB;
 355                 }
 356                 random_shuffle(randomGroups.begin(), randomGroups.end());
 357
 358                 int randomCounter = 0;
 359                 for(int i=0;i<numLeaves;i++){
 360                         if(tree[i].getGroup() == groupA || tree[i].getGroup() == groupB){
 361                                 tree[i].setGroup(randomGroups[randomCounter]);
 362                                 tree[i].pcount.clear();
 363                                 tree[i].pcount[randomGroups[randomCounter]] = 1;
 364                                 tree[i].pGroups.clear();
 365                                 tree[i].pGroups[randomGroups[randomCounter]] = 1;
 366                                 randomCounter++;
 367                         }
 368                 }
 369         }
 370         catch(exception& e) {
 371                 cout << "Standard Error: " << e.what() << " has occurred in the Tree class Function randomLabels. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 372                 exit(1);
 373         }
 374         catch(...) {
 375                 cout << "An unknown error has occurred in the Tree class function randomLabels. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 376                 exit(1);
 377         }
 378 }
 379 /**************************************************************************************************/
 380 void Tree::randomBlengths()  {
 381         try {
 382                 for(int i=numNodes-1;i>=0;i--){
 383                         int z = int((float)(i+1) * (float)(rand()) / ((float)RAND_MAX+1.0));
 384
 385                         float bl_hold = tree[z].getBranchLength();
 386                         tree[z].setBranchLength(tree[i].getBranchLength());
 387                         tree[i].setBranchLength(bl_hold);
 388                 }
 389         }
 390         catch(exception& e) {
 391                 cout << "Standard Error: " << e.what() << " has occurred in the Tree class Function randomBlengths. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 392                 exit(1);
 393         }
 394         catch(...) {
 395                 cout << "An unknown error has occurred in the Tree class function randomBlengths. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 396                 exit(1);
 397         }
 398 }
 399 /*************************************************************************************************/
 400 void Tree::assembleRandomUnifracTree(vector<string> g) {
 401         randomLabels(g);
 402         assembleTree();
 403 }
 404 /*************************************************************************************************/
 405 void Tree::assembleRandomUnifracTree(string groupA, string groupB) {
 406         randomLabels(groupA, groupB);
 407         assembleTree();
 408 }
 409
 410 /*************************************************************************************************/
 411 //for now it's just random topology but may become random labels as well later that why this is such a simple function now...
 412 void Tree::assembleRandomTree() {
 413         randomTopology();
 414         assembleTree();
 415 }
 416 /**************************************************************************************************/
 417
 418 void Tree::randomTopology() {
 419         try {
 420                 for(int i=0;i<numNodes;i++){
 421                         tree[i].setParent(-1);
 422                 }
 423                 for(int i=numLeaves;i<numNodes;i++){
 424                         tree[i].setChildren(-1, -1);
 425                 }
 426
 427                 for(int i=numLeaves;i<numNodes;i++){
 428                         int escape =0;
 429                         int rnd_index1, rnd_index2;
 430                         while(escape == 0){
 431                                 rnd_index1 = (int)(((double)rand() / (double) RAND_MAX)*i);
 432                                 if(tree[rnd_index1].getParent() == -1){escape = 1;}
 433                         }
 434
 435                         escape = 0;
 436                         while(escape == 0){
 437                                 rnd_index2 = (int)(((double)rand() / (double) RAND_MAX)*i);
 438                                 if(rnd_index2 != rnd_index1 && tree[rnd_index2].getParent() == -1){
 439                                         escape = 1;
 440                                 }
 441                         }
 442
 443                         tree[i].setChildren(rnd_index1,rnd_index2);
 444                         tree[i].setParent(-1);
 445                         tree[rnd_index1].setParent(i);
 446                         tree[rnd_index2].setParent(i);
 447                 }
 448         }
 449         catch(exception& e) {
 450                 cout << "Standard Error: " << e.what() << " has occurred in the Tree class Function randomTopology. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 451                 exit(1);
 452         }
 453         catch(...) {
 454                 cout << "An unknown error has occurred in the Tree class function randomTopology. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 455                 exit(1);
 456         }
 457 }
 458 /*****************************************************************/
 459 void Tree::print(ostream& out) {
 460         try {
 461                 int root = findRoot();
 462                 printBranch(root, out, "branch");
 463                 out << ";" << endl;
 464         }
 465         catch(exception& e) {
 466                 cout << "Standard Error: " << e.what() << " has occurred in the Tree class Function print. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 467                 exit(1);
 468         }
 469         catch(...) {
 470                 cout << "An unknown error has occurred in the Tree class function print. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 471                 exit(1);
 472         }
 473 }
 474 /*****************************************************************/
 475 void Tree::printForBoot(ostream& out) {
 476         try {
 477                 int root = findRoot();
 478                 printBranch(root, out, "boot");
 479                 out << ";" << endl;
 480         }
 481         catch(exception& e) {
 482                 cout << "Standard Error: " << e.what() << " has occurred in the Tree class Function printForBoot. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 483                 exit(1);
 484         }
 485         catch(...) {
 486                 cout << "An unknown error has occurred in the Tree class function printForBoot. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 487                 exit(1);
 488         }
 489 }
 490
 491 /*****************************************************************/
 492 // This prints out the tree in Newick form.
 493 void Tree::createNewickFile(string f) {
 494         try {
 495                 int root = findRoot();
 496                 //filename = getRootName(globaldata->getTreeFile()) + "newick";
 497                 filename = f;
 498
 499                 openOutputFile(filename, out);
 500
 501                 printBranch(root, out, "branch");
 502
 503                 // you are at the end of the tree
 504                 out << ";" << endl;
 505                 out.close();
 506         }
 507         catch(exception& e) {
 508                 cout << "Standard Error: " << e.what() << " has occurred in the Tree class Function createNewickFile. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 509                 exit(1);
 510         }
 511         catch(...) {
 512                 cout << "An unknown error has occurred in the Tree class function createNewickFile. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 513                 exit(1);
 514         }
 515 }
 516
 517 /*****************************************************************/
 518 //This function finds the index of the root node.
 519
 520 int Tree::findRoot() {
 521         try {
 522                 for (int i = 0; i < numNodes; i++) {
 523                         //you found the root
 524                         if (tree[i].getParent() == -1) { return i; }
 525                         //cout << "i = " << i << endl;
 526                         //cout << "i's parent = " << tree[i].getParent() << endl;
 527                 }
 528                 return -1;
 529         }
 530         catch(exception& e) {
 531                 cout << "Standard Error: " << e.what() << " has occurred in the Tree class Function findRoot. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 532                 exit(1);
 533         }
 534         catch(...) {
 535                 cout << "An unknown error has occurred in the Tree class function findRoot. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 536                 exit(1);
 537         }
 538 }
 539
 540 /*****************************************************************/
 541 void Tree::printBranch(int node, ostream& out, string mode) {
 542         try {
 543
 544                 // you are not a leaf
 545                 if (tree[node].getLChild() != -1) {
 546                         out << "(";
 547                         printBranch(tree[node].getLChild(), out, mode);
 548                         out << ",";
 549                         printBranch(tree[node].getRChild(), out, mode);
 550                         out << ")";
 551                         if (mode == "branch") {
 552                                 //if there is a branch length then print it
 553                                 if (tree[node].getBranchLength() != -1) {
 554                                         out << ":" << tree[node].getBranchLength();
 555                                 }
 556                         }else if (mode == "boot") {
 557                                 //if there is a label then print it
 558                                 if (tree[node].getLabel() != -1) {
 559                                         out << tree[node].getLabel();
 560                                 }
 561                         }
 562                 }else { //you are a leaf
 563                         out << tree[node].getGroup();
 564                         if (mode == "branch") {
 565                                 //if there is a branch length then print it
 566                                 if (tree[node].getBranchLength() != -1) {
 567                                         out << ":" << tree[node].getBranchLength();
 568                                 }
 569                         }else if (mode == "boot") {
 570                                 //if there is a label then print it
 571                                 if (tree[node].getLabel() != -1) {
 572                                         out << tree[node].getLabel();
 573                                 }
 574                         }
 575                 }
 576
 577         }
 578         catch(exception& e) {
 579                 cout << "Standard Error: " << e.what() << " has occurred in the Tree class Function printBranch. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 580                 exit(1);
 581         }
 582         catch(...) {
 583                 cout << "An unknown error has occurred in the Tree class function printBranch. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 584                 exit(1);
 585         }
 586 }
 587
 588 /*****************************************************************/
 589
 590 void Tree::printTree() {
 591
 592         for(int i=0;i<numNodes;i++){
 593                 cout << i << '\t';
 594                 tree[i].printNode();
 595         }
 596
 597 }
 598
 599 /*****************************************************************/
 600
 601 void Tree::parseTreeFile() {
 602
 603         //only takes names from the first tree and assumes that all trees use the same names.
 604         try {
 605                 string filename = globaldata->getTreeFile();
 606                 ifstream filehandle;
 607                 openInputFile(filename, filehandle);
 608                 int c, comment;
 609                 comment = 0;
 610
 611                 //ifyou are not a nexus file
 612                 if((c = filehandle.peek()) != '#') {
 613                         while((c = filehandle.peek()) != ';') {
 614                                 while ((c = filehandle.peek()) != ';') {
 615                                         // get past comments
 616                                         if(c == '[') {
 617                                                 comment = 1;
 618                                         }
 619                                         if(c == ']'){
 620                                                 comment = 0;
 621                                         }
 622                                         if((c == '(') && (comment != 1)){ break; }
 623                                         filehandle.get();
 624                                 }
 625
 626                                 readTreeString(filehandle);
 627                         }
 628                 //ifyou are a nexus file
 629                 }else if((c = filehandle.peek()) == '#') {
 630                         string holder = "";
 631
 632                         // get past comments
 633                         while(holder != "translate" && holder != "Translate"){
 634                                 if(holder == "[" || holder == "[!"){
 635                                         comment = 1;
 636                                 }
 637                                 if(holder == "]"){
 638                                         comment = 0;
 639                                 }
 640                                 filehandle >> holder;
 641
 642                                 //ifthere is no translate then you must read tree string otherwise use translate to get names
 643                                 if(holder == "tree" && comment != 1){
 644                                         //pass over the "tree rep.6878900 = "
 645                                         while (((c = filehandle.get()) != '(') && ((c = filehandle.peek()) != EOF)) {;}
 646
 647                                         if(c == EOF) { break; }
 648                                         filehandle.putback(c);  //put back first ( of tree.
 649                                         readTreeString(filehandle);
 650                                         break;
 651                                 }
 652                         }
 653
 654                         //use nexus translation rather than parsing tree to save time
 655                         if((holder == "translate") || (holder == "Translate")) {
 656
 657                                 string number, name, h;
 658                                 h = ""; // so it enters the loop the first time
 659                                 while((h != ";") && (number != ";")) {
 660                                         filehandle >> number;
 661                                         filehandle >> name;
 662
 663                                         //c = , until done with translation then c = ;
 664                                         h = name.substr(name.length()-1, name.length());
 665                                         name.erase(name.end()-1);  //erase the comma
 666                                         globaldata->Treenames.push_back(number);
 667                                 }
 668                                 if(number == ";") { globaldata->Treenames.pop_back(); }  //in case ';' from translation is on next line instead of next to last name
 669                         }
 670                 }
 671                 filehandle.close();
 672         }
 673         catch(exception& e) {
 674                 cout << "Standard Error: " << e.what() << " has occurred in the Tree class Function parseTreeFile. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 675                 exit(1);
 676         }
 677         catch(...) {
 678                 cout << "An unknown error has occurred in the Tree class function parseTreeFile. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 679                 exit(1);
 680         }
 681 }
 682 /*******************************************************/
 683
 684 /*******************************************************/
 685 void Tree::readTreeString(ifstream& filehandle) {
 686         try {
 687                 int c;
 688                 string name; //k
 689
 690                 while((c = filehandle.peek()) != ';') {
 691                                 //ifyou are a name
 692                         if((c != '(') && (c != ')') && (c != ',') && (c != ':') && (c != '\n') && (c != '\t') && (c != 32)) { //32 is space
 693                                 name = "";
 694                                 c = filehandle.get();
 695         //              k = c;
 696 //cout << k << endl;
 697                                 while ((c != '(') && (c != ')') && (c != ',') && (c != ':') && (c != '\n') && (c != 32) && (c != '\t')) {
 698                                         name += c;
 699                                         c = filehandle.get();
 700                 //      k = c;
 701 //cout << " in name while " << k << endl;
 702                                 }
 703
 704 //cout << "name = " << name << endl;
 705                                 globaldata->Treenames.push_back(name);
 706                                 filehandle.putback(c);
 707 //k = c;
 708 //cout << " after putback" <<  k << endl;
 709                         }
 710
 711                         if(c  == ':') { //read until you reach the end of the branch length
 712                                 while ((c != '(') && (c != ')') && (c != ',') && (c != ';') && (c != '\n') && (c != '\t') && (c != 32)) {
 713                                         c = filehandle.get();
 714                                 //      k = c;
 715         //cout << " in branch while " << k << endl;
 716                                 }
 717                                 filehandle.putback(c);
 718                         }
 719                         c = filehandle.get();
 720                         if(c == ';') { break; }
 721                 //      k = c;
 722 //cout << k << endl;
 723
 724                 }
 725         }
 726         catch(exception& e) {
 727                 cout << "Standard Error: " << e.what() << " has occurred in the Tree class Function parseTreeFile. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 728                 exit(1);
 729         }
 730         catch(...) {
 731                 cout << "An unknown error has occurred in the Tree class function parseTreeFile. Please contact Pat Schloss at pschloss@microbio.umass.edu." << "\n";
 732                 exit(1);
 733         }
 734 }
 735
 736 /*******************************************************/
 737
 738 /*******************************************************/
 739