TTK
Loading...
Searching...
No Matches
ContourTreeAlignment.cpp
Go to the documentation of this file.
2
3/*
4=====================================================================================================================
5 branch decomposition
6=====================================================================================================================
7*/
8
10
11 // find global minimum
12 std::shared_ptr<ttk::cta::AlignmentNode> minNode = nodes[0];
13 for(size_t i = 1; i < nodes.size(); i++) {
14 if(minNode->scalarValue > nodes[i]->scalarValue)
15 minNode = nodes[i];
16 }
17
18 // find path to global max
19 std::shared_ptr<ttk::cta::AlignmentNode> nextNode
20 = minNode->edgeList[0]->node1.lock() == minNode
21 ? minNode->edgeList[0]->node2.lock()
22 : minNode->edgeList[0]->node1.lock();
23 std::vector<std::shared_ptr<ttk::cta::AlignmentNode>> maxPath_
24 = pathToMax(nextNode, minNode).second;
25 std::vector<std::shared_ptr<ttk::cta::AlignmentNode>> maxPath;
26 maxPath.push_back(minNode);
27 maxPath.insert(maxPath.end(), maxPath_.begin(), maxPath_.end());
28
29 int currID = 0;
30 minNode->branchID = 0;
31 std::stack<std::vector<std::shared_ptr<ttk::cta::AlignmentNode>>> q;
32 q.push(maxPath);
33
34 while(!q.empty()) {
35
36 std::vector<std::shared_ptr<ttk::cta::AlignmentNode>> path = q.top();
37 q.pop();
38
39 for(size_t i = 1; i < path.size() - 1; i++) {
40
41 std::shared_ptr<ttk::cta::AlignmentNode> currNode = path[i];
42
43 for(const auto &cE : currNode->edgeList) {
44
45 std::shared_ptr<ttk::cta::AlignmentNode> cN
46 = (cE->node1.lock()) == currNode ? cE->node2.lock()
47 : cE->node1.lock();
48 if(cN == path[i - 1])
49 continue;
50 if(cN == path[i + 1])
51 continue;
52
53 if(cN->scalarValue > currNode->scalarValue) {
54 std::vector<std::shared_ptr<ttk::cta::AlignmentNode>> newPath_
55 = pathToMax(cN, currNode).second;
56 std::vector<std::shared_ptr<ttk::cta::AlignmentNode>> newPath;
57 newPath.push_back(currNode);
58 newPath.insert(newPath.end(), newPath_.begin(), newPath_.end());
59 q.push(newPath);
60 } else {
61 std::vector<std::shared_ptr<ttk::cta::AlignmentNode>> newPath_
62 = pathToMin(cN, currNode).second;
63 std::vector<std::shared_ptr<ttk::cta::AlignmentNode>> newPath;
64 newPath.push_back(currNode);
65 newPath.insert(newPath.end(), newPath_.begin(), newPath_.end());
66 q.push(newPath);
67 }
68 }
69
70 currNode->branchID = currID;
71 }
72
73 for(const auto &cE : path.back()->edgeList) {
74
75 std::shared_ptr<ttk::cta::AlignmentNode> cN
76 = cE->node1.lock() == path.back() ? cE->node2.lock() : cE->node1.lock();
77 if(cN == path[path.size() - 2])
78 continue;
79
80 if(cN->scalarValue > path.back()->scalarValue) {
81 std::vector<std::shared_ptr<ttk::cta::AlignmentNode>> newPath_
82 = pathToMax(cN, path.back()).second;
83 std::vector<std::shared_ptr<ttk::cta::AlignmentNode>> newPath;
84 newPath.push_back(path.back());
85 newPath.insert(newPath.end(), newPath_.begin(), newPath_.end());
86 q.push(newPath);
87 } else {
88 std::vector<std::shared_ptr<ttk::cta::AlignmentNode>> newPath_
89 = pathToMin(cN, path.back()).second;
90 std::vector<std::shared_ptr<ttk::cta::AlignmentNode>> newPath;
91 newPath.push_back(path.back());
92 newPath.insert(newPath.end(), newPath_.begin(), newPath_.end());
93 q.push(newPath);
94 }
95 }
96
97 path.back()->branchID = currID;
98 currID++;
99 }
100}
101
102std::pair<float, std::vector<std::shared_ptr<ttk::cta::AlignmentNode>>>
104 const std::shared_ptr<ttk::cta::AlignmentNode> &root,
105 const std::shared_ptr<ttk::cta::AlignmentNode> &parent) {
106
107 std::vector<std::shared_ptr<ttk::cta::AlignmentNode>> path;
108 path.push_back(root);
109
110 if(root->edgeList.size() == 1) {
111 return std::make_pair(root->scalarValue, path);
112 }
113
114 std::vector<std::shared_ptr<ttk::cta::AlignmentNode>> bestPath;
115 float bestVal = -FLT_MAX;
116
117 for(const auto &cE : root->edgeList) {
118
119 std::shared_ptr<ttk::cta::AlignmentNode> nextNode
120 = cE->node1.lock() == root ? cE->node2.lock() : cE->node1.lock();
121 if(parent == nextNode)
122 continue;
123 if(nextNode->scalarValue < root->scalarValue)
124 continue;
125
126 auto p = pathToMax(nextNode, root);
127 if(p.first > bestVal) {
128 bestVal = p.first;
129 bestPath = p.second;
130 }
131 }
132
133 path.insert(path.end(), bestPath.begin(), bestPath.end());
134
135 return std::make_pair(bestVal, path);
136}
137
138std::pair<float, std::vector<std::shared_ptr<ttk::cta::AlignmentNode>>>
140 const std::shared_ptr<ttk::cta::AlignmentNode> &root,
141 const std::shared_ptr<ttk::cta::AlignmentNode> &parent) {
142
143 std::vector<std::shared_ptr<ttk::cta::AlignmentNode>> path;
144 path.push_back(root);
145
146 if(root->edgeList.size() == 1) {
147 return std::make_pair(root->scalarValue, path);
148 }
149
150 std::vector<std::shared_ptr<ttk::cta::AlignmentNode>> bestPath;
151 float bestVal = FLT_MAX;
152
153 for(const auto &cE : root->edgeList) {
154
155 std::shared_ptr<ttk::cta::AlignmentNode> nextNode
156 = cE->node1.lock() == root ? cE->node2.lock() : cE->node1.lock();
157 if(parent == nextNode)
158 continue;
159 if(nextNode->scalarValue > root->scalarValue)
160 continue;
161
162 auto p = pathToMin(nextNode, root);
163 if(p.first < bestVal) {
164 bestVal = p.first;
165 bestPath = p.second;
166 }
167 }
168
169 path.insert(path.end(), bestPath.begin(), bestPath.end());
170
171 return std::make_pair(bestVal, path);
172}
173
174/*
175=====================================================================================================================
176 iterated aligning
177=====================================================================================================================
178*/
179
181
183 const std::shared_ptr<ContourTree> &ct) {
184
185 contourtrees.push_back(ct);
186
187 // cancel computation if tree is not binary
188 if(!ct->isBinary())
189 return false;
190
191 // compute initial Alignment from initial contourtree
192
193 std::shared_ptr<ttk::cta::BinaryTree> t = ct->rootAtMax();
194
195 std::queue<std::pair<std::shared_ptr<ttk::cta::BinaryTree>,
196 std::shared_ptr<ttk::cta::AlignmentNode>>>
197 q;
198
199 auto currNode = std::make_shared<ttk::cta::AlignmentNode>();
200 std::shared_ptr<ttk::cta::BinaryTree> currTree;
201
202 currNode->freq = 1;
203 currNode->type = t->type;
204 currNode->branchID = -1;
205 currNode->scalarValue = t->scalarValue;
206
207 currNode->nodeRefs = std::vector<std::pair<int, int>>();
208 currNode->nodeRefs.emplace_back(0, t->nodeRefs[0].second);
209
210 nodes.push_back(currNode);
211
212 q.push(std::make_pair(t, currNode));
213
214 while(!q.empty()) {
215
216 currTree = q.front().first;
217 currNode = q.front().second;
218 q.pop();
219
220 if(currTree->child1 != nullptr) {
221
222 auto childNode = std::make_shared<ttk::cta::AlignmentNode>();
223 childNode->freq = 1;
224 childNode->type = currTree->child1->type;
225 childNode->branchID = -1;
226 childNode->scalarValue = currTree->child1->scalarValue;
227
228 childNode->nodeRefs = std::vector<std::pair<int, int>>();
229 childNode->nodeRefs.emplace_back(0, currTree->child1->nodeRefs[0].second);
230
231 auto childEdge = std::make_shared<ttk::cta::AlignmentEdge>();
232 childEdge->area = currTree->child1->area;
233 childEdge->scalardistance = currTree->child1->scalardistanceParent;
234 childEdge->volume = currTree->child1->volume;
235 childEdge->node1 = currNode;
236 childEdge->node2 = childNode;
237
238 childNode->edgeList.push_back(childEdge);
239 currNode->edgeList.push_back(childEdge);
240
241 nodes.push_back(childNode);
242 arcs.push_back(childEdge);
243
244 q.push(std::make_pair(currTree->child1, childNode));
245 }
246
247 if(currTree->child2 != nullptr) {
248
249 auto childNode = std::make_shared<ttk::cta::AlignmentNode>();
250 childNode->freq = 1;
251 childNode->type = currTree->child2->type;
252 childNode->branchID = -1;
253 childNode->scalarValue = currTree->child2->scalarValue;
254
255 childNode->nodeRefs = std::vector<std::pair<int, int>>();
256 childNode->nodeRefs.emplace_back(0, currTree->child2->nodeRefs[0].second);
257
258 auto childEdge = std::make_shared<ttk::cta::AlignmentEdge>();
259 childEdge->area = currTree->child2->area;
260 childEdge->scalardistance = currTree->child2->scalardistanceParent;
261 childEdge->volume = currTree->child2->volume;
262 childEdge->node1 = currNode;
263 childEdge->node2 = childNode;
264
265 childNode->edgeList.push_back(childEdge);
266 currNode->edgeList.push_back(childEdge);
267
268 nodes.push_back(childNode);
269 arcs.push_back(childEdge);
270
271 q.push(std::make_pair(currTree->child2, childNode));
272 }
273 }
274
275 return true;
276}
277
279 const std::shared_ptr<ContourTree> &ct, int rootIdx) {
280
281 // cancel computation if tree is not binary
282 if(!ct->isBinary())
283 return false;
284
285 contourtrees.push_back(ct);
286
287 // compute initial Alignment from initial contourtree
288
289 std::shared_ptr<ttk::cta::BinaryTree> t = ct->rootAtMax();
290
291 std::queue<std::pair<std::shared_ptr<ttk::cta::BinaryTree>,
292 std::shared_ptr<ttk::cta::AlignmentNode>>>
293 q;
294
295 auto currNode = std::make_shared<ttk::cta::AlignmentNode>();
296 std::shared_ptr<ttk::cta::BinaryTree> currTree;
297
298 currNode->freq = 1;
299 currNode->type = t->type;
300 currNode->branchID = -1;
301 currNode->scalarValue = t->scalarValue;
302
303 currNode->nodeRefs = std::vector<std::pair<int, int>>();
304 currNode->nodeRefs.emplace_back(0, t->nodeRefs[0].second);
305
306 nodes.push_back(currNode);
307
308 q.push(std::make_pair(t, currNode));
309
310 while(!q.empty()) {
311
312 currTree = q.front().first;
313 currNode = q.front().second;
314 q.pop();
315
316 if(currTree->child1 != nullptr) {
317
318 auto childNode = std::make_shared<ttk::cta::AlignmentNode>();
319 childNode->freq = 1;
320 childNode->type = currTree->child1->type;
321 childNode->branchID = -1;
322 childNode->scalarValue = currTree->child1->scalarValue;
323
324 childNode->nodeRefs = std::vector<std::pair<int, int>>();
325 childNode->nodeRefs.emplace_back(0, currTree->child1->nodeRefs[0].second);
326
327 auto childEdge = std::make_shared<ttk::cta::AlignmentEdge>();
328 childEdge->area = currTree->child1->area;
329 childEdge->scalardistance = currTree->child1->scalardistanceParent;
330 childEdge->volume = currTree->child1->volume;
331 childEdge->region = currTree->child1->region;
332 childEdge->node1 = currNode;
333 childEdge->node2 = childNode;
334
335 childEdge->arcRefs = std::vector<std::pair<int, int>>();
336 childEdge->arcRefs.emplace_back(0, currTree->child1->arcRefs[0].second);
337
338 childNode->edgeList.push_back(childEdge);
339 currNode->edgeList.push_back(childEdge);
340
341 nodes.push_back(childNode);
342 arcs.push_back(childEdge);
343
344 q.push(std::make_pair(currTree->child1, childNode));
345 }
346
347 if(currTree->child2 != nullptr) {
348
349 auto childNode = std::make_shared<ttk::cta::AlignmentNode>();
350 childNode->freq = 1;
351 childNode->type = currTree->child2->type;
352 childNode->branchID = -1;
353 childNode->scalarValue = currTree->child2->scalarValue;
354
355 childNode->nodeRefs = std::vector<std::pair<int, int>>();
356 childNode->nodeRefs.emplace_back(0, currTree->child2->nodeRefs[0].second);
357
358 auto childEdge = std::make_shared<ttk::cta::AlignmentEdge>();
359 childEdge->area = currTree->child2->area;
360 childEdge->scalardistance = currTree->child2->scalardistanceParent;
361 childEdge->volume = currTree->child2->volume;
362 childEdge->region = currTree->child2->region;
363 childEdge->node1 = currNode;
364 childEdge->node2 = childNode;
365
366 childEdge->arcRefs = std::vector<std::pair<int, int>>();
367 childEdge->arcRefs.emplace_back(0, currTree->child2->arcRefs[0].second);
368
369 childNode->edgeList.push_back(childEdge);
370 currNode->edgeList.push_back(childEdge);
371
372 nodes.push_back(childNode);
373 arcs.push_back(childEdge);
374
375 q.push(std::make_pair(currTree->child2, childNode));
376 }
377 }
378
379 if(nodes.size() != ct->getGraph().first.size()) {
380 printErr("wtf?");
381 }
382
383 alignmentRoot = nodes[rootIdx];
384 alignmentRootIdx = rootIdx;
385
386 return true;
387}
388
390 const std::shared_ptr<ContourTree> &ct) {
391
392 contourtrees.push_back(ct);
393
394 // cancel computation if tree not binary
395 if(!ct->isBinary())
396 return false;
397
398 // compute optimal alignment between current alignment and new tree
399
400 std::shared_ptr<ttk::cta::BinaryTree> t1, t2;
401
402 std::shared_ptr<ttk::cta::AlignmentTree> res = nullptr;
403 float resVal = FLT_MAX;
404
405 std::vector<std::shared_ptr<ttk::cta::AlignmentNode>> nodes1 = nodes;
406 std::vector<std::shared_ptr<ttk::cta::CTNode>> nodes2 = ct->getGraph().first;
407
408 for(const auto &node1 : nodes1) {
409
410 t1 = this->rootAtNode(node1);
411
412 for(const auto &node2 : nodes2) {
413
414 t2 = ct->rootAtNode(node2);
415
416 // compute matching
417
418 if((node1->type == ttk::cta::maxNode && node2->type == ttk::cta::maxNode)
419 || (node1->type == ttk::cta::minNode
420 && node2->type == ttk::cta::minNode)) {
421
422 std::pair<float, std::shared_ptr<ttk::cta::AlignmentTree>> match
423 = getAlignmentBinary(t1, t2);
424
425 if(match.first < resVal) {
426 resVal = match.first;
427 res = match.second;
428 }
429 }
430 }
431 }
432
433 if(res)
434 computeNewAlignmenttree(res);
435 else {
436 printErr("Alignment computation failed.");
437 return false;
438 }
439
440 return true;
441}
442
444 const std::shared_ptr<ContourTree> &ct) {
445
446 // cancel computation if tree not binary
447 if(!ct->isBinary())
448 return false;
449
450 contourtrees.push_back(ct);
451
452 // compute optimal alignment between current alignment and new tree
453
454 std::shared_ptr<ttk::cta::BinaryTree> t1, t2;
455
456 std::shared_ptr<ttk::cta::AlignmentTree> res = nullptr;
457 float resVal = FLT_MAX;
458
459 std::vector<std::shared_ptr<ttk::cta::CTNode>> nodes2 = ct->getGraph().first;
460
461 t1 = this->rootAtNode(alignmentRoot);
462
463 for(const auto &node2 : nodes2) {
464
465 // compute matching
466
467 if((alignmentRoot->type == ttk::cta::maxNode
468 && node2->type == ttk::cta::maxNode)
469 || (alignmentRoot->type == ttk::cta::minNode
470 && node2->type == ttk::cta::minNode)) {
471
472 t2 = ct->rootAtNode(node2);
473
474 std::pair<float, std::shared_ptr<ttk::cta::AlignmentTree>> match
475 = getAlignmentBinary(t1, t2);
476
477 if(match.first < resVal) {
478 resVal = match.first;
479 res = match.second;
480 }
481 }
482 }
483
484 if(res)
485 computeNewAlignmenttree(res);
486 else {
487 printErr("Alignment computation failed.");
488 return false;
489 }
490
491 alignmentVal += resVal;
492
493 alignmentRoot = nodes[0];
494
495 return true;
496}
497
499 const std::shared_ptr<ttk::cta::AlignmentTree> &res) {
500
501 nodes.clear();
502 arcs.clear();
503
504 std::queue<std::tuple<std::shared_ptr<ttk::cta::AlignmentTree>,
505 std::shared_ptr<ttk::cta::AlignmentNode>,
506 std::vector<std::shared_ptr<ttk::cta::AlignmentEdge>>,
507 std::vector<std::shared_ptr<ttk::cta::AlignmentEdge>>>>
508 q;
509
510 std::shared_ptr<ttk::cta::AlignmentNode> currNode;
511 std::shared_ptr<ttk::cta::AlignmentTree> currTree;
512
513 currNode = std::make_shared<ttk::cta::AlignmentNode>();
514
515 if(res->node1 == nullptr && res->node2 == nullptr) {
516 return;
517 }
518
519 currNode->freq = (res->node1 == nullptr ? 0 : res->node1->freq)
520 + (res->node2 == nullptr ? 0 : res->node2->freq);
521 currNode->type = res->node1 == nullptr ? res->node2->type : res->node1->type;
522 currNode->branchID = -1;
523
524 if(alignmenttreeType == ttk::cta::lastMatchedValue) {
525
526 currNode->scalarValue = res->node2 == nullptr ? res->node1->scalarValue
527 : res->node2->scalarValue;
528
529 currNode->nodeRefs = std::vector<std::pair<int, int>>();
530 if(res->node1 != nullptr)
531 currNode->nodeRefs.insert(currNode->nodeRefs.end(),
532 res->node1->nodeRefs.begin(),
533 res->node1->nodeRefs.end());
534 if(res->node2 != nullptr)
535 currNode->nodeRefs.emplace_back(
536 (int)contourtrees.size() - 1, res->node2->nodeRefs[0].second);
537
538 } else if(alignmenttreeType == ttk::cta::averageValues) {
539
540 currNode->scalarValue = res->node1 == nullptr ? res->node2->scalarValue
541 : res->node2 == nullptr
542 ? res->node1->scalarValue
543 : (res->node1->scalarValue * res->node1->freq
544 + res->node2->scalarValue)
545 / currNode->freq;
546
547 } else {
548
549 if(res->node1 == nullptr)
550 currNode->scalarValue = res->node2->scalarValue;
551 else if(res->node2 == nullptr)
552 currNode->scalarValue = res->node1->scalarValue;
553 else {
554 std::vector<float> values;
555 for(auto p : res->node1->nodeRefs) {
556 values.push_back(
557 contourtrees[p.first]->getGraph().first[p.second]->scalarValue);
558 }
559 values.push_back(res->node2->scalarValue);
560 std::sort(values.begin(), values.end());
561 float newMedian = values[values.size() / 2];
562 currNode->scalarValue = newMedian;
563 }
564 }
565
566 currNode->nodeRefs = std::vector<std::pair<int, int>>();
567 if(res->node1 != nullptr)
568 currNode->nodeRefs.insert(currNode->nodeRefs.end(),
569 res->node1->nodeRefs.begin(),
570 res->node1->nodeRefs.end());
571 if(res->node2 != nullptr)
572 currNode->nodeRefs.emplace_back(
573 (int)contourtrees.size() - 1, res->node2->nodeRefs[0].second);
574
575 nodes.push_back(currNode);
576
577 q.push(std::make_tuple(
578 res, currNode, std::vector<std::shared_ptr<ttk::cta::AlignmentEdge>>(),
579 std::vector<std::shared_ptr<ttk::cta::AlignmentEdge>>()));
580
581 while(!q.empty()) {
582
583 currTree = std::get<0>(q.front());
584 currNode = std::get<1>(q.front());
585 auto openEdgesOld1 = std::get<2>(q.front());
586 auto openEdgesNew1 = std::get<3>(q.front());
587 auto openEdgesOld2 = std::get<2>(q.front());
588 auto openEdgesNew2 = std::get<3>(q.front());
589 q.pop();
590
591 // type 'rootNode' not possible, otherwise has to be caught
592
593 if(currTree->child1 != nullptr) {
594
595 if(currTree->child1->node1 == nullptr
596 && currTree->child1->node2 == nullptr) {
597 continue;
598 }
599
600 auto childNode = std::make_shared<ttk::cta::AlignmentNode>();
601
602 childNode->freq
603 = (currTree->child1->node1 == nullptr ? 0
604 : currTree->child1->node1->freq)
605 + (currTree->child1->node2 == nullptr
606 ? 0
607 : currTree->child1->node2->freq);
608 childNode->type = currTree->child1->node1 == nullptr
609 ? currTree->child1->node2->type
610 : currTree->child1->node1->type;
611
612 childNode->branchID = -1;
613
614 if(alignmenttreeType == ttk::cta::lastMatchedValue) {
615
616 childNode->scalarValue = currTree->child1->node2 == nullptr
617 ? currTree->child1->node1->scalarValue
618 : currTree->child1->node2->scalarValue;
619
620 } else if(alignmenttreeType == ttk::cta::averageValues) {
621
622 childNode->scalarValue = currTree->child1->node1 == nullptr
623 ? currTree->child1->node2->scalarValue
624 : currTree->child1->node2 == nullptr
625 ? currTree->child1->node1->scalarValue
626 : (currTree->child1->node1->scalarValue
627 * currTree->child1->node1->freq
628 + currTree->child1->node2->scalarValue)
629 / childNode->freq;
630
631 } else {
632
633 if(currTree->child1->node1 == nullptr)
634 childNode->scalarValue = currTree->child1->node2->scalarValue;
635 else if(currTree->child1->node2 == nullptr)
636 childNode->scalarValue = currTree->child1->node1->scalarValue;
637 else {
638 std::vector<float> values;
639 for(auto p : currTree->child1->node1->nodeRefs) {
640 values.push_back(
641 contourtrees[p.first]->getGraph().first[p.second]->scalarValue);
642 }
643 values.push_back(res->node2->scalarValue);
644 std::sort(values.begin(), values.end());
645 float newMedian = values[values.size() / 2];
646 childNode->scalarValue = newMedian;
647 }
648 }
649
650 childNode->nodeRefs = std::vector<std::pair<int, int>>();
651 if(currTree->child1->node1 != nullptr)
652 childNode->nodeRefs.insert(childNode->nodeRefs.end(),
653 currTree->child1->node1->nodeRefs.begin(),
654 currTree->child1->node1->nodeRefs.end());
655 if(currTree->child1->node2 != nullptr)
656 childNode->nodeRefs.emplace_back(
657 (int)contourtrees.size() - 1,
658 currTree->child1->node2->nodeRefs[0].second);
659
660 auto childEdge = std::make_shared<ttk::cta::AlignmentEdge>();
661
662 if(alignmenttreeType == ttk::cta::lastMatchedValue) {
663
664 childEdge->area = currTree->child1->node2 == nullptr
665 ? currTree->child1->node1->area
666 : currTree->child1->node2->area;
667
668 childEdge->scalardistance
669 = currTree->child1->node2 == nullptr
670 ? currTree->child1->node1->scalardistanceParent
671 : currTree->child1->node2->scalardistanceParent;
672
673 } else if(alignmenttreeType == ttk::cta::averageValues) {
674
675 childEdge->area
676 = currTree->child1->node1 == nullptr ? currTree->child1->node2->area
677 : currTree->child1->node2 == nullptr
678 ? currTree->child1->node1->area
679 : (currTree->child1->node1->area * currTree->child1->node1->freq
680 + currTree->child1->node2->area)
681 / childNode->freq;
682
683 childEdge->scalardistance
684 = currTree->child1->node1 == nullptr
685 ? currTree->child1->node2->scalardistanceParent
686 : currTree->child1->node2 == nullptr
687 ? currTree->child1->node1->scalardistanceParent
688 : (currTree->child1->node1->scalardistanceParent
689 * currTree->child1->node1->freq
690 + currTree->child1->node2->scalardistanceParent)
691 / childNode->freq;
692
693 } else {
694
695 if(currTree->child1->node1 == nullptr) {
696 childEdge->area = currTree->child1->node2->area;
697 childEdge->scalardistance
698 = currTree->child1->node2->scalardistanceParent;
699 } else if(currTree->child1->node2 == nullptr) {
700 childEdge->area = currTree->child1->node1->scalarValue;
701 childEdge->scalardistance
702 = currTree->child1->node1->scalardistanceParent;
703 } else {
704 std::vector<float> values;
705 for(auto p : currTree->child1->node1->arcRefs) {
706 values.push_back(
707 contourtrees[p.first]->getGraph().second[p.second]->area);
708 }
709 values.push_back(currTree->child1->node2->area);
710 std::sort(values.begin(), values.end());
711 float newMedian = values[values.size() / 2];
712 childEdge->area = newMedian;
713 values.clear();
714 for(auto p : currTree->child1->node1->arcRefs) {
715 values.push_back(contourtrees[p.first]
716 ->getGraph()
717 .second[p.second]
718 ->scalardistance);
719 }
720 values.push_back(currTree->child1->node2->scalardistanceParent);
721 std::sort(values.begin(), values.end());
722 newMedian = values[values.size() / 2];
723 childEdge->scalardistance = newMedian;
724 }
725 }
726
727 childEdge->region = currTree->child1->node2 == nullptr
728 ? currTree->child1->node1->region
729 : currTree->child1->node2->region;
730
731 childEdge->arcRefs = std::vector<std::pair<int, int>>();
732 if(currTree->child1->node1 != nullptr) {
733 for(const auto &e : openEdgesOld1) {
734 e->arcRefs.insert(e->arcRefs.end(),
735 currTree->child1->node1->arcRefs.begin(),
736 currTree->child1->node1->arcRefs.end());
737 }
738 openEdgesOld1.clear();
739 childEdge->arcRefs.insert(childEdge->arcRefs.end(),
740 currTree->child1->node1->arcRefs.begin(),
741 currTree->child1->node1->arcRefs.end());
742 } else
743 openEdgesOld1.push_back(childEdge);
744 if(currTree->child1->node2 != nullptr) {
745 for(const auto &e : openEdgesNew1) {
746 e->arcRefs.emplace_back((int)contourtrees.size() - 1,
747 currTree->child1->node2->arcRefs[0].second);
748 }
749 openEdgesNew1.clear();
750 childEdge->arcRefs.emplace_back(
751 (int)contourtrees.size() - 1,
752 currTree->child1->node2->arcRefs[0].second);
753 } else
754 openEdgesNew1.push_back(childEdge);
755
756 childEdge->volume = childEdge->area * childEdge->scalardistance;
757
758 childEdge->node1 = currNode;
759 childEdge->node2 = childNode;
760
761 childNode->edgeList.push_back(childEdge);
762 currNode->edgeList.push_back(childEdge);
763
764 nodes.push_back(childNode);
765 arcs.push_back(childEdge);
766
767 q.push(std::make_tuple(
768 currTree->child1, childNode, openEdgesOld1, openEdgesNew1));
769 }
770
771 if(currTree->child2 != nullptr) {
772
773 if(currTree->child2->node1 == nullptr
774 && currTree->child2->node2 == nullptr) {
775 continue;
776 }
777
778 auto childNode = std::make_shared<ttk::cta::AlignmentNode>();
779
780 childNode->freq
781 = (currTree->child2->node1 == nullptr ? 0
782 : currTree->child2->node1->freq)
783 + (currTree->child2->node2 == nullptr
784 ? 0
785 : currTree->child2->node2->freq);
786 childNode->type = currTree->child2->node1 == nullptr
787 ? currTree->child2->node2->type
788 : currTree->child2->node1->type;
789
790 childNode->branchID = -1;
791
792 if(alignmenttreeType == ttk::cta::lastMatchedValue) {
793
794 childNode->scalarValue = currTree->child2->node2 == nullptr
795 ? currTree->child2->node1->scalarValue
796 : currTree->child2->node2->scalarValue;
797
798 } else if(alignmenttreeType == ttk::cta::averageValues) {
799
800 childNode->scalarValue = currTree->child2->node1 == nullptr
801 ? currTree->child2->node2->scalarValue
802 : currTree->child2->node2 == nullptr
803 ? currTree->child2->node1->scalarValue
804 : (currTree->child2->node1->scalarValue
805 * currTree->child2->node1->freq
806 + currTree->child2->node2->scalarValue)
807 / childNode->freq;
808
809 } else {
810
811 if(currTree->child2->node1 == nullptr)
812 childNode->scalarValue = currTree->child2->node2->scalarValue;
813 else if(currTree->child2->node2 == nullptr)
814 childNode->scalarValue = currTree->child2->node1->scalarValue;
815 else {
816 std::vector<float> values;
817 for(auto p : currTree->child2->node1->nodeRefs) {
818 values.push_back(
819 contourtrees[p.first]->getGraph().first[p.second]->scalarValue);
820 }
821 values.push_back(res->node2->scalarValue);
822 std::sort(values.begin(), values.end());
823 float newMedian = values[values.size() / 2];
824 childNode->scalarValue = newMedian;
825 }
826 }
827
828 childNode->nodeRefs = std::vector<std::pair<int, int>>();
829 if(currTree->child2->node1 != nullptr)
830 childNode->nodeRefs.insert(childNode->nodeRefs.end(),
831 currTree->child2->node1->nodeRefs.begin(),
832 currTree->child2->node1->nodeRefs.end());
833 if(currTree->child2->node2 != nullptr)
834 childNode->nodeRefs.emplace_back(
835 (int)contourtrees.size() - 1,
836 currTree->child2->node2->nodeRefs[0].second);
837
838 auto childEdge = std::make_shared<ttk::cta::AlignmentEdge>();
839
840 if(alignmenttreeType == ttk::cta::lastMatchedValue) {
841
842 childEdge->area = currTree->child2->node2 == nullptr
843 ? currTree->child2->node1->area
844 : currTree->child2->node2->area;
845
846 childEdge->scalardistance
847 = currTree->child2->node2 == nullptr
848 ? currTree->child2->node1->scalardistanceParent
849 : currTree->child2->node2->scalardistanceParent;
850
851 } else if(alignmenttreeType == ttk::cta::averageValues) {
852
853 childEdge->area
854 = currTree->child2->node1 == nullptr ? currTree->child2->node2->area
855 : currTree->child2->node2 == nullptr
856 ? currTree->child2->node1->area
857 : (currTree->child2->node1->area * currTree->child2->node1->freq
858 + currTree->child2->node2->area)
859 / childNode->freq;
860
861 childEdge->scalardistance
862 = currTree->child2->node1 == nullptr
863 ? currTree->child2->node2->scalardistanceParent
864 : currTree->child2->node2 == nullptr
865 ? currTree->child2->node1->scalardistanceParent
866 : (currTree->child2->node1->scalardistanceParent
867 * currTree->child2->node1->freq
868 + currTree->child2->node2->scalardistanceParent)
869 / childNode->freq;
870
871 } else {
872
873 if(currTree->child2->node1 == nullptr) {
874 childEdge->area = currTree->child2->node2->area;
875 childEdge->scalardistance
876 = currTree->child2->node2->scalardistanceParent;
877 } else if(currTree->child2->node2 == nullptr) {
878 childEdge->area = currTree->child2->node1->scalarValue;
879 childEdge->scalardistance
880 = currTree->child2->node1->scalardistanceParent;
881 } else {
882 std::vector<float> values;
883 for(auto p : currTree->child2->node1->arcRefs) {
884 values.push_back(
885 contourtrees[p.first]->getGraph().second[p.second]->area);
886 }
887 values.push_back(currTree->child2->node2->area);
888 std::sort(values.begin(), values.end());
889 float newMedian = values[values.size() / 2];
890 childEdge->area = newMedian;
891 values.clear();
892 for(auto p : currTree->child2->node1->arcRefs) {
893 values.push_back(contourtrees[p.first]
894 ->getGraph()
895 .second[p.second]
896 ->scalardistance);
897 }
898 values.push_back(currTree->child2->node2->scalardistanceParent);
899 std::sort(values.begin(), values.end());
900 newMedian = values[values.size() / 2];
901 childEdge->scalardistance = newMedian;
902 }
903 }
904
905 childEdge->region = currTree->child2->node2 == nullptr
906 ? currTree->child2->node1->region
907 : currTree->child2->node2->region;
908
909 childEdge->arcRefs = std::vector<std::pair<int, int>>();
910 if(currTree->child2->node1 != nullptr) {
911 for(const auto &e : openEdgesOld2) {
912 e->arcRefs.insert(e->arcRefs.end(),
913 currTree->child2->node1->arcRefs.begin(),
914 currTree->child2->node1->arcRefs.end());
915 }
916 openEdgesOld2.clear();
917 childEdge->arcRefs.insert(childEdge->arcRefs.end(),
918 currTree->child2->node1->arcRefs.begin(),
919 currTree->child2->node1->arcRefs.end());
920 } else
921 openEdgesOld2.push_back(childEdge);
922 if(currTree->child2->node2 != nullptr) {
923 for(const auto &e : openEdgesNew1) {
924 e->arcRefs.emplace_back((int)contourtrees.size() - 1,
925 currTree->child2->node2->arcRefs[0].second);
926 }
927 openEdgesNew2.clear();
928 childEdge->arcRefs.emplace_back(
929 (int)contourtrees.size() - 1,
930 currTree->child2->node2->arcRefs[0].second);
931 } else
932 openEdgesNew2.push_back(childEdge);
933
934 childEdge->volume = childEdge->area * childEdge->scalardistance;
935
936 childEdge->node1 = currNode;
937 childEdge->node2 = childNode;
938
939 childNode->edgeList.push_back(childEdge);
940 currNode->edgeList.push_back(childEdge);
941
942 nodes.push_back(childNode);
943 arcs.push_back(childEdge);
944
945 // q.push(std::make_pair(currTree->child2,childNode));
946 q.push(std::make_tuple(
947 currTree->child2, childNode, openEdgesOld2, openEdgesNew2));
948 }
949 }
950}
951
952/*
953=====================================================================================================================
954 getters and setters
955=====================================================================================================================
956*/
957
959 int idx = 0;
960 for(const auto &node : nodes) {
961 if(node == alignmentRoot)
962 break;
963 idx++;
964 }
965 return idx;
966}
967
968std::vector<std::shared_ptr<ContourTree>>
970
971 return contourtrees;
972}
973
974std::vector<std::pair<std::vector<std::shared_ptr<ttk::cta::CTNode>>,
975 std::vector<std::shared_ptr<ttk::cta::CTEdge>>>>
977
978 std::vector<std::pair<std::vector<std::shared_ptr<ttk::cta::CTNode>>,
979 std::vector<std::shared_ptr<ttk::cta::CTEdge>>>>
980 trees_simplified;
981
982 for(const auto &ct : contourtrees) {
983 trees_simplified.push_back(ct->getGraph());
984 }
985
986 return trees_simplified;
987}
988
989std::pair<std::vector<std::shared_ptr<ttk::cta::AlignmentNode>>,
990 std::vector<std::shared_ptr<ttk::cta::AlignmentEdge>>>
992
993 return std::make_pair(nodes, arcs);
994}
995
996std::shared_ptr<ttk::cta::BinaryTree>
998
999 std::shared_ptr<ttk::cta::AlignmentNode> root = nodes[0];
1000 float maxScalar = FLT_MIN;
1001 for(const auto &node : nodes) {
1002
1003 // if(node->type==maxNode && node->edgeList[0]->scalardistance > maxRange){
1004 if(node->scalarValue > maxScalar) {
1005 root = node;
1006 maxScalar = node->scalarValue;
1007 }
1008 }
1009
1010 return rootAtNode(root);
1011}
1012
1013/*
1014=====================================================================================================================
1015 aligning two trees
1016=====================================================================================================================
1017*/
1018
1019std::pair<float, std::shared_ptr<ttk::cta::AlignmentTree>>
1021 const std::shared_ptr<ttk::cta::BinaryTree> &t1,
1022 const std::shared_ptr<ttk::cta::BinaryTree> &t2) {
1023
1024 // initialize memoization tables
1025 std::vector<std::vector<float>> memT(
1026 t1->size + 1, std::vector<float>(t2->size + 1, -1));
1027 std::vector<std::vector<float>> memF(
1028 t1->size + 1, std::vector<float>(t2->size + 1, -1));
1029
1030 // compute table of distances
1031 float dist = alignTreeBinary(t1, t2, memT, memF);
1032
1033 // backtrace through the table to get the alignment
1034 std::shared_ptr<ttk::cta::AlignmentTree> res
1035 = traceAlignmentTree(t1, t2, memT, memF);
1036
1037 return std::make_pair(dist, res);
1038}
1039
1041 const std::shared_ptr<ttk::cta::BinaryTree> &t1,
1042 const std::shared_ptr<ttk::cta::BinaryTree> &t2,
1043 std::vector<std::vector<float>> &memT,
1044 std::vector<std::vector<float>> &memF) {
1045
1046 // base cases for matching to empty tree
1047
1048 if(t1 == nullptr && t2 == nullptr) {
1049 if(memT[0][0] < 0) {
1050 memT[0][0] = 0;
1051 }
1052 return memT[0][0];
1053 }
1054
1055 else if(t1 == nullptr) {
1056 if(memT[0][t2->id] < 0) {
1057 memT[0][t2->id]
1058 = editCost(nullptr, t2) + alignForestBinary(nullptr, t2, memT, memF);
1059 }
1060 return memT[0][t2->id];
1061 }
1062
1063 else if(t2 == nullptr) {
1064 if(memT[t1->id][0] < 0) {
1065 memT[t1->id][0]
1066 = editCost(t1, nullptr) + alignForestBinary(t1, nullptr, memT, memF);
1067 }
1068 return memT[t1->id][0];
1069 }
1070
1071 // find optimal possible matching in other cases
1072
1073 else {
1074 if(memT[t1->id][t2->id] < 0) {
1075
1076 // match t1 to t2 and then try to match their children
1077 memT[t1->id][t2->id]
1078 = editCost(t1, t2) + alignForestBinary(t1, t2, memT, memF);
1079
1080 // match t1 to blank, one of its children to t2, the other to blank (try
1081 // both children)
1082 if(t1->size > 1)
1083 memT[t1->id][t2->id]
1084 = std::min(editCost(t1, nullptr)
1085 + alignTreeBinary(t1->child2, nullptr, memT, memF)
1086 + alignTreeBinary(t1->child1, t2, memT, memF),
1087 memT[t1->id][t2->id]);
1088 if(t1->size > 1)
1089 memT[t1->id][t2->id]
1090 = std::min(editCost(t1, nullptr)
1091 + alignTreeBinary(t1->child1, nullptr, memT, memF)
1092 + alignTreeBinary(t1->child2, t2, memT, memF),
1093 memT[t1->id][t2->id]);
1094
1095 // match t2 to blank, one of its children to t1, the other to blank (try
1096 // both children)
1097 if(t2->size > 1)
1098 memT[t1->id][t2->id]
1099 = std::min(editCost(nullptr, t2)
1100 + alignTreeBinary(nullptr, t2->child2, memT, memF)
1101 + alignTreeBinary(t1, t2->child1, memT, memF),
1102 memT[t1->id][t2->id]);
1103 if(t2->size > 1)
1104 memT[t1->id][t2->id]
1105 = std::min(editCost(nullptr, t2)
1106 + alignTreeBinary(nullptr, t2->child1, memT, memF)
1107 + alignTreeBinary(t1, t2->child2, memT, memF),
1108 memT[t1->id][t2->id]);
1109 }
1110 return memT[t1->id][t2->id];
1111 }
1112}
1113
1115 const std::shared_ptr<ttk::cta::BinaryTree> &t1,
1116 const std::shared_ptr<ttk::cta::BinaryTree> &t2,
1117 std::vector<std::vector<float>> &memT,
1118 std::vector<std::vector<float>> &memF) {
1119
1120 // base cases for matching to empty tree
1121
1122 if(t1 == nullptr && t2 == nullptr) {
1123 if(memF[0][0] < 0) {
1124 memF[0][0] = 0;
1125 }
1126 return memF[0][0];
1127 }
1128
1129 else if(t1 == nullptr) {
1130 if(memF[0][t2->id] < 0) {
1131 memF[0][t2->id] = 0;
1132 memF[0][t2->id] += alignTreeBinary(nullptr, t2->child1, memT, memF);
1133 memF[0][t2->id] += alignTreeBinary(nullptr, t2->child2, memT, memF);
1134 }
1135 return memF[0][t2->id];
1136 }
1137
1138 else if(t2 == nullptr) {
1139 if(memF[t1->id][0] < 0) {
1140 memF[t1->id][0] = 0;
1141 memF[t1->id][0] += alignTreeBinary(t1->child1, nullptr, memT, memF);
1142 memF[t1->id][0] += alignTreeBinary(t1->child2, nullptr, memT, memF);
1143 }
1144 return memF[t1->id][0];
1145 }
1146
1147 // find optimal possible matching in other cases
1148
1149 else {
1150 if(memF[t1->id][t2->id] < 0) {
1151
1152 memF[t1->id][t2->id] = FLT_MAX;
1153
1154 if(t1->child2 != nullptr && t1->child2->size > 1)
1155 memF[t1->id][t2->id]
1156 = std::min(memF[t1->id][t2->id],
1157 editCost(t1->child2, nullptr)
1158 + alignForestBinary(t1->child2, t2, memT, memF)
1159 + alignTreeBinary(t1->child1, nullptr, memT, memF));
1160 if(t1->child1 != nullptr && t1->child1->size > 1)
1161 memF[t1->id][t2->id]
1162 = std::min(memF[t1->id][t2->id],
1163 editCost(t1->child1, nullptr)
1164 + alignForestBinary(t1->child1, t2, memT, memF)
1165 + alignTreeBinary(t1->child2, nullptr, memT, memF));
1166
1167 if(t2->child2 != nullptr && t2->child2->size > 1)
1168 memF[t1->id][t2->id]
1169 = std::min(memF[t1->id][t2->id],
1170 editCost(nullptr, t2->child2)
1171 + alignForestBinary(t1, t2->child2, memT, memF)
1172 + alignTreeBinary(nullptr, t2->child1, memT, memF));
1173 if(t2->child1 != nullptr && t2->child1->size > 1)
1174 memF[t1->id][t2->id]
1175 = std::min(memF[t1->id][t2->id],
1176 editCost(nullptr, t2->child1)
1177 + alignForestBinary(t1, t2->child1, memT, memF)
1178 + alignTreeBinary(nullptr, t2->child2, memT, memF));
1179
1180 memF[t1->id][t2->id]
1181 = std::min(memF[t1->id][t2->id],
1182 alignTreeBinary(t1->child1, t2->child1, memT, memF)
1183 + alignTreeBinary(t1->child2, t2->child2, memT, memF));
1184 memF[t1->id][t2->id]
1185 = std::min(memF[t1->id][t2->id],
1186 alignTreeBinary(t1->child1, t2->child2, memT, memF)
1187 + alignTreeBinary(t1->child2, t2->child1, memT, memF));
1188 }
1189 return memF[t1->id][t2->id];
1190 }
1191}
1192
1194 const std::shared_ptr<ttk::cta::BinaryTree> &t1,
1195 const std::shared_ptr<ttk::cta::BinaryTree> &t2) {
1196
1197 float v1 = 0, v2 = 0;
1198 if(t1 != nullptr)
1199 v1 = arcMatchMode == ttk::cta::persistence ? t1->scalardistanceParent
1200 : arcMatchMode == ttk::cta::area ? t1->area
1201 : t1->volume;
1202 if(t2 != nullptr)
1203 v2 = arcMatchMode == ttk::cta::persistence ? t2->scalardistanceParent
1204 : arcMatchMode == ttk::cta::area ? t2->area
1205 : t2->volume;
1206
1207 if(arcMatchMode == ttk::cta::overlap) {
1208 // this->printMsg("overlap");
1209 int unionsize = 0;
1210 int intersectionsize = 0;
1211 size_t i = 0;
1212 size_t j = 0;
1213 if(t1 && t2) {
1214 while(i < t1->region.size() && j < t2->region.size()) {
1215 int vi = t1->region[i];
1216 int vj = t2->region[j];
1217 if(vi == vj) {
1218 intersectionsize++;
1219 i++;
1220 j++;
1221 } else if(vi < vj)
1222 i++;
1223 else
1224 j++;
1225 unionsize++;
1226 }
1227 unionsize += i == (t1->region.size()) ? t2->region.size() - j
1228 : t1->region.size() - i;
1229 if(false) {
1230 std::cout << "========================\nRegion 1: ";
1231 for(size_t k = 0; k < t1->region.size(); k++)
1232 std::cout << t1->region[k] << " ";
1233 std::cout << std::endl;
1234 std::cout << "Region 2: ";
1235 for(size_t k = 0; k < t2->region.size(); k++)
1236 std::cout << t2->region[k] << " ";
1237 std::cout << std::endl;
1238 std::cout << "Intersection size: " << intersectionsize
1239 << "\nUnion size: " << unionsize << std::endl;
1240 }
1241 }
1242
1243 if(t1 == nullptr && t2 == nullptr)
1244 return 0;
1245
1246 else if(t1 == nullptr || t2 == nullptr)
1247 return weightCombinatorialMatch + weightArcMatch * 1
1248 + weightScalarValueMatch;
1249
1250 else if(t1->type == t2->type)
1251 return weightArcMatch * (1 - ((float)intersectionsize / (float)unionsize))
1252 + weightScalarValueMatch
1253 * std::abs(t1->scalarValue - t2->scalarValue);
1254
1255 else
1256 return FLT_MAX;
1257 }
1258
1259 if(t1 == nullptr && t2 == nullptr)
1260 return 0;
1261
1262 else if(t1 == nullptr)
1263 return weightCombinatorialMatch + weightArcMatch * v2
1264 + weightScalarValueMatch;
1265
1266 else if(t2 == nullptr)
1267 return weightCombinatorialMatch + weightArcMatch * v1
1268 + weightScalarValueMatch;
1269
1270 else if(t1->type == t2->type)
1271 return weightArcMatch * std::abs(v1 - v2)
1272 + weightScalarValueMatch
1273 * std::abs(t1->scalarValue - t2->scalarValue);
1274
1275 else
1276 return FLT_MAX;
1277}
1278
1279std::shared_ptr<ttk::cta::AlignmentTree>
1281 const std::shared_ptr<ttk::cta::BinaryTree> &t1,
1282 const std::shared_ptr<ttk::cta::BinaryTree> &t2,
1283 std::vector<std::vector<float>> &memT,
1284 std::vector<std::vector<float>> &memF) {
1285
1286 if(t1 == nullptr)
1287 return traceNullAlignment(t2, false);
1288 if(t2 == nullptr)
1289 return traceNullAlignment(t1, true);
1290
1291 auto id = [](std::shared_ptr<ttk::cta::BinaryTree> &t) {
1292 return t == nullptr ? 0 : t->id;
1293 };
1294
1295 if(memT[t1->id][t2->id] == editCost(t1, t2) + memF[t1->id][t2->id]) {
1296
1297 auto resNode = std::make_shared<ttk::cta::AlignmentTree>();
1298
1299 resNode->node1 = t1;
1300 resNode->node2 = t2;
1301 resNode->child1 = nullptr;
1302 resNode->child2 = nullptr;
1303 resNode->height = 0;
1304 resNode->size = 1;
1305
1306 std::vector<std::shared_ptr<ttk::cta::AlignmentTree>> resChildren
1307 = traceAlignmentForest(t1, t2, memT, memF);
1308
1309 if(resChildren.size() > 0)
1310 resNode->child1 = resChildren[0];
1311 if(resChildren.size() > 1)
1312 resNode->child2 = resChildren[1];
1313
1314 for(const auto &child : resChildren) {
1315
1316 if(child != nullptr) {
1317 resNode->height = std::max(resNode->height, child->height + 1);
1318 resNode->size += child->size;
1319 }
1320 }
1321
1322 return resNode;
1323 }
1324
1325 if(memT[t1->id][t2->id]
1326 == editCost(t1, nullptr) + memT[id(t1->child2)][0]
1327 + memT[id(t1->child1)]
1328 [t2->id] /* && t1->type != maxNode && t1->type != minNode */) {
1329
1330 std::shared_ptr<ttk::cta::AlignmentTree> resChild1
1331 = traceAlignmentTree(t1->child1, t2, memT, memF);
1332 std::shared_ptr<ttk::cta::AlignmentTree> resChild2
1333 = traceNullAlignment(t1->child2, true);
1334 auto res = std::make_shared<ttk::cta::AlignmentTree>();
1335 res->node1 = t1;
1336 res->node2 = nullptr;
1337 res->height = 0;
1338 res->size = 1;
1339 res->child1 = resChild1;
1340 res->child2 = resChild2;
1341 res->size += resChild1 == nullptr ? 0 : resChild1->size;
1342 res->size += resChild2 == nullptr ? 1 : resChild2->size;
1343 res->height
1344 = std::max(res->height, resChild1 == nullptr ? 0 : resChild1->height + 1);
1345 res->height
1346 = std::max(res->height, resChild2 == nullptr ? 0 : resChild2->height + 1);
1347 return res;
1348 }
1349
1350 if(memT[t1->id][t2->id]
1351 == editCost(t1, nullptr) + memT[id(t1->child1)][0]
1352 + memT[id(t1->child2)]
1353 [t2->id] /* && t1->type != maxNode && t1->type != minNode */) {
1354
1355 std::shared_ptr<ttk::cta::AlignmentTree> resChild1
1356 = traceAlignmentTree(t1->child2, t2, memT, memF);
1357 std::shared_ptr<ttk::cta::AlignmentTree> resChild2
1358 = traceNullAlignment(t1->child1, true);
1359 auto res = std::make_shared<ttk::cta::AlignmentTree>();
1360 res->node1 = t1;
1361 res->node2 = nullptr;
1362 res->height = 0;
1363 res->size = 1;
1364 res->child1 = resChild1;
1365 res->child2 = resChild2;
1366 res->size += resChild1 == nullptr ? 0 : resChild1->size;
1367 res->size += resChild2 == nullptr ? 0 : resChild2->size;
1368 res->height
1369 = std::max(res->height, resChild1 == nullptr ? 0 : resChild1->height + 1);
1370 res->height
1371 = std::max(res->height, resChild2 == nullptr ? 0 : resChild2->height + 1);
1372 return res;
1373 }
1374
1375 if(memT[t1->id][t2->id]
1376 == editCost(nullptr, t2) + memT[0][id(t2->child2)]
1377 + memT[t1->id][id(
1378 t2->child1)] /* && t2->type != maxNode && t2->type != minNode */) {
1379
1380 std::shared_ptr<ttk::cta::AlignmentTree> resChild1
1381 = traceAlignmentTree(t1, t2->child1, memT, memF);
1382 std::shared_ptr<ttk::cta::AlignmentTree> resChild2
1383 = traceNullAlignment(t2->child2, false);
1384 auto res = std::make_shared<ttk::cta::AlignmentTree>();
1385 res->node1 = nullptr;
1386 res->node2 = t2;
1387 res->height = 0;
1388 res->size = 1;
1389 res->child1 = resChild1;
1390 res->child2 = resChild2;
1391 res->size += resChild1 == nullptr ? 0 : resChild1->size;
1392 res->size += resChild2 == nullptr ? 0 : resChild2->size;
1393 res->height
1394 = std::max(res->height, resChild1 == nullptr ? 0 : resChild1->height + 1);
1395 res->height
1396 = std::max(res->height, resChild2 == nullptr ? 0 : resChild2->height + 1);
1397 return res;
1398 }
1399
1400 if(memT[t1->id][t2->id]
1401 == editCost(nullptr, t2) + memT[0][id(t2->child1)]
1402 + memT[t1->id][id(
1403 t2->child2)] /* && t2->type != maxNode && t2->type != minNode */) {
1404
1405 std::shared_ptr<ttk::cta::AlignmentTree> resChild1
1406 = traceAlignmentTree(t1, t2->child2, memT, memF);
1407 std::shared_ptr<ttk::cta::AlignmentTree> resChild2
1408 = traceNullAlignment(t2->child1, false);
1409 auto res = std::make_shared<ttk::cta::AlignmentTree>();
1410 res->node1 = nullptr;
1411 res->node2 = t2;
1412 res->height = 0;
1413 res->size = 1;
1414 res->child1 = resChild1;
1415 res->child2 = resChild2;
1416 res->size += resChild1 == nullptr ? 0 : resChild1->size;
1417 res->size += resChild2 == nullptr ? 0 : resChild2->size;
1418 res->height
1419 = std::max(res->height, resChild1 == nullptr ? 0 : resChild1->height + 1);
1420 res->height
1421 = std::max(res->height, resChild2 == nullptr ? 0 : resChild2->height + 1);
1422 return res;
1423 }
1424
1425 printErr("Alignment computation failed. Traceback of memoization table not "
1426 "possible.");
1427 return std::make_shared<ttk::cta::AlignmentTree>();
1428}
1429
1430std::vector<std::shared_ptr<ttk::cta::AlignmentTree>>
1432 const std::shared_ptr<ttk::cta::BinaryTree> &t1,
1433 const std::shared_ptr<ttk::cta::BinaryTree> &t2,
1434 std::vector<std::vector<float>> &memT,
1435 std::vector<std::vector<float>> &memF) {
1436
1437 if(t1 == nullptr && t2 == nullptr)
1438 return std::vector<std::shared_ptr<ttk::cta::AlignmentTree>>();
1439 if(t1 == nullptr) {
1440 std::vector<std::shared_ptr<ttk::cta::AlignmentTree>> res;
1441 if(t2->child1 != nullptr)
1442 res.push_back(traceNullAlignment(t2->child1, false));
1443 if(t2->child2 != nullptr)
1444 res.push_back(traceNullAlignment(t2->child2, false));
1445 }
1446 if(t2 == nullptr) {
1447 std::vector<std::shared_ptr<ttk::cta::AlignmentTree>> res;
1448 if(t1->child1 != nullptr)
1449 res.push_back(traceNullAlignment(t1->child1, true));
1450 if(t1->child2 != nullptr)
1451 res.push_back(traceNullAlignment(t1->child2, true));
1452 }
1453
1454 auto id = [](const std::shared_ptr<ttk::cta::BinaryTree> &t) {
1455 return t == nullptr ? 0 : t->id;
1456 };
1457
1458 if(memF[t1->id][t2->id]
1459 == memT[id(t1->child1)][id(t2->child1)]
1460 + memT[id(t1->child2)][id(t2->child2)]) {
1461
1462 std::vector<std::shared_ptr<ttk::cta::AlignmentTree>> res;
1463 std::shared_ptr<ttk::cta::AlignmentTree> res1
1464 = traceAlignmentTree(t1->child1, t2->child1, memT, memF);
1465 if(res1 != nullptr)
1466 res.push_back(res1);
1467 std::shared_ptr<ttk::cta::AlignmentTree> res2
1468 = traceAlignmentTree(t1->child2, t2->child2, memT, memF);
1469 if(res2 != nullptr)
1470 res.push_back(res2);
1471
1472 return res;
1473 }
1474
1475 if(memF[t1->id][t2->id]
1476 == memT[id(t1->child1)][id(t2->child2)]
1477 + memT[id(t1->child2)][id(t2->child1)]) {
1478
1479 std::vector<std::shared_ptr<ttk::cta::AlignmentTree>> res;
1480 std::shared_ptr<ttk::cta::AlignmentTree> res1
1481 = traceAlignmentTree(t1->child1, t2->child2, memT, memF);
1482 if(res1 != nullptr)
1483 res.push_back(res1);
1484 std::shared_ptr<ttk::cta::AlignmentTree> res2
1485 = traceAlignmentTree(t1->child2, t2->child1, memT, memF);
1486 if(res2 != nullptr)
1487 res.push_back(res2);
1488
1489 return res;
1490 }
1491
1492 if(memF[t1->id][t2->id]
1493 == editCost(t1->child1, nullptr) + memF[id(t1->child1)][t2->id]
1494 + memT[id(t1->child2)][0]) {
1495
1496 if(t1->child1 != nullptr) {
1497
1498 std::vector<std::shared_ptr<ttk::cta::AlignmentTree>> res;
1499
1500 auto t = std::make_shared<ttk::cta::AlignmentTree>();
1501 t->node1 = t1->child1;
1502 t->node2 = nullptr;
1503
1504 t->child1 = nullptr;
1505 t->child2 = nullptr;
1506
1507 t->size = 1;
1508 t->height = 0;
1509
1510 std::vector<std::shared_ptr<ttk::cta::AlignmentTree>> resChildren
1511 = traceAlignmentForest(t1->child1, t2, memT, memF);
1512 if(resChildren.size() > 0)
1513 t->child1 = resChildren[0];
1514 if(resChildren.size() > 1)
1515 t->child2 = resChildren[1];
1516
1517 for(const auto &c : resChildren) {
1518 if(c != nullptr) {
1519 t->height = std::max(t->height, c->height + 1);
1520 t->size += c->size;
1521 }
1522 }
1523
1524 res.push_back(t);
1525 if(t1->child2 != nullptr)
1526 res.push_back(traceNullAlignment(t1->child2, true));
1527
1528 return res;
1529 }
1530 }
1531
1532 if(memF[t1->id][t2->id]
1533 == editCost(t1->child2, nullptr) + memF[id(t1->child2)][t2->id]
1534 + memT[id(t1->child1)][0]) {
1535
1536 if(t1->child2 != nullptr) {
1537
1538 std::vector<std::shared_ptr<ttk::cta::AlignmentTree>> res;
1539
1540 auto t = std::make_shared<ttk::cta::AlignmentTree>();
1541 t->node1 = t1->child2;
1542 t->node2 = nullptr;
1543
1544 t->child1 = nullptr;
1545 t->child2 = nullptr;
1546
1547 t->size = 1;
1548 t->height = 0;
1549
1550 std::vector<std::shared_ptr<ttk::cta::AlignmentTree>> resChildren
1551 = traceAlignmentForest(t1->child2, t2, memT, memF);
1552 if(resChildren.size() > 0)
1553 t->child1 = resChildren[0];
1554 if(resChildren.size() > 1)
1555 t->child2 = resChildren[1];
1556
1557 for(const auto &c : resChildren) {
1558 if(c != nullptr) {
1559 t->height = std::max(t->height, c->height + 1);
1560 t->size += c->size;
1561 }
1562 }
1563
1564 res.push_back(t);
1565 if(t1->child1 != nullptr)
1566 res.push_back(traceNullAlignment(t1->child1, true));
1567
1568 return res;
1569 }
1570 }
1571
1572 if(memF[t1->id][t2->id]
1573 == editCost(nullptr, t2->child1) + memF[t1->id][id(t2->child1)]
1574 + memT[0][id(t2->child2)]) {
1575
1576 if(t2->child1 != nullptr) {
1577
1578 std::vector<std::shared_ptr<ttk::cta::AlignmentTree>> res;
1579
1580 auto t = std::make_shared<ttk::cta::AlignmentTree>();
1581 t->node1 = nullptr;
1582 t->node2 = t2->child1;
1583
1584 t->child1 = nullptr;
1585 t->child2 = nullptr;
1586
1587 t->size = 1;
1588 t->height = 0;
1589
1590 std::vector<std::shared_ptr<ttk::cta::AlignmentTree>> resChildren
1591 = traceAlignmentForest(t1, t2->child1, memT, memF);
1592 if(resChildren.size() > 0)
1593 t->child1 = resChildren[0];
1594 if(resChildren.size() > 1)
1595 t->child2 = resChildren[1];
1596
1597 for(const auto &c : resChildren) {
1598 if(c != nullptr) {
1599 t->height = std::max(t->height, c->height + 1);
1600 t->size += c->size;
1601 }
1602 }
1603
1604 res.push_back(t);
1605 if(t2->child2 != nullptr)
1606 res.push_back(traceNullAlignment(t2->child2, false));
1607
1608 return res;
1609 }
1610 }
1611
1612 if(memF[t1->id][t2->id]
1613 == editCost(nullptr, t2->child2) + memF[t1->id][id(t2->child2)]
1614 + memT[0][id(t2->child1)]) {
1615
1616 if(t2->child2 != nullptr) {
1617
1618 std::vector<std::shared_ptr<ttk::cta::AlignmentTree>> res;
1619
1620 auto t = std::make_shared<ttk::cta::AlignmentTree>();
1621 t->node1 = nullptr;
1622 t->node2 = t2->child2;
1623
1624 t->child1 = nullptr;
1625 t->child2 = nullptr;
1626
1627 t->size = 1;
1628 t->height = 0;
1629
1630 std::vector<std::shared_ptr<ttk::cta::AlignmentTree>> resChildren
1631 = traceAlignmentForest(t1, t2->child2, memT, memF);
1632 if(resChildren.size() > 0)
1633 t->child1 = resChildren[0];
1634 if(resChildren.size() > 1)
1635 t->child2 = resChildren[1];
1636
1637 for(const auto &c : resChildren) {
1638 if(c != nullptr) {
1639 t->height = std::max(t->height, c->height + 1);
1640 t->size += c->size;
1641 }
1642 }
1643
1644 res.push_back(t);
1645 if(t2->child1 != nullptr)
1646 res.push_back(traceNullAlignment(t2->child1, false));
1647
1648 return res;
1649 }
1650 }
1651
1652 printErr("Alignment computation failed. Traceback of memoization table not "
1653 "possible.");
1654 return std::vector<std::shared_ptr<ttk::cta::AlignmentTree>>();
1655}
1656
1657std::shared_ptr<ttk::cta::AlignmentTree>
1659 const std::shared_ptr<ttk::cta::BinaryTree> &t, bool first) {
1660
1661 if(t == nullptr)
1662 return nullptr;
1663 auto at = std::make_shared<ttk::cta::AlignmentTree>();
1664 at->node1 = first ? t : nullptr;
1665 at->node2 = first ? nullptr : t;
1666 at->height = t->height;
1667 at->size = t->size;
1668 at->child1 = traceNullAlignment(t->child1, first);
1669 at->child2 = traceNullAlignment(t->child2, first);
1670 return at;
1671}
1672
1673/*
1674=====================================================================================================================
1675 helper functions
1676=====================================================================================================================
1677*/
1678
1680 const std::shared_ptr<ttk::cta::Tree> &t) {
1681
1682 if(t->children.size() > 2)
1683 return false;
1684 else {
1685 bool res = true;
1686 for(const auto &c : t->children) {
1687 res = res & isBinary(c);
1688 }
1689 return res;
1690 }
1691}
1692
1693std::shared_ptr<ttk::cta::BinaryTree> ttk::ContourTreeAlignment::rootAtNode(
1694 const std::shared_ptr<ttk::cta::AlignmentNode> &root) {
1695
1696 int id = 1;
1697 std::shared_ptr<ttk::cta::BinaryTree> t
1698 = computeRootedTree(root, nullptr, id);
1699 return t;
1700}
1701
1702std::shared_ptr<ttk::cta::BinaryTree>
1704 const std::shared_ptr<ttk::cta::AlignmentNode> &node,
1705 const std::shared_ptr<ttk::cta::AlignmentEdge> &parent,
1706 int &id) {
1707
1708 auto t = std::make_shared<ttk::cta::BinaryTree>();
1709
1710 if(parent == nullptr) {
1711 t->scalardistanceParent = 10000;
1712 t->area = 10000;
1713 t->volume = 10000;
1714 t->region = std::vector<int>(1, -1);
1715 } else {
1716 t->scalardistanceParent = parent->scalardistance;
1717 t->area = parent->area;
1718 t->volume = t->area * t->scalardistanceParent;
1719 t->region = parent->region;
1720 }
1721 t->freq = node->freq;
1722 t->type = node->type;
1723 t->child1 = nullptr;
1724 t->child2 = nullptr;
1725 t->id = id;
1726 t->scalarValue = node->scalarValue;
1727 t->nodeRefs = node->nodeRefs;
1728 if(parent != nullptr)
1729 t->arcRefs = parent->arcRefs;
1730 else
1731 t->arcRefs = std::vector<std::pair<int, int>>();
1732 id++;
1733
1734 t->size = 1;
1735 t->height = 0;
1736
1737 std::vector<std::shared_ptr<ttk::cta::BinaryTree>> children;
1738
1739 for(const auto &edge : node->edgeList) {
1740
1741 if(edge != parent) {
1742
1743 std::shared_ptr<ttk::cta::BinaryTree> child = computeRootedTree(
1744 edge->node1.lock() == node ? edge->node2.lock() : edge->node1.lock(),
1745 edge, id);
1746 children.push_back(child);
1747 t->size += child->size;
1748 if(t->height < child->height + 1)
1749 t->height = child->height + 1;
1750 }
1751 }
1752
1753 if(children.size() > 0)
1754 t->child1 = children[0];
1755 if(children.size() > 1)
1756 t->child2 = children[1];
1757
1758 return t;
1759}
1760
1761std::shared_ptr<ttk::cta::BinaryTree>
1763 const std::shared_ptr<ttk::cta::AlignmentEdge> &arc,
1764 bool parent1,
1765 int &id) {
1766
1767 auto t = std::make_shared<ttk::cta::BinaryTree>();
1768
1769 t->scalardistanceParent = arc->scalardistance;
1770 t->area = arc->area;
1771 t->volume = t->area * t->scalardistanceParent;
1772 t->freq = arc->freq;
1773 t->type = arc->node1.lock()->type == ttk::cta::maxNode
1774 || arc->node2.lock()->type == ttk::cta::maxNode
1776 : arc->node1.lock()->type == ttk::cta::minNode
1777 || arc->node2.lock()->type == ttk::cta::minNode
1780 t->child1 = nullptr;
1781 t->child2 = nullptr;
1782 t->id = id;
1783 t->scalarValue = -1;
1784 t->arcRefs = arc->arcRefs;
1785 id++;
1786
1787 t->size = 1;
1788 t->height = 0;
1789
1790 std::vector<std::shared_ptr<ttk::cta::BinaryTree>> children;
1791
1792 std::shared_ptr<ttk::cta::AlignmentNode> node
1793 = parent1 ? arc->node2.lock() : arc->node1.lock();
1794
1795 for(const auto &edge : node->edgeList) {
1796
1797 if(edge != arc) {
1798
1799 std::shared_ptr<ttk::cta::BinaryTree> child
1800 = computeRootedDualTree(edge, edge->node1.lock() == node, id);
1801 children.push_back(child);
1802 t->size += child->size;
1803 if(t->height < child->height + 1)
1804 t->height = child->height + 1;
1805 }
1806 }
1807
1808 if(children.size() > 0)
1809 t->child1 = children[0];
1810 if(children.size() > 1)
1811 t->child2 = children[1];
1812
1813 return t;
1814}
float alignTreeBinary(const std::shared_ptr< ttk::cta::BinaryTree > &t1, const std::shared_ptr< ttk::cta::BinaryTree > &t2, std::vector< std::vector< float > > &memT, std::vector< std::vector< float > > &memF)
bool alignTree_consistentRoot(const std::shared_ptr< ContourTree > &t)
std::shared_ptr< ttk::cta::BinaryTree > computeRootedDualTree(const std::shared_ptr< ttk::cta::AlignmentEdge > &arc, bool parent1, int &id)
std::vector< std::shared_ptr< ttk::cta::AlignmentTree > > traceAlignmentForest(const std::shared_ptr< ttk::cta::BinaryTree > &t1, const std::shared_ptr< ttk::cta::BinaryTree > &t2, std::vector< std::vector< float > > &memT, std::vector< std::vector< float > > &memF)
std::vector< std::pair< std::vector< std::shared_ptr< ttk::cta::CTNode > >, std::vector< std::shared_ptr< ttk::cta::CTEdge > > > > getGraphs()
bool initialize(const std::shared_ptr< ContourTree > &t)
std::shared_ptr< ttk::cta::AlignmentTree > traceAlignmentTree(const std::shared_ptr< ttk::cta::BinaryTree > &t1, const std::shared_ptr< ttk::cta::BinaryTree > &t2, std::vector< std::vector< float > > &memT, std::vector< std::vector< float > > &memF)
std::pair< float, std::shared_ptr< ttk::cta::AlignmentTree > > getAlignmentBinary(const std::shared_ptr< ttk::cta::BinaryTree > &t1, const std::shared_ptr< ttk::cta::BinaryTree > &t2)
void computeNewAlignmenttree(const std::shared_ptr< ttk::cta::AlignmentTree > &res)
std::pair< std::vector< std::shared_ptr< ttk::cta::AlignmentNode > >, std::vector< std::shared_ptr< ttk::cta::AlignmentEdge > > > getAlignmentGraph()
float editCost(const std::shared_ptr< ttk::cta::BinaryTree > &t1, const std::shared_ptr< ttk::cta::BinaryTree > &t2)
std::vector< std::shared_ptr< ttk::cta::AlignmentNode > > nodes
bool isBinary(const std::shared_ptr< ttk::cta::Tree > &t)
bool alignTree(const std::shared_ptr< ContourTree > &t)
std::shared_ptr< ttk::cta::BinaryTree > getAlignmentGraphRooted()
float alignForestBinary(const std::shared_ptr< ttk::cta::BinaryTree > &t1, const std::shared_ptr< ttk::cta::BinaryTree > &t2, std::vector< std::vector< float > > &memT, std::vector< std::vector< float > > &memF)
std::pair< float, std::vector< std::shared_ptr< ttk::cta::AlignmentNode > > > pathToMin(const std::shared_ptr< ttk::cta::AlignmentNode > &root, const std::shared_ptr< ttk::cta::AlignmentNode > &parent)
std::shared_ptr< ttk::cta::BinaryTree > computeRootedTree(const std::shared_ptr< ttk::cta::AlignmentNode > &node, const std::shared_ptr< ttk::cta::AlignmentEdge > &parent, int &id)
std::pair< float, std::vector< std::shared_ptr< ttk::cta::AlignmentNode > > > pathToMax(const std::shared_ptr< ttk::cta::AlignmentNode > &root, const std::shared_ptr< ttk::cta::AlignmentNode > &parent)
std::vector< std::shared_ptr< ContourTree > > getContourTrees()
bool initialize_consistentRoot(const std::shared_ptr< ContourTree > &t, int rootIdx)
std::shared_ptr< ttk::cta::AlignmentTree > traceNullAlignment(const std::shared_ptr< ttk::cta::BinaryTree > &t, bool first)
std::shared_ptr< ttk::cta::BinaryTree > rootAtNode(const std::shared_ptr< ttk::cta::AlignmentNode > &root)
Contour Tree Data Structure for an unrooted contour tree of unbounded degree for internal use from th...