source: branches/stable/CONSENSUS_TREE/CT_ntree.cxx

Last change on this file was 11401, checked in by westram, 7 years ago
  • reintegrates 'tree' into 'trunk':
    • consensus trees:
      • support for merging partial trees ("worked" before, but results were crap; implements #65)
      • generated trees are automatically re-rooted and -ordered
      • always list source trees in consensus-tree-comment; show info about partial trees
      • fixed progress bar
    • made GBT_TREE a base class of other tree classes (implements #31)
    • save tree properties in properties (not in DB)
    • new functions 'Remove zombies/marked from ALL trees'
    • tree load/save: layout fixes
    • unit tests
      • added tests for basic tree modifications (PARSIMONY)
    • performance:
      • compute_tree updates tree information in one traversal
      • tree generators are now capable to generate any type of tree (w/o needing to copy it once)
    • bugfixes:
      • NNI (of marked species) was also always performed for colored species
      • centered beautify-order is stable now
      • improved 'search optimal root'
  • adds:
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 9.7 KB
Line 
1// ============================================================= //
2//                                                               //
3//   File      : CT_ntree.cxx                                    //
4//   Purpose   :                                                 //
5//                                                               //
6//   Institute of Microbiology (Technical University Munich)     //
7//   http://www.arb-home.de/                                     //
8//                                                               //
9// ============================================================= //
10
11#include "CT_ntree.hxx"
12#include <arbdbt.h>
13
14// Einen Binaerbaum erzeugen ueber einen Multitree
15
16static NT_NODE *ntree = NULL;
17
18
19const NT_NODE *ntree_get() {
20    // returns the current ntree
21    return ntree;
22}
23
24
25static NT_NODE *new_ntnode(PART*& p) {
26    // build a new node and store the partition p in it
27    NT_NODE *= (NT_NODE *) getmem(sizeof(NT_NODE));
28    n->part     = p;
29    n->son_list = NULL;
30
31    p = NULL;
32    return n;
33}
34
35
36static void del_tree(NT_NODE *tree) {
37    // delete the tree
38    if (tree) {
39        for (NSONS *nsonp = tree->son_list; nsonp;) {
40            NSONS *nson_next = nsonp->next;
41            del_tree(nsonp->node);
42            free(nsonp);
43            nsonp = nson_next;
44        }
45        tree->son_list = NULL;
46
47        // now is leaf
48        delete tree->part;
49        tree->part = NULL;
50        freenull(tree);
51    }
52}
53
54
55void ntree_init(const PartitionSize *registry) {
56    // Initialization of the tree
57    arb_assert(!ntree);              // forgot to call ntree_cleanup ?
58    PART *root = registry->create_root();
59    ntree      = new_ntnode(root); // Set root to completely filled partition
60}
61
62void ntree_cleanup() {
63    // Destruct old tree
64    del_tree(ntree);
65    ntree = NULL;
66}
67
68#if 0
69// test if the tree is already complete (all necessary partitions are inserted)
70static int ntree_cont(int len)
71{
72    return (ntree_count<len);
73}
74#endif
75
76int ntree_count_sons(const NT_NODE *tree) {
77    int sons = 0;
78    if (tree->son_list) {
79        for (NSONS *node = tree->son_list; node; node = node->next) {
80            sons++;
81        }
82    }
83    return sons;
84}
85
86static void move_son(NT_NODE *f_node, NT_NODE *s_node, NSONS *nson) {
87    // Move son from parent-sonlist to new sonlist
88    // nson is pointer on element in parent-sonlist
89    // sonlist is new sonlist where to move in
90
91    // Move out of parent-sonlist
92   
93    if (nson == f_node->son_list) f_node->son_list = f_node->son_list->next;
94    if (nson->prev) nson->prev->next = nson->next;
95    if (nson->next) nson->next->prev = nson->prev;
96
97    // Move in node-sonlist
98    nson->next = s_node->son_list;
99    nson->prev = NULL;
100   
101    if (s_node->son_list) s_node->son_list->prev = nson;
102    s_node->son_list                             = nson;
103}
104
105
106
107static int ins_ntree(NT_NODE *tree, PART*& newpart) {
108    /* Construct a multitree under the constraint,
109     * that the final tree may result in a binary tree.
110     *
111     * To ensure this, it is important to follow two ideas:
112     *
113     * 1. a son only fits below a father
114     *    - if the father has all son-bits set AND
115     *    - the father is different from the son (so it is possible to add a brother)
116     *
117     * 2. brothers are distinct (i.e. they do not share any bits)
118     */
119
120    // Tree is leaf
121    if (!tree->son_list) {
122#if defined(DUMP_PART_INSERTION)
123        fputs("ins_ntree part=", stdout); newpart->print();
124#endif
125
126        tree->son_list       = (NSONS *) getmem(sizeof(NSONS));
127        tree->son_list->node = new_ntnode(newpart);
128
129        return 1;
130    }
131
132    arb_assert(newpart->is_subset_of(tree->part)); // @@@ should be invariant for entering this function (really ensured by caller?)
133
134    // test if part fits under one son of tree. if so, recurse.
135    for (NSONS *nsonp = tree->son_list; nsonp; nsonp=nsonp->next) {
136        const PART *sonpart = nsonp->node->part;
137        if (newpart->is_subset_of(sonpart)) {
138            if (newpart->equals(sonpart)) return 0; // already inserted -> drop
139
140            arb_assert(newpart->is_real_son_of(sonpart));
141            int res = ins_ntree(nsonp->node, newpart);
142            arb_assert(contradicted(newpart, res));
143            return res;
144        }
145    }
146
147    // Now we are sure 'newpart' is not a son (of any of my sons)!
148    // -> Test whether it is a brother of a son
149    // If it is neither brother nor son -> don't fit here
150    for (NSONS *nsonp = tree->son_list; nsonp; nsonp=nsonp->next) {
151        const PART *sonpart = nsonp->node->part;
152        if (sonpart->overlaps_with(newpart)) {
153            if (!sonpart->is_subset_of(newpart)) {
154                arb_assert(newpart);
155                return 0;
156            }
157            arb_assert(sonpart->is_real_son_of(newpart));
158            // accept if nsonp is son of newpart (will be pulled down below)
159        }
160    }
161
162#if defined(DUMP_PART_INSERTION)
163        fputs("ins_ntree part=", stdout); newpart->print();
164#endif
165
166    // Okay, insert part here ...
167    NT_NODE *newntnode = new_ntnode(newpart);
168
169    // Move sons from parent-sonlist into the new sons sonlist
170    {
171        NSONS *nsonp = tree->son_list;
172        while (nsonp) {
173            NSONS      *nsonp_next = nsonp->next;
174            const PART *sonpart    = nsonp->node->part;
175            if (sonpart->is_subset_of(newntnode->part)) {
176                arb_assert(sonpart->is_real_son_of(newntnode->part));
177                move_son(tree, newntnode, nsonp);
178            }
179            nsonp = nsonp_next;
180        }
181    }
182
183    // insert nsons-elem in son-list of father
184    {
185        NSONS *new_son = (NSONS *) getmem(sizeof(NSONS));
186   
187        new_son->node = newntnode;
188        new_son->prev = NULL;
189        new_son->next = tree->son_list;
190
191        if (tree->son_list) tree->son_list->prev = new_son;
192        tree->son_list                           = new_son;
193    }
194
195    arb_assert(!newpart);
196
197    return 1;
198}
199
200
201
202void insert_ntree(PART*& part) {
203    /* Insert a partition in the NTree.
204     *
205     * Tries both representations, normal and inverse partition,  which
206     * represent the two subtrees at both sides of one edge.
207     *
208     * If neither can be inserted, the partition gets dropped.
209     */
210
211    arb_assert(part->is_valid());
212
213    bool firstCall = ntree->son_list == NULL;
214    if (firstCall) {
215        part->set_len(part->get_len()/2); // insert as root-edge -> distribute length
216
217        PART *inverse = part->clone();
218        inverse->invert();
219
220        ASSERT_RESULT(bool, true, ins_ntree(ntree, part));
221        ASSERT_RESULT(bool, true, ins_ntree(ntree, inverse));
222
223        arb_assert(!inverse);
224    }
225    else {
226        if (!ins_ntree(ntree, part)) {
227            part->invert();
228            if (!ins_ntree(ntree, part)) {
229#if defined(DUMP_PART_INSERTION)
230                fputs("insert_ntree drops part=", stdout); part->print();
231#endif
232                delete part; // drop non-fitting partition
233                part = NULL;
234            }
235        }
236    }
237    arb_assert(!part);
238}
239
240// --------------------------------------------------------------------------------
241
242#if defined(NTREE_DEBUG_FUNCTIONS)
243
244inline void do_indent(int indent) {
245    for (int i = 0; i<indent; ++i) fputc(' ', stdout);
246}
247
248void print_ntree(NT_NODE *tree, int indent) {
249    // testfunction to print a NTree
250
251    NSONS *nsonp;
252    if (tree == NULL) {
253        do_indent(indent); 
254        fputs("tree is empty\n", stdout);
255        return;
256    }
257
258    // print father
259    do_indent(indent);
260    fputs("(\n", stdout);
261
262    indent++;
263
264    do_indent(indent);
265    tree->part->print();
266
267    // and sons
268    for (nsonp=tree->son_list; nsonp; nsonp = nsonp->next) {
269        print_ntree(nsonp->node, indent);
270    }
271
272    indent--;
273   
274    do_indent(indent);
275    fputs(")\n", stdout);
276}
277
278#define FAIL_IF_NOT_WELLFORMED
279
280#if defined(FAIL_IF_NOT_WELLFORMED)
281#define SHOW_FAILURE() arb_assert(0)
282#else
283#define SHOW_FAILURE()
284#endif
285
286bool is_well_formed(const NT_NODE *tree) {
287    // checks whether
288    // - tree has sons
289    // - all sons are part of father
290    // - all sons are distinct
291    // - father is sum of sons
292
293    int sons = ntree_count_sons(tree);
294    bool well_formed = true;
295
296    if (!sons) {
297        if (tree->part->get_members() != 1) { // leafs should contain single species
298            well_formed = false;
299            SHOW_FAILURE();
300        }
301    }
302    else {
303        arb_assert(tree->son_list);
304
305        PART *pmerge = 0;
306        for (NSONS *nson = tree->son_list; nson; nson = nson->next) {
307            PART *pson = nson->node->part;
308
309            if (!pson->is_subset_of(tree->part)) {
310                well_formed = false;
311                SHOW_FAILURE(); // son is not a subset of father
312            }
313            if (pmerge) {
314                if (pson->overlaps_with(pmerge)) {
315                    well_formed  = false;
316                    SHOW_FAILURE(); // sons are not distinct
317                }
318                pmerge->add_members_from(pson);
319            }
320            else {
321                pmerge = pson->clone();
322            }
323            if (!is_well_formed(nson->node)) {
324                well_formed = false;
325                SHOW_FAILURE(); // son is not well formed
326            }
327        }
328        arb_assert(pmerge);
329        if (tree->part->differs(pmerge)) {
330            well_formed = false;
331
332#if defined(FAIL_IF_NOT_WELLFORMED)
333            printf("tree with %i sons {\n", sons);
334            for (NSONS *nson = tree->son_list; nson; nson = nson->next) {
335                PART *pson = nson->node->part;
336                fputs("  pson   =", stdout); pson->print();
337            }
338            printf("} end of tree with %i sons\n", sons);
339
340            fputs("tree part=", stdout); tree->part->print();
341            fputs("pmerge   =", stdout); pmerge->print();
342#endif
343            SHOW_FAILURE(); // means: father is not same as sum of sons
344        }
345        delete pmerge;
346    }
347    return well_formed;
348}
349
350#endif
351
Note: See TracBrowser for help on using the repository browser.