ARB
TreeNode.cxx
Go to the documentation of this file.
1 // ================================================================ //
2 // //
3 // File : TreeNode.cxx //
4 // Purpose : //
5 // //
6 // Coded by Ralf Westram (coder@reallysoft.de) in December 2013 //
7 // Institute of Microbiology (Technical University Munich) //
8 // http://www.arb-home.de/ //
9 // //
10 // ================================================================ //
11 
12 #include "TreeNode.h"
13 #include <arb_progress.h>
14 #include <arb_str.h>
15 #include <map>
16 #include <set>
17 #include <cmath> // needed with 4.4.3 (but not with 4.7.3)
18 
19 // ------------------
20 // TreeRoot
21 
23  deleteWithNodes = false; // avoid recursive call of ~TreeRoot (obsolete?)
24  rt_assert(!rootNode); // you have to call TreeRoot::predelete() before dtor! you can do this is dtor of that derived class, which defines makeNode/destroyNode
25  // Note: destroying nodes from here is impossible (leads to pure virtual call, as derived class instance of 'this' is already under destruction)
26 }
27 
28 void TreeRoot::change_root(TreeNode *oldroot, TreeNode *newroot) {
29  rt_assert(rootNode == oldroot);
30  rt_assert(implicated(newroot, !newroot->father));
31  rootNode = newroot;
32 
33  if (oldroot && oldroot->get_tree_root() && !oldroot->is_inside(newroot)) oldroot->set_tree_root(NULp); // unlink from this
34  if (newroot && newroot->get_tree_root() != this) newroot->set_tree_root(this); // link to this
35 }
36 
37 // --------------------
38 // TreeNode
39 
40 #if defined(PROVIDE_TREE_STRUCTURE_TESTS)
41 
42 Validity TreeNode::is_valid() const {
43  rt_assert(knownNonNull(this));
45 
46  TreeRoot *troot = get_tree_root();
47  if (troot) {
48  if (is_leaf()) {
49  valid = Validity(!rightson && !leftson, "leaf has son");
50  }
51  else {
52  valid = Validity(rightson && leftson, "inner node lacks sons");
53  if (valid) valid = get_rightson()->is_valid();
54  if (valid) valid = get_leftson()->is_valid();
55  }
56  if (father) {
57  if (valid) valid = Validity(is_inside(get_father()), "node not inside father subtree");
58  if (valid) valid = Validity(troot->get_root_node()->is_ancestor_of(this), "root is not nodes ancestor");
59  if (valid) valid = Validity(get_father()->get_tree_root() == troot, "node and father have different TreeRoot");
60  }
61  else {
62  if (valid) valid = Validity(troot->get_root_node() == this, "node has no father, but isn't root-node");
63  if (valid) valid = Validity(!is_leaf(), "root-node is leaf"); // leaf@root (tree has to have at least 2 leafs)
64  if (valid) valid = Validity(has_valid_root_remarks(), "root-node has invalid remarks");
65  }
66  }
67  else { // removed node (may be incomplete)
68  if (is_leaf()) {
69  valid = Validity(!rightson && !leftson, "(removed) leaf has son");
70  }
71  else {
72  if (rightson) valid = get_rightson()->is_valid();
73  if (leftson && valid) valid = get_leftson()->is_valid();
74  }
75  if (father) {
76  if (valid) valid = Validity(is_inside(get_father()), "(removed) node not inside father subtree");
77  if (valid) valid = Validity(get_father()->get_tree_root() == troot, "(removed) node and father have different TreeRoot");
78  }
79  }
80  return valid;
81 }
82 #endif // PROVIDE_TREE_STRUCTURE_TESTS
83 
85  if (tree_root != new_root) {
86  tree_root = new_root;
87  if (leftson) get_leftson()->set_tree_root(new_root);
88  if (rightson) get_rightson()->set_tree_root(new_root);
89  }
90 }
91 
92 void TreeNode::reorder_subtree(TreeOrder mode) {
93  static const char *smallest_leafname; // has to be set to the alphabetically smallest name (when function exits)
94 
95  if (is_leaf()) {
96  smallest_leafname = name;
97  }
98  else {
99  int leftsize = get_leftson() ->get_leaf_count();
100  int rightsize = get_rightson()->get_leaf_count();
101 
102  {
103  bool big_at_top = leftsize>rightsize;
104  bool big_at_bottom = leftsize<rightsize;
105  bool swap_branches = (mode&ORDER_BIG_DOWN) ? big_at_top : big_at_bottom;
106  if (swap_branches) swap_sons();
107  }
108 
109  TreeOrder lmode, rmode;
110  if (mode & (ORDER_BIG_TO_EDGE|ORDER_BIG_TO_CENTER)) { // symmetric
112 
113  if (mode & ORDER_BIG_TO_CENTER) {
114  lmode = TreeOrder(mode | ORDER_BIG_DOWN);
115  rmode = TreeOrder(mode & ~ORDER_BIG_DOWN);
116  }
117  else {
118  lmode = TreeOrder(mode & ~ORDER_BIG_DOWN);
119  rmode = TreeOrder(mode | ORDER_BIG_DOWN);
120  }
121  }
122  else { // asymmetric
123  if (mode & ORDER_ALTERNATING) mode = TreeOrder(mode^ORDER_BIG_DOWN);
124 
125  lmode = mode;
126  rmode = mode;
127  }
128 
129  get_leftson()->reorder_subtree(lmode);
130  const char *leftleafname = smallest_leafname;
131 
132  get_rightson()->reorder_subtree(rmode);
133  const char *rightleafname = smallest_leafname;
134 
135  if (leftleafname && rightleafname) {
136  int name_cmp = strcmp(leftleafname, rightleafname);
137  if (name_cmp <= 0) {
138  smallest_leafname = leftleafname;
139  }
140  else {
141  smallest_leafname = rightleafname;
142  if (leftsize == rightsize) { // if sizes of subtrees are equal and rightleafname<leftleafname -> swap branches
143  const char *smallest_leafname_save = smallest_leafname;
144 
145  swap_sons();
146  get_leftson ()->reorder_subtree(lmode); rt_assert(strcmp(smallest_leafname, rightleafname)== 0);
147  get_rightson()->reorder_subtree(rmode); rt_assert(strcmp(smallest_leafname, leftleafname) == 0);
148 
149  smallest_leafname = smallest_leafname_save;
150  }
151  }
152  }
153  }
154  rt_assert(smallest_leafname);
155 }
156 
160  compute_tree();
161  reorder_subtree(mode);
162 }
163 
165  if (!is_leaf()) {
166  swap_sons();
167  get_leftson()->rotate_subtree();
168  get_rightson()->rotate_subtree();
169  }
170 }
171 
172 void TreeNode::keelOver(TreeNode *prev, TreeNode *next, double len) {
179  if (leftson == prev) {
180  leftson = next;
181  leftlen = len;
182 
183  if (keeledOver) {
184  if (inverseLeft) keeledOver = false;
185  }
186  else {
187  keeledOver = true;
188  inverseLeft = true;
189  }
190  }
191  else {
192  rightson = next;
193  rightlen = len;
194 
195  if (keeledOver) {
196  if (!inverseLeft) keeledOver = false;
197  }
198  else {
199  keeledOver = true;
200  inverseLeft = false;
201  }
202  }
203  father = prev;
204 }
205 
213  if (at_root()) return; // already root
214 
215  TreeNode *old_root = get_root_node();
216  TreeNode *old_brother = is_inside(old_root->get_leftson()) ? old_root->get_rightson() : old_root->get_leftson();
217 
218  rt_assert(old_root->has_valid_root_remarks());
219 
220  // move remark branches to top
221  {
222  // Note: no remark is lost here (duplicate removed from old root; new duplicate created at new root)
223  SmartCharPtr remarkPtr;
224  if (!is_leaf()) remarkPtr = get_remark_ptr();
225  for (TreeNode *node = this; node->father; node = node->get_father()) {
226  std::swap(node->remark_branch, remarkPtr);
227  }
228  }
229 
230  GBT_LEN old_root_len = old_root->leftlen + old_root->rightlen;
231 
232  // new node & this init
233  old_root->leftson = this;
234  old_root->rightson = father; // will be set later
235 
236  if (father->leftson == this) {
237  old_root->leftlen = old_root->rightlen = father->leftlen*.5;
238  }
239  else {
240  old_root->leftlen = old_root->rightlen = father->rightlen*.5;
241  }
242 
243  TreeNode *next = get_father()->get_father();
244  TreeNode *prev = old_root;
245  TreeNode *pntr = get_father();
246 
247  if (father->leftson == this) father->leftson = old_root; // to set the flag correctly
248 
249  // loop from father to son of root, rotate tree
250  while (next->father) {
251  double len = (next->leftson == pntr) ? next->leftlen : next->rightlen;
252 
253  pntr->keelOver(prev, next, len);
254 
255  prev = pntr;
256  pntr = next;
257  next = next->get_father();
258  }
259  // now 'next' points to the old root, which has been destroyed above
260  // 'pntr' points to one former son-of-root (the one nearer to new root)
261  //
262  // pointer at oldroot
263  // pntr == brother before old root == next
264 
265  pntr->keelOver(prev, old_brother, old_root_len);
266 
267  old_brother->father = pntr;
268  father = old_root;
269 
270  rt_assert(get_root_node() == old_root); // the root node itself remains unchanged (its sons change)
271  rt_assert(old_root->has_valid_root_remarks());
272 }
273 
274 TreeNode *TreeNode::findLeafNamed(const char *wantedName) {
275  TreeNode *found = NULp;
276  if (is_leaf()) {
277  if (name && strcmp(name, wantedName) == 0) found = this;
278  }
279  else {
280  found = get_leftson()->findLeafNamed(wantedName);
281  if (!found) found = get_rightson()->findLeafNamed(wantedName);
282  }
283  return found;
284 }
285 
286 // ----------------------------
287 // find_innermost_edge
288 
290  GBT_LEN downdist, updist;
291  enum { NLD_NODIST = 0, NLD_DOWNDIST, NLD_BOTHDIST } state;
292 
293 public:
294 
296  : downdist(-1.0),
297  updist(-1.0),
298  state(NLD_NODIST)
299  {}
300 
301  GBT_LEN get_downdist() const { rt_assert(state >= NLD_DOWNDIST); return downdist; }
302  void set_downdist(GBT_LEN DownDist) {
303  if (state < NLD_DOWNDIST) state = NLD_DOWNDIST;
304  downdist = DownDist;
305  }
306 
307  GBT_LEN get_updist() const { rt_assert(state >= NLD_BOTHDIST); return updist; }
308  void set_updist(GBT_LEN UpDist) {
309  if (state < NLD_BOTHDIST) state = NLD_BOTHDIST;
310  updist = UpDist;
311  }
312 
313 };
314 
315 class EdgeFinder {
316  std::map<TreeNode*, NodeLeafDistance> data; // maximum distance to farthest leaf
317 
318  ARB_edge innermost;
319  double min_distdiff; // abs diff between up- and downdiff
320 
321  GBT_LEN calc_distdiff(GBT_LEN d1, GBT_LEN d2) { return fabs(d1-d2); }
322 
323  void insert_tree(TreeNode *node) {
324  if (node->is_leaf()) {
325  data[node].set_downdist(0.0);
326  }
327  else {
328  insert_tree(node->get_leftson());
329  insert_tree(node->get_rightson());
330 
331  data[node].set_downdist(std::max(data[node->get_leftson()].get_downdist()+node->leftlen,
332  data[node->get_rightson()].get_downdist()+node->rightlen));
333  }
334  }
335 
336  void findBetterEdge_sub(TreeNode *node) {
337  TreeNode *father = node->get_father();
338  TreeNode *brother = node->get_brother();
339 
340  GBT_LEN len = node->get_branchlength();
341  GBT_LEN brothLen = brother->get_branchlength();
342 
343  GBT_LEN upDist = std::max(data[father].get_updist(), data[brother].get_downdist()+brothLen);
344  GBT_LEN downDist = data[node].get_downdist();
345 
346  {
347  GBT_LEN edge_dd = calc_distdiff(upDist, downDist);
348  if (edge_dd<min_distdiff) { // found better edge
349  innermost = ARB_edge(node, father);
350  min_distdiff = edge_dd;
351  }
352  }
353 
354  data[node].set_updist(upDist+len);
355 
356  if (!node->is_leaf()) {
357  findBetterEdge_sub(node->get_leftson());
358  findBetterEdge_sub(node->get_rightson());
359  }
360  }
361 
362  void findBetterEdge(TreeNode *node) {
363  if (!node->is_leaf()) {
364  findBetterEdge_sub(node->get_leftson());
365  findBetterEdge_sub(node->get_rightson());
366  }
367  }
368 
369 public:
371  : innermost(rootNode->get_leftson(), rootNode->get_rightson()) // root-edge
372  {
373  insert_tree(rootNode);
374 
375  TreeNode *lson = rootNode->get_leftson();
376  TreeNode *rson = rootNode->get_rightson();
377 
378  GBT_LEN rootEdgeLen = rootNode->leftlen + rootNode->rightlen;
379 
380  GBT_LEN lddist = data[lson].get_downdist();
381  GBT_LEN rddist = data[rson].get_downdist();
382 
383  data[lson].set_updist(rddist+rootEdgeLen);
384  data[rson].set_updist(lddist+rootEdgeLen);
385 
386  min_distdiff = calc_distdiff(lddist, rddist);
387 
388  findBetterEdge(lson);
389  findBetterEdge(rson);
390  }
391 
392  const ARB_edge& innermost_edge() const { return innermost; }
393 };
394 
396  EdgeFinder edgeFinder(get_root_node());
397  return edgeFinder.innermost_edge();
398 }
399 
400 // ------------------------
401 // multifurcation
402 
404  typedef std::map<TreeNode*,GBT_LEN> LengthMap;
405  typedef std::set<TreeNode*> NodeSet;
406 
407  LengthMap eliminatedParentLength;
408  LengthMap addedParentLength;
409 
410 public:
412  rt_assert(!node->is_root_node());
413  eliminatedParentLength[node] += parentEdge(node).eliminate();
414  }
415 
417  rt_assert(!node->is_root_node());
418  addedParentLength[node] += addLen;
419  }
420 
421  void independent_distribution(bool useProgress) {
422  // step 2: (see caller)
423  arb_progress *progress = NULp;
424  int redistCount = 0;
425  if (useProgress) progress = new arb_progress("Distributing eliminated lengths", eliminatedParentLength.size());
426 
427  while (!eliminatedParentLength.empty()) { // got eliminated lengths which need to be distributed
428  for (LengthMap::iterator from = eliminatedParentLength.begin(); from != eliminatedParentLength.end(); ++from) {
429  ARB_edge elimEdge = parentEdge(from->first);
430  GBT_LEN elimLen = from->second;
431 
432  elimEdge.virtually_distribute_length(elimLen, *this);
433  if (progress) ++*progress;
434  }
435  eliminatedParentLength.clear(); // all distributed!
436 
437  // handle special cases where distributed length is negative and results in negative destination branches.
438  // Avoid generating negative dest. branchlengths by
439  // - eliminating the dest. branch
440  // - redistributing the additional (negative) length (may cause additional negative lengths on other dest. branches)
441 
442  NodeSet handled;
443  for (LengthMap::iterator to = addedParentLength.begin(); to != addedParentLength.end(); ++to) {
444  ARB_edge affectedEdge = parentEdge(to->first);
445  GBT_LEN additionalLen = to->second;
446  double effective_length = affectedEdge.length() + additionalLen;
447 
448  if (effective_length<=0.0) { // negative or zero
449  affectedEdge.set_length(effective_length);
450  eliminate_parent_edge(to->first); // adds entry to eliminatedParentLength and causes another additional loop
451  handled.insert(to->first);
452  }
453  }
454 
455  if (progress && !eliminatedParentLength.empty()) {
456  delete progress;
457  ++redistCount;
458  progress = new arb_progress(GBS_global_string("Redistributing negative lengths (#%i)", redistCount), eliminatedParentLength.size());
459  }
460 
461  // remove all redistributed nodes
462  for (NodeSet::iterator del = handled.begin(); del != handled.end(); ++del) {
463  addedParentLength.erase(*del);
464  }
465  }
466 
467  // step 3:
468  for (LengthMap::iterator to = addedParentLength.begin(); to != addedParentLength.end(); ++to) {
469  ARB_edge affectedEdge = parentEdge(to->first);
470  GBT_LEN additionalLen = to->second;
471  double effective_length = affectedEdge.length() + additionalLen;
472 
473  affectedEdge.set_length(effective_length);
474  }
475 
476  if (progress) delete progress;
477  }
478 };
479 
480 GBT_LEN ARB_edge::adjacent_distance() const {
482 
483  if (is_edge_to_leaf()) return 0.0;
484  return next().length_or_adjacent_distance() + counter_next().length_or_adjacent_distance();
485 }
486 
487 void ARB_edge::virtually_add_or_distribute_length_forward(GBT_LEN len, TreeNode::LengthCollector& collect) const {
488  rt_assert(!is_nan_or_inf(len));
489  if (length() > 0.0) {
490  collect.add_parent_length(son(), len);
491  }
492  else {
493  if (len != 0.0) virtually_distribute_length_forward(len, collect);
494  }
495 }
496 
497 
498 void ARB_edge::virtually_distribute_length_forward(GBT_LEN len, TreeNode::LengthCollector& collect) const {
505  rt_assert(is_normal(len));
506  rt_assert(!is_edge_to_leaf()); // cannot forward anything (nothing beyond leafs)
507 
508  ARB_edge e1 = next();
509  ARB_edge e2 = counter_next();
510 
511  GBT_LEN d1 = e1.length_or_adjacent_distance();
512  GBT_LEN d2 = e2.length_or_adjacent_distance();
513 
514  len = len/(d1+d2);
515 
516  e1.virtually_add_or_distribute_length_forward(len*d1, collect);
517  e2.virtually_add_or_distribute_length_forward(len*d2, collect);
518 }
519 
531  ARB_edge backEdge = inverse();
532  GBT_LEN len_fwd, len_bwd;
533  {
534  GBT_LEN dist_fwd = adjacent_distance();
535  GBT_LEN dist_bwd = backEdge.adjacent_distance();
536  GBT_LEN lenW = len/(dist_fwd+dist_bwd);
537  len_fwd = lenW*dist_fwd;
538  len_bwd = lenW*dist_bwd;
539 
540  }
541 
542  if (is_normal(len_fwd)) virtually_distribute_length_forward(len_fwd, collect);
543  if (is_normal(len_bwd)) backEdge.virtually_distribute_length_forward(len_bwd, collect);
544 }
545 
546 void TreeNode::eliminate_and_collect(const multifurc_limits& below, LengthCollector& collect) {
551  if (!is_leaf() || below.applyAtLeafs) {
552  double value;
553  if (is_leaf()) {
554  value = 100.0;
555  goto hack; // @@@ remove applyAtLeafs from multifurc_limits (does that really make sense? rethink!)
556  }
557  switch (parse_bootstrap(value)) {
558  case REMARK_NONE:
559  value = 100.0;
560  // fall-through
561  case REMARK_BOOTSTRAP:
562  hack:
563  if (value<below.bootstrap && get_branchlength_unrooted()<below.branchlength) {
564  collect.eliminate_parent_edge(this);
565  }
566  break;
567 
568  case REMARK_OTHER: break;
569  }
570  }
571 
572  if (!is_leaf()) {
573  get_leftson() ->eliminate_and_collect(below, collect);
574  get_rightson()->eliminate_and_collect(below, collect);
575  }
576 }
577 
584  TreeNode::LengthCollector collector;
585  collector.eliminate_parent_edge(son());
586  collector.independent_distribution(false);
587 }
592  rt_assert(father); // cannot multifurcate at root; call with son of root to multifurcate root-edge
593  if (father) parentEdge(this).multifurcate();
594 }
595 
604  GBT_LEN change = new_len-old_len;
605 
606  char *old_remark = is_leaf() ? NULp : nulldup(get_remark());
607 
608  // distribute the negative 'change' to neighbours:
609  set_branchlength_unrooted(-change);
610  multifurcate();
611 
612  set_branchlength_unrooted(new_len);
613  if (old_remark) {
614  use_as_remark(old_remark); // restore remark (was removed by multifurcate())
615  }
616 #if defined(ASSERTION_USED)
617  else {
619  }
620 #endif
621 }
622 
629  TreeNode *root = get_root_node();
630  LengthCollector collector;
631  arb_progress progress("Multifurcating tree");
632 
633  // step 1:
634  progress.subtitle("Collecting branches to eliminate");
635  root->get_leftson()->eliminate_and_collect(below, collector);
636  root->get_rightson()->eliminate_and_collect(below, collector);
637  // root-edge is handled twice by the above calls.
638  // Unproblematic: first call will eliminate root-edge, so second call will do nothing.
639 
640  // step 2 and 3:
641  collector.independent_distribution(true);
642 }
643 
645  remark_branch.setNull();
646  if (!is_leaf()) {
647  get_leftson()->remove_bootstrap();
648  get_rightson()->remove_bootstrap();
649  }
650 }
652  if (!is_leaf()) {
654 
655  get_leftson()->reset_branchlengths();
656  get_rightson()->reset_branchlengths();
657  }
658 }
659 
660 void TreeNode::scale_branchlengths(double factor) {
661  if (!is_leaf()) {
662  leftlen *= factor;
663  rightlen *= factor;
664 
665  get_leftson()->scale_branchlengths(factor);
666  get_rightson()->scale_branchlengths(factor);
667  }
668 }
669 
671  if (is_leaf()) return 0.0;
672  return
673  leftlen +
674  rightlen +
675  get_leftson()->sum_child_lengths() +
676  get_rightson()->sum_child_lengths();
677 }
678 
681  if (is_leaf()) {
683  }
684  else {
685  if (father) {
686  double bootstrap;
687  GBT_RemarkType rtype = parse_bootstrap(bootstrap);
688 
689  if (rtype == REMARK_BOOTSTRAP) {
690  double len = bootstrap/100.0;
692  }
693  else {
694  set_branchlength_unrooted(1.0); // no bootstrap means "100%"
695  }
696  }
697  get_leftson()->bootstrap2branchlen();
698  get_rightson()->bootstrap2branchlen();
699  }
700 }
701 
704  if (!is_leaf()) {
705  remove_remark();
706  if (!is_root_node()) {
708  }
709  get_leftson()->branchlen2bootstrap();
710  get_rightson()->branchlen2bootstrap();
711  }
712 #if defined(ASSERTION_USED)
713  else {
715  }
716 #endif
717 }
718 
720  // fix node after one son has been deleted
721  TreeNode *result = NULp;
722 
723  if (leftson) {
725  result = get_leftson();
726  leftson = NULp;
727  }
728  else {
729  gb_assert(!leftson);
731 
732  result = get_rightson();
733  rightson = NULp;
734  }
735 
736  // now 'result' contains the lasting tree
737  result->father = father;
738 
739  // rescue remarks if possible
740  if (!is_leaf() && !result->is_leaf()) {
741  if (get_remark() && !result->get_remark()) {
742  result->use_as_remark(get_remark_ptr());
743  remove_remark();
744  }
745  }
746 
747  if (gb_node && !result->gb_node) { // rescue group if possible
748  result->gb_node = gb_node;
749  gb_node = NULp;
750  }
751 
752  if (!result->father) {
753  get_tree_root()->change_root(this, result);
754  }
755 
757 
758  forget_origin();
760  delete this;
761 
762  return result;
763 }
764 
766  if (this == other) return this;
767  if (is_ancestor_of(other)) return this;
768  if (other->is_ancestor_of(this)) return other;
769  return get_father()->ancestor_common_with(other->get_father());
770 }
771 
773  if (is_leaf()) return is_clade();
774  return get_leftson()->count_clades() + get_rightson()->count_clades() + is_clade();
775 }
776 
777 #if defined(ASSERTION_USED) || defined(PROVIDE_TREE_STRUCTURE_TESTS)
779  // tests whether the root-edge has a valid remark:
780  // - if one son is a leaf, the other son may contain the remark for the root-edge
781  // - if no son is a leaf, both sons shall contain the same remark (or none)
783  return implicated(!get_leftson()->is_leaf() && !get_rightson()->is_leaf(),
784  ARB_strNULLcmp(get_leftson()->get_remark(), get_rightson()->get_remark()) == 0);
785 }
786 #endif
787 
788 // --------------------------------------------------------------------------------
789 
790 #ifdef UNIT_TESTS
791 #ifndef TEST_UNIT_H
792 #include <test_unit.h>
793 #endif
794 
795 void TEST_tree_iterator() {
796  GB_shell shell;
797  GBDATA *gb_main = GB_open("TEST_trees.arb", "r");
798  {
799  GB_transaction ta(gb_main);
800  TreeNode *tree = GBT_read_tree(gb_main, "tree_removal", new SimpleRoot);
801 
802  int leafs = GBT_count_leafs(tree);
803  TEST_EXPECT_EQUAL(leafs, 17);
805 
806  int iter_steps = ARB_edge::iteration_count(leafs);
807  TEST_EXPECT_EQUAL(iter_steps, 62);
808 
809  const ARB_edge start = rootEdge(tree->get_tree_root());
810 
811  // iterate forward + count (until same edge reached)
812  int count = 0;
813  int count_leafs = 0;
814  ARB_edge edge = start;
815  do {
816  ARB_edge next = edge.next();
817  TEST_EXPECT(next.previous() == edge); // test reverse operation
818  edge = next;
819  ++count;
820  if (edge.is_edge_to_leaf()) ++count_leafs;
821  }
822  while (edge != start);
823  TEST_EXPECT_EQUAL(count, iter_steps);
824  TEST_EXPECT_EQUAL(count_leafs, leafs);
825 
826  // iterate backward + count (until same edge reached)
827  count = 0;
828  count_leafs = 0;
829  edge = start;
830  do {
831  ARB_edge next = edge.previous();
832  TEST_EXPECT(next.next() == edge); // test reverse operation
833  edge = next;
834  ++count;
835  if (edge.is_edge_to_leaf()) ++count_leafs;
836  }
837  while (edge != start);
838  TEST_EXPECT_EQUAL(count, iter_steps);
839  TEST_EXPECT_EQUAL(count_leafs, leafs);
840 
841  if (tree) {
842  gb_assert(tree->is_root_node());
843  destroy(tree);
844  }
845  }
846  GB_close(gb_main);
847 }
848 
849 void TEST_tree_branch_modifications() {
850  GB_shell shell;
851  GBDATA *gb_main = GB_open("TEST_trees.arb", "r");
852  {
853  const char *left_newick = "((((((CloTyro3:1.046,CloTyro4:0.061)'40%':0.026,CloTyro2:0.017)'0%':0.017,CloTyrob:0.009)'97%':0.274,CloInnoc:0.371)'0%':0.057,CloBifer:0.388)'53%':0.124,(((CloButy2:0.009,CloButyr:0.000):0.564,CloCarni:0.120)'33%':0.010,CloPaste:0.179)'97%':0.131):0.081;";
854  const char *left_newick_bs2bl = "((((((CloTyro3:0.100,CloTyro4:0.100):0.400,CloTyro2:0.100):0.000,CloTyrob:0.100):0.970,CloInnoc:0.100):0.000,CloBifer:0.100):0.530,(((CloButy2:0.100,CloButyr:0.100):1.000,CloCarni:0.100):0.330,CloPaste:0.100):0.970):0.500;"; // bootstrap2branchlen
855 
856  const char *right_newick = "((((CorAquat:0.084,CurCitre:0.058):0.103,CorGluta:0.522)'17%':0.053,CelBiazo:0.059)'40%':0.207,CytAquat:0.711):0.081;";
857  const char *right_newick_preserved1 = "((((CorAquat:0.084,CurCitre:0.058):0.103,CorGluta:0.522)'17%':0.060,CelBiazo:0.029)'40%':0.231,CytAquat:0.711):0.081;"; // set_branchlength_preserving to 0.029 at CelBiazo
858  const char *right_newick_preserved2 = "((((CorAquat:0.084,CurCitre:0.058):0.103,CorGluta:0.522)'17%':0.041,CelBiazo:0.117)'40%':0.161,CytAquat:0.711):0.081;"; // set_branchlength_preserving to 0.117 at CelBiazo
859  const char *right_newick_bl2bs = "((((CorAquat,CurCitre)'10%',CorGluta)'5%',CelBiazo)'21%',CytAquat)'100%';"; // branchlen2bootstrap
860 
862 
863  GB_transaction ta(gb_main);
864  {
865  TreeNode *tree = GBT_read_tree(gb_main, "tree_test", new SimpleRoot);
866 
867  TreeNode *left = tree->get_leftson();
868  TreeNode *right = tree->get_rightson();
869 
870  TEST_EXPECT_NEWICK(BSLEN, left, left_newick);
871  TEST_EXPECT_NEWICK(BSLEN, right, right_newick);
872 
873  left->bootstrap2branchlen();
874  right->branchlen2bootstrap();
875 
876  TEST_EXPECT_NEWICK(nLENGTH, left, left_newick_bs2bl);
877  TEST_EXPECT_NEWICK(nREMARK, right, right_newick_bl2bs);
878 
879  destroy(tree);
880  }
881  {
882  TreeNode *tree = GBT_read_tree(gb_main, "tree_test", new SimpleRoot);
883 
884  TreeNode *right = tree->get_rightson();
885  TreeNode *CelBiazo = right->findLeafNamed("CelBiazo");
886 
887  CelBiazo->set_branchlength_preserving(CelBiazo->get_branchlength() * 0.5);
888  TEST_EXPECT_NEWICK(BSLEN, right, right_newick_preserved1);
889 
890  CelBiazo->set_branchlength_preserving(CelBiazo->get_branchlength() * 4.0);
891  TEST_EXPECT_NEWICK(BSLEN, right, right_newick_preserved2);
892 
893  destroy(tree);
894  }
895  }
896  GB_close(gb_main);
897 }
898 
899 TEST_PUBLISH(TEST_tree_branch_modifications);
900 
901 #endif // UNIT_TESTS
902 
903 // --------------------------------------------------------------------------------
void set_bootstrap(double bootstrap)
Definition: TreeNode.h:282
void set_branchlength_unrooted(GBT_LEN newlen)
Definition: TreeNode.h:232
void set_updist(GBT_LEN UpDist)
Definition: TreeNode.cxx:308
string result
size_t GBT_count_leafs(const TreeNode *tree)
Definition: adtree.cxx:796
GBDATA * GB_open(const char *path, const char *opent)
Definition: ad_load.cxx:1363
virtual ~TreeRoot()
Definition: TreeNode.cxx:22
void virtually_distribute_length(GBT_LEN len, TreeNode::LengthCollector &collect) const
Definition: TreeNode.cxx:520
void bootstrap2branchlen()
Definition: TreeNode.cxx:679
virtual void swap_sons()
Definition: TreeNode.h:512
GBT_RemarkType parse_bootstrap(double &bootstrap) const
Definition: TreeNode.h:261
#define implicated(hypothesis, conclusion)
Definition: arb_assert.h:289
TreeNode * findLeafNamed(const char *wantedName)
Definition: TreeNode.cxx:274
const TreeNode * get_root_node() const
Definition: TreeNode.h:382
virtual void set_root()
Definition: TreeNode.cxx:206
GBT_LEN get_branchlength_unrooted() const
Definition: TreeNode.h:225
virtual void compute_tree()=0
bool is_clade() const
Definition: TreeNode.h:439
POS_TREE1 * get_father() const
Definition: probe_tree.h:211
void forget_origin()
Definition: TreeNode.h:373
TreeRoot * get_tree_root() const
Definition: TreeNode.h:380
TreeNode * GBT_read_tree(GBDATA *gb_main, const char *tree_name, TreeRoot *troot)
Definition: adtree.cxx:791
ARB_edge inverse() const
Definition: TreeNode.h:753
#define DEFAULT_BRANCH_LENGTH
Definition: arbdbt.h:18
const char * GBS_global_string(const char *templat,...)
Definition: arb_msg.cxx:204
ARB_edge previous() const
Definition: TreeNode.h:774
GBT_LEN length() const
Definition: TreeNode.h:732
TreeNode * son() const
Definition: TreeNode.h:729
ARB_edge rootEdge(TreeRoot *root)
Definition: TreeNode.h:857
CONSTEXPR_INLINE bool is_normal(const T &n)
Definition: arbtools.h:176
void use_as_remark(const SmartCharPtr &newRemark)
Definition: TreeNode.h:275
int ARB_strNULLcmp(const char *s1, const char *s2)
Definition: arb_str.h:52
void reset_branchlengths()
Definition: TreeNode.cxx:651
GBT_LEN leftlen
Definition: TreeNode.h:132
TreeNode * rightson
Definition: TreeNode.h:131
bool has_valid_root_remarks() const
Definition: TreeNode.cxx:778
ARB_edge next() const
Definition: TreeNode.h:763
static HelixNrInfo * start
ARB_edge parentEdge(TreeNode *son)
Definition: TreeNode.h:842
CONSTEXPR_INLINE bool is_nan_or_inf(const T &n)
Definition: arbtools.h:175
POS_TREE1 * father
Definition: probe_tree.h:39
#define TEST_PUBLISH(testfunction)
Definition: test_unit.h:1484
POS_TREE1 * get_father() const
Definition: probe_tree.h:49
void branchlen2bootstrap()
Definition: TreeNode.cxx:702
void add_parent_length(TreeNode *node, GBT_LEN addLen)
Definition: TreeNode.cxx:416
#define TEST_EXPECT(cond)
Definition: test_unit.h:1312
#define TEST_EXPECT_NEWICK(format, tree, expected_newick)
Definition: test_unit.h:1448
const TreeNode * ancestor_common_with(const TreeNode *other) const
Definition: TreeNode.cxx:765
CONSTEXPR_INLINE int leafs_2_edges(int leafs, TreeModel model)
Definition: arbdbt.h:61
void multifurcate()
Definition: TreeNode.cxx:578
TreeNode * father
Definition: TreeNode.h:131
bool is_root_node() const
Definition: TreeNode.h:391
CONSTEXPR_INLINE_Cxx14 void swap(unsigned char &c1, unsigned char &c2)
Definition: ad_io_inline.h:19
TreeNode * get_brother()
Definition: TreeNode.h:394
const ARB_edge & innermost_edge() const
Definition: TreeNode.cxx:392
EdgeFinder(TreeNode *rootNode)
Definition: TreeNode.cxx:370
void multifurcate_whole_tree(const multifurc_limits &below)
Definition: TreeNode.cxx:623
void set_downdist(GBT_LEN DownDist)
Definition: TreeNode.cxx:302
void rotate_subtree()
Definition: TreeNode.cxx:164
bool at_root() const
Definition: TreeNode.h:308
AP_tree_nlen * rootNode()
Definition: ap_main.hxx:54
NewickFormat
Definition: arbdb_base.h:68
CONSTEXPR_INLINE bool valid(SpeciesCreationMode m)
Definition: ed4_class.hxx:2249
TreeNode * leftson
Definition: TreeNode.h:131
GBT_RemarkType
Definition: arbdbt.h:29
void eliminate_parent_edge(TreeNode *node)
Definition: TreeNode.cxx:411
GBT_LEN rightlen
Definition: TreeNode.h:132
bool is_ancestor_of(const TreeNode *descendant) const
Definition: TreeNode.h:201
int count_clades() const
Definition: TreeNode.cxx:772
void reorder_tree(TreeOrder mode)
Definition: TreeNode.cxx:157
bool knownNonNull(const void *nonnull)
Definition: arb_assert.h:368
void remove_remark()
Definition: TreeNode.h:285
bool has_no_remark() const
Definition: TreeNode.h:290
#define rt_assert(cond)
Definition: TreeNode.h:22
bool is_edge_to_leaf() const
Definition: TreeNode.h:823
bool is_leaf() const
Definition: TreeNode.h:171
void set_branchlength_preserving(GBT_LEN new_len)
Definition: TreeNode.cxx:596
TreeNode * fixDeletedSon()
Definition: TreeNode.cxx:719
#define gb_assert(cond)
Definition: arbdbt.h:11
void multifurcate()
Definition: TreeNode.cxx:588
bool is_inside(const TreeNode *subtree) const
Definition: TreeNode.h:198
GBT_LEN get_updist() const
Definition: TreeNode.cxx:307
char * name
Definition: TreeNode.h:134
void subtitle(const char *stitle)
Definition: arb_progress.h:263
void scale_branchlengths(double factor)
Definition: TreeNode.cxx:660
void independent_distribution(bool useProgress)
Definition: TreeNode.cxx:421
TreeOrder
Definition: TreeNode.h:35
void set_tree_root(TreeRoot *new_root)
Definition: TreeNode.cxx:84
GBT_LEN sum_child_lengths() const
Definition: TreeNode.cxx:670
void remove_bootstrap()
Definition: TreeNode.cxx:644
ARB_edge counter_next() const
Definition: TreeNode.h:786
float GBT_LEN
Definition: arbdb_base.h:34
#define NULp
Definition: cxxforward.h:97
GBT_LEN get_downdist() const
Definition: TreeNode.cxx:301
ARB_edge find_innermost_edge()
Definition: TreeNode.cxx:395
GBT_LEN get_branchlength() const
Definition: TreeNode.h:219
GB_transaction ta(gb_var)
void destroy(TreeNode *that)
Definition: TreeNode.h:559
GBDATA * gb_node
Definition: TreeNode.h:133
GBDATA * gb_main
Definition: adname.cxx:33
GBT_LEN eliminate()
Definition: TreeNode.h:745
virtual void change_root(TreeNode *old, TreeNode *newroot)
Definition: TreeNode.cxx:28
void set_length(GBT_LEN len)
Definition: TreeNode.h:736
const char * get_remark() const
Definition: TreeNode.h:266
const SmartCharPtr & get_remark_ptr() const
Definition: TreeNode.h:270
void forget_relatives()
Definition: TreeNode.h:374
#define TEST_EXPECT_EQUAL(expr, want)
Definition: test_unit.h:1283
void GB_close(GBDATA *gbd)
Definition: arbdb.cxx:625
static int iteration_count(int leafs_in_tree)
Definition: TreeNode.h:809
#define max(a, b)
Definition: f2c.h:154