1 | // =============================================================== // |
---|
2 | // // |
---|
3 | // File : AP_tree_nlen.cxx // |
---|
4 | // Purpose : // |
---|
5 | // // |
---|
6 | // Coded by Ralf Westram (coder@reallysoft.de) in Summer 1995 // |
---|
7 | // Institute of Microbiology (Technical University Munich) // |
---|
8 | // http://www.arb-home.de/ // |
---|
9 | // // |
---|
10 | // =============================================================== // |
---|
11 | |
---|
12 | #include "ap_tree_nlen.hxx" |
---|
13 | #include "pars_debug.hxx" |
---|
14 | |
---|
15 | #include <AP_seq_dna.hxx> |
---|
16 | #include <aw_root.hxx> |
---|
17 | |
---|
18 | using namespace std; |
---|
19 | |
---|
20 | // --------------------------------- |
---|
21 | // Section base operations: |
---|
22 | // --------------------------------- |
---|
23 | |
---|
24 | AP_UPDATE_FLAGS AP_tree_nlen::check_update() { |
---|
25 | AP_UPDATE_FLAGS res = AP_tree::check_update(); |
---|
26 | |
---|
27 | return res == AP_UPDATE_RELOADED ? AP_UPDATE_OK : res; |
---|
28 | } |
---|
29 | |
---|
30 | void AP_tree_nlen::copy(AP_tree_nlen *tree) { |
---|
31 | // like = operator |
---|
32 | // but copies sequence if is leaf |
---|
33 | |
---|
34 | this->is_leaf = tree->is_leaf; |
---|
35 | this->leftlen = tree->leftlen; |
---|
36 | this->rightlen = tree->rightlen; |
---|
37 | this->gb_node = tree->gb_node; |
---|
38 | |
---|
39 | if (tree->name != NULL) { |
---|
40 | this->name = strdup(tree->name); |
---|
41 | } |
---|
42 | else { |
---|
43 | this->name = NULL; |
---|
44 | } |
---|
45 | |
---|
46 | if (is_leaf) { |
---|
47 | ap_assert(tree->get_seq()); /* oops - AP_tree_nlen expects to have sequences at leafs! |
---|
48 | * did you forget to remove_leafs() ? */ |
---|
49 | |
---|
50 | set_seq(tree->get_seq()); |
---|
51 | // dangerous - no copy, just moves pointer |
---|
52 | // will result in undefined behavior |
---|
53 | |
---|
54 | ap_assert(0); // this will not work, but is only used in GA_genetic. |
---|
55 | // Use some kind of SmartPtr there! |
---|
56 | } |
---|
57 | } |
---|
58 | |
---|
59 | ostream& operator<<(ostream& out, const AP_tree_nlen& node) { |
---|
60 | out << ' '; |
---|
61 | |
---|
62 | if (&node==NULL) { |
---|
63 | out << "NULL"; |
---|
64 | } |
---|
65 | if (node.is_leaf) { |
---|
66 | out << ((void *)&node) << '(' << node.name << ')'; |
---|
67 | } |
---|
68 | else { |
---|
69 | static int notTooDeep; |
---|
70 | |
---|
71 | if (notTooDeep) { |
---|
72 | out << ((void *)&node); |
---|
73 | if (!node.father) out << " (ROOT)"; |
---|
74 | } |
---|
75 | else { |
---|
76 | notTooDeep = 1; |
---|
77 | |
---|
78 | out << "NODE(" << ((void *)&node); |
---|
79 | |
---|
80 | if (!node.father) { |
---|
81 | out << " (ROOT)"; |
---|
82 | } |
---|
83 | else { |
---|
84 | out << ", father=" << node.father; |
---|
85 | } |
---|
86 | |
---|
87 | out << ", leftson=" << node.leftson |
---|
88 | << ", rightson=" << node.rightson |
---|
89 | << ", edge[0]=" << *(node.edge[0]) |
---|
90 | << ", edge[1]=" << *(node.edge[1]) |
---|
91 | << ", edge[2]=" << *(node.edge[2]) |
---|
92 | << ")"; |
---|
93 | |
---|
94 | notTooDeep = 0; |
---|
95 | } |
---|
96 | } |
---|
97 | |
---|
98 | return out << ' '; |
---|
99 | } |
---|
100 | |
---|
101 | int AP_tree_nlen::unusedEdgeIndex() const { |
---|
102 | for (int e=0; e<3; e++) if (edge[e]==NULL) return e; |
---|
103 | return -1; |
---|
104 | } |
---|
105 | |
---|
106 | AP_tree_edge* AP_tree_nlen::edgeTo(const AP_tree_nlen *neighbour) const { |
---|
107 | for (int e=0; e<3; e++) { |
---|
108 | if (edge[e]!=NULL && edge[e]->node[1-index[e]]==neighbour) { |
---|
109 | return edge[e]; |
---|
110 | } |
---|
111 | } |
---|
112 | return NULL; |
---|
113 | } |
---|
114 | |
---|
115 | AP_tree_edge* AP_tree_nlen::nextEdge(const AP_tree_edge *afterThatEdge) const { |
---|
116 | /*! @return one edge of 'this' |
---|
117 | * |
---|
118 | * @param afterThatEdge |
---|
119 | * - if == NULL -> returns the "first" edge (edge[0]) |
---|
120 | * - otherwise -> returns the next edge following 'afterThatEdge' in the array edge[] |
---|
121 | */ |
---|
122 | return edge[afterThatEdge ? ((indexOf(afterThatEdge)+1) % 3) : 0]; |
---|
123 | } |
---|
124 | |
---|
125 | void AP_tree_nlen::unlinkAllEdges(AP_tree_edge **edgePtr1, AP_tree_edge **edgePtr2, AP_tree_edge **edgePtr3) |
---|
126 | { |
---|
127 | ap_assert(edge[0]!=NULL); |
---|
128 | ap_assert(edge[1]!=NULL); |
---|
129 | ap_assert(edge[2]!=NULL); |
---|
130 | |
---|
131 | *edgePtr1 = edge[0]->unlink(); |
---|
132 | *edgePtr2 = edge[1]->unlink(); |
---|
133 | *edgePtr3 = edge[2]->unlink(); |
---|
134 | } |
---|
135 | |
---|
136 | void AP_tree_nlen::linkAllEdges(AP_tree_edge *edge1, AP_tree_edge *edge2, AP_tree_edge *edge3) |
---|
137 | { |
---|
138 | ap_assert(edge[0]==NULL); |
---|
139 | ap_assert(edge[1]==NULL); |
---|
140 | ap_assert(edge[2]==NULL); |
---|
141 | |
---|
142 | edge1->relink(this, get_father()->get_father() ? get_father() : get_brother()); |
---|
143 | edge2->relink(this, get_leftson()); |
---|
144 | edge3->relink(this, get_rightson()); |
---|
145 | } |
---|
146 | |
---|
147 | // ----------------------------- |
---|
148 | // Check tree structure |
---|
149 | |
---|
150 | #if defined(PROVIDE_TREE_STRUCTURE_TESTS) |
---|
151 | |
---|
152 | inline const AP_tree_edge *edge_between(const AP_tree_nlen *node1, const AP_tree_nlen *node2) { |
---|
153 | AP_tree_edge *edge_12 = node1->edgeTo(node2); |
---|
154 | |
---|
155 | #if defined(ASSERTION_USED) |
---|
156 | AP_tree_edge *edge_21 = node2->edgeTo(node1); |
---|
157 | ap_assert(edge_12 == edge_21); // nodes should agree about their edge |
---|
158 | #endif |
---|
159 | |
---|
160 | return edge_12; |
---|
161 | } |
---|
162 | |
---|
163 | void AP_tree_nlen::assert_edges_valid() const { |
---|
164 | if (get_father()) { // root has no edges |
---|
165 | if (get_father()->is_root_node()) { // sons of root have one edge between them |
---|
166 | ap_assert(edge_between(this, get_brother())); |
---|
167 | } |
---|
168 | else { |
---|
169 | ap_assert(edge_between(this, get_father())); |
---|
170 | if (!is_leaf) { |
---|
171 | ap_assert(edge_between(this, get_leftson())); |
---|
172 | ap_assert(edge_between(this, get_rightson())); |
---|
173 | } |
---|
174 | } |
---|
175 | } |
---|
176 | |
---|
177 | if (!is_leaf) { |
---|
178 | get_leftson()->assert_edges_valid(); |
---|
179 | get_rightson()->assert_edges_valid(); |
---|
180 | } |
---|
181 | } |
---|
182 | |
---|
183 | void AP_tree_nlen::assert_valid() const { |
---|
184 | ap_assert(this); |
---|
185 | assert_edges_valid(); |
---|
186 | AP_tree::assert_valid(); |
---|
187 | } |
---|
188 | |
---|
189 | #endif // PROVIDE_TREE_STRUCTURE_TESTS |
---|
190 | |
---|
191 | // ------------------------- |
---|
192 | // Tree operations: |
---|
193 | // |
---|
194 | // insert |
---|
195 | // remove |
---|
196 | // swap |
---|
197 | // set_root |
---|
198 | // move |
---|
199 | // costs |
---|
200 | |
---|
201 | |
---|
202 | inline void push_all_upnode_sequences(AP_tree_nlen *nodeBelow) { |
---|
203 | for (AP_tree_nlen *upnode = nodeBelow->get_father(); |
---|
204 | upnode; |
---|
205 | upnode = upnode->get_father()) |
---|
206 | { |
---|
207 | ap_main->push_node(upnode, SEQUENCE); |
---|
208 | } |
---|
209 | } |
---|
210 | |
---|
211 | inline void sortOldestFirst(AP_tree_edge **e1, AP_tree_edge **e2) { |
---|
212 | if ((*e1)->Age() > (*e2)->Age()) { |
---|
213 | swap(*e1, *e2); |
---|
214 | } |
---|
215 | } |
---|
216 | |
---|
217 | inline void sortOldestFirst(AP_tree_edge **e1, AP_tree_edge **e2, AP_tree_edge **e3) { |
---|
218 | sortOldestFirst(e1, e2); |
---|
219 | sortOldestFirst(e2, e3); |
---|
220 | sortOldestFirst(e1, e2); |
---|
221 | } |
---|
222 | |
---|
223 | void AP_tree_nlen::initial_insert(AP_tree_nlen *newBrother, AP_tree_root *troot) { |
---|
224 | // construct initial tree from 'this' and 'newBrother' |
---|
225 | // (both have to be leafs) |
---|
226 | |
---|
227 | ap_assert(newBrother); |
---|
228 | ap_assert(is_leaf); |
---|
229 | ap_assert(newBrother->is_leaf); |
---|
230 | |
---|
231 | AP_tree::initial_insert(newBrother, troot); |
---|
232 | new AP_tree_edge(newBrother, this); // build the root edge |
---|
233 | |
---|
234 | ASSERT_VALID_TREE(this->get_father()); |
---|
235 | } |
---|
236 | |
---|
237 | void AP_tree_nlen::insert(AP_tree_nlen *newBrother) { |
---|
238 | // inserts 'this' (a new node) at the father-edge of 'newBrother' |
---|
239 | ap_assert(newBrother); |
---|
240 | |
---|
241 | ASSERT_VALID_TREE(this); |
---|
242 | ASSERT_VALID_TREE(newBrother); |
---|
243 | |
---|
244 | ap_main->push_node(newBrother, STRUCTURE); |
---|
245 | |
---|
246 | AP_tree_nlen *brothersFather = newBrother->get_father(); |
---|
247 | if (brothersFather) { |
---|
248 | ap_main->push_node(brothersFather, BOTH); |
---|
249 | push_all_upnode_sequences(brothersFather); |
---|
250 | |
---|
251 | if (brothersFather->get_father()) { |
---|
252 | AP_tree_edge *oldEdge = newBrother->edgeTo(newBrother->get_father())->unlink(); |
---|
253 | AP_tree::insert(newBrother); |
---|
254 | oldEdge->relink(get_father(), get_father()->get_father()); |
---|
255 | } |
---|
256 | else { // insert to son of root |
---|
257 | AP_tree_edge *oldEdge = newBrother->edgeTo(newBrother->get_brother())->unlink(); |
---|
258 | AP_tree::insert(newBrother); |
---|
259 | oldEdge->relink(get_father(), get_father()->get_brother()); |
---|
260 | } |
---|
261 | |
---|
262 | new AP_tree_edge(this, get_father()); |
---|
263 | new AP_tree_edge(get_father(), newBrother); |
---|
264 | |
---|
265 | ASSERT_VALID_TREE(get_father()->get_father()); |
---|
266 | } |
---|
267 | else { // insert at root |
---|
268 | ap_assert(!newBrother->is_leaf); // either swap 'this' and 'newBrother' or use initial_insert() to construct the initial tree |
---|
269 | |
---|
270 | AP_tree_nlen *lson = newBrother->get_leftson(); |
---|
271 | AP_tree_nlen *rson = newBrother->get_rightson(); |
---|
272 | |
---|
273 | ap_main->push_node(lson, STRUCTURE); |
---|
274 | ap_main->push_node(rson, STRUCTURE); |
---|
275 | |
---|
276 | AP_tree_edge *oldEdge = lson->edgeTo(rson)->unlink(); |
---|
277 | |
---|
278 | AP_tree::insert(newBrother); |
---|
279 | |
---|
280 | oldEdge->relink(this, newBrother); |
---|
281 | new AP_tree_edge(newBrother, rson); |
---|
282 | new AP_tree_edge(newBrother, lson); |
---|
283 | |
---|
284 | ASSERT_VALID_TREE(get_father()); |
---|
285 | } |
---|
286 | } |
---|
287 | |
---|
288 | void AP_tree_nlen::remove() { |
---|
289 | // Removes the node and its father from the tree: |
---|
290 | // |
---|
291 | // grandpa grandpa |
---|
292 | // / / |
---|
293 | // / / |
---|
294 | // father => brother |
---|
295 | // / \ . |
---|
296 | // / \ . |
---|
297 | // this brother |
---|
298 | // |
---|
299 | // One of the edges is relinked between brother and grandpa. |
---|
300 | // The other two edges are lost. This is not very relevant in respect to |
---|
301 | // memory usage because very few remove()s are really performed - the majority |
---|
302 | // is undone by a pop(). |
---|
303 | // In the last case the two unlinked edges will be re-used, cause their |
---|
304 | // memory location was stored in the tree-stack. |
---|
305 | |
---|
306 | AP_tree_nlen *oldBrother = get_brother(); |
---|
307 | |
---|
308 | ASSERT_VALID_TREE(this); |
---|
309 | |
---|
310 | ap_assert(father); // can't remove complete tree, |
---|
311 | |
---|
312 | ap_main->push_node(this, STRUCTURE); |
---|
313 | ap_main->push_node(oldBrother, STRUCTURE); |
---|
314 | push_all_upnode_sequences(get_father()); |
---|
315 | |
---|
316 | AP_tree_edge *oldEdge; |
---|
317 | AP_tree_nlen *grandPa = get_father()->get_father(); |
---|
318 | if (grandPa) { |
---|
319 | ASSERT_VALID_TREE(grandPa); |
---|
320 | |
---|
321 | ap_main->push_node(get_father(), BOTH); |
---|
322 | ap_main->push_node(grandPa, STRUCTURE); |
---|
323 | |
---|
324 | edgeTo(get_father())->unlink(); // LOST_EDGE |
---|
325 | get_father()->edgeTo(oldBrother)->unlink(); // LOST_EDGE |
---|
326 | |
---|
327 | if (grandPa->father) { |
---|
328 | oldEdge = get_father()->edgeTo(grandPa)->unlink(); |
---|
329 | AP_tree::remove(); |
---|
330 | oldEdge->relink(oldBrother, grandPa); |
---|
331 | } |
---|
332 | else { // remove grandson of root |
---|
333 | AP_tree_nlen *uncle = get_father()->get_brother(); |
---|
334 | ap_main->push_node(uncle, STRUCTURE); |
---|
335 | |
---|
336 | oldEdge = get_father()->edgeTo(uncle)->unlink(); |
---|
337 | AP_tree::remove(); |
---|
338 | oldEdge->relink(oldBrother, uncle); |
---|
339 | } |
---|
340 | ASSERT_VALID_TREE(grandPa); |
---|
341 | } |
---|
342 | else { // remove son of root |
---|
343 | AP_tree_nlen *oldRoot = get_father(); |
---|
344 | ASSERT_VALID_TREE(oldRoot); |
---|
345 | |
---|
346 | if (oldBrother->is_leaf) { |
---|
347 | // root |
---|
348 | // oo |
---|
349 | // o o |
---|
350 | // o o |
---|
351 | // oldBrother --- this -----> NULL |
---|
352 | // |
---|
353 | ap_main->push_node(oldRoot, ROOT); |
---|
354 | |
---|
355 | edgeTo(oldBrother)->unlink(); // LOST_EDGE |
---|
356 | |
---|
357 | #if defined(ASSERTION_USED) |
---|
358 | AP_tree_root *troot = get_tree_root(); |
---|
359 | #endif // ASSERTION_USED |
---|
360 | AP_tree::remove(); |
---|
361 | ap_assert(!troot->get_root_node()); // tree should have been removed |
---|
362 | } |
---|
363 | else { |
---|
364 | // |
---|
365 | // root |
---|
366 | // oo . |
---|
367 | // o o root (=oldBrother) |
---|
368 | // o o oo . |
---|
369 | // oldBrother --- this -----> o o . |
---|
370 | // /\ o o . |
---|
371 | // / \ lson ----- rson |
---|
372 | // / \ . |
---|
373 | // lson rson |
---|
374 | // |
---|
375 | AP_tree_nlen *lson = oldBrother->get_leftson(); |
---|
376 | AP_tree_nlen *rson = oldBrother->get_rightson(); |
---|
377 | |
---|
378 | ap_assert(lson && rson); |
---|
379 | |
---|
380 | ap_main->push_node(lson, STRUCTURE); |
---|
381 | ap_main->push_node(rson, STRUCTURE); |
---|
382 | ap_main->push_node(oldRoot, ROOT); |
---|
383 | |
---|
384 | edgeTo(oldBrother)->unlink(); // LOST_EDGE |
---|
385 | oldBrother->edgeTo(lson)->unlink(); // LOST_EDGE |
---|
386 | |
---|
387 | oldEdge = oldBrother->edgeTo(rson)->unlink(); |
---|
388 | AP_tree::remove(); |
---|
389 | oldEdge->relink(lson, rson); |
---|
390 | |
---|
391 | ap_assert(lson->get_tree_root()->get_root_node() == oldBrother); |
---|
392 | ASSERT_VALID_TREE(oldBrother); |
---|
393 | } |
---|
394 | } |
---|
395 | |
---|
396 | father = NULL; |
---|
397 | set_tree_root(NULL); |
---|
398 | |
---|
399 | ASSERT_VALID_TREE(this); |
---|
400 | } |
---|
401 | |
---|
402 | void AP_tree_nlen::swap_sons() { |
---|
403 | ap_assert(!is_leaf); // cannot swap leafs |
---|
404 | |
---|
405 | ap_main->push_node(this, STRUCTURE); |
---|
406 | AP_tree::swap_sons(); |
---|
407 | } |
---|
408 | |
---|
409 | void AP_tree_nlen::swap_assymetric(AP_TREE_SIDE mode) { |
---|
410 | // mode AP_LEFT exchanges leftson with brother |
---|
411 | // mode AP_RIGHT exchanges rightson with brother |
---|
412 | |
---|
413 | ap_assert(!is_leaf); // cannot swap leafs |
---|
414 | ap_assert(father); // cannot swap root (has no brother) |
---|
415 | ap_assert(mode == AP_LEFT || mode == AP_RIGHT); // illegal mode |
---|
416 | |
---|
417 | AP_tree_nlen *oldBrother = get_brother(); |
---|
418 | AP_tree_nlen *movedSon = mode == AP_LEFT ? get_leftson() : get_rightson(); |
---|
419 | |
---|
420 | if (!father->father) { |
---|
421 | // son of root case |
---|
422 | // take leftson of brother to exchange with |
---|
423 | |
---|
424 | if (!oldBrother->is_leaf) { // swap needed ? |
---|
425 | AP_tree_nlen *nephew = oldBrother->get_leftson(); |
---|
426 | |
---|
427 | ap_main->push_node(this, BOTH); |
---|
428 | ap_main->push_node(movedSon, STRUCTURE); |
---|
429 | ap_main->push_node(get_father(), SEQUENCE); |
---|
430 | ap_main->push_node(nephew, STRUCTURE); |
---|
431 | ap_main->push_node(oldBrother, BOTH); |
---|
432 | |
---|
433 | AP_tree_edge *edge1 = edgeTo(movedSon)->unlink(); |
---|
434 | AP_tree_edge *edge2 = oldBrother->edgeTo(nephew)->unlink(); |
---|
435 | |
---|
436 | AP_tree::swap_assymetric(mode); |
---|
437 | |
---|
438 | edge1->relink(this, nephew); |
---|
439 | edge2->relink(oldBrother, movedSon); |
---|
440 | } |
---|
441 | } |
---|
442 | else { |
---|
443 | ap_main->push_node(this, BOTH); |
---|
444 | ap_main->push_node(get_father(), BOTH); |
---|
445 | ap_main->push_node(oldBrother, STRUCTURE); |
---|
446 | ap_main->push_node(movedSon, STRUCTURE); |
---|
447 | |
---|
448 | push_all_upnode_sequences(get_father()); |
---|
449 | |
---|
450 | AP_tree_edge *edge1 = edgeTo(movedSon)->unlink(); |
---|
451 | AP_tree_edge *edge2 = get_father()->edgeTo(oldBrother)->unlink(); |
---|
452 | |
---|
453 | AP_tree::swap_assymetric(mode); |
---|
454 | |
---|
455 | edge1->relink(this, oldBrother); |
---|
456 | edge2->relink(get_father(), movedSon); |
---|
457 | } |
---|
458 | } |
---|
459 | |
---|
460 | void AP_tree_nlen::set_root() { |
---|
461 | if (at_root()) return; // already root |
---|
462 | |
---|
463 | // from this to root buffer the nodes |
---|
464 | ap_main->push_node(this, STRUCTURE); |
---|
465 | |
---|
466 | AP_tree_nlen *old_brother = 0; |
---|
467 | AP_tree_nlen *old_root = 0; |
---|
468 | { |
---|
469 | AP_tree_nlen *pntr; |
---|
470 | for (pntr = get_father(); pntr->father; pntr = pntr->get_father()) { |
---|
471 | ap_main->push_node(pntr, BOTH); |
---|
472 | old_brother = pntr; |
---|
473 | } |
---|
474 | old_root = pntr; |
---|
475 | } |
---|
476 | |
---|
477 | if (old_brother) { |
---|
478 | old_brother = old_brother->get_brother(); |
---|
479 | ap_main->push_node(old_brother, STRUCTURE); |
---|
480 | } |
---|
481 | |
---|
482 | ap_main->push_node(old_root, ROOT); |
---|
483 | AP_tree::set_root(); |
---|
484 | } |
---|
485 | |
---|
486 | void AP_tree_nlen::moveNextTo(AP_tree_nlen *newBrother, AP_FLOAT rel_pos) { |
---|
487 | ap_assert(father); |
---|
488 | ap_assert(newBrother->father); |
---|
489 | |
---|
490 | ASSERT_VALID_TREE(rootNode()); |
---|
491 | |
---|
492 | // push everything that will be modified onto stack |
---|
493 | ap_main->push_node(this, STRUCTURE); |
---|
494 | ap_main->push_node(get_brother(), STRUCTURE); |
---|
495 | |
---|
496 | if (father->father) { |
---|
497 | AP_tree_nlen *grandpa = get_father()->get_father(); |
---|
498 | |
---|
499 | ap_main->push_node(get_father(), BOTH); |
---|
500 | |
---|
501 | if (grandpa->father) { |
---|
502 | ap_main->push_node(grandpa, BOTH); |
---|
503 | push_all_upnode_sequences(grandpa); |
---|
504 | } |
---|
505 | else { // grandson of root |
---|
506 | ap_main->push_node(grandpa, ROOT); |
---|
507 | ap_main->push_node(get_father()->get_brother(), STRUCTURE); |
---|
508 | } |
---|
509 | } |
---|
510 | else { // son of root |
---|
511 | ap_main->push_node(get_father(), ROOT); |
---|
512 | |
---|
513 | if (!get_brother()->is_leaf) { |
---|
514 | ap_main->push_node(get_brother()->get_leftson(), STRUCTURE); |
---|
515 | ap_main->push_node(get_brother()->get_rightson(), STRUCTURE); |
---|
516 | } |
---|
517 | } |
---|
518 | |
---|
519 | ap_main->push_node(newBrother, STRUCTURE); |
---|
520 | if (newBrother->father) { |
---|
521 | if (newBrother->father->father) { |
---|
522 | ap_main->push_node(newBrother->get_father(), BOTH); |
---|
523 | } |
---|
524 | else { // move to son of root |
---|
525 | ap_main->push_node(newBrother->get_father(), BOTH); |
---|
526 | ap_main->push_node(newBrother->get_brother(), STRUCTURE); |
---|
527 | } |
---|
528 | push_all_upnode_sequences(newBrother->get_father()); |
---|
529 | } |
---|
530 | |
---|
531 | AP_tree_nlen *thisFather = get_father(); |
---|
532 | AP_tree_nlen *grandFather = thisFather->get_father(); |
---|
533 | AP_tree_nlen *oldBrother = get_brother(); |
---|
534 | AP_tree_nlen *newBrothersFather = newBrother->get_father(); |
---|
535 | int edgesChange = ! (father==newBrother || newBrother->father==father); |
---|
536 | AP_tree_edge *e1, *e2, *e3; |
---|
537 | |
---|
538 | if (edgesChange) { |
---|
539 | if (thisFather==newBrothersFather->get_father()) { // son -> son of brother |
---|
540 | if (grandFather) { |
---|
541 | if (grandFather->get_father()) { |
---|
542 | thisFather->unlinkAllEdges(&e1, &e2, &e3); |
---|
543 | AP_tree_edge *e4 = newBrother->edgeTo(oldBrother)->unlink(); |
---|
544 | |
---|
545 | AP_tree::moveNextTo(newBrother, rel_pos); |
---|
546 | |
---|
547 | sortOldestFirst(&e1, &e2, &e3); |
---|
548 | e1->relink(oldBrother, grandFather); // use oldest edge at remove position |
---|
549 | thisFather->linkAllEdges(e2, e3, e4); |
---|
550 | } |
---|
551 | else { // grandson of root -> son of brother |
---|
552 | AP_tree_nlen *uncle = thisFather->get_brother(); |
---|
553 | |
---|
554 | thisFather->unlinkAllEdges(&e1, &e2, &e3); |
---|
555 | AP_tree_edge *e4 = newBrother->edgeTo(oldBrother)->unlink(); |
---|
556 | |
---|
557 | AP_tree::moveNextTo(newBrother, rel_pos); |
---|
558 | |
---|
559 | sortOldestFirst(&e1, &e2, &e3); |
---|
560 | e1->relink(oldBrother, uncle); |
---|
561 | thisFather->linkAllEdges(e2, e3, e4); |
---|
562 | } |
---|
563 | } |
---|
564 | else { // son of root -> grandson of root |
---|
565 | oldBrother->unlinkAllEdges(&e1, &e2, &e3); |
---|
566 | AP_tree::moveNextTo(newBrother, rel_pos); |
---|
567 | thisFather->linkAllEdges(e1, e2, e3); |
---|
568 | } |
---|
569 | } |
---|
570 | else if (grandFather==newBrothersFather) { // son -> brother of father |
---|
571 | if (grandFather->father) { |
---|
572 | thisFather->unlinkAllEdges(&e1, &e2, &e3); |
---|
573 | AP_tree_edge *e4 = grandFather->edgeTo(newBrother)->unlink(); |
---|
574 | |
---|
575 | AP_tree::moveNextTo(newBrother, rel_pos); |
---|
576 | |
---|
577 | sortOldestFirst(&e1, &e2, &e3); |
---|
578 | e1->relink(oldBrother, grandFather); |
---|
579 | thisFather->linkAllEdges(e2, e3, e4); |
---|
580 | } |
---|
581 | else { // no edges change if we move grandson of root -> son of root |
---|
582 | AP_tree::moveNextTo(newBrother, rel_pos); |
---|
583 | } |
---|
584 | } |
---|
585 | else { |
---|
586 | // now we are sure, the minimal distance |
---|
587 | // between 'this' and 'newBrother' is 4 edges |
---|
588 | // or if the root-edge is between them, the |
---|
589 | // minimal distance is 3 edges |
---|
590 | |
---|
591 | if (!grandFather) { // son of root |
---|
592 | oldBrother->unlinkAllEdges(&e1, &e2, &e3); |
---|
593 | AP_tree_edge *e4 = newBrother->edgeTo(newBrothersFather)->unlink(); |
---|
594 | |
---|
595 | AP_tree::moveNextTo(newBrother, rel_pos); |
---|
596 | |
---|
597 | sortOldestFirst(&e1, &e2, &e3); |
---|
598 | e1->relink(oldBrother->get_leftson(), oldBrother->get_rightson()); // new root-edge |
---|
599 | thisFather->linkAllEdges(e2, e3, e4); // old root |
---|
600 | } |
---|
601 | else if (!grandFather->get_father()) { // grandson of root |
---|
602 | if (newBrothersFather->get_father()->get_father()==NULL) { // grandson of root -> grandson of root |
---|
603 | thisFather->unlinkAllEdges(&e1, &e2, &e3); |
---|
604 | AP_tree_edge *e4 = newBrother->edgeTo(newBrothersFather)->unlink(); |
---|
605 | |
---|
606 | AP_tree::moveNextTo(newBrother, rel_pos); |
---|
607 | |
---|
608 | sortOldestFirst(&e1, &e2, &e3); |
---|
609 | e1->relink(oldBrother, newBrothersFather); // new root-edge |
---|
610 | thisFather->linkAllEdges(e2, e3, e4); |
---|
611 | } |
---|
612 | else { |
---|
613 | AP_tree_nlen *uncle = thisFather->get_brother(); |
---|
614 | |
---|
615 | thisFather->unlinkAllEdges(&e1, &e2, &e3); |
---|
616 | AP_tree_edge *e4 = newBrother->edgeTo(newBrothersFather)->unlink(); |
---|
617 | |
---|
618 | AP_tree::moveNextTo(newBrother, rel_pos); |
---|
619 | |
---|
620 | sortOldestFirst(&e1, &e2, &e3); |
---|
621 | e1->relink(oldBrother, uncle); |
---|
622 | thisFather->linkAllEdges(e2, e3, e4); |
---|
623 | } |
---|
624 | } |
---|
625 | else { |
---|
626 | if (newBrothersFather->get_father()==NULL) { // move to son of root |
---|
627 | AP_tree_nlen *newBrothersBrother = newBrother->get_brother(); |
---|
628 | |
---|
629 | thisFather->unlinkAllEdges(&e1, &e2, &e3); |
---|
630 | AP_tree_edge *e4 = newBrother->edgeTo(newBrothersBrother)->unlink(); |
---|
631 | |
---|
632 | AP_tree::moveNextTo(newBrother, rel_pos); |
---|
633 | |
---|
634 | sortOldestFirst(&e1, &e2, &e3); |
---|
635 | e1->relink(oldBrother, grandFather); |
---|
636 | thisFather->linkAllEdges(e2, e3, e4); |
---|
637 | } |
---|
638 | else { // simple independent move |
---|
639 | thisFather->unlinkAllEdges(&e1, &e2, &e3); |
---|
640 | AP_tree_edge *e4 = newBrother->edgeTo(newBrothersFather)->unlink(); |
---|
641 | |
---|
642 | AP_tree::moveNextTo(newBrother, rel_pos); |
---|
643 | |
---|
644 | sortOldestFirst(&e1, &e2, &e3); |
---|
645 | e1->relink(oldBrother, grandFather); |
---|
646 | thisFather->linkAllEdges(e2, e3, e4); |
---|
647 | } |
---|
648 | } |
---|
649 | } |
---|
650 | } |
---|
651 | else { // edgesChange==0 |
---|
652 | AP_tree::moveNextTo(newBrother, rel_pos); |
---|
653 | } |
---|
654 | |
---|
655 | ASSERT_VALID_TREE(this); |
---|
656 | ASSERT_VALID_TREE(rootNode()); |
---|
657 | } |
---|
658 | |
---|
659 | void AP_tree_nlen::unhash_sequence() { |
---|
660 | /*! removes the parsimony sequence from an inner node |
---|
661 | * (has no effect for leafs) |
---|
662 | */ |
---|
663 | |
---|
664 | AP_sequence *sequence = get_seq(); |
---|
665 | if (sequence && !is_leaf) sequence->forget_sequence(); |
---|
666 | } |
---|
667 | |
---|
668 | bool AP_tree_nlen::clear(unsigned long datum, unsigned long user_buffer_count) { |
---|
669 | // returns |
---|
670 | // - true if the first element is removed |
---|
671 | // - false if it is copied into the previous level |
---|
672 | // according if user_buffer is greater than datum (wot?) |
---|
673 | |
---|
674 | if (stack_level != datum) { |
---|
675 | ap_assert(0); // internal control number check failed |
---|
676 | return false; |
---|
677 | } |
---|
678 | |
---|
679 | AP_tree_buffer * buff = stack.pop(); |
---|
680 | bool result; |
---|
681 | |
---|
682 | if (buff->controll == datum - 1 || user_buffer_count >= datum) { |
---|
683 | // previous node is buffered |
---|
684 | |
---|
685 | if (buff->mode & SEQUENCE) delete buff->sequence; |
---|
686 | |
---|
687 | stack_level = buff->controll; |
---|
688 | delete buff; |
---|
689 | result = true; |
---|
690 | } |
---|
691 | else { |
---|
692 | stack_level = datum - 1; |
---|
693 | stack.push(buff); |
---|
694 | result = false; |
---|
695 | } |
---|
696 | |
---|
697 | return result; |
---|
698 | } |
---|
699 | |
---|
700 | |
---|
701 | bool AP_tree_nlen::push(AP_STACK_MODE mode, unsigned long datum) { |
---|
702 | // according to mode |
---|
703 | // tree_structure or sequence is buffered in the node |
---|
704 | |
---|
705 | AP_tree_buffer *new_buff; |
---|
706 | bool ret; |
---|
707 | |
---|
708 | if (is_leaf && !(STRUCTURE & mode)) return false; // tips push only structure |
---|
709 | |
---|
710 | if (this->stack_level == datum) { |
---|
711 | AP_tree_buffer *last_buffer = stack.get_first(); |
---|
712 | AP_sequence *sequence = get_seq(); |
---|
713 | |
---|
714 | if (sequence && (mode & SEQUENCE)) sequence->forget_sequence(); |
---|
715 | if (0 == (mode & ~last_buffer->mode)) { // already buffered |
---|
716 | return false; |
---|
717 | } |
---|
718 | new_buff = last_buffer; |
---|
719 | ret = false; |
---|
720 | } |
---|
721 | else { |
---|
722 | new_buff = new AP_tree_buffer; |
---|
723 | new_buff->count = 1; |
---|
724 | new_buff->controll = stack_level; |
---|
725 | new_buff->mode = NOTHING; |
---|
726 | |
---|
727 | stack.push(new_buff); |
---|
728 | this->stack_level = datum; |
---|
729 | ret = true; |
---|
730 | } |
---|
731 | |
---|
732 | if ((mode & STRUCTURE) && !(new_buff->mode & STRUCTURE)) { |
---|
733 | new_buff->father = get_father(); |
---|
734 | new_buff->leftson = get_leftson(); |
---|
735 | new_buff->rightson = get_rightson(); |
---|
736 | new_buff->leftlen = leftlen; |
---|
737 | new_buff->rightlen = rightlen; |
---|
738 | new_buff->root = get_tree_root(); |
---|
739 | new_buff->gb_node = gb_node; |
---|
740 | new_buff->distance = distance; |
---|
741 | |
---|
742 | for (int e=0; e<3; e++) { |
---|
743 | new_buff->edge[e] = edge[e]; |
---|
744 | new_buff->edgeIndex[e] = index[e]; |
---|
745 | if (edge[e]) { |
---|
746 | new_buff->edgeData[e] = edge[e]->data; |
---|
747 | } |
---|
748 | } |
---|
749 | } |
---|
750 | |
---|
751 | if ((mode & SEQUENCE) && !(new_buff->mode & SEQUENCE)) { |
---|
752 | AP_sequence *sequence = take_seq(); |
---|
753 | new_buff->sequence = sequence; |
---|
754 | new_buff->mutation_rate = mutation_rate; |
---|
755 | mutation_rate = 0.0; |
---|
756 | } |
---|
757 | |
---|
758 | new_buff->mode = (AP_STACK_MODE)(new_buff->mode|mode); |
---|
759 | |
---|
760 | return ret; |
---|
761 | } |
---|
762 | |
---|
763 | void AP_tree_nlen::pop(unsigned long IF_ASSERTION_USED(datum)) { // pop old tree costs |
---|
764 | ap_assert(stack_level == datum); // error in node stack |
---|
765 | |
---|
766 | AP_tree_buffer *buff = stack.pop(); |
---|
767 | AP_STACK_MODE mode = buff->mode; |
---|
768 | |
---|
769 | if (mode&STRUCTURE) { |
---|
770 | father = buff->father; |
---|
771 | leftson = buff->leftson; |
---|
772 | rightson = buff->rightson; |
---|
773 | leftlen = buff->leftlen; |
---|
774 | rightlen = buff->rightlen; |
---|
775 | set_tree_root(buff->root); |
---|
776 | gb_node = buff->gb_node; |
---|
777 | distance = buff->distance; |
---|
778 | |
---|
779 | for (int e=0; e<3; e++) { |
---|
780 | edge[e] = buff->edge[e]; |
---|
781 | |
---|
782 | if (edge[e]) { |
---|
783 | index[e] = buff->edgeIndex[e]; |
---|
784 | |
---|
785 | edge[e]->index[index[e]] = e; |
---|
786 | edge[e]->node[index[e]] = this; |
---|
787 | edge[e]->data = buff->edgeData[e]; |
---|
788 | } |
---|
789 | } |
---|
790 | } |
---|
791 | |
---|
792 | if (mode&SEQUENCE) { |
---|
793 | replace_seq(buff->sequence); |
---|
794 | mutation_rate = buff->mutation_rate; |
---|
795 | } |
---|
796 | |
---|
797 | if (ROOT==mode) { |
---|
798 | buff->root->change_root(buff->root->get_root_node(), this); |
---|
799 | } |
---|
800 | |
---|
801 | stack_level = buff->controll; |
---|
802 | delete buff; |
---|
803 | } |
---|
804 | |
---|
805 | void AP_tree_nlen::parsimony_rek(char *mutPerSite) { |
---|
806 | AP_sequence *sequence = get_seq(); |
---|
807 | |
---|
808 | if (is_leaf) { |
---|
809 | ap_assert(sequence); // tree w/o aliview? |
---|
810 | sequence->ensure_sequence_loaded(); |
---|
811 | } |
---|
812 | else { |
---|
813 | if (!sequence) { |
---|
814 | sequence = set_seq(get_tree_root()->get_seqTemplate()->dup()); |
---|
815 | ap_assert(sequence); |
---|
816 | } |
---|
817 | |
---|
818 | if (!sequence->got_sequence()) { |
---|
819 | AP_tree_nlen *lson = get_leftson(); |
---|
820 | AP_tree_nlen *rson = get_rightson(); |
---|
821 | |
---|
822 | ap_assert(lson); |
---|
823 | ap_assert(rson); |
---|
824 | |
---|
825 | lson->parsimony_rek(mutPerSite); |
---|
826 | rson->parsimony_rek(mutPerSite); |
---|
827 | |
---|
828 | AP_sequence *lseq = lson->get_seq(); |
---|
829 | AP_sequence *rseq = rson->get_seq(); |
---|
830 | |
---|
831 | ap_assert(lseq); |
---|
832 | ap_assert(rseq); |
---|
833 | |
---|
834 | AP_FLOAT mutations_for_combine = sequence->combine(lseq, rseq, mutPerSite); |
---|
835 | mutation_rate = lson->mutation_rate + rson->mutation_rate + mutations_for_combine; |
---|
836 | } |
---|
837 | } |
---|
838 | } |
---|
839 | |
---|
840 | AP_FLOAT AP_tree_nlen::costs(char *mutPerSite) { |
---|
841 | // returns costs of a tree ( = number of mutations) |
---|
842 | |
---|
843 | ap_assert(get_tree_root()->get_seqTemplate()); // forgot to set_seqTemplate() ? (previously returned 0.0 in this case) |
---|
844 | parsimony_rek(mutPerSite); |
---|
845 | return mutation_rate; |
---|
846 | } |
---|
847 | |
---|
848 | AP_FLOAT AP_tree_nlen::nn_interchange_rek(int deep, AP_BL_MODE mode, bool skip_hidden) |
---|
849 | { |
---|
850 | if (!father) |
---|
851 | { |
---|
852 | return rootEdge()->nni_rek(deep, skip_hidden, mode, NULL); |
---|
853 | } |
---|
854 | |
---|
855 | if (!father->father) |
---|
856 | { |
---|
857 | AP_tree_edge *e = rootEdge(); |
---|
858 | |
---|
859 | return e->nni_rek(deep, skip_hidden, mode, e->otherNode(this)); |
---|
860 | } |
---|
861 | |
---|
862 | return edgeTo(get_father())->nni_rek(deep, skip_hidden, mode, get_father()); |
---|
863 | } |
---|
864 | |
---|
865 | |
---|
866 | void AP_tree_nlen::kernighan_rek(int rek_deep, int *rek_2_width, int rek_2_width_max, const int rek_deep_max, |
---|
867 | double(*function) (double, double *, int), double *param_liste, int param_anz, |
---|
868 | AP_FLOAT pars_best, AP_FLOAT pars_start, AP_FLOAT pars_prev, |
---|
869 | AP_KL_FLAG rek_width_type, bool *abort_flag) |
---|
870 | { |
---|
871 | // |
---|
872 | // rek_deep Rekursionstiefe |
---|
873 | // rek_2_width Verzweigungsgrad |
---|
874 | // neg_counter zaehler fuer die Aeste in denen Kerninghan Lin schon angewendet wurde |
---|
875 | // function Funktion fuer den dynamischen Schwellwert |
---|
876 | // pars_ Verschiedene Parsimonywerte |
---|
877 | |
---|
878 | AP_FLOAT help, pars[8]; |
---|
879 | // acht parsimony werte |
---|
880 | AP_tree_nlen * pars_refpntr[8]; |
---|
881 | // zeiger auf die naechsten Aeste |
---|
882 | int help_ref, pars_ref[8]; |
---|
883 | // referenzen auf die vertauschten parsimonies |
---|
884 | static AP_TREE_SIDE pars_side_ref[8]; |
---|
885 | // linker oder rechter ast |
---|
886 | int i, t, bubblesort_change = 0; |
---|
887 | // |
---|
888 | int rek_width, rek_width_static = 0, rek_width_dynamic = 0; |
---|
889 | AP_FLOAT schwellwert = function(rek_deep, param_liste, param_anz) + pars_start; |
---|
890 | |
---|
891 | // parameterausgabe |
---|
892 | |
---|
893 | if (rek_deep >= rek_deep_max || is_leaf || *abort_flag) return; |
---|
894 | |
---|
895 | // Referenzzeiger auf die vier Kanten und zwei swapmoeglichkeiten initialisieren |
---|
896 | AP_tree_nlen *this_brother = this->get_brother(); |
---|
897 | if (rek_deep == 0) { |
---|
898 | for (i = 0; i < 8; i+=2) { |
---|
899 | pars_side_ref[i] = AP_LEFT; |
---|
900 | pars_side_ref[i+1] = AP_RIGHT; |
---|
901 | } |
---|
902 | pars_refpntr[0] = pars_refpntr[1] = this; |
---|
903 | pars_refpntr[2] = pars_refpntr[3] = 0; |
---|
904 | pars_refpntr[4] = pars_refpntr[5] = 0; |
---|
905 | pars_refpntr[6] = pars_refpntr[7] = 0; |
---|
906 | } |
---|
907 | else { |
---|
908 | pars_refpntr[0] = pars_refpntr[1] = this->get_leftson(); |
---|
909 | pars_refpntr[2] = pars_refpntr[3] = this->get_rightson(); |
---|
910 | if (father->father != 0) { |
---|
911 | // Referenzzeiger falls nicht an der Wurzel |
---|
912 | pars_refpntr[4] = pars_refpntr[5] = this->get_father(); |
---|
913 | pars_refpntr[6] = pars_refpntr[7] = this_brother; |
---|
914 | } |
---|
915 | else { |
---|
916 | // an der Wurzel nehme linken und rechten Sohns des Bruders |
---|
917 | if (!get_brother()->is_leaf) { |
---|
918 | pars_refpntr[4] = pars_refpntr[5] = this_brother->get_leftson(); |
---|
919 | pars_refpntr[6] = pars_refpntr[7] = this_brother->get_rightson(); |
---|
920 | } |
---|
921 | else { |
---|
922 | pars_refpntr[4] = pars_refpntr[5] = 0; |
---|
923 | pars_refpntr[6] = pars_refpntr[7] = 0; |
---|
924 | } |
---|
925 | } |
---|
926 | } |
---|
927 | |
---|
928 | |
---|
929 | if (!father) return; // no kl at root |
---|
930 | |
---|
931 | // |
---|
932 | // parsimony werte bestimmen |
---|
933 | // |
---|
934 | |
---|
935 | // Wurzel setzen |
---|
936 | |
---|
937 | ap_main->push(); |
---|
938 | this->set_root(); |
---|
939 | rootNode()->costs(); |
---|
940 | |
---|
941 | int visited_subtrees = 0; |
---|
942 | int better_subtrees = 0; |
---|
943 | for (i = 0; i < 8; i++) { |
---|
944 | pars_ref[i] = i; |
---|
945 | pars[i] = -1; |
---|
946 | |
---|
947 | if (!pars_refpntr[i]) continue; |
---|
948 | if (pars_refpntr[i]->is_leaf) continue; |
---|
949 | |
---|
950 | // KL recursion was broken (see changeset [11010] for how) |
---|
951 | // - IMO it should only descent into AP_NONE branches (see setters of 'kernighan'-flag) |
---|
952 | // - quick test shows calculation is much faster and results seem to be better. |
---|
953 | if (pars_refpntr[i]->kernighan != AP_NONE) continue; |
---|
954 | |
---|
955 | if (pars_refpntr[i]->gr.hidden) continue; |
---|
956 | if (pars_refpntr[i]->get_father()->gr.hidden) continue; |
---|
957 | |
---|
958 | // nur wenn kein Blatt ist |
---|
959 | ap_main->push(); |
---|
960 | pars_refpntr[i]->swap_assymetric(pars_side_ref[i]); |
---|
961 | pars[i] = rootNode()->costs(); |
---|
962 | if (pars[i] < pars_best) { |
---|
963 | better_subtrees++; |
---|
964 | pars_best = pars[i]; |
---|
965 | rek_width_type = AP_BETTER; |
---|
966 | } |
---|
967 | if (pars[i] < schwellwert) { |
---|
968 | rek_width_dynamic++; |
---|
969 | } |
---|
970 | ap_main->pop(); |
---|
971 | visited_subtrees ++; |
---|
972 | |
---|
973 | } |
---|
974 | // Bubblesort, in pars[0] steht kleinstes element |
---|
975 | // |
---|
976 | // CAUTION! The original parsimonies will be exchanged |
---|
977 | |
---|
978 | |
---|
979 | for (i=7, t=0; t<i; t++) { |
---|
980 | if (pars[t] <0) { |
---|
981 | pars[t] = pars[i]; |
---|
982 | pars_ref[t] = i; |
---|
983 | t--; |
---|
984 | i--; |
---|
985 | } |
---|
986 | } |
---|
987 | |
---|
988 | bubblesort_change = 0; |
---|
989 | for (t = visited_subtrees - 1; t > 0; t--) { |
---|
990 | for (i = 0; i < t; i++) { |
---|
991 | if (pars[i] > pars[i+1]) { |
---|
992 | bubblesort_change = 1; |
---|
993 | help_ref = pars_ref[i]; |
---|
994 | pars_ref[i] = pars_ref[i + 1]; |
---|
995 | pars_ref[i + 1] = help_ref; |
---|
996 | help = pars[i]; |
---|
997 | pars[i] = pars[i + 1]; |
---|
998 | pars[i + 1] = help; |
---|
999 | } |
---|
1000 | } |
---|
1001 | if (bubblesort_change == 0) |
---|
1002 | break; |
---|
1003 | } |
---|
1004 | |
---|
1005 | display_out(pars, visited_subtrees, pars_prev, pars_start, rek_deep); |
---|
1006 | // Darstellen |
---|
1007 | |
---|
1008 | if (rek_deep < rek_2_width_max) rek_width_static = rek_2_width[rek_deep]; |
---|
1009 | else rek_width_static = 1; |
---|
1010 | |
---|
1011 | rek_width = visited_subtrees; |
---|
1012 | if (rek_width_type == AP_BETTER) { |
---|
1013 | rek_width = better_subtrees; |
---|
1014 | } |
---|
1015 | else { |
---|
1016 | if (rek_width_type & AP_STATIC) { |
---|
1017 | if (rek_width> rek_width_static) rek_width = rek_width_static; |
---|
1018 | } |
---|
1019 | if (rek_width_type & AP_DYNAMIK) { |
---|
1020 | if (rek_width> rek_width_dynamic) rek_width = rek_width_dynamic; |
---|
1021 | } |
---|
1022 | else if (!(rek_width_type & AP_STATIC)) { |
---|
1023 | if (rek_width> 1) rek_width = 1; |
---|
1024 | } |
---|
1025 | |
---|
1026 | } |
---|
1027 | |
---|
1028 | if (rek_width > visited_subtrees) rek_width = visited_subtrees; |
---|
1029 | |
---|
1030 | for (i=0; i < rek_width; i++) { |
---|
1031 | ap_main->push(); |
---|
1032 | pars_refpntr[pars_ref[i]]->kernighan = pars_side_ref[pars_ref[i]]; |
---|
1033 | // Markieren |
---|
1034 | pars_refpntr[pars_ref[i]]->swap_assymetric(pars_side_ref[pars_ref[i]]); |
---|
1035 | // vertausche seite |
---|
1036 | rootNode()->parsimony_rek(); |
---|
1037 | switch (rek_width_type) { |
---|
1038 | case AP_BETTER: { |
---|
1039 | // starte kerninghan_rek mit rekursionstiefe 3, statisch |
---|
1040 | bool flag = false; |
---|
1041 | cout << "found better !\n"; |
---|
1042 | pars_refpntr[pars_ref[i]]->kernighan_rek(rek_deep + 1, rek_2_width, |
---|
1043 | rek_2_width_max, rek_deep_max + 4, |
---|
1044 | function, param_liste, param_anz, |
---|
1045 | pars_best, pars_start, pars[i], |
---|
1046 | AP_STATIC, &flag); |
---|
1047 | *abort_flag = true; |
---|
1048 | break; |
---|
1049 | } |
---|
1050 | default: |
---|
1051 | pars_refpntr[pars_ref[i]]->kernighan_rek(rek_deep + 1, rek_2_width, |
---|
1052 | rek_2_width_max, rek_deep_max, |
---|
1053 | function, param_liste, param_anz, |
---|
1054 | pars_best, pars_start, pars[i], |
---|
1055 | rek_width_type, abort_flag); |
---|
1056 | break; |
---|
1057 | } |
---|
1058 | pars_refpntr[pars_ref[i]]->kernighan = AP_NONE; |
---|
1059 | // Demarkieren |
---|
1060 | if (*abort_flag) { |
---|
1061 | cout << " parsimony: " << pars_best << "took: " << i << "\n"; |
---|
1062 | for (i=0; i<visited_subtrees; i++) cout << " " << pars[i]; |
---|
1063 | cout << "\n"; |
---|
1064 | if (!rek_deep) { |
---|
1065 | cout << "NEW RECURSION\n\n"; |
---|
1066 | } |
---|
1067 | cout.flush(); |
---|
1068 | |
---|
1069 | ap_main->clear(); |
---|
1070 | break; |
---|
1071 | } |
---|
1072 | else { |
---|
1073 | ap_main->pop(); |
---|
1074 | } |
---|
1075 | } |
---|
1076 | if (*abort_flag) { // pop/clear wegen set_root |
---|
1077 | ap_main->clear(); |
---|
1078 | } |
---|
1079 | else { |
---|
1080 | ap_main->pop(); |
---|
1081 | } |
---|
1082 | return; |
---|
1083 | } |
---|
1084 | |
---|
1085 | |
---|
1086 | const char* AP_tree_nlen::sortByName() |
---|
1087 | { |
---|
1088 | if (name) return name; // leafs |
---|
1089 | |
---|
1090 | const char *n1 = get_leftson()->sortByName(); |
---|
1091 | const char *n2 = get_rightson()->sortByName(); |
---|
1092 | |
---|
1093 | if (strcmp(n1, n2)<0) return n1; |
---|
1094 | |
---|
1095 | AP_tree::swap_sons(); |
---|
1096 | |
---|
1097 | return n2; |
---|
1098 | } |
---|
1099 | |
---|
1100 | const char *AP_tree_nlen::fullname() const |
---|
1101 | { |
---|
1102 | if (!name) { |
---|
1103 | static char *buffer; |
---|
1104 | char *lName = strdup(get_leftson()->fullname()); |
---|
1105 | char *rName = strdup(get_rightson()->fullname()); |
---|
1106 | int len = strlen(lName)+strlen(rName)+4; |
---|
1107 | |
---|
1108 | if (buffer) free(buffer); |
---|
1109 | |
---|
1110 | buffer = (char*)malloc(len); |
---|
1111 | |
---|
1112 | strcpy(buffer, "["); |
---|
1113 | strcat(buffer, lName); |
---|
1114 | strcat(buffer, ","); |
---|
1115 | strcat(buffer, rName); |
---|
1116 | strcat(buffer, "]"); |
---|
1117 | |
---|
1118 | free(lName); |
---|
1119 | free(rName); |
---|
1120 | |
---|
1121 | return buffer; |
---|
1122 | } |
---|
1123 | |
---|
1124 | return name; |
---|
1125 | } |
---|
1126 | |
---|
1127 | |
---|
1128 | char* AP_tree_nlen::getSequenceCopy() { |
---|
1129 | costs(); |
---|
1130 | |
---|
1131 | AP_sequence_parsimony *pseq = DOWNCAST(AP_sequence_parsimony*, get_seq()); |
---|
1132 | ap_assert(pseq->got_sequence()); |
---|
1133 | |
---|
1134 | size_t len = pseq->get_sequence_length(); |
---|
1135 | char *s = new char[len]; |
---|
1136 | memcpy(s, pseq->get_sequence(), len); |
---|
1137 | |
---|
1138 | return s; |
---|
1139 | } |
---|
1140 | |
---|