X-Git-Url: https://git.donarmstrong.com/?p=mothur.git;a=blobdiff_plain;f=tree.cpp;h=745893471e065abee12e7752b91c71bb37c1a635;hp=52b7322cb1064546fd0f446f63fd61ef61d868fe;hb=d1c97b8c04bb75faca1e76ffad60b37a4d789d3d;hpb=5f44783e6d74a9c207492ac244210c915cadc272 diff --git a/tree.cpp b/tree.cpp index 52b7322..7458934 100644 --- a/tree.cpp +++ b/tree.cpp @@ -9,48 +9,230 @@ #include "tree.h" - /*****************************************************************/ -Tree::Tree() { +Tree::Tree(int num, CountTable* t) : ct(t) { try { - globaldata = GlobalData::getInstance(); + m = MothurOut::getInstance(); - if (globaldata->runParse == true) { parseTreeFile(); globaldata->runParse = false; } -//for(int i = 0; i < globaldata->Treenames.size(); i++) { cout << i << '\t' << globaldata->Treenames[i] << endl; } - numLeaves = globaldata->Treenames.size(); + numLeaves = num; numNodes = 2*numLeaves - 1; - + tree.resize(numNodes); + } + catch(exception& e) { + m->errorOut(e, "Tree", "Tree - numNodes"); + exit(1); + } +} +/*****************************************************************/ +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. + try { + m = MothurOut::getInstance(); + parseTreeFile(); m->runParse = false; + } + catch(exception& e) { + m->errorOut(e, "Tree", "Tree - just parse"); + exit(1); + } +} +/*****************************************************************/ +Tree::Tree(CountTable* t) : ct(t) { + try { + m = MothurOut::getInstance(); + + if (m->runParse == true) { parseTreeFile(); m->runParse = false; } + numLeaves = m->Treenames.size(); + numNodes = 2*numLeaves - 1; + + tree.resize(numNodes); + + //initialize groupNodeInfo + vector namesOfGroups = ct->getNamesOfGroups(); + for (int i = 0; i < namesOfGroups.size(); i++) { groupNodeInfo[namesOfGroups[i]].resize(0); } + //initialize tree with correct number of nodes, name and group info. for (int i = 0; i < numNodes; i++) { //initialize leaf nodes if (i <= (numLeaves-1)) { - tree[i].setName(globaldata->Treenames[i]); - tree[i].setGroup(globaldata->gTreemap->getGroup(globaldata->Treenames[i])); - //set pcount and pGroup for groupname to 1. - tree[i].pcount[globaldata->gTreemap->getGroup(globaldata->Treenames[i])] = 1; - tree[i].pGroups[globaldata->gTreemap->getGroup(globaldata->Treenames[i])] = 1; - //Treemap knows name, group and index to speed up search - globaldata->gTreemap->setIndex(globaldata->Treenames[i], i); - + tree[i].setName(m->Treenames[i]); + + //save group info + int maxPars = 1; + vector group; + vector counts = ct->getGroupCounts(m->Treenames[i]); + for (int j = 0; j < namesOfGroups.size(); j++) { + if (counts[j] != 0) { //you have seqs from this group + groupNodeInfo[namesOfGroups[j]].push_back(i); + group.push_back(namesOfGroups[j]); + tree[i].pGroups[namesOfGroups[j]] = counts[j]; + tree[i].pcount[namesOfGroups[j]] = counts[j]; + //keep highest group + if(counts[j] > maxPars){ maxPars = counts[j]; } + } + } + tree[i].setGroup(group); + setIndex(m->Treenames[i], i); + + if (maxPars > 1) { //then we have some more dominant groups + //erase all the groups that are less than maxPars because you found a more dominant group. + for(it=tree[i].pGroups.begin();it!=tree[i].pGroups.end();){ + if(it->second < maxPars){ + tree[i].pGroups.erase(it++); + }else { it++; } + } + //set one remaining groups to 1 + for(it=tree[i].pGroups.begin();it!=tree[i].pGroups.end();it++){ + tree[i].pGroups[it->first] = 1; + } + }//end if + //intialize non leaf nodes }else if (i > (numLeaves-1)) { tree[i].setName(""); - tree[i].setGroup(""); + vector tempGroups; + tree[i].setGroup(tempGroups); } } + } catch(exception& e) { - errorOut(e, "Tree", "Tree"); + m->errorOut(e, "Tree", "Tree"); exit(1); } } +/*****************************************************************/ +Tree::Tree(CountTable* t, vector< vector >& sims) : ct(t) { + try { + m = MothurOut::getInstance(); + + if (m->runParse == true) { parseTreeFile(); m->runParse = false; } + numLeaves = m->Treenames.size(); + numNodes = 2*numLeaves - 1; + + tree.resize(numNodes); + + //initialize groupNodeInfo + vector namesOfGroups = ct->getNamesOfGroups(); + for (int i = 0; i < namesOfGroups.size(); i++) { groupNodeInfo[namesOfGroups[i]].resize(0); } + + //initialize tree with correct number of nodes, name and group info. + for (int i = 0; i < numNodes; i++) { + //initialize leaf nodes + if (i <= (numLeaves-1)) { + tree[i].setName(m->Treenames[i]); + + //save group info + int maxPars = 1; + vector group; + vector counts = ct->getGroupCounts(m->Treenames[i]); + for (int j = 0; j < namesOfGroups.size(); j++) { + if (counts[j] != 0) { //you have seqs from this group + groupNodeInfo[namesOfGroups[j]].push_back(i); + group.push_back(namesOfGroups[j]); + tree[i].pGroups[namesOfGroups[j]] = counts[j]; + tree[i].pcount[namesOfGroups[j]] = counts[j]; + //keep highest group + if(counts[j] > maxPars){ maxPars = counts[j]; } + } + } + tree[i].setGroup(group); + setIndex(m->Treenames[i], i); + + if (maxPars > 1) { //then we have some more dominant groups + //erase all the groups that are less than maxPars because you found a more dominant group. + for(it=tree[i].pGroups.begin();it!=tree[i].pGroups.end();){ + if(it->second < maxPars){ + tree[i].pGroups.erase(it++); + }else { it++; } + } + //set one remaining groups to 1 + for(it=tree[i].pGroups.begin();it!=tree[i].pGroups.end();it++){ + tree[i].pGroups[it->first] = 1; + } + }//end if + + //intialize non leaf nodes + }else if (i > (numLeaves-1)) { + tree[i].setName(""); + vector tempGroups; + tree[i].setGroup(tempGroups); + } + } + + //build tree from matrix + //initialize indexes + map thisIndexes; //maps row in simMatrix to vector index in the tree + for (int g = 0; g < numLeaves; g++) { thisIndexes[g] = g; } + + //do merges and create tree structure by setting parents and children + //there are numGroups - 1 merges to do + for (int i = 0; i < (numLeaves - 1); i++) { + float largest = -1000.0; + + if (m->control_pressed) { break; } + + int row, column; + //find largest value in sims matrix by searching lower triangle + for (int j = 1; j < sims.size(); j++) { + for (int k = 0; k < j; k++) { + if (sims[j][k] > largest) { largest = sims[j][k]; row = j; column = k; } + } + } + + //set non-leaf node info and update leaves to know their parents + //non-leaf + tree[numLeaves + i].setChildren(thisIndexes[row], thisIndexes[column]); + + //parents + tree[thisIndexes[row]].setParent(numLeaves + i); + tree[thisIndexes[column]].setParent(numLeaves + i); + + //blength = distance / 2; + float blength = ((1.0 - largest) / 2); + + //branchlengths + tree[thisIndexes[row]].setBranchLength(blength - tree[thisIndexes[row]].getLengthToLeaves()); + tree[thisIndexes[column]].setBranchLength(blength - tree[thisIndexes[column]].getLengthToLeaves()); + + //set your length to leaves to your childs length plus branchlength + tree[numLeaves + i].setLengthToLeaves(tree[thisIndexes[row]].getLengthToLeaves() + tree[thisIndexes[row]].getBranchLength()); + + + //update index + thisIndexes[row] = numLeaves+i; + thisIndexes[column] = numLeaves+i; + + //remove highest value that caused the merge. + sims[row][column] = -1000.0; + sims[column][row] = -1000.0; + + //merge values in simsMatrix + for (int n = 0; n < sims.size(); n++) { + //row becomes merge of 2 groups + sims[row][n] = (sims[row][n] + sims[column][n]) / 2; + sims[n][row] = sims[row][n]; + //delete column + sims[column][n] = -1000.0; + sims[n][column] = -1000.0; + } + } + + //adjust tree to make sure root to tip length is .5 + int root = findRoot(); + tree[root].setBranchLength((0.5 - tree[root].getLengthToLeaves())); + + } + catch(exception& e) { + m->errorOut(e, "Tree", "Tree"); + exit(1); + } +} /*****************************************************************/ Tree::~Tree() {} -/*****************************************************************/ -void Tree::addNamesToCounts() { +/***************************************************************** +void Tree::addNamesToCounts(map nameMap) { try { //ex. seq1 seq2,seq3,se4 // seq1 = pasture @@ -66,22 +248,30 @@ void Tree::addNamesToCounts() { //go through each leaf and update its pcounts and pgroups + + //float A = clock(); + for (int i = 0; i < numLeaves; i++) { + string name = tree[i].getName(); - - map::iterator itNames = globaldata->names.find(name); - - if (itNames == globaldata->names.end()) { mothurOut(name + " is not in your name file, please correct."); mothurOutEndLine(); exit(1); } + + map::iterator itNames = nameMap.find(name); + + if (itNames == nameMap.end()) { m->mothurOut(name + " is not in your name file, please correct."); m->mothurOutEndLine(); exit(1); } else { vector dupNames; - splitAtComma(globaldata->names[name], dupNames); + m->splitAtComma(nameMap[name], dupNames); map::iterator itCounts; int maxPars = 1; + set groupsAddedForThisNode; for (int j = 0; j < dupNames.size(); j++) { - + + string group = tmap->getGroup(dupNames[j]); + if (dupNames[j] != name) {//you already added yourself in the constructor - string group = globaldata->gTreemap->getGroup(dupNames[j]); + + 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 //update pcounts itCounts = tree[i].pcount.find(group); @@ -95,7 +285,7 @@ void Tree::addNamesToCounts() { itCounts = tree[i].pGroups.find(group); if (itCounts == tree[i].pGroups.end()) { //new group, add it tree[i].pGroups[group] = 1; - }else { + }else{ tree[i].pGroups[group]++; } @@ -103,7 +293,7 @@ void Tree::addNamesToCounts() { if(tree[i].pGroups[group] > maxPars){ maxPars = tree[i].pGroups[group]; } - }//end if + }else { groupsAddedForThisNode.insert(group); } //add it so you don't add it to groupNodeInfo again }//end for if (maxPars > 1) { //then we have some more dominant groups @@ -119,26 +309,37 @@ void Tree::addNamesToCounts() { } }//end if - }//end else - }//end for + //update groups to reflect all the groups this node represents + vector nodeGroups; + map::iterator itGroups; + for (itGroups = tree[i].pcount.begin(); itGroups != tree[i].pcount.end(); itGroups++) { + nodeGroups.push_back(itGroups->first); + } + tree[i].setGroup(nodeGroups); + }//end else + }//end for + + //float B = clock(); + //cout << "addNamesToCounts\t" << (B - A) / CLOCKS_PER_SEC << endl; + } catch(exception& e) { - errorOut(e, "Tree", "addNamesToCounts"); + m->errorOut(e, "Tree", "addNamesToCounts"); exit(1); } -} +}*/ /*****************************************************************/ int Tree::getIndex(string searchName) { try { - //Treemap knows name, group and index to speed up search - // getIndex function will return the vector index or -1 if seq is not found. - int index = globaldata->gTreemap->getIndex(searchName); - return index; - + map::iterator itIndex = indexes.find(searchName); + if (itIndex != indexes.end()) { + return itIndex->second; + } + return -1; } catch(exception& e) { - errorOut(e, "Tree", "getIndex"); + m->errorOut(e, "Tree", "getIndex"); exit(1); } } @@ -146,29 +347,299 @@ int Tree::getIndex(string searchName) { void Tree::setIndex(string searchName, int index) { try { - //set index in treemap - globaldata->gTreemap->setIndex(searchName, index); + map::iterator itIndex = indexes.find(searchName); + if (itIndex == indexes.end()) { + indexes[searchName] = index; + } } catch(exception& e) { - errorOut(e, "Tree", "setIndex"); + m->errorOut(e, "Tree", "setIndex"); exit(1); } } /*****************************************************************/ -void Tree::assembleTree() { +int Tree::assembleTree() { + try { + //build the pGroups in non leaf nodes to be used in the parsimony calcs. + for (int i = numLeaves; i < numNodes; i++) { + if (m->control_pressed) { return 1; } + + tree[i].pGroups = (mergeGroups(i)); + tree[i].pcount = (mergeGcounts(i)); + } + + return 0; + } + catch(exception& e) { + m->errorOut(e, "Tree", "assembleTree"); + exit(1); + } +} +/*****************************************************************/ +//assumes leaf node names are in groups and no names file - used by indicator command +void Tree::getSubTree(Tree* Ctree, vector Groups) { try { - - //if user has given a names file we want to include that info in the pgroups and pcount info. - if(globaldata->names.size() != 0) { addNamesToCounts(); } + + //copy Tree since we are going to destroy it + Tree* copy = new Tree(ct); + copy->getCopy(Ctree); + copy->assembleTree(); + + //we want to select some of the leaf nodes to create the output tree + //go through the input Tree starting at parents of leaves + //initialize groupNodeInfo + vector namesOfGroups = ct->getNamesOfGroups(); + for (int i = 0; i < namesOfGroups.size(); i++) { groupNodeInfo[namesOfGroups[i]].resize(0); } - //build the pGroups in non leaf nodes to be used in the parsimony calcs. + //initialize tree with correct number of nodes, name and group info. + for (int i = 0; i < numNodes; i++) { + //initialize leaf nodes + if (i <= (numLeaves-1)) { + tree[i].setName(Groups[i]); + + //save group info + int maxPars = 1; + vector group; + vector counts = ct->getGroupCounts(Groups[i]); + for (int j = 0; j < namesOfGroups.size(); j++) { + if (counts[j] != 0) { //you have seqs from this group + groupNodeInfo[namesOfGroups[j]].push_back(i); + group.push_back(namesOfGroups[j]); + tree[i].pGroups[namesOfGroups[j]] = counts[j]; + tree[i].pcount[namesOfGroups[j]] = counts[j]; + //keep highest group + if(counts[j] > maxPars){ maxPars = counts[j]; } + } + } + tree[i].setGroup(group); + setIndex(Groups[i], i); + + if (maxPars > 1) { //then we have some more dominant groups + //erase all the groups that are less than maxPars because you found a more dominant group. + for(it=tree[i].pGroups.begin();it!=tree[i].pGroups.end();){ + if(it->second < maxPars){ + tree[i].pGroups.erase(it++); + }else { it++; } + } + //set one remaining groups to 1 + for(it=tree[i].pGroups.begin();it!=tree[i].pGroups.end();it++){ + tree[i].pGroups[it->first] = 1; + } + }//end if + + //intialize non leaf nodes + }else if (i > (numLeaves-1)) { + tree[i].setName(""); + vector tempGroups; + tree[i].setGroup(tempGroups); + } + } + + set removedLeaves; + for (int i = 0; i < copy->getNumLeaves(); i++) { + + if (removedLeaves.count(i) == 0) { + + //am I in the group + int parent = copy->tree[i].getParent(); + + if (parent != -1) { + + if (m->inUsersGroups(copy->tree[i].getName(), Groups)) { + //find my siblings name + int parentRC = copy->tree[parent].getRChild(); + int parentLC = copy->tree[parent].getLChild(); + + //if I am the right child, then my sib is the left child + int sibIndex = parentRC; + if (parentRC == i) { sibIndex = parentLC; } + + string sibsName = copy->tree[sibIndex].getName(); + + //if yes, is my sibling + if ((m->inUsersGroups(sibsName, Groups)) || (sibsName == "")) { + //we both are okay no trimming required + }else{ + //i am, my sib is not, so remove sib by setting my parent to my grandparent + int grandparent = copy->tree[parent].getParent(); + int grandparentLC = copy->tree[grandparent].getLChild(); + int grandparentRC = copy->tree[grandparent].getRChild(); + + //whichever of my granparents children was my parent now equals me + if (grandparentLC == parent) { grandparentLC = i; } + else { grandparentRC = i; } + + copy->tree[i].setParent(grandparent); + copy->tree[i].setBranchLength((copy->tree[i].getBranchLength()+copy->tree[parent].getBranchLength())); + if (grandparent != -1) { + copy->tree[grandparent].setChildren(grandparentLC, grandparentRC); + } + removedLeaves.insert(sibIndex); + } + }else{ + //find my siblings name + int parentRC = copy->tree[parent].getRChild(); + int parentLC = copy->tree[parent].getLChild(); + + //if I am the right child, then my sib is the left child + int sibIndex = parentRC; + if (parentRC == i) { sibIndex = parentLC; } + + string sibsName = copy->tree[sibIndex].getName(); + + //if no is my sibling + if ((m->inUsersGroups(sibsName, Groups)) || (sibsName == "")) { + //i am not, but my sib is + int grandparent = copy->tree[parent].getParent(); + int grandparentLC = copy->tree[grandparent].getLChild(); + int grandparentRC = copy->tree[grandparent].getRChild(); + + //whichever of my granparents children was my parent now equals my sib + if (grandparentLC == parent) { grandparentLC = sibIndex; } + else { grandparentRC = sibIndex; } + + copy->tree[sibIndex].setParent(grandparent); + copy->tree[sibIndex].setBranchLength((copy->tree[sibIndex].getBranchLength()+copy->tree[parent].getBranchLength())); + if (grandparent != -1) { + copy->tree[grandparent].setChildren(grandparentLC, grandparentRC); + } + removedLeaves.insert(i); + }else{ + //neither of us are, so we want to eliminate ourselves and our parent + //so set our parents sib to our great-grandparent + int parent = copy->tree[i].getParent(); + int grandparent = copy->tree[parent].getParent(); + int parentsSibIndex; + if (grandparent != -1) { + int greatgrandparent = copy->tree[grandparent].getParent(); + int greatgrandparentLC, greatgrandparentRC; + if (greatgrandparent != -1) { + greatgrandparentLC = copy->tree[greatgrandparent].getLChild(); + greatgrandparentRC = copy->tree[greatgrandparent].getRChild(); + } + + int grandparentLC = copy->tree[grandparent].getLChild(); + int grandparentRC = copy->tree[grandparent].getRChild(); + + parentsSibIndex = grandparentLC; + if (grandparentLC == parent) { parentsSibIndex = grandparentRC; } + + //whichever of my greatgrandparents children was my grandparent + if (greatgrandparentLC == grandparent) { greatgrandparentLC = parentsSibIndex; } + else { greatgrandparentRC = parentsSibIndex; } + + copy->tree[parentsSibIndex].setParent(greatgrandparent); + copy->tree[parentsSibIndex].setBranchLength((copy->tree[parentsSibIndex].getBranchLength()+copy->tree[grandparent].getBranchLength())); + if (greatgrandparent != -1) { + copy->tree[greatgrandparent].setChildren(greatgrandparentLC, greatgrandparentRC); + } + }else{ + copy->tree[parent].setParent(-1); + //cout << "issues with making subtree" << endl; + } + removedLeaves.insert(sibIndex); + removedLeaves.insert(i); + } + } + } + } + } + + int root = 0; + for (int i = 0; i < copy->getNumNodes(); i++) { + //you found the root + if (copy->tree[i].getParent() == -1) { root = i; break; } + } + + int nextSpot = numLeaves; + populateNewTree(copy->tree, root, nextSpot); + + delete copy; + } + catch(exception& e) { + m->errorOut(e, "Tree", "getSubTree"); + exit(1); + } +} +/***************************************************************** +//assumes nameMap contains unique names as key or is empty. +//assumes numLeaves defined in tree constructor equals size of seqsToInclude and seqsToInclude only contains unique seqs. +int Tree::getSubTree(Tree* copy, vector seqsToInclude, map nameMap) { + try { + + if (numLeaves != seqsToInclude.size()) { m->mothurOut("[ERROR]: numLeaves does not equal numUniques, cannot create subtree.\n"); m->control_pressed = true; return 0; } + + getSubTree(copy, seqsToInclude); + if (nameMap.size() != 0) { addNamesToCounts(nameMap); } + + //build the pGroups in non leaf nodes to be used in the parsimony calcs. for (int i = numLeaves; i < numNodes; i++) { + if (m->control_pressed) { return 1; } + tree[i].pGroups = (mergeGroups(i)); tree[i].pcount = (mergeGcounts(i)); } + + return 0; + } + catch(exception& e) { + m->errorOut(e, "Tree", "getSubTree"); + exit(1); + } +} +/*****************************************************************/ +int Tree::populateNewTree(vector& oldtree, int node, int& index) { + try { + + if (oldtree[node].getLChild() != -1) { + int rc = populateNewTree(oldtree, oldtree[node].getLChild(), index); + int lc = populateNewTree(oldtree, oldtree[node].getRChild(), index); + + tree[index].setChildren(lc, rc); + tree[rc].setParent(index); + tree[lc].setParent(index); + + tree[index].setBranchLength(oldtree[node].getBranchLength()); + tree[rc].setBranchLength(oldtree[oldtree[node].getLChild()].getBranchLength()); + tree[lc].setBranchLength(oldtree[oldtree[node].getRChild()].getBranchLength()); + + return (index++); + }else { //you are a leaf + int indexInNewTree = getIndex(oldtree[node].getName()); + return indexInNewTree; + } } catch(exception& e) { - errorOut(e, "Tree", "assembleTree"); + m->errorOut(e, "Tree", "populateNewTree"); + exit(1); + } +} +/*****************************************************************/ +void Tree::getCopy(Tree* copy, bool subsample) { + try { + + //for each node in the tree copy its info + for (int i = 0; i < numNodes; i++) { + //copy branch length + tree[i].setBranchLength(copy->tree[i].getBranchLength()); + + //copy parent + tree[i].setParent(copy->tree[i].getParent()); + + //copy children + tree[i].setChildren(copy->tree[i].getLChild(), copy->tree[i].getRChild()); + } + + //build the pGroups in non leaf nodes to be used in the parsimony calcs. + for (int i = numLeaves; i < numNodes; i++) { + if (m->control_pressed) { break; } + + tree[i].pGroups = (mergeGroups(i)); + tree[i].pcount = (mergeGcounts(i)); + } + } + catch(exception& e) { + m->errorOut(e, "Tree", "getCopy"); exit(1); } } @@ -194,8 +665,8 @@ void Tree::getCopy(Tree* copy) { tree[i].setChildren(copy->tree[i].getLChild(), copy->tree[i].getRChild()); //copy index in node and tmap + setIndex(copy->tree[i].getName(), getIndex(copy->tree[i].getName())); tree[i].setIndex(copy->tree[i].getIndex()); - setIndex(copy->tree[i].getName(), getIndex(copy->tree[i].getName())); //copy pGroups tree[i].pGroups = copy->tree[i].pGroups; @@ -204,9 +675,11 @@ void Tree::getCopy(Tree* copy) { tree[i].pcount = copy->tree[i].pcount; } + groupNodeInfo = copy->groupNodeInfo; + } catch(exception& e) { - errorOut(e, "Tree", "getCopy"); + m->errorOut(e, "Tree", "getCopy"); exit(1); } } @@ -259,7 +732,7 @@ map Tree::mergeGroups(int i) { return parsimony; } catch(exception& e) { - errorOut(e, "Tree", "mergeGroups"); + m->errorOut(e, "Tree", "mergeGroups"); exit(1); } } @@ -277,14 +750,14 @@ map Tree::mergeUserGroups(int i, vector g) { //loop through nodes groups removing the ones the user doesn't want for(it=tree[lc].pGroups.begin();it!=tree[lc].pGroups.end();){ - if (inUsersGroups(it->first, g) != true) { + if (m->inUsersGroups(it->first, g) != true) { tree[lc].pGroups.erase(it++); }else { it++; } } //loop through nodes groups removing the ones the user doesn't want for(it=tree[rc].pGroups.begin();it!=tree[rc].pGroups.end();){ - if (inUsersGroups(it->first, g) != true) { + if (m->inUsersGroups(it->first, g) != true) { tree[rc].pGroups.erase(it++); }else { it++; } } @@ -325,7 +798,7 @@ map Tree::mergeUserGroups(int i, vector g) { return parsimony; } catch(exception& e) { - errorOut(e, "Tree", "mergeUserGroups"); + m->errorOut(e, "Tree", "mergeUserGroups"); exit(1); } } @@ -348,14 +821,18 @@ map Tree::mergeGcounts(int position) { return sum; } catch(exception& e) { - errorOut(e, "Tree", "mergeGcounts"); + m->errorOut(e, "Tree", "mergeGcounts"); exit(1); } } /**************************************************************************************************/ - void Tree::randomLabels(vector g) { try { + + //initialize groupNodeInfo + for (int i = 0; i < (ct->getNamesOfGroups()).size(); i++) { + groupNodeInfo[(ct->getNamesOfGroups())[i]].resize(0); + } for(int i = 0; i < numLeaves; i++){ int z; @@ -366,8 +843,8 @@ void Tree::randomLabels(vector g) { //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. bool treez, treei; - treez = inUsersGroups(tree[z].getGroup(), g); - treei = inUsersGroups(tree[i].getGroup(), g); + treez = m->inUsersGroups(tree[z].getGroup(), g); + treei = m->inUsersGroups(tree[i].getGroup(), g); if ((treez == true) && (treei == true)) { //switches node i and node z's info. @@ -375,7 +852,7 @@ void Tree::randomLabels(vector g) { tree[z].pGroups = (tree[i].pGroups); tree[i].pGroups = (lib_hold); - string zgroup = tree[z].getGroup(); + vector zgroup = tree[z].getGroup(); tree[z].setGroup(tree[i].getGroup()); tree[i].setGroup(zgroup); @@ -387,40 +864,13 @@ void Tree::randomLabels(vector g) { tree[z].pcount = (tree[i].pcount); tree[i].pcount = (gcount_hold); } + + for (int k = 0; k < (tree[i].getGroup()).size(); k++) { groupNodeInfo[(tree[i].getGroup())[k]].push_back(i); } + for (int k = 0; k < (tree[z].getGroup()).size(); k++) { groupNodeInfo[(tree[z].getGroup())[k]].push_back(z); } } } catch(exception& e) { - errorOut(e, "Tree", "randomLabels"); - exit(1); - } -} -/**************************************************************************************************/ - -void Tree::randomLabels(string groupA, string groupB) { - try { - int numSeqsA = globaldata->gTreemap->seqsPerGroup[groupA]; - int numSeqsB = globaldata->gTreemap->seqsPerGroup[groupB]; - - vector randomGroups(numSeqsA+numSeqsB, groupA); - for(int i=numSeqsA;ierrorOut(e, "Tree", "randomLabels"); exit(1); } } @@ -436,7 +886,7 @@ void Tree::randomBlengths() { } } catch(exception& e) { - errorOut(e, "Tree", "randomBlengths"); + m->errorOut(e, "Tree", "randomBlengths"); exit(1); } } @@ -447,7 +897,8 @@ void Tree::assembleRandomUnifracTree(vector g) { } /*************************************************************************************************/ void Tree::assembleRandomUnifracTree(string groupA, string groupB) { - randomLabels(groupA, groupB); + vector temp; temp.push_back(groupA); temp.push_back(groupB); + randomLabels(temp); assembleTree(); } @@ -491,7 +942,7 @@ void Tree::randomTopology() { } } catch(exception& e) { - errorOut(e, "Tree", "randomTopology"); + m->errorOut(e, "Tree", "randomTopology"); exit(1); } } @@ -503,32 +954,43 @@ void Tree::print(ostream& out) { out << ";" << endl; } catch(exception& e) { - errorOut(e, "Tree", "print"); + m->errorOut(e, "Tree", "print"); exit(1); } } /*****************************************************************/ -void Tree::printForBoot(ostream& out) { +void Tree::print(ostream& out, map nameMap) { try { int root = findRoot(); - printBranch(root, out, "boot"); + printBranch(root, out, nameMap); out << ";" << endl; } catch(exception& e) { - errorOut(e, "Tree", "printForBoot"); + m->errorOut(e, "Tree", "print"); + exit(1); + } +} +/*****************************************************************/ +void Tree::print(ostream& out, string mode) { + try { + int root = findRoot(); + printBranch(root, out, mode); + out << ";" << endl; + } + catch(exception& e) { + m->errorOut(e, "Tree", "print"); exit(1); } } - /*****************************************************************/ // This prints out the tree in Newick form. void Tree::createNewickFile(string f) { try { int root = findRoot(); - //filename = getRootName(globaldata->getTreeFile()) + "newick"; + filename = f; - openOutputFile(filename, out); + m->openOutputFile(filename, out); printBranch(root, out, "branch"); @@ -537,7 +999,7 @@ void Tree::createNewickFile(string f) { out.close(); } catch(exception& e) { - errorOut(e, "Tree", "createNewickFile"); + m->errorOut(e, "Tree", "createNewickFile"); exit(1); } } @@ -556,16 +1018,87 @@ int Tree::findRoot() { return -1; } catch(exception& e) { - errorOut(e, "Tree", "findRoot"); + m->errorOut(e, "Tree", "findRoot"); exit(1); } } +/*****************************************************************/ +void Tree::printBranch(int node, ostream& out, map names) { +try { +// you are not a leaf + if (tree[node].getLChild() != -1) { + out << "("; + printBranch(tree[node].getLChild(), out, names); + out << ","; + printBranch(tree[node].getRChild(), out, names); + out << ")"; + + //if there is a branch length then print it + if (tree[node].getBranchLength() != -1) { + out << ":" << tree[node].getBranchLength(); + } + + }else { //you are a leaf + map::iterator itNames = names.find(tree[node].getName()); + + string outputString = ""; + if (itNames != names.end()) { + + vector dupNames; + m->splitAtComma((itNames->second), dupNames); + + if (dupNames.size() == 1) { + outputString += tree[node].getName(); + if (tree[node].getBranchLength() != -1) { + outputString += ":" + toString(tree[node].getBranchLength()); + } + }else { + outputString += "("; + + for (int u = 0; u < dupNames.size()-1; u++) { + outputString += dupNames[u]; + + if (tree[node].getBranchLength() != -1) { + outputString += ":" + toString(0.0); + } + outputString += ","; + } + + outputString += dupNames[dupNames.size()-1]; + if (tree[node].getBranchLength() != -1) { + outputString += ":" + toString(0.0); + } + + outputString += ")"; + if (tree[node].getBranchLength() != -1) { + outputString += ":" + toString(tree[node].getBranchLength()); + } + } + }else { + outputString = tree[node].getName(); + //if there is a branch length then print it + if (tree[node].getBranchLength() != -1) { + outputString += ":" + toString(tree[node].getBranchLength()); + } + + m->mothurOut("[ERROR]: " + tree[node].getName() + " is not in your namefile, please correct."); m->mothurOutEndLine(); + } + + out << outputString; + } + + } + catch(exception& e) { + m->errorOut(e, "Tree", "printBranch"); + exit(1); + } +} /*****************************************************************/ void Tree::printBranch(int node, ostream& out, string mode) { - try { - - // you are not a leaf + try { + + // you are not a leaf if (tree[node].getLChild() != -1) { out << "("; printBranch(tree[node].getLChild(), out, mode); @@ -582,29 +1115,111 @@ void Tree::printBranch(int node, ostream& out, string mode) { if (tree[node].getLabel() != -1) { out << tree[node].getLabel(); } + }else if (mode == "both") { + if (tree[node].getLabel() != -1) { + out << tree[node].getLabel(); + } + //if there is a branch length then print it + if (tree[node].getBranchLength() != -1) { + out << ":" << tree[node].getBranchLength(); + } } }else { //you are a leaf - out << tree[node].getGroup(); + vector leafGroup = ct->getGroups(tree[node].getName()); + if (mode == "branch") { + out << leafGroup[0]; //if there is a branch length then print it if (tree[node].getBranchLength() != -1) { out << ":" << tree[node].getBranchLength(); } }else if (mode == "boot") { + out << leafGroup[0]; //if there is a label then print it if (tree[node].getLabel() != -1) { out << tree[node].getLabel(); } + }else if (mode == "both") { + out << tree[node].getName(); + if (tree[node].getLabel() != -1) { + out << tree[node].getLabel(); + } + //if there is a branch length then print it + if (tree[node].getBranchLength() != -1) { + out << ":" << tree[node].getBranchLength(); + } } } } catch(exception& e) { - errorOut(e, "Tree", "printBranch"); + m->errorOut(e, "Tree", "printBranch"); + exit(1); + } +} +/*****************************************************************/ +void Tree::printBranch(int node, ostream& out, string mode, vector& theseNodes) { + try { + + // you are not a leaf + if (theseNodes[node].getLChild() != -1) { + out << "("; + printBranch(theseNodes[node].getLChild(), out, mode); + out << ","; + printBranch(theseNodes[node].getRChild(), out, mode); + out << ")"; + if (mode == "branch") { + //if there is a branch length then print it + if (theseNodes[node].getBranchLength() != -1) { + out << ":" << theseNodes[node].getBranchLength(); + } + }else if (mode == "boot") { + //if there is a label then print it + if (theseNodes[node].getLabel() != -1) { + out << theseNodes[node].getLabel(); + } + }else if (mode == "both") { + if (theseNodes[node].getLabel() != -1) { + out << theseNodes[node].getLabel(); + } + //if there is a branch length then print it + if (theseNodes[node].getBranchLength() != -1) { + out << ":" << theseNodes[node].getBranchLength(); + } + } + }else { //you are a leaf + vector leafGroup = ct->getGroups(theseNodes[node].getName()); + + if (mode == "branch") { + out << leafGroup[0]; + //if there is a branch length then print it + if (theseNodes[node].getBranchLength() != -1) { + out << ":" << theseNodes[node].getBranchLength(); + } + }else if (mode == "boot") { + out << leafGroup[0]; + //if there is a label then print it + if (theseNodes[node].getLabel() != -1) { + out << theseNodes[node].getLabel(); + } + }else if (mode == "both") { + out << theseNodes[node].getName(); + if (theseNodes[node].getLabel() != -1) { + out << theseNodes[node].getLabel(); + } + //if there is a branch length then print it + if (theseNodes[node].getBranchLength() != -1) { + out << ":" << theseNodes[node].getBranchLength(); + } + } + } + + } + catch(exception& e) { + m->errorOut(e, "Tree", "printBranch"); exit(1); } } - /*****************************************************************/ void Tree::printTree() { @@ -618,21 +1233,23 @@ void Tree::printTree() { /*****************************************************************/ //this code is a mess and should be rethought...-slw -void Tree::parseTreeFile() { +int Tree::parseTreeFile() { //only takes names from the first tree and assumes that all trees use the same names. try { - string filename = globaldata->getTreeFile(); + string filename = m->getTreeFile(); ifstream filehandle; - openInputFile(filename, filehandle); + m->openInputFile(filename, filehandle); int c, comment; comment = 0; int done = 1; //ifyou are not a nexus file if((c = filehandle.peek()) != '#') { - while((c = filehandle.peek()) != ';') { + while((c = filehandle.peek()) != ';') { + if (m->control_pressed) { filehandle.close(); return 0; } while ((c = filehandle.peek()) != ';') { + if (m->control_pressed) { filehandle.close(); return 0; } // get past comments if(c == '[') { comment = 1; @@ -652,7 +1269,8 @@ void Tree::parseTreeFile() { string holder = ""; // get past comments - while(holder != "translate" && holder != "Translate"){ + while(holder != "translate" && holder != "Translate"){ + if (m->control_pressed) { filehandle.close(); return 0; } if(holder == "[" || holder == "[!"){ comment = 1; } @@ -681,22 +1299,27 @@ void Tree::parseTreeFile() { string number, name, h; h = ""; // so it enters the loop the first time - while((h != ";") && (number != ";")) { + while((h != ";") && (number != ";")) { + if (m->control_pressed) { filehandle.close(); return 0; } filehandle >> number; filehandle >> name; //c = , until done with translation then c = ; h = name.substr(name.length()-1, name.length()); name.erase(name.end()-1); //erase the comma - globaldata->Treenames.push_back(number); + m->Treenames.push_back(number); } - if(number == ";") { globaldata->Treenames.pop_back(); } //in case ';' from translation is on next line instead of next to last name + if(number == ";") { m->Treenames.pop_back(); } //in case ';' from translation is on next line instead of next to last name } } filehandle.close(); + return 0; + //for (int i = 0; i < globaldata->Treenames.size(); i++) { +//cout << globaldata->Treenames[i] << endl; } +//cout << globaldata->Treenames.size() << endl; } catch(exception& e) { - errorOut(e, "Tree", "parseTreeFile"); + m->errorOut(e, "Tree", "parseTreeFile"); exit(1); } } @@ -708,7 +1331,8 @@ int Tree::readTreeString(ifstream& filehandle) { int c; string name; //, k - while((c = filehandle.peek()) != ';') { + while((c = filehandle.peek()) != ';') { + if (m->control_pressed) { return 0; } //k = c; //cout << " at beginning of while " << k << endl; if(c == ')') { @@ -725,7 +1349,7 @@ int Tree::readTreeString(ifstream& filehandle) { c = filehandle.get(); //k = c; //cout << k << endl; - while ((c != '(') && (c != ')') && (c != ',') && (c != ':') && (c != '\n') && (c != 32) && (c != '\t')) { + while ((c != '(') && (c != ')') && (c != ',') && (c != ':') && (c != '\n') && (c != 32) && (c != '\t')) { name += c; c = filehandle.get(); //k = c; @@ -733,7 +1357,9 @@ int Tree::readTreeString(ifstream& filehandle) { } //cout << "name = " << name << endl; - globaldata->Treenames.push_back(name); + if (name != "\r" ) { + m->Treenames.push_back(name); } //cout << m->Treenames.size() << '\t' << name << endl; + filehandle.putback(c); //k = c; //cout << " after putback" << k << endl; @@ -760,7 +1386,7 @@ int Tree::readTreeString(ifstream& filehandle) { return 0; } catch(exception& e) { - errorOut(e, "Tree", "readTreeString"); + m->errorOut(e, "Tree", "readTreeString"); exit(1); } }