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 | |
---|
14 | PART *ConsensusTree::deconstruct_full_subtree(const GBT_TREE *tree, const GBT_LEN& len, const double& weight) { |
---|
15 | /*! deconstruct GBT_TREE and register found partitions. |
---|
16 | * @param len length of branch towards subtree 'tree' |
---|
17 | * @param weight summarized for indentical branches (from different trees) |
---|
18 | */ |
---|
19 | |
---|
20 | arb_assert(tree->father); |
---|
21 | |
---|
22 | PART *ptree = NULL; |
---|
23 | if (tree->is_leaf) { |
---|
24 | ptree = create_tree_PART(tree, weight); |
---|
25 | } |
---|
26 | else { |
---|
27 | PART *p1 = deconstruct_full_subtree(tree->leftson, tree->leftlen, weight); |
---|
28 | PART *p2 = deconstruct_full_subtree(tree->rightson, tree->rightlen, weight); |
---|
29 | |
---|
30 | arb_assert(p1->disjunct_from(p2)); |
---|
31 | |
---|
32 | ptree = p1->clone(); |
---|
33 | ptree->add_members_from(p2); |
---|
34 | |
---|
35 | registry->put_part_from_complete_tree(p1); |
---|
36 | registry->put_part_from_complete_tree(p2); |
---|
37 | } |
---|
38 | ptree->set_len(len); |
---|
39 | inc_insert_progress(); |
---|
40 | return ptree; |
---|
41 | } |
---|
42 | |
---|
43 | void ConsensusTree::deconstruct_full_rootnode(const GBT_TREE *tree, const double& weight) { |
---|
44 | /*! deconstruct GBT_TREE and register found partitions. |
---|
45 | * @param weight summarized for indentical branches (from different trees) |
---|
46 | */ |
---|
47 | |
---|
48 | arb_assert(!tree->father); |
---|
49 | arb_assert(!tree->is_leaf); |
---|
50 | |
---|
51 | double root_length = (tree->leftlen + tree->rightlen); |
---|
52 | |
---|
53 | PART *p1 = deconstruct_full_subtree(tree->leftson, root_length, weight); |
---|
54 | PART *p2 = deconstruct_full_subtree(tree->rightson, root_length, weight); |
---|
55 | |
---|
56 | arb_assert(p1->disjunct_from(p2)); |
---|
57 | |
---|
58 | // add only one of the partition p1 and p2 (they both represent the root-edge) |
---|
59 | registry->put_part_from_complete_tree(p1); |
---|
60 | delete p2; |
---|
61 | |
---|
62 | inc_insert_progress(); |
---|
63 | } |
---|
64 | |
---|
65 | PART *ConsensusTree::deconstruct_partial_subtree(const GBT_TREE *tree, const GBT_LEN& len, const double& weight, const PART *partialTree) { |
---|
66 | /*! deconstruct partial GBT_TREE |
---|
67 | * |
---|
68 | * similar to deconstruct_full_subtree(), |
---|
69 | * but the set of missing species is added at each branch. |
---|
70 | */ |
---|
71 | |
---|
72 | arb_assert(tree->father); |
---|
73 | |
---|
74 | PART *ptree = NULL; |
---|
75 | if (tree->is_leaf) { |
---|
76 | ptree = create_tree_PART(tree, weight); |
---|
77 | } |
---|
78 | else { |
---|
79 | PART *p1 = deconstruct_partial_subtree(tree->leftson, tree->leftlen, weight, partialTree); |
---|
80 | PART *p2 = deconstruct_partial_subtree(tree->rightson, tree->rightlen, weight, partialTree); |
---|
81 | |
---|
82 | arb_assert(p1->disjunct_from(p2)); |
---|
83 | |
---|
84 | ptree = p1->clone(); |
---|
85 | ptree->add_members_from(p2); |
---|
86 | |
---|
87 | registry->put_part_from_partial_tree(p1, partialTree); |
---|
88 | registry->put_part_from_partial_tree(p2, partialTree); |
---|
89 | } |
---|
90 | ptree->set_len(len); |
---|
91 | inc_insert_progress(); |
---|
92 | return ptree; |
---|
93 | } |
---|
94 | |
---|
95 | void ConsensusTree::deconstruct_partial_rootnode(const GBT_TREE *tree, const double& weight, const PART *partialTree) { |
---|
96 | /*! deconstruct partial GBT_TREE |
---|
97 | * |
---|
98 | * similar to deconstruct_full_rootnode(), |
---|
99 | * but the set of missing species is added at each branch. |
---|
100 | */ |
---|
101 | |
---|
102 | arb_assert(!tree->father); |
---|
103 | arb_assert(!tree->is_leaf); |
---|
104 | |
---|
105 | double root_length = (tree->leftlen + tree->rightlen); |
---|
106 | |
---|
107 | PART *p1 = deconstruct_partial_subtree(tree->leftson, root_length, weight, partialTree); |
---|
108 | PART *p2 = deconstruct_partial_subtree(tree->rightson, root_length, weight, partialTree); |
---|
109 | |
---|
110 | arb_assert(p1->disjunct_from(p2)); |
---|
111 | |
---|
112 | p2->add_members_from(p1); // in p2 we collect the whole partialTree |
---|
113 | registry->put_part_from_partial_tree(p1, partialTree); // because we are at root edge, we only insert one partition |
---|
114 | |
---|
115 | arb_assert(p2->equals(partialTree)); |
---|
116 | |
---|
117 | arb_assert(is_similar(p2->get_weight(), weight, 0.01)); |
---|
118 | registry->put_artificial_part(p2); |
---|
119 | inc_insert_progress(); |
---|
120 | } |
---|
121 | |
---|
122 | void ConsensusTree::add_tree_to_PART(const GBT_TREE *tree, PART& part) const { |
---|
123 | if (tree->is_leaf) { |
---|
124 | part.setbit(get_species_index(tree->name)); |
---|
125 | } |
---|
126 | else { |
---|
127 | add_tree_to_PART(tree->leftson, part); |
---|
128 | add_tree_to_PART(tree->rightson, part); |
---|
129 | } |
---|
130 | } |
---|
131 | |
---|
132 | PART *ConsensusTree::create_tree_PART(const GBT_TREE *tree, const double& weight) const { |
---|
133 | PART *part = new PART(size, weight); |
---|
134 | if (part) add_tree_to_PART(tree, *part); |
---|
135 | return part; |
---|
136 | } |
---|
137 | |
---|