source: tags/ms_r16q2/CONSENSUS_TREE/CT_ctree.hxx

Last change on this file was 13625, checked in by westram, 7 years ago
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 7.5 KB
Line 
1// ============================================================= //
2//                                                               //
3//   File      : CT_ctree.hxx                                    //
4//   Purpose   : interface of CONSENSUS_TREE library             //
5//                                                               //
6//   Institute of Microbiology (Technical University Munich)     //
7//   http://www.arb-home.de/                                     //
8//                                                               //
9// ============================================================= //
10
11#ifndef CT_CTREE_HXX
12#define CT_CTREE_HXX
13
14#ifndef ARBTOOLS_H
15#include <arbtools.h>
16#endif
17#ifndef ARBDBT_H
18#include <arbdbt.h>
19#endif
20#ifndef ARB_STRARRAY_H
21#include <arb_strarray.h>
22#endif
23#ifndef _GLIBCXX_MAP
24#include <map>
25#endif
26#ifndef _GLIBCXX_VECTOR
27#include <vector>
28#endif
29#ifndef _GLIBCXX_STRING
30#include <string>
31#endif
32#ifndef TREENODE_H
33#include <TreeNode.h>
34#endif
35#ifndef ARB_PROGRESS_H
36#include <arb_progress.h>
37#endif
38
39class  PART;
40struct NT_NODE;
41class  PartitionSize;
42class  PartRegistry;
43class  RB_INFO;
44
45// -----------------------
46//      SizeAwareTree
47
48struct SizeAwareRoot : public TreeRoot {
49    inline SizeAwareRoot();
50    inline TreeNode *makeNode() const OVERRIDE;
51    inline void destroyNode(TreeNode *node) const OVERRIDE;
52};
53
54class SizeAwareTree : public TreeNode {
55    // simple size-aware tree
56    unsigned leaf_count;
57protected:
58    ~SizeAwareTree() OVERRIDE {}
59    friend class SizeAwareRoot; // allowed to call dtor
60public:
61    SizeAwareTree(TreeRoot *root) : TreeNode(root) {}
62    unsigned get_leaf_count() const OVERRIDE {
63        return leaf_count;
64    }
65    void compute_tree() OVERRIDE {
66        if (is_leaf) {
67            leaf_count = 1;
68        }
69        else {
70            get_leftson()->compute_tree();
71            get_rightson()->compute_tree();
72            leaf_count = get_leftson()->get_leaf_count()+get_rightson()->get_leaf_count();
73        }
74    }
75};
76
77SizeAwareRoot::SizeAwareRoot() : TreeRoot(true) {}
78inline TreeNode *SizeAwareRoot::makeNode() const { return new SizeAwareTree(const_cast<SizeAwareRoot*>(this)); }
79inline void SizeAwareRoot::destroyNode(TreeNode *node) const { delete DOWNCAST(SizeAwareTree*,node); }
80
81// -----------------------
82//      ConsensusTree
83
84class ConsensusTree : virtual Noncopyable {
85    double               overall_weight;
86    GB_HASH             *Name_hash;
87    PartitionSize       *size;
88    PART                *allSpecies;
89    PartRegistry        *registry;
90    const CharPtrArray&  names;
91
92    arb_progress *insertProgress;
93
94    PART *deconstruct_full_subtree(const TreeNode *tree, const GBT_LEN& len, const double& weight);
95    PART *deconstruct_partial_subtree(const TreeNode *tree, const GBT_LEN& len, const double& weight, const PART *partialTree);
96
97    void deconstruct_full_rootnode(const TreeNode *tree, const double& weight);
98    void deconstruct_partial_rootnode(const TreeNode *tree, const double& weight, const PART *partialTree);
99
100    int get_species_index(const char *name) const {
101        int idx = GBS_read_hash(Name_hash, name);
102        arb_assert(idx>0); // given 'name' is unknown
103        return idx-1;
104    }
105
106    const char *get_species_name(int idx) const {
107        return names[idx];
108    }
109
110    struct RB_INFO *rbtree(const NT_NODE *tree, TreeRoot *root);
111    SizeAwareTree  *rb_gettree(const NT_NODE *tree);
112
113    void add_tree_to_PART(const TreeNode *tree, PART& part) const;
114    PART *create_tree_PART(const TreeNode *tree, const double& weight) const;
115
116    void inc_insert_progress() { if (insertProgress) ++(*insertProgress); }
117
118public:
119    ConsensusTree(const CharPtrArray& names_);
120    ~ConsensusTree();
121
122    __ATTR__USERESULT GB_ERROR insert_tree_weighted(const TreeNode *tree, int leafs, double weight, bool provideProgress);
123
124    SizeAwareTree *get_consensus_tree(GB_ERROR& error);
125};
126
127// ------------------------------
128//      ConsensusTreeBuilder
129
130class TreeInfo {
131    std::string Name;
132    size_t      specCount;
133
134public:
135    explicit TreeInfo(const char *Name_, size_t specCount_)
136        : Name(Name_),
137          specCount(specCount_)
138    {
139    }
140
141    const char *name() const { return Name.c_str(); }
142    size_t species_count() const { return specCount; }
143};
144
145class ConsensusTreeBuilder {
146    // wrapper for ConsensusTree
147    // - automatically collects species occurring in added trees (has to be done by caller of ConsensusTree)
148    // - uses much more memory than using ConsensusTree directly, since it stores all added trees
149    //
150    // Not helpful for consensing thousands of trees like bootstrapping does
151
152    typedef std::map<std::string, size_t> OccurCount;
153    typedef std::vector<SizeAwareTree*>   Trees;
154    typedef std::vector<double>           Weights;
155
156    OccurCount species_occurred;
157    Trees      trees;
158    Weights    weights;
159
160    std::vector<TreeInfo> tree_info;
161
162public:
163    ~ConsensusTreeBuilder() {
164        for (size_t i = 0; i<trees.size(); ++i) {
165            destroy(trees[i]);
166        }
167    }
168
169    void add(SizeAwareTree*& tree, const char *treename, double weight) {
170        tree->get_tree_root()->find_innermost_edge().set_root();
171
172        // (currently) reordering trees before deconstructing no longer
173        // affects the resulting consense tree (as performed as unit tests).
174        //
175        // tree->reorder_tree(BIG_BRANCHES_TO_TOP);
176        // tree->reorder_tree(BIG_BRANCHES_TO_BOTTOM);
177        // tree->reorder_tree(BIG_BRANCHES_TO_EDGE);
178
179        trees.push_back(tree);
180        weights.push_back(weight);
181
182        size_t   name_count;
183        GB_CSTR *names = GBT_get_names_of_species_in_tree(tree, &name_count);
184
185        for (size_t n = 0; n<name_count; ++n) {
186            const char *name = names[n];
187            if (species_occurred.find(name) == species_occurred.end()) {
188                species_occurred[name] = 1;
189            }
190            else {
191                species_occurred[name]++;
192            }
193        }
194
195        tree_info.push_back(TreeInfo(treename, name_count));
196
197        free(names);
198        tree = NULL;
199    }
200
201    SizeAwareTree *get(size_t& different_species, GB_ERROR& error) {
202        arb_assert(!error);
203
204        ConstStrArray species_names;
205        for (OccurCount::iterator s = species_occurred.begin(); s != species_occurred.end(); ++s) {
206            species_names.put(s->first.c_str());
207        }
208
209        different_species = species_occurred.size();
210        ConsensusTree ctree(species_names);
211        {
212            arb_progress deconstruct("deconstructing", trees.size());
213
214            for (size_t i = 0; i<trees.size() && !error; ++i) {
215                error = ctree.insert_tree_weighted(trees[i], tree_info[i].species_count(), weights[i], true);
216                ++deconstruct;
217                if (error) {
218                    error = GBS_global_string("Failed to deconstruct '%s' (Reason: %s)", tree_info[i].name(), error);
219                }
220                else {
221                    error = deconstruct.error_if_aborted();
222                }
223            }
224            if (error) deconstruct.done();
225        }
226
227        if (error) return NULL;
228
229#if defined(DEBUG)
230        // if class ConsensusTree does depend on any local data,
231        // instanciating another instance will interfere:
232        ConsensusTree influence(species_names);
233#endif
234
235        arb_progress reconstruct("reconstructing");
236        return ctree.get_consensus_tree(error);
237    }
238
239    char *get_remark() const;
240    size_t species_count() const { return species_occurred.size(); }
241};
242
243
244#else
245#error CT_ctree.hxx included twice
246#endif // CT_CTREE_HXX
Note: See TracBrowser for help on using the repository browser.