source: branches/stable/CONSENSUS_TREE/CT_ctree.cxx

Last change on this file was 11488, checked in by westram, 7 years ago
  • reintegrates 'tree' into 'trunk'
    • implements #417 (multifurcate tree)
    • tree display
      • adds MULTIFURC MODE
      • reordered modes (synchronizes NTREE and PARSIMONY)
    • branch analysis
      • display number of multifurcations in 'mark long branches'
      • display "in-tree-distance" and "per-species-distance"
    • added function to toggle '100%' bootstraps
    • document bug in GBT_remove_leafs (#452)
  • adds:
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 4.9 KB
Line 
1// ============================================================= //
2//                                                               //
3//   File      : CT_ctree.cxx                                    //
4//   Purpose   : consensus tree                                  //
5//                                                               //
6//   Institute of Microbiology (Technical University Munich)     //
7//   http://www.arb-home.de/                                     //
8//                                                               //
9// ============================================================= //
10
11#include "CT_ctree.hxx"
12#include "CT_hash.hxx"
13#include "CT_ntree.hxx"
14#include <arb_strbuf.h>
15
16ConsensusTree::ConsensusTree(const CharPtrArray& names_)
17    : overall_weight(0),
18      Name_hash(NULL),
19      size(NULL),
20      names(names_),
21      insertProgress(NULL)
22{
23    // names = leafnames (=species names)
24
25    int leaf_count = names.size();
26    Name_hash = GBS_create_hash(leaf_count, GB_MIND_CASE);
27    for (int i=0; i< leaf_count; i++) {
28        GBS_write_hash(Name_hash, names[i], i+1);
29    }
30
31    size       = new PartitionSize(leaf_count);
32    allSpecies = size->create_root();
33    registry   = new PartRegistry;
34}
35
36ConsensusTree::~ConsensusTree() {
37    arb_assert(!insertProgress);
38
39    delete registry;
40    delete allSpecies;
41    delete size;
42
43    if (Name_hash) {
44        GBS_free_hash(Name_hash);
45        Name_hash  = 0;
46    }
47}
48
49GB_ERROR ConsensusTree::insert_tree_weighted(const GBT_TREE *tree, int leafs, double weight, bool provideProgress) {
50    // Insert a GBT-tree in the Hash-Table
51    // The GBT-tree is destructed afterwards!
52    arb_assert(GBT_count_leafs(tree) == size_t(leafs));
53
54    overall_weight += weight;
55
56    PART *wholeTree = create_tree_PART(tree, weight);
57    if (wholeTree->get_members() != leafs) {
58        arb_assert(wholeTree->get_members() < leafs);
59        return "tree contains duplicated species";
60    }
61
62    if (provideProgress) {
63        int nodeCount  = leafs_2_nodes(wholeTree->get_members(), ROOTED);
64        insertProgress = new arb_progress(nodeCount);
65    }
66
67    bool contains_all_species = wholeTree->equals(allSpecies);
68
69    if (contains_all_species) {
70        deconstruct_full_rootnode(tree, weight);
71    }
72    else {
73        deconstruct_partial_rootnode(tree, weight, wholeTree);
74    }
75
76    if (provideProgress) {
77        delete insertProgress;
78        insertProgress = NULL;
79    }
80
81    delete wholeTree;
82    return NULL;
83}
84
85SizeAwareTree *ConsensusTree::get_consensus_tree(GB_ERROR& error) {
86    // Get new consensus-tree -> SizeAwareTree
87
88    /* This function is little bit tricky:
89       the root-partition consist of 111....111 so it must have two sons
90       that represent the same partition son1 == ~son2 to do this we must split
91       the fist son-partition in two parts through logical calculation there
92       could only be one son! */
93
94    arb_assert(!error);
95    ntree_init(size);
96
97    registry->build_sorted_list(overall_weight);
98
99    arb_progress progress(registry->size()+2);
100    {
101#if defined(DUMP_PART_INSERTION)
102        PART::start_pretty_printing(names);
103#endif
104
105        PART *p = registry->get_part();
106        while (p != NULL && !progress.aborted()) {
107            insert_ntree(p);
108            ++progress;
109            p = registry->get_part();
110        }
111
112#if defined(DUMP_PART_INSERTION)
113        PART::stop_pretty_printing();
114#endif
115    }
116
117    SizeAwareTree *result_tree = NULL;
118
119    error = progress.error_if_aborted();
120    if (!error) {
121        const NT_NODE *n = ntree_get();
122
123        arb_assert(ntree_count_sons(n) == 2);
124
125#if defined(NTREE_DEBUG_FUNCTIONS)
126        arb_assert(is_well_formed(n));
127#endif
128
129        result_tree = rb_gettree(n);
130
131        ++progress;
132
133        result_tree->get_tree_root()->find_innermost_edge().set_root();
134        result_tree->reorder_tree(BIG_BRANCHES_TO_BOTTOM);
135
136        ++progress;
137    }
138
139    ntree_cleanup();
140    arb_assert(contradicted(result_tree, error));
141    return result_tree;
142}
143
144
145char *ConsensusTreeBuilder::get_remark() const {
146    GBS_strstruct remark(1000);
147    {
148        char *build_info = GBS_global_string_copy("ARB consensus tree build from %zu trees:", tree_info.size());
149        char *dated      = GBS_log_dated_action_to(NULL, build_info);
150        remark.cat(dated);
151        free(dated);
152        free(build_info);
153    }
154
155    size_t allCount = species_count();
156
157    size_t maxnamelen = 0;
158    for (size_t t = 0; t<tree_info.size(); ++t) {
159        maxnamelen = std::max(maxnamelen, strlen(tree_info[t].name()));
160    }
161    for (size_t t = 0; t<tree_info.size(); ++t) {
162        const TreeInfo& tree = tree_info[t];
163        remark.cat(" - ");
164        remark.nprintf(maxnamelen, "%-*s", int(maxnamelen), tree.name());
165        if (tree.species_count()<allCount) {
166            double pc = tree.species_count() / double(allCount);
167            remark.nprintf(50, " (%.1f%%; %zu/%zu)", pc*100.0, tree.species_count(), allCount);
168        }
169        remark.put('\n');
170    }
171
172    return remark.release();
173}
Note: See TracBrowser for help on using the repository browser.