source: branches/help/CONSENSUS_TREE/CT_dtree.cxx

Last change on this file was 18634, checked in by westram, 4 years ago
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 6.6 KB
Line 
1// ============================================================= //
2//                                                               //
3//   File      : CT_dtree.cxx                                    //
4//   Purpose   :                                                 //
5//                                                               //
6//   Institute of Microbiology (Technical University Munich)     //
7//   http://www.arb-home.de/                                     //
8//                                                               //
9// ============================================================= //
10
11#include "CT_hash.hxx"
12#include "CT_ctree.hxx"
13
14inline void inc_insert_progress(arb_progress *insertProgress) { if (insertProgress) ++(*insertProgress); }
15
16PART *DeconstructedTree::deconstruct_full_subtree(const TreeNode *tree, const GBT_LEN& len, const double& weight, arb_progress *insertProgress) {
17    /*! deconstruct TreeNode and register found partitions.
18     * @param len length of branch towards subtree 'tree'
19     * @param weight summarized for indentical branches (from different trees)
20     */
21
22    arb_assert(tree->father);
23
24    PART *ptree = NULp;
25    if (tree->is_leaf()) {
26        ptree = specSpace.create_tree_PART(tree, weight);
27    }
28    else {
29        if (!(insertProgress && insertProgress->aborted())) {
30            PART *pl = deconstruct_full_subtree(tree->get_leftson(), tree->leftlen, weight, insertProgress);
31            if (pl) {
32                PART *pr = deconstruct_full_subtree(tree->get_rightson(), tree->rightlen, weight, insertProgress);
33                if (!pr) {
34                    arb_assert(insertProgress && insertProgress->aborted());
35                    delete pl;
36                }
37                else {
38                    arb_assert(pl->disjunct_from(pr));
39
40                    ptree = pl->clone();
41                    ptree->add_members_from(pr);
42
43                    registry->put_part_from_complete_tree(pl, tree->get_leftson());
44                    registry->put_part_from_complete_tree(pr, tree->get_rightson());
45                }
46            }
47        }
48    }
49    if (ptree) ptree->set_len(len);
50    inc_insert_progress(insertProgress);
51
52    return ptree;
53}
54
55void DeconstructedTree::deconstruct_full_rootnode(const TreeNode *tree, const double& weight, arb_progress *insertProgress) {
56    /*! deconstruct TreeNode and register found partitions.
57     * @param weight summarized for indentical branches (from different trees)
58     */
59
60    arb_assert(!tree->father);
61    arb_assert(!tree->is_leaf());
62
63    double root_length = (tree->leftlen + tree->rightlen);
64
65    PART *pl = deconstruct_full_subtree(tree->get_leftson(), root_length, weight, insertProgress);
66    if (!pl) {
67        arb_assert(insertProgress && insertProgress->aborted());
68    }
69    else {
70        PART *pr = deconstruct_full_subtree(tree->get_rightson(), root_length, weight, insertProgress);
71        if (!pr) {
72            arb_assert(insertProgress && insertProgress->aborted());
73            delete pl;
74        }
75        else {
76            arb_assert(pl->disjunct_from(pr));
77
78            // add only one of the partition pl and pr (they both represent the root-edge)
79            registry->put_part_from_complete_tree(pl, tree->get_leftson());
80            delete pr;
81
82            inc_insert_progress(insertProgress);
83        }
84    }
85}
86
87PART *DeconstructedTree::deconstruct_partial_subtree(const TreeNode *tree, const GBT_LEN& len, const double& weight, const PART *partialTree, arb_progress *insertProgress) {
88    /*! deconstruct partial TreeNode
89     *
90     * similar to deconstruct_full_subtree(),
91     * but the set of missing species is added at each branch.
92     */
93
94    arb_assert(tree->father);
95
96    PART *ptree = NULp;
97    if (tree->is_leaf()) {
98        ptree = specSpace.create_tree_PART(tree, weight);
99    }
100    else {
101        if (!(insertProgress && insertProgress->aborted())) {
102            PART *pl = deconstruct_partial_subtree(tree->get_leftson(), tree->leftlen, weight, partialTree, insertProgress);
103            if (pl) {
104                PART *pr = deconstruct_partial_subtree(tree->get_rightson(), tree->rightlen, weight, partialTree, insertProgress);
105                if (!pr) {
106                    arb_assert(insertProgress && insertProgress->aborted());
107                    delete pl;
108                }
109                else {
110                    arb_assert(pl->disjunct_from(pr));
111
112                    ptree = pl->clone();
113                    ptree->add_members_from(pr);
114
115                    registry->put_part_from_partial_tree(pl, partialTree, tree->get_leftson());
116                    registry->put_part_from_partial_tree(pr, partialTree, tree->get_rightson());
117                }
118            }
119        }
120    }
121    if (ptree) ptree->set_len(len);
122    inc_insert_progress(insertProgress);
123
124    return ptree;
125}
126
127void DeconstructedTree::deconstruct_partial_rootnode(const TreeNode *tree, const double& weight, const PART *partialTree, arb_progress *insertProgress) {
128    /*! deconstruct partial TreeNode
129     *
130     * similar to deconstruct_full_rootnode(),
131     * but the set of missing species is added at each branch.
132     */
133
134    arb_assert(!tree->father);
135    arb_assert(!tree->is_leaf());
136
137    double root_length = (tree->leftlen + tree->rightlen);
138
139    PART *pl = deconstruct_partial_subtree(tree->get_leftson(), root_length, weight, partialTree, insertProgress);
140    if (!pl) {
141        arb_assert(insertProgress && insertProgress->aborted());
142    }
143    else {
144        PART *pr = deconstruct_partial_subtree(tree->get_rightson(), root_length, weight, partialTree, insertProgress);
145        if (!pr) {
146            arb_assert(insertProgress && insertProgress->aborted());
147            delete pl;
148        }
149        else {
150            arb_assert(pl->disjunct_from(pr));
151
152            pr->add_members_from(pl); // in 'pr' we collect the whole partialTree
153            registry->put_part_from_partial_tree(pl, partialTree, tree->get_leftson()); // because we are at root edge, we only insert one partition ('pl')
154
155            arb_assert(pr->equals(partialTree));
156
157            arb_assert(is_similar(pr->get_weight(), weight, 0.01));
158            registry->put_artificial_part(pr);
159            inc_insert_progress(insertProgress);
160        }
161    }
162}
163
164void SpeciesSpace::add_tree_to_PART(const TreeNode *tree, PART& part) const {
165    if (tree->is_leaf()) {
166        part.setbit(get_species_index(tree->name));
167    }
168    else {
169        add_tree_to_PART(tree->get_leftson(), part);
170        add_tree_to_PART(tree->get_rightson(), part);
171    }
172}
173
174PART *SpeciesSpace::create_tree_PART(const TreeNode *tree, const double& weight) const {
175    PART *part = new PART(get_PartitionSize(), weight);
176    if (part) add_tree_to_PART(tree, *part);
177    return part;
178}
179
Note: See TracBrowser for help on using the repository browser.