bpp-phyl  2.1.0
 All Classes Namespaces Files Functions Variables Friends Pages
TreeTemplateTools.h
Go to the documentation of this file.
1 //
2 // File: TreeTemplateTools.h
3 // Created by: Julien Dutheil
4 // Created on: Fri Oct 13 13:00 2006
5 // From file TreeTools.h
6 // Created on: Wed Aug 6 13:45:28 2003
7 //
8 
9 /*
10 Copyright or © or Copr. Bio++ Development Team, (November 16, 2004)
11 
12 This software is a computer program whose purpose is to provide classes
13 for phylogenetic data analysis.
14 
15 This software is governed by the CeCILL license under French law and
16 abiding by the rules of distribution of free software. You can use,
17 modify and/ or redistribute the software under the terms of the CeCILL
18 license as circulated by CEA, CNRS and INRIA at the following URL
19 "http://www.cecill.info".
20 
21 As a counterpart to the access to the source code and rights to copy,
22 modify and redistribute granted by the license, users are provided only
23 with a limited warranty and the software's author, the holder of the
24 economic rights, and the successive licensors have only limited
25 liability.
26 
27 In this respect, the user's attention is drawn to the risks associated
28 with loading, using, modifying and/or developing or reproducing the
29 software by the user in light of its specific status of free software,
30 that may mean that it is complicated to manipulate, and that also
31 therefore means that it is reserved for developers and experienced
32 professionals having in-depth computer knowledge. Users are therefore
33 encouraged to load and test the software's suitability as regards their
34 requirements in conditions enabling the security of their systems and/or
35 data to be ensured and, more generally, to use and operate it in the
36 same conditions as regards security.
37 
38 The fact that you are presently reading this means that you have had
39 knowledge of the CeCILL license and that you accept its terms.
40 */
41 
42 #ifndef _TREETEMPLATETOOLS_H_
43 #define _TREETEMPLATETOOLS_H_
44 
45 #include "TreeTools.h"
47 
48 //From the STL:
49 #include <string>
50 #include <vector>
51 
52 namespace bpp
53 {
54 
55 template<class N> class TreeTemplate;
56 
57 
64 {
65  public:
67  virtual ~TreeTemplateTools() {}
68 
69  public:
70 
83  template<class N>
84  static std::vector<N*> getLeaves(N& node)
85  {
86  std::vector<N*> leaves;
87  getLeaves<N>(node, leaves);
88  return leaves;
89  }
90 
97  template<class N>
98  static void getLeaves(N & node, std::vector<N *> & leaves)
99  {
100  if(node.isLeaf())
101  {
102  leaves.push_back(& node);
103  }
104  for(size_t i = 0; i < node.getNumberOfSons(); i++)
105  {
106  getLeaves<N>(* node.getSon(i), leaves);
107  }
108  }
109 
116  static std::vector<int> getLeavesId(const Node& node)
117  {
118  std::vector<int> ids;
119  getLeavesId(node, ids);
120  return ids;
121  }
122 
129  static void getLeavesId(const Node& node, std::vector<int>& ids)
130  {
131  if(node.isLeaf()) {
132  ids.push_back(node.getId());
133  }
134  for(size_t i = 0; i < node.getNumberOfSons(); i++) {
135  getLeavesId(* node.getSon(i), ids);
136  }
137  }
138 
145  static std::vector<int> getAncestorsId(const Node& node)
146  {
147  std::vector<int> ids;
148  const Node* n = &node;
149  while (n->hasFather()) {
150  n = n->getFather();
151  ids.push_back(n->getId());
152  }
153  return ids;
154  }
155 
164  static int getLeafId(const Node& node, const std::string& name) throw (NodeNotFoundException)
165  {
166  int* id = 0;
167  searchLeaf(node, name, id);
168  if (id == 0) throw NodeNotFoundException("TreeTemplateTools::getLeafId().", name);
169  else
170  {
171  int i = *id;
172  delete id;
173  return i;
174  }
175  }
176 
185  static void searchLeaf(const Node& node, const std::string& name, int*& id) throw (NodeNotFoundException)
186  {
187  if (node.isLeaf())
188  {
189  if (node.getName() == name)
190  {
191  id = new int(node.getId());
192  return;
193  }
194  }
195  for (size_t i = 0; i < node.getNumberOfSons(); i++)
196  {
197  searchLeaf(* node.getSon(i), name, id);
198  }
199  }
200 
208  template<class N>
209  static void dropLeaf(TreeTemplate<N>& tree, const std::string& leafName) throw (NodeNotFoundException, Exception)
210  {
211  N* leaf = tree.getNode(leafName);
212  if (!leaf->hasFather())
213  throw Exception("TreeTemplateTools::dropLeaf(). Leaf is the only node in the tree, can't remove it.");
214  N* parent = leaf->getFather();
215  if (parent->getNumberOfSons() > 2)
216  {
217  //The easy case:
218  parent->removeSon(leaf);
219  delete leaf;
220  }
221  else if (parent->getNumberOfSons() == 2)
222  {
223  //We have to delete the parent node as well:
224  N* brother = parent->getSon(0);
225  if (brother == leaf) brother = parent->getSon(1);
226  if (!parent->hasFather())
227  {
228  //The brother becomes the root:
229  if (leaf->hasDistanceToFather() && brother->hasDistanceToFather())
230  {
231  brother->setDistanceToFather(brother->getDistanceToFather() + leaf->getDistanceToFather());
232  }
233  brother->removeFather();
234  tree.setRootNode(brother);
235  delete parent;
236  delete leaf;
237  }
238  else
239  {
240  N* gParent = parent->getFather();
241  if (brother->hasDistanceToFather() && parent->hasDistanceToFather())
242  {
243  brother->setDistanceToFather(brother->getDistanceToFather() + parent->getDistanceToFather());
244  }
245  size_t pos = gParent->getSonPosition(parent);
246  gParent->setSon(pos, brother);
247  delete parent;
248  delete leaf;
249  }
250  }
251  else
252  {
253  //Dunno what to do in that case :(
254  throw Exception("TreeTemplateTools::dropLeaf. Parent node as only one child, I don't know what to do in that case :(");
255  }
256  }
257 
265  template<class N>
266  static void dropSubtree(TreeTemplate<N>& tree, Node* subtree) throw (Exception)
267  {
268  if (!subtree->hasFather())
269  throw Exception("TreeTemplateTools::dropSubtree(). Trying to remove the full tree!");
270  N* parent = subtree->getFather();
271  if (parent->getNumberOfSons() > 2)
272  {
273  //The easy case:
274  parent->removeSon(subtree);
275  deleteSubtree(subtree);
276  }
277  else if (parent->getNumberOfSons() == 2)
278  {
279  //We have to delete the parent node as well:
280  N* brother = parent->getSon(0);
281  if (brother == subtree) brother = parent->getSon(1);
282  if (!parent->hasFather())
283  {
284  //The brother becomes the root:
285  if (subtree->hasDistanceToFather() && brother->hasDistanceToFather())
286  {
287  brother->setDistanceToFather(brother->getDistanceToFather() + subtree->getDistanceToFather());
288  }
289  tree.setRootNode(brother);
290  delete parent;
291  deleteSubtree(subtree);
292  }
293  else
294  {
295  N* gParent = parent->getFather();
296  if (brother->hasDistanceToFather() && parent->hasDistanceToFather())
297  {
298  brother->setDistanceToFather(brother->getDistanceToFather() + parent->getDistanceToFather());
299  }
300  size_t pos = gParent->getSonPosition(parent);
301  gParent->setSon(pos, brother);
302  delete parent;
303  deleteSubtree(subtree);
304  }
305  }
306  else
307  {
308  //Dunno what to do in that case :(
309  throw Exception("TreeTemplateTools::dropSubtree. Parent node as only one child, I don't know what to do in that case :(");
310  }
311  }
312 
320  template<class N>
321  static void sampleSubtree(TreeTemplate<N>& tree, const std::vector<std::string>& leaves, size_t size)
322  {
323  std::vector<std::string> names = leaves;
324  for (size_t n = names.size(); n > size; --n) {
326  dropLeaf(tree, names[i]);
327  names.erase(names.begin() + i);
328  }
329  }
330 
337  template<class N>
338  static std::vector<N*> getNodes(N& node)
339  {
340  std::vector<N *> nodes;
341  getNodes<N>(node, nodes);
342  return nodes;
343  }
344 
351  template<class N>
352  static void getNodes(N & node, std::vector<N*> & nodes)
353  {
354  for(size_t i = 0; i < node.getNumberOfSons(); i++)
355  {
356  getNodes<N>(*node.getSon(i), nodes);
357  }
358  nodes.push_back(& node);
359  }
360 
367  static std::vector<int> getNodesId(const Node& node)
368  {
369  std::vector<int> ids;
370  getNodesId(node, ids);
371  return ids;
372  }
373 
380  static std::vector<int> getBranchesId(const Node& node)
381  {
382  std::vector<int> ids;
383  getBranchesId(node, ids);
384  return ids;
385  }
386 
393  static void getNodesId(const Node& node, std::vector<int>& ids)
394  {
395  for (size_t i = 0; i < node.getNumberOfSons(); i++)
396  {
397  getNodesId(*node.getSon(i), ids);
398  }
399  ids.push_back(node.getId());
400  }
401 
408  static void getBranchesId(const Node& node, std::vector<int>& ids)
409  {
410  for (size_t i = 0; i < node.getNumberOfSons(); i++)
411  {
412  getNodesId(*node.getSon(i), ids);
413  }
414  }
415 
422  template<class N>
423  static std::vector<N*> getInnerNodes(N& node)
424  {
425  std::vector<N *> nodes;
426  getInnerNodes<N>(node, nodes);
427  return nodes;
428  }
429 
438  template<class N>
439  static void getInnerNodes(N& node, std::vector<N*>& nodes)
440  {
441  for(size_t i = 0; i < node.getNumberOfSons(); i++)
442  {
443  getInnerNodes<N>(* node.getSon(i), nodes);
444  }
445  if (!node.isLeaf())
446  nodes.push_back(&node); //Do not add leaves!
447  }
448 
457  static std::vector<int> getInnerNodesId(const Node& node)
458  {
459  std::vector<int> ids;
460  getInnerNodesId(node, ids);
461  return ids;
462  }
463 
470  static void getInnerNodesId(const Node& node, std::vector<int> & ids)
471  {
472  for (size_t i = 0; i < node.getNumberOfSons(); i++)
473  {
474  getInnerNodesId(* node.getSon(i), ids);
475  }
476  if (!node.isLeaf())
477  ids.push_back(node.getId()); //Do not add leaves!
478  }
479 
485  template<class N>
486  static std::vector<N*> searchNodeWithId(N& node, int id)
487  {
488  std::vector<N*> nodes;
489  searchNodeWithId<N>(node, id, nodes);
490  return nodes;
491  }
492 
498  template<class N>
499  static void searchNodeWithId(N& node, int id, std::vector<N*>& nodes)
500  {
501  for (size_t i = 0; i < node.getNumberOfSons(); ++i)
502  {
503  searchNodeWithId<N>(*node.getSon(i), id, nodes);
504  }
505  if (node.getId() == id) nodes.push_back(&node);
506  }
507 
513  static Node* searchFirstNodeWithId(Node& node, int id)
514  {
515  if (node.getId() == id)
516  return &node;
517  else {
518  for (size_t i = 0; i < node.getNumberOfSons(); ++i)
519  {
520  Node* result = searchFirstNodeWithId(*node.getSon(i), id);
521  if (result)
522  return result;
523  }
524  }
525  return 0;
526  }
527 
533  static const Node* searchFirstNodeWithId(const Node& node, int id)
534  {
535  if (node.getId() == id)
536  return &node;
537  else {
538  for (size_t i = 0; i < node.getNumberOfSons(); ++i)
539  {
540  const Node* result = searchFirstNodeWithId(*node.getSon(i), id);
541  if (result)
542  return result;
543  }
544  }
545  return 0;
546  }
547 
553  template<class N>
554  static bool hasNodeWithId(const N& node, int id)
555  {
556  if (node.getId() == id) return true;
557  else
558  {
559  for(size_t i = 0; i < node.getNumberOfSons(); i++)
560  {
561  if(hasNodeWithId(*node.getSon(i), id)) return true;
562  }
563  return false;
564  }
565  }
566 
572  template<class N>
573  static std::vector<N*> searchNodeWithName(N& node, const std::string& name)
574  {
575  std::vector<N*> nodes;
576  searchNodeWithId<N>(node, name, nodes);
577  return nodes;
578  }
579 
585  template<class N>
586  static void searchNodeWithName(N& node, const std::string& name, std::vector<N*> & nodes)
587  {
588  for(size_t i = 0; i < node.getNumberOfSons(); i++)
589  {
590  searchNodeWithName<N>(*node.getSon(i), name, nodes);
591  }
592  if(node.hasName() && node.getName() == name) nodes.push_back(&node);
593  }
594 
600  template<class N>
601  static bool hasNodeWithName(const N& node, const std::string& name)
602  {
603  if(node.hasName() & node.getName() == name) return true;
604  else
605  {
606  for(size_t i = 0; i < node.getNumberOfSons(); i++)
607  {
608  if(hasNodeWithName(*node.getSon(i), name)) return true;
609  }
610  return false;
611  }
612  }
613 
621  static bool isRoot(const Node& node) { return !node.hasFather(); }
622 
629  static unsigned int getNumberOfLeaves(const Node& node);
630 
637  static unsigned int getNumberOfNodes(const Node& node);
638 
645  static std::vector<std::string> getLeavesNames(const Node& node);
646 
666  static unsigned int getDepth(const Node& node);
667 
688  static unsigned int getDepths(const Node& node, std::map<const Node*, unsigned int>& depths);
689 
701  static double getHeight(const Node& node);
702 
714  static double getHeights(const Node& node, std::map<const Node*, double>& heights);
715 
723  static bool isMultifurcating(const Node& node);
724 
736  static bool haveSameOrderedTopology(const Node& n1, const Node& n2);
737 
738  static std::vector<Node*> getPathBetweenAnyTwoNodes(Node& node1, Node& node2, bool includeAncestor = true);
739 
740  static std::vector<const Node*> getPathBetweenAnyTwoNodes(const Node & node1, const Node & node2, bool includeAncestor = true);
741 
751  template<class N>
752  static N* cloneSubtree(const Node& node)
753  {
754  //First we copy this node using default copy constuctor:
755  N* clone = new N(node);
756  //We remove the link toward the father:
757  //clone->removeFather();
758 
759  //Now we perform a hard copy:
760  for (int i = 0; i < static_cast<int>(node.getNumberOfSons()); i++)
761  {
762  clone->addSon(cloneSubtree<N>(*node[i]));
763  }
764  return clone;
765  }
766 
772  template<class N>
773  static void deleteSubtree(N* node)
774  {
775  for (size_t i = 0; i < node->getNumberOfSons(); ++i)
776  {
777  N* son = node->getSon(i);
778  deleteSubtree(son);
779  delete son;
780  }
781  }
782 
783 
784  template<class N>
785  static N* cloneSubtree(const Tree& tree, int nodeId)
786  {
787  //First we copy this node using default copy constuctor:
788  N* clone = tree.hasNodeName(nodeId) ? new N(nodeId, tree.getNodeName(nodeId)) : new N(nodeId);
789  //Then we set the length:
790  if (tree.hasDistanceToFather(nodeId))
791  clone->setDistanceToFather(tree.getDistanceToFather(nodeId));
792  //Now we copy all sons:
793  std::vector<int> sonsId = tree.getSonsId(nodeId);
794  for (size_t i = 0; i < sonsId.size(); i++)
795  {
796  clone->addSon(cloneSubtree<N>(tree, sonsId[i]));
797  }
798  //Must copy all properties too:
799  std::vector<std::string> names;
800  names = tree.getNodePropertyNames(nodeId);
801  for (size_t i = 0; i < names.size(); i++)
802  {
803  clone->setNodeProperty(names[i], *tree.getNodeProperty(nodeId, names[i]));
804  }
805  names = tree.getBranchPropertyNames(nodeId);
806  for (size_t i = 0; i < names.size(); i++)
807  {
808  clone->setBranchProperty(names[i], *tree.getBranchProperty(nodeId, names[i]));
809  }
810 
811  return clone;
812  }
828  static Vdouble getBranchLengths(const Node& node) throw (NodePException);
829 
839  static double getTotalLength(const Node& node, bool includeAncestor = true) throw (NodePException);
840 
847  static void setBranchLengths(Node& node, double brLen);
848 
854  static void deleteBranchLengths(Node& node);
855 
862  static void setVoidBranchLengths(Node& node, double brLen);
863 
873  static void scaleTree(Node& node, double factor) throw (NodePException);
874 
884  static double getDistanceBetweenAnyTwoNodes(const Node& node1, const Node& node2);
885 
904  static DistanceMatrix* getDistanceMatrix(const TreeTemplate<Node>& tree);
905 
906  private:
918  static void processDistsInSubtree_(const Node* node, DistanceMatrix& matrix, std::vector< std::pair<std::string, double> >& distsToNodeFather);
919 
920  public:
933  struct Element
934  {
935  public:
936  std::string content;
937  std::string length;
938  std::string bootstrap;
939  bool isLeaf;
940 
941  public:
942  Element() : content(), length(), bootstrap(), isLeaf(false) {}
943  };
944 
945  static Element getElement(const std::string& elt) throw (IOException);
946 
958  static Node* parenthesisToNode(const std::string& description, bool bootstrap=true, const std::string& propertyName=TreeTools::BOOTSTRAP, bool withId=false);
959 
972  static TreeTemplate<Node>* parenthesisToTree(const std::string& description, bool bootstrap = true, const std::string& propertyName = TreeTools::BOOTSTRAP, bool withId = false) throw (Exception);
973 
983  static std::string nodeToParenthesis(const Node & node, bool writeId = false);
984 
997  static std::string nodeToParenthesis(const Node & node, bool bootstrap, const std::string & propertyName);
998 
1008  static std::string treeToParenthesis(const TreeTemplate<Node>& tree, bool writeId = false);
1009 
1022  static std::string treeToParenthesis(const TreeTemplate<Node> & tree, bool bootstrap, const std::string& propertyName);
1023 
1039  static TreeTemplate<Node>* getRandomTree(std::vector<std::string>& leavesNames, bool rooted=true);
1040 
1054  static std::vector<const Node*> getRemainingNeighbors(const Node* node1, const Node* node2, const Node* node3);
1055 
1062  static void incrementAllIds(Node* node, int increment);
1063 
1076  static void getNodePropertyNames(const Node& node, std::vector<std::string>& propertyNames);
1077 
1088  static void getNodeProperties(const Node& node, const std::string& propertyName, std::map<int, const Clonable*>& properties);
1089 
1100  static void getNodeProperties(Node& node, const std::string& propertyName, std::map<int, Clonable*>& properties);
1101 
1108  static void getBranchPropertyNames(const Node& node, std::vector<std::string>& propertyNames);
1109 
1120  static void getBranchProperties(const Node& node, const std::string& propertyName, std::map<int, const Clonable*>& properties);
1121 
1132  static void getBranchProperties(Node& node, const std::string& propertyName, std::map<int, Clonable*>& properties);
1133 
1141  static void orderTree(Node& node, bool downward = true, bool orderLeaves = false) {
1142  orderTree_(node, downward, orderLeaves);
1143  }
1181  static void midRoot (bpp::TreeTemplate<bpp::Node>& tree, const std::string& criterion);
1182 
1188  static double getRadius (bpp::TreeTemplate<bpp::Node>& tree);
1189 
1190  private:
1192  size_t size;
1193  std::string firstLeaf;
1195  };
1196 
1197  static OrderTreeData_ orderTree_(Node& node, bool downward, bool orderLeaves);
1198 
1209  struct Moments_
1210  {
1211  double sum;
1212  double squaresSum;
1214  };
1215 
1223  static Moments_ getSubtreeMoments (const Node* node);
1224 
1239  static void getBestRootInSubtree (bpp::TreeTemplate<bpp::Node>& tree, const std::string& criterion, bpp::Node* node, std::pair<bpp::Node*, std::map<std::string, double> >& bestRoot);
1240 
1241 };
1242 
1243 } //end of namespace bpp.
1244 
1245 #endif //_TREETEMPLATETOOLS_H_
1246