← Back to branch summary

~ubuntu-branches/ubuntu/raring/libbpp-phyl/raring

« back to all changes in this revision

Viewing changes to src/Bpp/Phyl/TreeTemplate.h

  • Committer: Bazaar Package Importer
  • Author(s): Julien Dutheil
  • Date: 2011-06-09 11:00:00 UTC
  • Revision ID: james.westby@ubuntu.com-20110609110000-yvx78svv6w7xxgph
Tags: upstream-2.0.2
Import upstream version 2.0.2

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/Bpp/Phyl/TreeTemplate.h
 
1
//
 
2
// File: TreeTemplate.h
 
3
// Created by: Julien Dutheil
 
4
//             Celine Scornavacca
 
5
// Created on: Thu Mar 13 12:03:18 2003
 
6
//
 
7
 
 
8
/*
 
9
  Copyright or © or Copr. CNRS, (November 16, 2004)
 
10
 
 
11
  This software is a computer program whose purpose is to provide classes
 
12
  for phylogenetic data analysis.
 
13
 
 
14
  This software is governed by the CeCILL  license under French law and
 
15
  abiding by the rules of distribution of free software.  You can  use, 
 
16
  modify and/ or redistribute the software under the terms of the CeCILL
 
17
  license as circulated by CEA, CNRS and INRIA at the following URL
 
18
  "http://www.cecill.info". 
 
19
 
 
20
  As a counterpart to the access to the source code and  rights to copy,
 
21
  modify and redistribute granted by the license, users are provided only
 
22
  with a limited warranty  and the software's author,  the holder of the
 
23
  economic rights,  and the successive licensors  have only  limited
 
24
  liability. 
 
25
 
 
26
  In this respect, the user's attention is drawn to the risks associated
 
27
  with loading,  using,  modifying and/or developing or reproducing the
 
28
  software by the user in light of its specific status of free software,
 
29
  that may mean  that it is complicated to manipulate,  and  that  also
 
30
  therefore means  that it is reserved for developers  and  experienced
 
31
  professionals having in-depth computer knowledge. Users are therefore
 
32
  encouraged to load and test the software's suitability as regards their
 
33
  requirements in conditions enabling the security of their systems and/or 
 
34
  data to be ensured and,  more generally, to use and operate it in the 
 
35
  same conditions as regards security. 
 
36
 
 
37
  The fact that you are presently reading this means that you have had
 
38
  knowledge of the CeCILL license and that you accept its terms.
 
39
*/
 
40
 
 
41
#ifndef _TREETEMPLATE_H_
 
42
#define _TREETEMPLATE_H_
 
43
 
 
44
#include "TreeExceptions.h"
 
45
#include "TreeTemplateTools.h"
 
46
#include "Tree.h"
 
47
 
 
48
// From the STL:
 
49
#include <string>
 
50
#include <vector>
 
51
#include <map>
 
52
 
 
53
namespace bpp
 
54
{
 
55
 
 
56
  /**
 
57
   * @brief The phylogenetic tree class.
 
58
   * 
 
59
   * This class is part of the object implementation of phylogenetic trees. Tree are made
 
60
   * made of nodes, instances of the class Node.
 
61
   * 
 
62
   * Trees are oriented (rooted), i.e. each node has one <i>father node</i> and possibly
 
63
   * many <i>son nodes</i>. Leaves are nodes without descendant and root is defined has the without
 
64
   * father. Inner nodes will generally contain two descendants (the tree is then called
 
65
   * <i>bifurcating</i>), but mutlifurcating trees are also allowed with this kind of description.
 
66
   * In the rooted case, each inner node also defines a <i>subtree</i>.
 
67
   * This allows to work recursively on trees, which is very convenient in most cases.
 
68
   * To deal with non-rooted trees, we place an artificial root at a particular node:
 
69
   * hence the root node appears to be trifurcated. This is the way unrooted trees are
 
70
   * described in the parenthetic description, the so called Newick format.
 
71
   * 
 
72
   * To clone a tree from from another tree with a different template,
 
73
   * consider using the TreeTools::cloneSutree<N>() method:
 
74
   * @code
 
75
   * Tree * t = new Tree<Node>(...)
 
76
   * NodeTemplate<int> * newRoot = TreeTools::cloneSubtree< NodeTemplate<int> >(* (t -> getRootNode()))
 
77
   * Tree< NodeTemplate<int> > * tt = new Tree< NodeTemplate<int> >(* newRoot);
 
78
   * @endcode
 
79
   *
 
80
   * The getNextId() method sends a id value which is not used in the tree.
 
81
   * In the current implementation, it uses the TreeTools::getMPNUId() method.
 
82
   * This avoids to use duplicated ids, but is time consuming.
 
83
   * In most cases, it is of better efficiency if the user deal with the ids himself, by using the Node::setId() method.
 
84
   * The TreeTools::getMaxId() method may also prove useful in this respect.
 
85
   * The resetNodesId() method can also be used to re-initialize all ids.
 
86
   * 
 
87
   * @see Node
 
88
   * @see NodeTemplate
 
89
   * @see TreeTools
 
90
   */
 
91
  template<class N>
 
92
  class TreeTemplate:
 
93
    public Tree
 
94
  {
 
95
    /**
 
96
     * Fields:
 
97
     */
 
98
  private:
 
99
    N * root_;
 
100
    std::string name_;
 
101
 
 
102
  public: // Constructors and destructor:
 
103
                
 
104
    TreeTemplate(): root_(0), name_() {}
 
105
 
 
106
    TreeTemplate(const TreeTemplate<N>& t):
 
107
      root_(0), name_(t.name_)
 
108
    {
 
109
      //Perform a hard copy of the nodes:
 
110
      root_ = TreeTemplateTools::cloneSubtree<N>(*t.getRootNode());
 
111
    }
 
112
 
 
113
    TreeTemplate(const Tree& t):
 
114
      root_(0), name_(t.getName())
 
115
    {
 
116
      //Create new nodes from an existing tree:
 
117
      root_ = TreeTemplateTools::cloneSubtree<N>(t, t.getRootId());
 
118
    }
 
119
 
 
120
    TreeTemplate(N* root): root_(root), name_()
 
121
    {
 
122
      root_->removeFather(); //In case this is a subtree from somewhere else...
 
123
    }
 
124
 
 
125
    TreeTemplate<N> & operator=(const TreeTemplate<N>& t)
 
126
    {
 
127
      //Perform a hard copy of the nodes:
 
128
      if(root_) { destroySubtree_(root_); delete root_; }
 
129
      root_ = TreeTemplateTools::cloneSubtree<N>(* t.getRootNode());
 
130
      name_ = t.name_;
 
131
      return *this;
 
132
    }
 
133
 
 
134
    TreeTemplate<N>* cloneSubtree(int newRootId) const
 
135
    {
 
136
      N* newRoot = TreeTemplateTools::cloneSubtree<N>(*this, newRootId);
 
137
      return new TreeTemplate<N> (newRoot);
 
138
    }
 
139
 
 
140
    virtual ~TreeTemplate()
 
141
    {
 
142
      destroySubtree_(root_);
 
143
      delete root_;
 
144
    }
 
145
 
 
146
    TreeTemplate<N>* clone() const { return new TreeTemplate<N>(*this); }
 
147
                        
 
148
    /**
 
149
     * Methods:
 
150
     */
 
151
        
 
152
  public:
 
153
                
 
154
    std::string getName() const { return name_; }
 
155
        
 
156
    void setName(const std::string& name) { name_ = name; }
 
157
 
 
158
    int getRootId() const { return root_->getId(); }
 
159
 
 
160
    unsigned int getNumberOfLeaves() const { return TreeTemplateTools::getNumberOfLeaves(*root_); }
 
161
                
 
162
    unsigned int getNumberOfNodes() const { return TreeTemplateTools::getNumberOfNodes(*root_); }
 
163
                
 
164
    int getLeafId(const std::string& name) const throw (NodeNotFoundException) { return TreeTemplateTools::getLeafId(*root_, name); }
 
165
                
 
166
    std::vector<int> getLeavesId() const { return TreeTemplateTools::getLeavesId(*root_); }
 
167
 
 
168
    std::vector<int> getNodesId() const { return TreeTemplateTools::getNodesId(*root_); }
 
169
    
 
170
    std::vector<int> getInnerNodesId() const { return TreeTemplateTools::getInnerNodesId(*root_); }
 
171
                
 
172
    std::vector<int> getBranchesId() const { return TreeTemplateTools::getBranchesId(*root_); }
 
173
 
 
174
    std::vector<double> getBranchLengths() const { return TreeTemplateTools::getBranchLengths(*root_); }
 
175
 
 
176
    std::vector<std::string> getLeavesNames() const { return TreeTemplateTools::getLeavesNames(*const_cast<const N*>( root_)); }
 
177
 
 
178
    std::vector<int> getSonsId(int parentId) const throw (NodeNotFoundException)        { return getNode(parentId)->getSonsId(); }
 
179
 
 
180
    std::vector<int> getAncestorsId(int nodeId) const throw (NodeNotFoundException)     { return TreeTemplateTools::getAncestorsId(*getNode(nodeId));}
 
181
 
 
182
    int getFatherId(int parentId) const throw (NodeNotFoundException) { return getNode(parentId)->getFatherId(); }
 
183
 
 
184
    bool hasFather(int nodeId) const throw (NodeNotFoundException) { return getNode(nodeId)->hasFather(); }
 
185
        
 
186
    std::string getNodeName(int nodeId) const throw (NodeNotFoundException) { return getNode(nodeId)->getName(); }
 
187
 
 
188
    bool hasNodeName(int nodeId) const throw (NodeNotFoundException) { return getNode(nodeId)->hasName(); }
 
189
                
 
190
    void setNodeName(int nodeId, const std::string& name) throw (NodeNotFoundException) { getNode(nodeId)->setName(name); }
 
191
                
 
192
    void deleteNodeName(int nodeId) throw (NodeNotFoundException) { return getNode(nodeId)->deleteName(); }
 
193
 
 
194
    bool hasNode(int nodeId) const { return TreeTemplateTools::hasNodeWithId(*root_, nodeId); }
 
195
 
 
196
    bool isLeaf(int nodeId) const throw (NodeNotFoundException) { return getNode(nodeId)->isLeaf(); }
 
197
 
 
198
    bool isRoot(int nodeId) const throw (NodeNotFoundException) { return TreeTemplateTools::isRoot(*getNode(nodeId)); }
 
199
 
 
200
    double getDistanceToFather(int nodeId) const { return getNode(nodeId)->getDistanceToFather(); }
 
201
                
 
202
    void setDistanceToFather(int nodeId, double length) { getNode(nodeId)->setDistanceToFather(length); }
 
203
                
 
204
    void deleteDistanceToFather(int nodeId) { getNode(nodeId)->deleteDistanceToFather(); }
 
205
                
 
206
    bool hasDistanceToFather(int nodeId) const { return getNode(nodeId)->hasDistanceToFather(); }
 
207
 
 
208
    bool hasNodeProperty(int nodeId, const std::string& name) const throw (NodeNotFoundException) { return getNode(nodeId)->hasNodeProperty(name); }
 
209
        
 
210
    void setNodeProperty(int nodeId, const std::string& name, const Clonable & property) throw (NodeNotFoundException) { getNode(nodeId)->setNodeProperty(name, property); }
 
211
                                
 
212
    Clonable* getNodeProperty(int nodeId, const std::string& name) throw (NodeNotFoundException) { return getNode(nodeId)->getNodeProperty(name); }
 
213
                                
 
214
    const Clonable* getNodeProperty(int nodeId, const std::string& name) const throw (NodeNotFoundException) { return getNode(nodeId)->getNodeProperty(name); }
 
215
                                
 
216
    Clonable* removeNodeProperty(int nodeId, const std::string& name) throw (NodeNotFoundException) { return getNode(nodeId)->removeNodeProperty(name); }
 
217
                
 
218
    std::vector<std::string> getNodePropertyNames(int nodeId) const throw (NodeNotFoundException) { return getNode(nodeId)->getNodePropertyNames(); }
 
219
                
 
220
    bool hasBranchProperty(int nodeId, const std::string& name) const throw (NodeNotFoundException) { return getNode(nodeId)->hasBranchProperty(name); }
 
221
        
 
222
    void setBranchProperty(int nodeId, const std::string& name, const Clonable & property) throw (NodeNotFoundException) { getNode(nodeId)->setBranchProperty(name, property); }
 
223
                                
 
224
    Clonable* getBranchProperty(int nodeId, const std::string& name) throw (NodeNotFoundException) { return getNode(nodeId)->getBranchProperty(name); }
 
225
                                
 
226
    const Clonable* getBranchProperty(int nodeId, const std::string& name) const throw (NodeNotFoundException) { return getNode(nodeId)->getBranchProperty(name); }
 
227
                                
 
228
    Clonable* removeBranchProperty(int nodeId, const std::string& name) throw (NodeNotFoundException) { return getNode(nodeId)->removeBranchProperty(name); }
 
229
                
 
230
    std::vector<std::string> getBranchPropertyNames(int nodeId) const throw (NodeNotFoundException) { return getNode(nodeId)->getBranchPropertyNames(); }
 
231
                
 
232
    void rootAt(int nodeId) throw (NodeNotFoundException)       {       rootAt(getNode(nodeId)); }
 
233
                
 
234
    void newOutGroup(int nodeId) throw (NodeNotFoundException) {        newOutGroup(getNode(nodeId)); }
 
235
 
 
236
    bool isRooted() const { return root_->getNumberOfSons() == 2; }
 
237
                
 
238
    bool unroot() throw (UnrootedTreeException)
 
239
    {
 
240
      if(!isRooted()) throw UnrootedTreeException("Tree::unroot", this);
 
241
 
 
242
      if(root_->getNumberOfSons() == 2)
 
243
        {
 
244
          N* son1 = root_->getSon(0);
 
245
          N* son2 = root_->getSon(1);
 
246
          if(son1->isLeaf() && son2->isLeaf()) return false; // We can't unroot a single branch!
 
247
                                
 
248
          // We manage to have a subtree in position 0:
 
249
          if(son1->isLeaf())
 
250
            {
 
251
              root_->swap(0, 1);
 
252
              son1 = root_->getSon(0);
 
253
              son2 = root_->getSon(1);
 
254
            }
 
255
 
 
256
          // Take care of branch lengths:
 
257
          if(son1->hasDistanceToFather())
 
258
            {
 
259
              if(son2->hasDistanceToFather())
 
260
                {
 
261
                  // Both nodes have lengths, we sum them:
 
262
                  son2->setDistanceToFather(son1->getDistanceToFather() + son2->getDistanceToFather());
 
263
                }
 
264
              else
 
265
                {
 
266
                  // Only node 1 has length, we set it to node 2:
 
267
                  son2->setDistanceToFather(son1->getDistanceToFather());
 
268
                }
 
269
              son1->deleteDistanceToFather();
 
270
            } // Else node 2 may or may not have a branch length, we do not care!
 
271
 
 
272
          // Remove the root:
 
273
          root_->removeSons();
 
274
          son1->addSon(son2);
 
275
          delete root_;
 
276
          setRootNode(son1);
 
277
          return true;
 
278
        }
 
279
      else return false; // Tree is already unrooted.
 
280
    }
 
281
 
 
282
    void resetNodesId()
 
283
    {
 
284
      std::vector<N *> nodes = getNodes();
 
285
      for (unsigned int i = 0; i < nodes.size(); i++)
 
286
        {
 
287
          nodes[i]->setId(i);
 
288
        }
 
289
    }
 
290
                
 
291
    bool isMultifurcating() const
 
292
    {
 
293
      bool b = false;
 
294
      for(unsigned int i = 0; i < root_ -> getNumberOfSons(); i++)
 
295
        {
 
296
          b = b || TreeTemplateTools::isMultifurcating(* root_->getSon(i));
 
297
        }
 
298
      return b;
 
299
    }
 
300
 
 
301
    /**
 
302
     * @brief Tells if this tree has the same topology as the one given for comparison.
 
303
     *
 
304
     * This method compares recursively all subtrees. The comparison is performed only on the nodes names and the parental relationships.
 
305
     * Nodes ids are ignored, and so are branch lengths and any branch/node properties. The default is to ignore the ordering of the descendants,
 
306
     * that is (A,B),C) will be considered as having the same topology as (B,A),C). Multifurcations are permited.
 
307
     * If ordering is ignored, a copy of the two trees to be compared is performed and are ordered before comparison, making the whole comparison
 
308
     * slower and more memory greedy.
 
309
     *
 
310
     * @param tree The tree to be compared with.
 
311
     * @param ordered Should the ordering of the branching be taken into account?
 
312
     * @return True if the input tree has the same topology as this one.
 
313
     */
 
314
    template<class N2>
 
315
    bool hasSameTopologyAs(const TreeTemplate<N2>& tree, bool ordered = false) const
 
316
    {
 
317
      const TreeTemplate<N>* t1 = 0;
 
318
      const TreeTemplate<N2>* t2 = 0;
 
319
      if (ordered) {
 
320
        t1 = this;
 
321
        t2 = &tree;
 
322
      } else {
 
323
        TreeTemplate<N>* t1tmp = this->clone();
 
324
        TreeTemplate<N2>* t2tmp = tree.clone();
 
325
        TreeTemplateTools::orderTree(*t1tmp->getRootNode(), true, true);
 
326
        TreeTemplateTools::orderTree(*t2tmp->getRootNode(), true, true);
 
327
        t1 = t1tmp;
 
328
        t2 = t2tmp;
 
329
      }
 
330
      bool test = TreeTemplateTools::haveSameOrderedTopology(*t1->getRootNode(), *t2->getRootNode());
 
331
      if (!ordered) {
 
332
        delete t1;
 
333
        delete t2;
 
334
      }
 
335
      return test;
 
336
    }
 
337
                
 
338
    std::vector<double> getBranchLengths() throw (NodeException)
 
339
    {
 
340
      Vdouble brLen(1);
 
341
      for(unsigned int i = 0; i < root_->getNumberOfSons(); i++)
 
342
        {
 
343
          Vdouble sonBrLen = TreeTemplateTools::getBranchLengths(* root_->getSon(i));
 
344
          for(unsigned int j = 0; j < sonBrLen.size(); j++) brLen.push_back(sonBrLen[j]);
 
345
        }
 
346
      return brLen;
 
347
    }
 
348
 
 
349
    double getTotalLength() throw (NodeException)
 
350
    {
 
351
      return TreeTemplateTools::getTotalLength(*root_, false);
 
352
    }
 
353
 
 
354
    void setBranchLengths(double brLen)
 
355
    {
 
356
      for(unsigned int i = 0; i < root_->getNumberOfSons(); i++)
 
357
        {
 
358
          TreeTemplateTools::setBranchLengths(*root_->getSon(i), brLen);
 
359
        }
 
360
    }
 
361
                
 
362
    void setVoidBranchLengths(double brLen)
 
363
    {
 
364
      for(unsigned int i = 0; i < root_->getNumberOfSons(); i++)
 
365
        {
 
366
          TreeTemplateTools::setVoidBranchLengths(*root_->getSon(i), brLen);
 
367
        }
 
368
    }
 
369
        
 
370
    void scaleTree(double factor) throw (NodeException)
 
371
    {
 
372
      for(unsigned int i = 0; i < root_->getNumberOfSons(); i++)
 
373
        {
 
374
          TreeTemplateTools::scaleTree(*root_->getSon(i), factor);
 
375
        }
 
376
    }
 
377
 
 
378
    int getNextId()
 
379
    { 
 
380
      return TreeTools::getMPNUId(*this, root_->getId());
 
381
    }
 
382
 
 
383
    void swapNodes(int parentId, unsigned int i1, unsigned int i2) throw (NodeNotFoundException,IndexOutOfBoundsException)
 
384
    {
 
385
      std::vector<N*> nodes = TreeTemplateTools::searchNodeWithId<N>(*root_, parentId);
 
386
      if(nodes.size() == 0) throw NodeNotFoundException("TreeTemplate:swapNodes(): Node with id not found.", "" + parentId);
 
387
      for(unsigned int i = 0; i < nodes.size(); i++) nodes[i]->swap(i1, i2); 
 
388
    }
 
389
 
 
390
 
 
391
    /**
 
392
     * @name Specific methods
 
393
     *
 
394
     * @{
 
395
     */
 
396
    virtual void setRootNode(N* root) { root_ = root; }
 
397
        
 
398
    virtual N* getRootNode() { return root_; }
 
399
                
 
400
    virtual const N* getRootNode() const { return root_; }
 
401
                
 
402
    virtual std::vector<const N*> getLeaves() const { return TreeTemplateTools::getLeaves(* const_cast<const N *>(root_)); }
 
403
 
 
404
    virtual std::vector<N*> getLeaves() { return TreeTemplateTools::getLeaves(* root_); }
 
405
        
 
406
    virtual std::vector<const N*> getNodes() const { return TreeTemplateTools::getNodes(* const_cast<const N *>(root_)); }
 
407
 
 
408
    virtual std::vector<N*> getNodes() { return TreeTemplateTools::getNodes(* root_); }
 
409
                
 
410
    virtual std::vector<const N*> getInnerNodes() const { return TreeTemplateTools::getInnerNodes(* const_cast<const N *>(root_)); }
 
411
 
 
412
    virtual std::vector<N *> getInnerNodes() { return TreeTemplateTools::getInnerNodes(* root_); }
 
413
        
 
414
    virtual N* getNode(int id) throw (NodeNotFoundException, Exception)
 
415
    {
 
416
      std::vector<N*> nodes;
 
417
      TreeTemplateTools::searchNodeWithId<N>(*root_, id, nodes);
 
418
      if (nodes.size() > 1) throw Exception("TreeTemplate::getNode(): Non-unique id! (" + TextTools::toString(id) + ").");
 
419
      if (nodes.size() == 0) throw NodeNotFoundException("TreeTemplate::getNode(): Node with id not found.", TextTools::toString(id));
 
420
      return nodes[0];
 
421
    }
 
422
                
 
423
    virtual const N* getNode(int id) const throw (NodeNotFoundException, Exception)
 
424
    {
 
425
      std::vector<const N*> nodes;
 
426
      TreeTemplateTools::searchNodeWithId<const N>(*root_, id, nodes);
 
427
      if (nodes.size() > 1) throw Exception("TreeTemplate::getNode(): Non-unique id! (" + TextTools::toString(id) + ").");
 
428
      if (nodes.size() == 0) throw NodeNotFoundException("TreeTemplate::getNode(): Node with id not found.", TextTools::toString(id));
 
429
      return nodes[0];
 
430
    }
 
431
 
 
432
    virtual N* getNode(const std::string& name) throw (NodeNotFoundException, Exception)
 
433
    {   
 
434
      std::vector<N*> nodes;
 
435
      TreeTemplateTools::searchNodeWithName(*root_, name, nodes);
 
436
      if (nodes.size() > 1)  throw NodeNotFoundException("TreeTemplate::getNode(): Non-unique name.", "" + name);
 
437
      if (nodes.size() == 0) throw NodeNotFoundException("TreeTemplate::getNode(): Node with name not found.", "" + name);
 
438
      return nodes[0];
 
439
    }
 
440
 
 
441
    virtual const N* getNode(const std::string& name) const throw (NodeNotFoundException, Exception)
 
442
    {   
 
443
      std::vector<const N*> nodes;
 
444
      TreeTemplateTools::searchNodeWithName<const N>(*root_, name, nodes);
 
445
      if(nodes.size() > 1)  throw NodeNotFoundException("TreeTemplate::getNode(): Non-unique name.", "" + name);
 
446
      if(nodes.size() == 0) throw NodeNotFoundException("TreeTemplate::getNode(): Node with name not found.", "" + name);
 
447
      return nodes[0];
 
448
    }
 
449
 
 
450
    void rootAt(N* newRoot)
 
451
    {
 
452
      if (root_ == newRoot) return;
 
453
      if (isRooted()) unroot();
 
454
      std::vector<Node*> path = TreeTemplateTools::getPathBetweenAnyTwoNodes(*root_, *newRoot);
 
455
 
 
456
      for (unsigned int i = 0; i < path.size() - 1 ; i++)
 
457
        {
 
458
          //pathMatrix[i] -> _father = pathMatrix[i + 1];
 
459
          //pathMatrix[i] -> setDistanceToFather(pathMatrix[i + 1] -> getDistanceToFather());
 
460
          //typename vector<Node *>::iterator vec_iter;
 
461
          //vec_iter = remove(pathMatrix[i] -> _sons.begin(), pathMatrix[i] -> _sons.end(), pathMatrix[i + 1]);
 
462
          //pathMatrix[i] -> _sons.erase(vec_iter, pathMatrix[i] -> _sons.end()); // pg 1170, primer.   
 
463
          //pathMatrix[i+1] -> _sons.push_back(pathMatrix[i + 1] -> getFather());
 
464
          //pathMatrix[i+1] -> _father = 0;
 
465
          path[i]->removeSon(path[i+1]);
 
466
          if(path[i+1]->hasDistanceToFather()) path[i]->setDistanceToFather(path[i+1]->getDistanceToFather());
 
467
          else path[i]->deleteDistanceToFather();
 
468
          path[i+1]->addSon(path[i]);
 
469
 
 
470
          std::vector<std::string> names = path[i+1]->getBranchPropertyNames();
 
471
          for(unsigned int j = 0; j < names.size(); j++)
 
472
            {
 
473
              path[i]->setBranchProperty(names[j], *path[i+1]->getBranchProperty(names[j]));
 
474
            }
 
475
          path[i+1]->deleteBranchProperties();
 
476
        }
 
477
      newRoot->deleteDistanceToFather();
 
478
      newRoot->deleteBranchProperties();
 
479
      root_ = newRoot;
 
480
    }
 
481
 
 
482
    void newOutGroup(N* outGroup)
 
483
    {
 
484
      if(root_ == outGroup) return;
 
485
      int rootId;
 
486
      if(isRooted())
 
487
        {
 
488
          for(unsigned int i = 0; i < root_->getNumberOfSons(); i++)
 
489
            {
 
490
              if(root_->getSon(i) == outGroup) return; //This tree is already rooted appropriately.
 
491
            }
 
492
          rootId = getRootId();
 
493
          unroot();
 
494
        }
 
495
      else
 
496
        {
 
497
          rootId = getNextId();
 
498
        }
 
499
      rootAt(outGroup->getFather());
 
500
      N* oldRoot = root_;
 
501
      oldRoot->removeSon(outGroup);
 
502
      root_ = new N();
 
503
      root_->setId(rootId);
 
504
      root_->addSon(oldRoot);
 
505
      root_->addSon(outGroup);
 
506
      // Check lengths:
 
507
      if(outGroup->hasDistanceToFather())
 
508
        {
 
509
          double l = outGroup->getDistanceToFather() / 2.;
 
510
          outGroup->setDistanceToFather(l);
 
511
          oldRoot->setDistanceToFather(l);
 
512
        }
 
513
    }
 
514
 
 
515
    /** @} */
 
516
                
 
517
  private:
 
518
                
 
519
    virtual void destroySubtree_(N* node)
 
520
    {
 
521
      for(unsigned int i = 0; i < node->getNumberOfSons(); i++)
 
522
        {
 
523
          N* son = node->getSon(i);
 
524
          destroySubtree_(son);
 
525
          delete son;
 
526
        }
 
527
    }
 
528
                
 
529
  };
 
530
 
 
531
} //end of namespace bpp.
 
532
 
 
533
#endif  //_TREETEMPLATE_H_
 
534