TTK
Loading...
Searching...
No Matches
MergeTree.cpp
Go to the documentation of this file.
1/*
2 * file: MergeTree.cpp
3 * description: MergeTree processing package.
4 * author: Gueunet Charles
5 * date: Juin 2015
6 */
7
8#include "MergeTree.h"
9
10using namespace std;
11using namespace ttk;
12using namespace cf;
13
14// Constructors & destructors
15
16MergeTree::MergeTree(std::shared_ptr<Params> params,
17 std::shared_ptr<Scalars> scalars,
18 TreeType type,
19 idPartition part)
20 : params_(std::move(params)), scalars_(std::move(scalars)) {
21 if(type == TreeType::Join) {
22 this->setDebugMsgPrefix("JoinTree");
23 } else if(type == TreeType::Split) {
24 this->setDebugMsgPrefix("SplitTree");
25 } else if(type == TreeType::Contour) {
26 this->setDebugMsgPrefix("ContourTree");
27 } else if(type == TreeType::JoinAndSplit) {
28 this->setDebugMsgPrefix("SplitJoinTree");
29 }
30 treeData_.treeType = type;
31 treeData_.partition = part;
32}
33
34MergeTree::~MergeTree() = default;
35// all is automatically destroyed in treedata
36// do not touch pointers
37
38// }
39// Process
40// {
41
42// update lately
43
45 auto compL
46 = [&](const pair<SimplexId, bool> &a, const pair<SimplexId, bool> &b) {
47 return isLower(a.first, b.first);
48 };
49
50 auto compH
51 = [&](const pair<SimplexId, bool> &a, const pair<SimplexId, bool> &b) {
52 return isHigher(a.first, b.first);
53 };
54
55 const idSuperArc nbArc = getNumberOfSuperArcs();
57 for(idSuperArc sa = 0; sa < nbArc; sa++) {
58 SuperArc *superArc = getSuperArc(sa);
59 if(!superArc->isVisible())
60 continue;
61
62 auto *segmentation = superArc->getVertList();
63 auto &segmSize = superArc->getVertSize();
64
65 // fix
66 if(!segmentation)
67 continue;
68
69 sort(segmentation, segmentation + segmSize, compH);
70 for(SimplexId i = 0; i < segmSize; i++) {
71 const SimplexId &vert = segmentation[i].first;
72 updateCorrespondingArc(vert, sa);
73 }
74 }
75 } else {
76 for(idSuperArc sa = 0; sa < nbArc; sa++) {
77 SuperArc *superArc = getSuperArc(sa);
78 if(!superArc->isVisible())
79 continue;
80
81 auto *segmentation = superArc->getVertList();
82 auto &segmSize = superArc->getVertSize();
83
84 // fix
85 if(!segmentation)
86 continue;
87
88 sort(segmentation, segmentation + segmSize, compL);
89 for(SimplexId i = 0; i < segmSize; i++) {
90 const SimplexId &vert = segmentation[i].first;
91 if(!segmentation[i].second) {
92 updateCorrespondingArc(vert, sa);
93 }
94 }
95 }
96 }
97
98 const idNode nbNode = getNumberOfNodes();
99 for(idNode n = 0; n < nbNode; n++) {
100 if(!getNode(n)->isHidden()) {
101 updateCorrespondingNode(getNode(n)->getVertexId(), n);
102 }
103 }
104}
105
107 // REMOVE THIS FUNCTION AND USE BOOL
108 auto compL
109 = [&](const pair<SimplexId, bool> &a, const pair<SimplexId, bool> &b) {
110 return isLower(a.first, b.first);
111 };
112
113 auto compH
114 = [&](const pair<SimplexId, bool> &a, const pair<SimplexId, bool> &b) {
115 return isHigher(a.first, b.first);
116 };
117
118 const idSuperArc nbArc = getNumberOfSuperArcs();
120#ifdef TTK_ENABLE_OPENMP
121#pragma omp parallel for
122#endif
123 for(idSuperArc sa = 0; sa < nbArc; sa++) {
124 SuperArc *superArc = getSuperArc(sa);
125 if(!superArc->isVisible())
126 continue;
127
128 auto *segmentation = superArc->getVertList();
129 auto &segmSize = superArc->getVertSize();
130
131 // fix
132 if(!segmentation)
133 continue;
134
135 sort(segmentation, segmentation + segmSize, compH);
136 for(SimplexId i = 0; i < segmSize; i++) {
137 const SimplexId &vert = segmentation[i].first;
138 updateCorrespondingArc(vert, sa);
139 }
140 }
141 } else {
142#ifdef TTK_ENABLE_OPENMP
143#pragma omp parallel for
144#endif
145 for(idSuperArc sa = 0; sa < nbArc; sa++) {
146 SuperArc *superArc = getSuperArc(sa);
147 if(!superArc->isVisible())
148 continue;
149
150 auto *segmentation = superArc->getVertList();
151 auto &segmSize = superArc->getVertSize();
152
153 // fix
154 if(!segmentation)
155 continue;
156
157 sort(segmentation, segmentation + segmSize, compL);
158 for(SimplexId i = 0; i < segmSize; i++) {
159 const SimplexId &vert = segmentation[i].first;
160 if(!segmentation[i].second) {
161 updateCorrespondingArc(vert, sa);
162 }
163 }
164 }
165 }
166
167 const idNode nbNode = getNumberOfNodes();
168 for(idNode n = 0; n < nbNode; n++) {
169 if(!getNode(n)->isHidden()) {
170 updateCorrespondingNode(getNode(n)->getVertexId(), n);
171 }
172 }
173}
174
175void MergeTree::parallelInitNodeValence(const int nbThreadValence) {
176 // cout << "SENTINEL : Parallel Init Node Valence " << endl;
177 const auto &nbNodes = getNumberOfNodes();
178
179#ifdef TTK_ENABLE_OPENMP
180#pragma omp parallel for num_threads(nbThreadValence)
181#endif
182 for(idNode n = 0; n < nbNodes; n++) {
183 short downVal = 0, upVal = 0;
184 Node *node = getNode(n);
185
186 const auto nbDown = node->getNumberOfDownSuperArcs();
187 for(idSuperArc i = 0; i < nbDown; i++) {
188 const SuperArc *sa = getSuperArc(node->getDownSuperArcId(i));
189 if(sa->isVisible()) {
190 ++downVal;
191 }
192 }
193
194 const auto nbUp = node->getNumberOfUpSuperArcs();
195 for(idSuperArc i = 0; i < nbUp; i++) {
196 const SuperArc *sa = getSuperArc(node->getUpSuperArcId(i));
197 if(sa->isVisible()) {
198 ++upVal;
199 }
200 }
201
202 node->setDownValence(downVal);
203 node->setUpValence(upVal);
204 }
205 TTK_FORCE_USE(nbThreadValence);
206}
207
208// }
209// Arcs and node manipulations
210// {
211
212// SuperArcs
214 const bool overlapB,
215 const bool overlapA) {
216#ifndef TTK_ENABLE_KAMIKAZE
217 if(downNodeId >= getNumberOfNodes()) {
218 cout << "[Merge Tree] openSuperArc on a inexisting node !" << endl;
219 return -2;
220 }
221#endif
222
223 const idSuperArc newSuperArcId = treeData_.superArcs.size();
224 treeData_.superArcs.emplace_back(downNodeId, nullNodes, overlapB, overlapA,
226 treeData_.nodes[downNodeId].addUpSuperArcId(newSuperArcId);
227 treeData_.nodes[downNodeId].incUpValence();
228
229 return newSuperArcId;
230}
231
233 const idNode &upNodeId,
234 const bool overlapB,
235 const bool overlapA,
236 pair<SimplexId, bool> *vertexList,
237 SimplexId vertexSize) {
238 const idSuperArc newSuperArcId = treeData_.superArcs.size();
239
240 if(downNodeId != upNodeId) {
241 treeData_.superArcs.emplace_back(downNodeId, upNodeId, overlapB, overlapA,
243 } else {
244 // arc on a 1 vertex partition ...
245 treeData_.superArcs.emplace_back(downNodeId, upNodeId, overlapB, overlapA,
248 }
249
250 treeData_.superArcs[newSuperArcId].setVertList(vertexList);
251 treeData_.superArcs[newSuperArcId].setVertSize(vertexSize);
252
253 treeData_.nodes[downNodeId].addUpSuperArcId(newSuperArcId);
254 treeData_.nodes[downNodeId].incUpValence();
255 treeData_.nodes[upNodeId].addDownSuperArcId(newSuperArcId);
256 treeData_.nodes[upNodeId].incDownValence();
257
258 return newSuperArcId;
259}
260
262 const idNode &upNodeId,
263 const bool overlapB,
264 const bool overlapA) {
265#ifndef TTK_ENABLE_KAMIKAZE
266
267 if(superArcId >= getNumberOfSuperArcs()) {
268 cout << "[Merge Tree] closeSuperArc on a inexisting arc !" << endl;
269 return;
270 }
271
272 if(upNodeId >= getNumberOfNodes()) {
273 cout << "[Merge Tree] closeOpenedArc on a inexisting node !" << endl;
274 return;
275 }
276
277#endif
278 treeData_.superArcs[superArcId].setUpNodeId(upNodeId);
279 // TODO why do we need to re-set last-visited ? (maybe Saddle, check it out)
280 treeData_.superArcs[superArcId].setLastVisited(
281 getNode(upNodeId)->getVertexId());
282 treeData_.nodes[upNodeId].addDownSuperArcId(superArcId);
283 treeData_.nodes[upNodeId].incDownValence();
284
285 treeData_.superArcs[superArcId].setOverlapBelow(
286 treeData_.superArcs[superArcId].getOverlapBelow() != overlapB);
287
288 if(treeData_.superArcs[superArcId].getOverlapBelow()) {
289 treeData_.arcsCrossingBelow.emplace_back(superArcId);
290 }
291
292 treeData_.superArcs[superArcId].setOverlapAbove(
293 treeData_.superArcs[superArcId].getOverlapAbove() != overlapA);
294
295 if(treeData_.superArcs[superArcId].getOverlapAbove()) {
296 treeData_.arcsCrossingAbove.emplace_back(superArcId);
297 }
298}
299
301 const pair<SimplexId, bool> &seed) {
302 auto isLowerComp
303 = [&](const pair<SimplexId, bool> &a, const pair<SimplexId, bool> &b) {
304 return isLower(a.first, b.first);
305 };
306
307 SuperArc *crossing = getSuperArc(arc);
308 SimplexId stitchVert;
309 // get stitching node
310 const auto &vertList = crossing->getVertList();
311 const auto &vertSize = crossing->getVertSize();
312
313 if(vertSize) {
314 auto posVert
315 = lower_bound(vertList, vertList + vertSize, seed, isLowerComp);
316 while(posVert < vertList + vertSize && posVert->second) {
317 ++posVert;
318 }
319
320 if(posVert == vertList + vertSize) {
321 // up node
322 stitchVert = getNode(crossing->getUpNodeId())->getVertexId();
323 } else {
324 // update segmentation
325 crossing->setVertSize(posVert - vertList);
326 stitchVert = posVert->first;
327 // need to insert node
328 const idNode &newNodeId = makeNode(stitchVert);
329 Node *newNode = getNode(newNodeId);
330 // for the insert node to works
331 updateCorrespondingArc(stitchVert, arc);
332 insertNode(newNode, false);
333 newNode->setUpValence(1);
334 newNode->setDownValence(1);
335 }
336 } else {
337 // no segmentation => up node
338 stitchVert = getNode(crossing->getUpNodeId())->getVertexId();
339 }
340
341 return stitchVert;
342}
343
345 const pair<SimplexId, bool> &seed,
346 const vector<idCorresp> &vert2treeOther) {
347 auto isLowerComp
348 = [&](const pair<SimplexId, bool> &a, const pair<SimplexId, bool> &b) {
349 return isLower(a.first, b.first);
350 };
351
352 SuperArc *crossing = getSuperArc(arc);
353 SimplexId stitchVert;
354 // get stitching node
355 const auto &vertList = crossing->getVertList();
356 const auto &vertSize = crossing->getVertSize();
357
358 if(vertSize) {
359 auto posVert
360 = lower_bound(vertList, vertList + vertSize, seed, isLowerComp);
361 if(posVert == vertList) {
362 stitchVert = getNode(crossing->getDownNodeId())->getVertexId();
363 } else {
364 --posVert; // we want below and not hidden (TODO remove nullCorresp ?)
365 while(
366 posVert > vertList
367 && (posVert->second || vert2treeOther[posVert->first] == nullCorresp)) {
368 --posVert;
369 }
370
371 if(posVert == vertList) {
372 stitchVert = getNode(crossing->getDownNodeId())->getVertexId();
373 } else {
374 // we only find, do not touch the segmentation
375 stitchVert = posVert->first;
376 }
377 }
378 } else {
379 stitchVert = getNode(crossing->getDownNodeId())->getVertexId();
380 }
381
382 return stitchVert;
383}
384
386 Node *node = getNode(n);
387
388 // need to check number of doan each time as it can change
389 for(idSuperArc i = 0; i < node->getNumberOfDownSuperArcs(); i++) {
390 const SuperArc *sa = getSuperArc(node->getDownSuperArcId(i));
391 if(!sa->isVisible()) {
392 node->removeDownSuperArcPos(i);
393 // when remove switch position with last
394 --i;
395 }
396 }
397}
398
400 Node *node = getNode(n);
401
402 // need to check number of doan each time as it can change
403 for(idSuperArc i = 0; i < node->getNumberOfDownSuperArcs(); i++) {
404 const SuperArc *sa = getSuperArc(node->getDownSuperArcId(i));
405 if(!sa->isExternal()) {
406 node->removeDownSuperArcPos(i);
407 // when remove switch position with last
408 --i;
409 }
410 }
411}
412
414
415 Node *node = getNode(n);
416
417 const auto nbDown = node->getNumberOfDownSuperArcs();
418 const auto nbUp = node->getNumberOfUpSuperArcs();
419 idSuperArc res = 0;
420 for(idSuperArc i = 0; i < nbDown; i++) {
421 const SuperArc *sa = getSuperArc(node->getDownSuperArcId(i));
422 if(sa->isVisible()) {
423 ++res;
424 }
425 }
426 for(idSuperArc i = 0; i < nbUp; i++) {
427 const SuperArc *sa = getSuperArc(node->getUpSuperArcId(i));
428 if(sa->isVisible()) {
429 ++res;
430 }
431 }
432
433 return res;
434}
435
437
438 Node *node = getNode(n);
439
440 const auto nbDown = node->getNumberOfDownSuperArcs();
441 idSuperArc res = 0;
442 for(idSuperArc i = 0; i < nbDown; i++) {
443 const SuperArc *sa = getSuperArc(node->getDownSuperArcId(i));
444 if(!sa->isMerged()) {
445 ++res;
446 }
447 }
448
449 return res;
450}
451
453 Node *node = getNode(n);
454
455 const auto nbDown = node->getNumberOfDownSuperArcs();
456 idSuperArc res = 0;
457 for(idSuperArc i = 0; i < nbDown; i++) {
458 const SuperArc *sa = getSuperArc(node->getDownSuperArcId(i));
459 if(sa->isExternal()) {
460 ++res;
461 }
462 }
463
464 return res;
465}
466
468 const idPartition &tree,
469 const idNode &treeNode) {
470 Node *n = getNode(node);
471
472 const auto nbUp = n->getNumberOfUpSuperArcs();
473 for(idSuperArc a = 0; a < nbUp; a++) {
474 const idSuperArc sa = n->getUpSuperArcId(a);
475
476 if(getSuperArc(sa)->getUpCT() == tree
477 && getSuperArc(sa)->getUpNodeId() == treeNode) {
478 return true;
479 }
480 }
481
482 return false;
483}
484
485// state
486
488 treeData_.superArcs[sa].hide();
489 treeData_.nodes[treeData_.superArcs[sa].getUpNodeId()].removeDownSuperArc(sa);
490 treeData_.nodes[treeData_.superArcs[sa].getUpNodeId()].decDownValence();
491 treeData_.nodes[treeData_.superArcs[sa].getDownNodeId()].removeUpSuperArc(sa);
492 treeData_.nodes[treeData_.superArcs[sa].getDownNodeId()].decUpValence();
493}
494
496 const idSuperArc &recept,
497 const bool changeConnectivity) {
498 treeData_.superArcs[sa].merge(recept);
499
500 if(changeConnectivity) {
501 treeData_.nodes[treeData_.superArcs[sa].getUpNodeId()].removeDownSuperArc(
502 sa);
503 treeData_.nodes[treeData_.superArcs[sa].getUpNodeId()].decDownValence();
504 treeData_.nodes[treeData_.superArcs[sa].getDownNodeId()].removeUpSuperArc(
505 sa);
506 treeData_.nodes[treeData_.superArcs[sa].getDownNodeId()].decUpValence();
507 }
508}
509
510void MergeTree::hideNode(const idNode &node) {
511 treeData_.nodes[node].hide();
512}
513
514// Nodes
515
516idNode MergeTree::makeNode(const SimplexId &vertexId, const SimplexId &term) {
517#ifndef TTK_ENABLE_KAMIKAZE
518 if(vertexId < 0 || vertexId >= scalars_->size) {
519 cout << "[Merge Tree] make node, wrong vertex :" << vertexId << " on "
520 << scalars_->size << endl;
521 return -1;
522 }
523#endif
524
525 if(isCorrespondingNode(vertexId)) {
526 return getCorrespondingNodeId(vertexId);
527 }
528
529 const SimplexId size_base = (SimplexId)treeData_.nodes.size();
530 treeData_.nodes.emplace_back(vertexId, term);
531 updateCorrespondingNode(vertexId, size_base);
532
533 return size_base;
534}
535
536idNode MergeTree::makeNode(const Node *const n, const SimplexId &term) {
537 return makeNode(n->getVertexId(), term);
538}
539
541 const idNode &node,
542 std::list<std::vector<std::pair<SimplexId, bool>>> &storage,
543 const pair<SimplexId, bool> *markVertices,
544 const SimplexId &nbMark) {
545 Node *mainNode = getNode(node);
546
547 if(mainNode->getNumberOfUpSuperArcs() == 0) {
548
549 // ----
550 // Root
551 // ----
552
553#ifndef TTK_ENABLE_KAMIKAZE
554 if(mainNode->getNumberOfDownSuperArcs() != 1) {
555 cout << endl << "[MergeTree]:delNode won't delete ";
556 cout << mainNode->getVertexId() << " (root) with ";
557 cout << static_cast<unsigned>(mainNode->getNumberOfDownSuperArcs())
558 << " down ";
559 cout << static_cast<unsigned>(mainNode->getNumberOfUpSuperArcs())
560 << " up ";
561 cout << " partition : " << static_cast<unsigned>(treeData_.partition)
562 << endl;
563 return;
564 }
565#endif
566
567 const idSuperArc downArc = mainNode->getDownSuperArcId(0);
568 Node *downNode = getNode(treeData_.superArcs[downArc].getDownNodeId());
569 downNode->removeUpSuperArc(downArc);
570 mainNode->clearDownSuperArcs();
571 // USELESS : TODO remove
572 treeData_.superArcs[downArc].hide();
573
574 } else if(mainNode->getNumberOfDownSuperArcs() < 2) {
575
576 // -------
577 // Regular
578 // -------
579
580 // We delete the upArc,
581 // if there is a down arc, we reattach it to the upNode
582
583 const idSuperArc upArc = mainNode->getUpSuperArcId(0);
584 const idNode upId = treeData_.superArcs[upArc].getUpNodeId();
585 Node *upNode = getNode(upId);
586
587 upNode->removeDownSuperArc(upArc);
588 treeData_.superArcs[upArc].hide();
589 mainNode->clearUpSuperArcs();
590 // Have child(s)
591 // Should be 0 or 1, verify
592 if(mainNode->getNumberOfDownSuperArcs() == 1) {
593 const idSuperArc &downArc = mainNode->getDownSuperArcId(0);
594
595 // if have segmentation to process
596 if(markVertices != nullptr) {
597 // In case the two segmenation are already contiguous,
598 // it means we are removing a regular node that was inserted in the
599 // tree only for the combinations.
600 if((treeData_.superArcs[downArc].getVertList()
601 + treeData_.superArcs[downArc].getVertSize())
602 == treeData_.superArcs[upArc].getVertList()) {
603 // down arc <- union of the two list
604 treeData_.superArcs[downArc].setVertSize(
605 treeData_.superArcs[downArc].getVertSize()
606 + treeData_.superArcs[upArc].getVertSize());
607 // mark removed ones (passed as parameter of this function)
608 // the markVertices is sorted in reverse order as it come form the
609 // other tree
610 SimplexId acc = -1;
611 for(SimplexId i = nbMark - 1; i >= 0; --i) {
612 if(!treeData_.superArcs[downArc].getVertSize())
613 break;
614 while(treeData_.superArcs[downArc].getRegularNodeId(++acc)
615 != markVertices[i].first) {
616 if(acc == treeData_.superArcs[downArc].getVertSize())
617 break;
618 }
619 if(acc == treeData_.superArcs[downArc].getVertSize())
620 break;
621
622 treeData_.superArcs[downArc].setMasqued(acc);
623 }
624
625 } else {
626 // we are removing a regular node of the tree who is a degenerate node
627 // in the final tree. we need to keep : SEGMENTATION DETAILS HERE
628 const auto &upSize = treeData_.superArcs[upArc].getVertSize();
629 const auto &downSize = treeData_.superArcs[downArc].getVertSize();
630
631 const auto *upSegm = treeData_.superArcs[upArc].getVertList();
632 const auto *downSegm = treeData_.superArcs[downArc].getVertList();
633
634 storage.emplace_back(upSize + downSize);
635 pair<SimplexId, bool> *newSegmentation = storage.back().data();
636
637 for(SimplexId i = 0; i < downSize; i++) {
638 newSegmentation[i] = downSegm[i];
639 }
640
641 for(SimplexId i = 0; i < upSize; i++) {
642 newSegmentation[i + downSize] = upSegm[i];
643 }
644
645 treeData_.superArcs[downArc].setVertList(newSegmentation);
646 treeData_.superArcs[downArc].setVertSize(downSize + upSize);
647 }
648 }
649
650 treeData_.superArcs[downArc].setUpNodeId(upId);
651 treeData_.superArcs[upArc].setDownNodeId(
652 getSuperArc(downArc)->getDownNodeId());
653 upNode->addDownSuperArcId(downArc);
654 }
655
656 mainNode->clearDownSuperArcs();
657 }
658}
659
660// Normal insert : existing arc stay below inserted (JT example)
661// * - <- upNodeId
662// | \ | <- newSA
663// | * <- newNodeId
664// | | <- currentSA
665// - - -
666idSuperArc MergeTree::insertNode(Node *node, const bool segment) {
667 // already present
668 if(isCorrespondingNode(node->getVertexId())) {
669 Node *myNode = vertex2Node(node->getVertexId());
670 // If it has been hidden / replaced we need to re-make it
671 if(myNode->isHidden()) {
672 SuperArc *sa = getSuperArc(myNode->getUpSuperArcId(0));
673 const idSuperArc &correspondingArcId
674 = (sa->getReplacantArcId() == nullSuperArc) ? myNode->getUpSuperArcId(0)
675 : sa->getReplacantArcId();
676 updateCorrespondingArc(myNode->getVertexId(), correspondingArcId);
677 } else {
678 return nullSuperArc;
679 }
680 }
681
682 idNode upNodeId, newNodeId;
683 idSuperArc currentSA, newSA;
684 SimplexId origin;
685
686 // Create new node
687 currentSA = getCorrespondingSuperArcId(node->getVertexId());
688 upNodeId = treeData_.superArcs[currentSA].getUpNodeId();
689 origin = treeData_.nodes[treeData_.superArcs[currentSA].getDownNodeId()]
690 .getOrigin();
691 newNodeId = makeNode(node, origin);
692
693 // Connectivity
694 // TODO use makeSuperArc for the newArc
695 // Insert only node inside the partition : created arc don t cross
696 newSA = openSuperArc(newNodeId, false, false);
697
698 treeData_.superArcs[newSA].setUpNodeId(upNodeId);
699 treeData_.nodes[upNodeId].removeDownSuperArc(currentSA);
700 treeData_.nodes[upNodeId].addDownSuperArcId(newSA);
701
702 treeData_.superArcs[currentSA].setUpNodeId(newNodeId);
703 treeData_.nodes[newNodeId].addDownSuperArcId(currentSA);
704
705 if(segment) {
706 // cut the vertex list at the node position and
707 // give each arc its part.
708 SuperArc *tmpSA = getSuperArc(currentSA);
709 pair<SimplexId, bool> *newNodePosPtr
711 ? lower_bound(tmpSA->getVertList(),
712 tmpSA->getVertList() + tmpSA->getVertSize(),
713 make_pair(node->getVertexId(), false),
714 [&](const pair<SimplexId, bool> &a,
715 const pair<SimplexId, bool> &b) {
716 return isHigher(a.first, b.first);
717 })
718 : lower_bound(tmpSA->getVertList(),
719 tmpSA->getVertList() + tmpSA->getVertSize(),
720 make_pair(node->getVertexId(), false),
721 [&](const pair<SimplexId, bool> &a,
722 const pair<SimplexId, bool> &b) {
723 return isLower(a.first, b.first);
724 });
725
726 const SimplexId newNodePos = newNodePosPtr - tmpSA->getVertList();
727
728 getSuperArc(newSA)->setVertList(newNodePosPtr);
729 getSuperArc(newSA)->setVertSize(tmpSA->getVertSize() - newNodePos);
730
731 tmpSA->setVertSize(newNodePos);
732 }
733
734 return newSA;
735}
736
737// Reverse insert : existing arc stay above inserted (JT example)
738// * - <- upNodeId
739// | | <- currentSa
740// | * <- newNodeId
741// | / | <- newSA
742// - - -
743idSuperArc MergeTree::reverseInsertNode(Node *node, const bool segment) {
744 // already present
745 if(isCorrespondingNode(node->getVertexId())) {
746 Node *myNode = vertex2Node(node->getVertexId());
747 // If it has been hidden / replaced we need to re-make it
748 if(myNode->isHidden()) {
749 cout << "reverse insert don t deal with hidden" << endl;
750 } else
751 return nullSuperArc;
752 }
753
754 idNode downNodeId, newNodeId;
755 idSuperArc currentSA, newSA;
756 SimplexId origin;
757
758 // Create new node
759 currentSA = getCorrespondingSuperArcId(node->getVertexId());
760 downNodeId = treeData_.superArcs[currentSA].getDownNodeId();
761 origin = treeData_.nodes[treeData_.superArcs[currentSA].getDownNodeId()]
762 .getOrigin();
763 newNodeId = makeNode(node, origin);
764
765 // Connectivity
766 // TODO use makeSuperArc for the newArc
767 // Insert only node inside the partition : created arc don t cross
768 newSA = openSuperArc(downNodeId, false, false);
769
770 treeData_.superArcs[newSA].setUpNodeId(newNodeId);
771 treeData_.nodes[downNodeId].removeUpSuperArc(currentSA);
772 treeData_.nodes[downNodeId].addUpSuperArcId(newSA);
773
774 treeData_.superArcs[currentSA].setDownNodeId(newNodeId);
775 treeData_.nodes[newNodeId].addUpSuperArcId(currentSA);
776
777 treeData_.nodes[newNodeId].addDownSuperArcId(newSA);
778
779 if(segment) {
780 // cut the vertex list at the node position and
781 // give each arc its part.
782 SuperArc *tmpSA = getSuperArc(currentSA);
783 pair<SimplexId, bool> *newNodePosPtr
785 ? lower_bound(tmpSA->getVertList(),
786 tmpSA->getVertList() + tmpSA->getVertSize(),
787 make_pair(node->getVertexId(), false),
788 [&](const pair<SimplexId, bool> &a,
789 const pair<SimplexId, bool> &b) {
790 return isHigher(a.first, b.first);
791 })
792 : lower_bound(tmpSA->getVertList(),
793 tmpSA->getVertList() + tmpSA->getVertSize(),
794 make_pair(node->getVertexId(), false),
795 [&](const pair<SimplexId, bool> &a,
796 const pair<SimplexId, bool> &b) {
797 return isLower(a.first, b.first);
798 });
799
800 const SimplexId newNodePos = newNodePosPtr - tmpSA->getVertList();
801
802 getSuperArc(newSA)->setVertList(tmpSA->getVertList());
803 getSuperArc(newSA)->setVertSize(newNodePos);
804
805 tmpSA->setVertList(newNodePosPtr);
806 tmpSA->setVertSize(tmpSA->getVertSize() - newNodePos);
807 }
808
809 return newSA;
810}
811
812// traverse
813
815 return &(treeData_.nodes[a->getDownNodeId()]);
816}
817
819 return &(treeData_.nodes[a->getUpNodeId()]);
820}
821
823 return getSuperArc(getNode(n)->getUpSuperArcId(0))->getUpNodeId();
824}
825
826// Here the return of the vector use the move constructor
827vector<idNode> MergeTree::getNodeNeighbors(const idNode &n) {
828 Node *node = getNode(n);
829 auto nbUp = node->getNumberOfUpSuperArcs();
830 auto nbDown = node->getNumberOfDownSuperArcs();
831
832 vector<idNode> res(nbDown + nbUp);
833
834 SimplexId currentPos = 0;
835
836 // Nodes below
837 for(idSuperArc i = 0; i < nbDown; i++) {
838 const idSuperArc &corArc = node->getDownSuperArcId(i);
839 const idNode &corNode = getSuperArc(corArc)->getDownNodeId();
840 res[currentPos++] = corNode;
841 }
842
843 // Nodes above
844 for(idSuperArc i = 0; i < nbUp; i++) {
845 const idSuperArc &corArc = node->getUpSuperArcId(i);
846 const idNode &corNode = getSuperArc(corArc)->getUpNodeId();
847 res[currentPos++] = corNode;
848 }
849
850 return res;
851}
852
853vector<idNode> MergeTree::getNodeUpNeighbors(const idNode &n) {
854 Node *node = getNode(n);
855 auto nbUp = node->getNumberOfUpSuperArcs();
856
857 vector<idNode> res(nbUp);
858
859 // Nodes above
860 for(idSuperArc i = 0; i < nbUp; i++) {
861 const idSuperArc &corArc = node->getUpSuperArcId(i);
862 const idNode &corNode = getSuperArc(corArc)->getUpNodeId();
863 res[i] = corNode;
864 }
865
866 return res;
867}
868
869vector<idNode> MergeTree::getNodeDownNeighbors(const idNode &n) {
870 Node *node = getNode(n);
871 auto nbDown = node->getNumberOfDownSuperArcs();
872
873 vector<idNode> res(nbDown);
874
875 // Nodes above
876 for(idNode i = 0; i < nbDown; i++) {
877 const idSuperArc &corArc = node->getDownSuperArcId(i);
878 const idNode &corNode = getSuperArc(corArc)->getDownNodeId();
879 res[i] = corNode;
880 }
881
882 return res;
883}
884
885// hide / clear
886
888 const idSuperArc nbArc = getNode(baseNode)->getNumberOfUpSuperArcs();
889 for(idSuperArc i = 0; i < nbArc; ++i) {
890 const idSuperArc &upsaid = getNode(baseNode)->getUpSuperArcId(i);
891 SuperArc *curArc = getSuperArc(upsaid);
892 if(curArc->getUpCT() != treeData_.partition) {
893 continue;
894 }
895
896 hideArc(upsaid);
897 hideNode(curArc->getUpNodeId());
898 }
899
900 getNode(baseNode)->clearUpSuperArcs();
901}
902
904 const SimplexId &seed) {
905 const idSuperArc nbArc = getNode(baseNode)->getNumberOfDownSuperArcs();
906 for(idSuperArc i = 0; i < nbArc; ++i) {
907 const idSuperArc &downsaid = getNode(baseNode)->getDownSuperArcId(i);
908 SuperArc *curArc = getSuperArc(downsaid);
909 if(curArc->getDownCT() != treeData_.partition) {
910 continue;
911 }
912
913 Node *downNode = getNode(curArc->getDownNodeId());
914
915 if(isLower(downNode->getVertexId(), seed)) {
916 hideArc(downsaid);
917 hideNode(curArc->getDownNodeId());
918 }
919 }
920
921 removeHiddenDownArcs(baseNode);
922}
923
924// add a from parameter
926 const SimplexId &v) {
927 if(isCorrespondingNode(v)) {
928 const auto nbDown = getNode(baseNode)->getNumberOfDownSuperArcs();
929 for(idSuperArc aid = 0; aid < nbDown; aid++) {
930 const idSuperArc a = getNode(baseNode)->getDownSuperArcId(aid);
931 if(getSuperArc(a)->getDownCT() != treeData_.partition
932 || !getSuperArc(a)->isVisible()) {
933 continue;
934 }
935
936 const idNode downNode = getSuperArc(a)->getDownNodeId();
937
938 if(getNode(downNode)->getVertexId() == v) {
939 hideArc(a);
940 return a;
941 }
942 }
943 } else {
944 if(isCorrespondingArc(v)) {
946 idNode p = getSuperArc(a)->getUpNodeId();
947 while(p != baseNode && getNode(p)->getUpValence()) {
948 // SHOULD HAVE ONLY ONE ARC
949 if(getNode(p)->getUpValence() != 1)
950 cout << "Noise with up valence ! (hide&clear Leading to)" << endl;
951
952 a = getNode(p)->getUpSuperArcId(0);
953 p = getSuperArc(a)->getUpNodeId();
954 }
955 hideArc(a);
956 return a;
957 }
958 }
959
960 return nullSuperArc;
961}
962
963// }
964
965// Operators : find, print & clone
966// {
967
968// Print
970#ifdef TTK_ENABLE_OPENMP
971#pragma omp critical
972#endif
973 {
974 cout << "Partition : " << static_cast<unsigned>(treeData_.partition)
975 << endl;
976
977 cout << "Nodes----------" << endl;
978 for(idNode nid = 0; nid < getNumberOfNodes(); nid++) {
979 const Node &n = treeData_.nodes[nid];
980 if(n.isVisible()) {
981 cout << printNode(nid) << endl;
982 }
983 }
984
985 cout << "Arcs-----------" << endl;
986 for(idSuperArc said = 0; said < getNumberOfSuperArcs(); ++said) {
987 const SuperArc &sa = treeData_.superArcs[said];
988 if(sa.isVisible()) {
989 cout << printArc(said) << endl;
990 }
991 }
992
993 cout << "Leaves" << endl;
994 for(const auto &l : treeData_.leaves)
995 cout << " " << treeData_.nodes[l].getVertexId();
996 cout << endl;
997
998 cout << "Roots" << endl;
999 for(const auto &r : treeData_.roots)
1000 cout << " " << treeData_.nodes[r].getVertexId();
1001 cout << endl;
1002 }
1003}
1004
1005// Clone
1006std::shared_ptr<MergeTree> MergeTree::clone() const {
1007 auto newMT = std::make_shared<MergeTree>(
1009
1010 newMT->treeData_.superArcs = treeData_.superArcs;
1011 newMT->treeData_.nodes = treeData_.nodes;
1012 newMT->treeData_.leaves = treeData_.leaves;
1013 newMT->treeData_.roots = treeData_.roots;
1014 newMT->treeData_.arcsCrossingBelow = treeData_.arcsCrossingBelow;
1015 newMT->treeData_.arcsCrossingAbove = treeData_.arcsCrossingAbove;
1016 newMT->treeData_.vert2tree = treeData_.vert2tree;
1017
1018 return newMT;
1019}
1020
1031
1033 // we already have common data
1035 treeData_.nodes.swap(mt->treeData_.nodes);
1036 treeData_.leaves.swap(mt->treeData_.leaves);
1037 treeData_.roots.swap(mt->treeData_.roots);
1041}
1042
1043// }
1044// Simplification
1045// {
1046
1047// Hide the basenode and its upArc, merging the segmentation with masterArc
1048void MergeTree::hideAndMerge(const idSuperArc &mergingArcId,
1049 const idSuperArc &receptacleArcId,
1050 const bool preserveNode) {
1051 SuperArc *mergingArc = getSuperArc(mergingArcId);
1052 SuperArc *receptacleArc = getSuperArc(receptacleArcId);
1053
1054 // merge HERE WE LOST THE SORTED SEGM
1055 if(mergingArc->getVertSize() != -1) {
1056 receptacleArc->appendSegmentation(mergingArc->getSegmentation());
1057 }
1058
1059 if(!preserveNode) {
1060 hideNode(mergingArc->getDownNodeId());
1061 }
1062
1063 mergeArc(mergingArcId, receptacleArcId);
1064}
1065
1066void MergeTree::markThisArc(vector<ExtendedUnionFind *> &ufArray,
1067 const idNode &curNodeId,
1068 const idSuperArc &mergingArcId,
1069 const idNode &parentNodeId) {
1070 // size of this subtree segmentation + segmentation of this arc
1071 const auto &curSegmenSize = getSuperArc(mergingArcId)->getVertSize()
1072 + ufArray[curNodeId]->find()->getOrigin() + 2;
1073 // +2 for the merging nodes
1074
1075 // UF propagation
1076 if(ufArray[parentNodeId] == nullptr) {
1077 // Parent have never been seen : recopy UF
1078 ufArray[parentNodeId] = ufArray[curNodeId]->find();
1079 ufArray[parentNodeId]->find()->setOrigin(curSegmenSize);
1080 // cout << "will merge " << getNode(curNodeId)->getVertexId() << endl;
1081 } else {
1082 // The parent have already been visited : merge UF and segmentation
1083 const auto &oldSegmentationSize
1084 = ufArray[parentNodeId]->find()->getOrigin();
1086 ufArray[curNodeId]->find(), ufArray[parentNodeId]->find())
1087 ->setOrigin(oldSegmentationSize + curSegmenSize);
1088 // cout << "Union on " << getNode(parentNodeId)->getVertexId();
1089 // cout << " from " << getNode(curNodeId)->getVertexId() << endl;
1090 }
1091
1092 // The last parentNode is the root of the subtree
1093 // cout << "for " << getNode(curNodeId)->getVertexId() << " set root " <<
1094 // getNode(parentNodeId)->getVertexId() << endl;
1095 ufArray[parentNodeId]->find()->setData(-((ufDataType)parentNodeId) - 1);
1096}
1097
1098idSuperArc MergeTree::newUpArc(const idNode &curNodeId,
1099 vector<ExtendedUnionFind *> &ufArray) {
1100
1101 idSuperArc keepArc = nullSuperArc;
1102 const auto nbUp = getNode(curNodeId)->getNumberOfUpSuperArcs();
1103 for(idSuperArc d = 0; d < nbUp; d++) {
1104 const idSuperArc &curArc = getNode(curNodeId)->getUpSuperArcId(d);
1105 if(!getSuperArc(curArc)->isVisible())
1106 continue;
1107
1108 keepArc = curArc;
1109
1110 const idNode &newUp = getSuperArc(curArc)->getUpNodeId();
1111 if(!ufArray[newUp]
1112 || ufArray[curNodeId]->find() != ufArray[newUp]->find()) {
1113 return curArc;
1114 }
1115 }
1116
1117 // cout << "node " << getNode(curNodeId)->getVertexId() << " have no up arc to
1118 // take" << endl;
1119 return keepArc;
1120}
1121
1122idSuperArc MergeTree::newDownArc(const idNode &curNodeId,
1123 vector<ExtendedUnionFind *> &ufArray) {
1124
1125 idSuperArc keepArc = nullSuperArc;
1126 const auto nbDown = getNode(curNodeId)->getNumberOfDownSuperArcs();
1127 for(idSuperArc d = 0; d < nbDown; d++) {
1128 const idSuperArc &curArc = getNode(curNodeId)->getDownSuperArcId(d);
1129 if(!getSuperArc(curArc)->isVisible())
1130 continue;
1131
1132 keepArc = curArc;
1133
1134 const idNode &newDown = getSuperArc(curArc)->getDownNodeId();
1135 if(!ufArray[newDown]
1136 || ufArray[curNodeId]->find() != ufArray[newDown]->find()) {
1137 return curArc;
1138 }
1139 }
1140
1141 // cout << "node " << printNode(curNodeId) << " have no down arc to take" <<
1142 // endl;
1143 return keepArc;
1144}
1145
1146tuple<idNode, idNode, SimplexId> MergeTree::createReceptArc(
1147 const idNode &root,
1148 const idSuperArc &receptacleArcId,
1149 vector<ExtendedUnionFind *> &ufArray,
1150 const vector<pair<idSuperArc, idSuperArc>> &valenceOffsets) {
1151
1152 const bool DEBUG = false;
1153
1154 ExtendedUnionFind *ufRoot = ufArray[root]->find();
1155 idNode downNode = root;
1156 idNode upNode = root;
1157
1158 if(DEBUG) {
1159 cout << " create receptarc for root : " << printNode(root) << endl;
1160 cout << " custom valence : " << valenceOffsets[root].first;
1161 cout << " + " << valenceOffsets[root].second << endl;
1162 }
1163
1164 // descend in the tree until valence is not 2
1165 SimplexId segmentationSize = ufRoot->find()->getOrigin();
1166 // cout << "init size " << segmentationSize << endl;
1167
1168 // We need a valence of 2 (we don't want to cross a futur saddle
1169 // But we want to avoid up && down = root
1170
1171 while(getNode(downNode)->getUpValence() - valenceOffsets[downNode].second == 1
1172 && getNode(downNode)->getDownValence() - valenceOffsets[downNode].first
1173 == 1) {
1174 // take the down node not leading to the current subtree
1175 // if have an UF, merge with current subtree
1176 // (else init it?)
1177 const idSuperArc &downArc = newDownArc(downNode, ufArray);
1178
1179 // deal with arc segmentation
1180 segmentationSize += getSuperArc(downArc)->getVertSize() + 2;
1181 // + 2 for merging nodes
1182
1183 downNode = getSuperArc(downArc)->getDownNodeId();
1184 const idNode tmpUp = getSuperArc(downArc)->getUpNodeId();
1185
1186 if(DEBUG) {
1187 cout << "change down to " << getNode(downNode)->getVertexId() << endl;
1188 cout << " new segmentation : " << segmentationSize << endl;
1189 }
1190
1191 // UF
1192 if(ufArray[downNode]) {
1193 segmentationSize += ufArray[downNode]->find()->getOrigin();
1194 // ExtendedUnionFind::makeUnion(ufArray[downNode], ufRoot);
1195 if(ufArray[downNode]->find()->getData() < 0) {
1196 ufArray[downNode]->find()->setData(receptacleArcId);
1197 }
1198 } else {
1199 // ufArray[downNode] = ufRoot->find();
1200 }
1201 mergeArc(downArc, receptacleArcId, false);
1202 hideNode(tmpUp);
1203 }
1204
1205 if(DEBUG) {
1206 cout << " continue receptarc for root : " << printNode(root) << endl;
1207 cout << " custom valence : " << valenceOffsets[root].first;
1208 cout << " + " << valenceOffsets[root].second << endl;
1209 }
1210
1211 // for a node to be regular, it must have a down valence = 1 but
1212 // but we process the down SO ADAPT HERE
1213 while(getNode(upNode)->getUpValence() - valenceOffsets[upNode].second == 1
1214 && getNode(upNode)->getDownValence() - valenceOffsets[upNode].first
1215 == 1) {
1216
1217 const idSuperArc &upArc = newUpArc(upNode, ufArray);
1218
1219 segmentationSize += getSuperArc(upArc)->getVertSize() + 2;
1220
1221 upNode = getSuperArc(upArc)->getUpNodeId();
1222 const idNode tmpDown = getSuperArc(upArc)->getDownNodeId();
1223
1224 if(DEBUG) {
1225 cout << "change up to " << getNode(upNode)->getVertexId() << endl;
1226 cout << " new segmentation : " << segmentationSize << endl;
1227 }
1228
1229 if(ufArray[upNode]) {
1230 segmentationSize += ufArray[upNode]->find()->getOrigin();
1231 // ExtendedUnionFind::makeUnion(ufArray[upNode], ufRoot);
1232 if(ufArray[upNode]->find()->getData() < 0) {
1233 ufArray[upNode]->find()->setData(receptacleArcId);
1234 }
1235 } else {
1236 // ufArray[upNode] = ufRoot->find();
1237 }
1238 mergeArc(upArc, receptacleArcId, false);
1239 hideNode(tmpDown);
1240 }
1241
1242 // if upNode == downNode, take one none merging arc randomly
1243 // (this case is possible if several degenerate node are following)
1244 if(upNode == downNode) {
1245 // several degen. nodes adjacent
1246 // Prefer down for JT / ST
1247 const idSuperArc tmpDown = newDownArc(downNode, ufArray);
1248 const idSuperArc tmpUp = newUpArc(upNode, ufArray);
1249
1250 if(tmpDown == nullSuperArc) {
1251 upNode = getSuperArc(tmpUp)->getUpNodeId();
1252 if(ufArray[upNode]) {
1253 segmentationSize += ufArray[upNode]->find()->getOrigin();
1254 // ExtendedUnionFind::makeUnion(ufArray[downNode], ufRoot);
1255 } else {
1256 ufArray[upNode] = ufRoot->find();
1257 }
1258 getSuperArc(tmpUp)->merge(receptacleArcId);
1259 } else {
1260 downNode = getSuperArc(tmpDown)->getDownNodeId();
1261 if(ufArray[downNode]) {
1262 segmentationSize += ufArray[downNode]->find()->getOrigin();
1263 // ExtendedUnionFind::makeUnion(ufArray[upNode], ufRoot);
1264 } else {
1265 ufArray[downNode] = ufRoot->find();
1266 }
1267 getSuperArc(tmpDown)->merge(receptacleArcId);
1268 }
1269
1270 if(tmpDown != nullSuperArc)
1271 segmentationSize += getSuperArc(tmpDown)->getVertSize() + 2;
1272 if(tmpUp != nullSuperArc)
1273 segmentationSize += getSuperArc(tmpUp)->getVertSize() + 2;
1274
1275 // cout << " special : new segmentation : " << segmentationSize << endl;
1276 }
1277
1278 return make_tuple(downNode, upNode, segmentationSize);
1279}
1280
1281// }
1282// ---------------------- Debug
1283// {
1284
1285// }
1286
1287// Operators
1288
1289std::ostream &ttk::cf::operator<<(std::ostream &o, ttk::cf::SuperArc const &a) {
1290 o << a.getDownNodeId() << " <>> " << a.getUpNodeId();
1291 return o;
1292}
1293
1294std::ostream &ttk::cf::operator<<(std::ostream &o, ttk::cf::Node const &n) {
1295 o << n.getNumberOfDownSuperArcs() << " .-. " << n.getNumberOfUpSuperArcs();
1296 return o;
1297}
#define TTK_FORCE_USE(x)
Force the compiler to use the function/method parameter.
Definition BaseClass.h:57
#define ttkNotUsed(x)
Mark function/method parameters that are not used in the function body at all.
Definition BaseClass.h:47
#define DEBUG(msg)
void setDebugMsgPrefix(const std::string &prefix)
Definition Debug.h:364
void setOrigin(const SimplexId &origin)
Definition ExtendedUF.h:64
const SimplexId & getOrigin() const
Definition ExtendedUF.h:72
static ExtendedUnionFind * makeUnion(ExtendedUnionFind *uf0, ExtendedUnionFind *uf1)
Definition ExtendedUF.h:98
ExtendedUnionFind * find()
Definition ExtendedUF.h:77
void hideAndClearArcsBelow(const idNode &baseNode, const SimplexId &seed)
void hideArc(const idSuperArc &sa)
void updateCorrespondingNode(const SimplexId &vert, const idNode &val)
Definition MergeTree.h:353
idSuperArc getNumberOfVisibleArcs() const
Definition MergeTree.h:187
idNode makeNode(const SimplexId &vertexId, const SimplexId &linked=nullVertex)
Node * vertex2Node(const SimplexId &vert)
Definition MergeTree.h:340
idSuperArc insertNode(Node *node, const bool segment)
void delNode(const idNode &node, std::list< std::vector< std::pair< SimplexId, bool > > > &storage, const std::pair< SimplexId, bool > *mv=nullptr, const SimplexId &nbm=0)
idNode getNumberOfNodes() const
Definition MergeTree.h:235
idSuperArc openSuperArc(const idNode &downNodeId, const bool overlapB, const bool overlapA)
std::string printArc(const idSuperArc &a)
Definition MergeTree.h:580
std::vector< idNode > getNodeNeighbors(const idNode &node)
void doSwap(MergeTree *mt)
std::shared_ptr< Scalars > scalars_
Definition MergeTree.h:44
bool isCorrespondingArc(const SimplexId &val) const
Definition MergeTree.h:294
void mergeArc(const idSuperArc &sa, const idSuperArc &recept, const bool changeConnectivity=true)
idNode getParent(const idNode &n)
void removeInternalDownArcs(const idNode &node)
void removeHiddenDownArcs(const idNode &n)
idSuperArc getNumberOfExternalDownArcs(const idNode &node)
std::shared_ptr< MergeTree > clone() const
void markThisArc(std::vector< ExtendedUnionFind * > &ufArray, const idNode &curNodeId, const idSuperArc &mergingArcId, const idNode &parentNodeId)
std::vector< idNode > getNodeUpNeighbors(const idNode &n)
idSuperArc getNumberOfSuperArcs() const
Definition MergeTree.h:183
Node * getUpNode(const SuperArc *a)
bool isCorrespondingNode(const SimplexId &val) const
Definition MergeTree.h:298
idSuperArc reverseInsertNode(Node *node, const bool segment)
SimplexId getVertBelowSeed(const idSuperArc &arc, const std::pair< SimplexId, bool > &seed, const std::vector< idCorresp > &vert2treeOther)
idSuperArc makeSuperArc(const idNode &downNodeId, const idNode &upNodeId, const bool overlapB, const bool overlapA, std::pair< SimplexId, bool > *vertexList=nullptr, SimplexId vertexSize=-1)
std::string printNode(const idNode &n)
Definition MergeTree.h:598
void updateCorrespondingArc(const SimplexId &arc, const idSuperArc &val)
Definition MergeTree.h:348
bool isHigher(const SimplexId &a, const SimplexId &b) const
Definition MergeTree.h:649
idNode getCorrespondingNodeId(const SimplexId &val) const
Definition MergeTree.h:310
idSuperArc getCorrespondingSuperArcId(const SimplexId &val) const
Definition MergeTree.h:321
void closeSuperArc(const idSuperArc &superArcId, const idNode &upNodeId, const bool overlapB, const bool overlapA)
void hideNode(const idNode &node)
TreeData treeData_
Definition MergeTree.h:47
Node * getDownNode(const SuperArc *a)
void parallelUpdateSegmentation(const bool ct=false)
idSuperArc getNumberOfUnmergedDownArcs(const idNode &n)
bool isLower(const SimplexId &a, const SimplexId &b) const
Definition MergeTree.h:645
void hideAndClearArcsAbove(const idNode &baseNode)
idSuperArc hideAndClearLeadingTo(const idNode &baseNode, const SimplexId &v)
~MergeTree() override
SimplexId insertNodeAboveSeed(const idSuperArc &arc, const std::pair< SimplexId, bool > &seed)
bool alreadyExtLinked(const idNode &node, const idPartition &tree, const idNode &treeNode)
const std::vector< SuperArc > & getSuperArc() const
Definition MergeTree.h:197
Node * getNode(const idNode &nodeId)
Definition MergeTree.h:244
void parallelInitNodeValence(const int nbThreadValence)
void updateSegmentation()
Definition MergeTree.cpp:44
std::shared_ptr< Params > params_
Definition MergeTree.h:43
std::vector< idNode > getNodeDownNeighbors(const idNode &n)
SimplexId getVertexId() const
idSuperArc clearUpSuperArcs()
idSuperArc clearDownSuperArcs()
void removeDownSuperArc(const idSuperArc &idSa)
void addDownSuperArcId(const idSuperArc &downSuperArcId)
idSuperArc getDownSuperArcId(const idSuperArc &neighborId) const
idSuperArc getNumberOfUpSuperArcs() const
bool isHidden() const
void setUpValence(const idSuperArc &v)
void removeUpSuperArc(const idSuperArc &idSa)
bool isVisible() const
idSuperArc getUpSuperArcId(const idSuperArc &neighborId) const
void setDownValence(const idSuperArc &v)
void removeDownSuperArcPos(const idSuperArc &i)
idSuperArc getNumberOfDownSuperArcs() const
idPartition getDownCT() const
const idNode & getUpNodeId() const
const SimplexId & getVertSize()
void appendSegmentation(const std::vector< std::pair< SimplexId, bool > > &other)
std::vector< std::pair< SimplexId, bool > > & getSegmentation()
std::pair< SimplexId, bool > * getVertList()
void setVertList(std::pair< SimplexId, bool > *vl)
void setVertSize(const SimplexId &s)
const idSuperArc & getReplacantArcId() const
const idNode & getDownNodeId() const
idPartition getUpCT() const
std::ostream & operator<<(std::ostream &o, Node const &n)
numThread idPartition
long unsigned int idSuperArc
SuperArc index in vect_superArcs_.
long int ufDataType
type stored by UnionFind
unsigned int idNode
Node index in vect_nodes_.
The Topology ToolKit.
int SimplexId
Identifier type for simplices of any dimension.
Definition DataTypes.h:22
std::vector< idSuperArc > arcsCrossingAbove
std::vector< idNode > leaves
std::vector< Node > nodes
std::vector< SuperArc > superArcs
std::vector< idSuperArc > arcsCrossingBelow
std::vector< idNode > roots
std::vector< idCorresp > vert2tree