TTK
Loading...
Searching...
No Matches
FTMTree_MT.cpp
Go to the documentation of this file.
1
13
14#include "FTMTree_MT.h"
15
16#include <stack>
17
18#define PRIOR(x)
19// #define PRIOR(x) priority(x)
20
21#ifdef __INTEL_COMPILER
22#define HIGHER
23#endif
24
25#ifndef TTK_ENABLE_OPENMP
26#define HIGHER
27#endif
28
29#ifdef TTK_ENABLE_OMP_PRIORITY
30#define OPTIONAL_PRIORITY(value) priority(value)
31#else
32#define OPTIONAL_PRIORITY(value)
33#endif
34
35using namespace std;
36using namespace ttk;
37using namespace ftm;
38
39FTMTree_MT::FTMTree_MT(const std::shared_ptr<Params> &params,
40 const std::shared_ptr<Scalars> &scalars,
41 TreeType type)
42 : params_(params), scalars_(scalars) {
43
44 this->setDebugMsgPrefix("FTMtree_MT");
45
46 mt_data_.treeType = type;
47}
48
50 this->clear();
51}
52
54
55 // remove UF data structures
56 if(!mt_data_.ufs.empty()) {
57 sort(mt_data_.ufs.begin(), mt_data_.ufs.end());
58 auto it = unique(mt_data_.ufs.begin(), mt_data_.ufs.end());
59 mt_data_.ufs.resize(std::distance(mt_data_.ufs.begin(), it));
60 }
61
62 // if (mt_data_.propagation) {
63 // Already cleaned by ufs
64 // sort(mt_data_.propagation->begin(), mt_data_.propagation->end());
65 // auto it = unique(mt_data_.propagation->begin(),
66 // mt_data_.propagation->end());
67 // mt_data_.propagation->resize(std::distance(mt_data_.propagation->begin(),
68 // it)); for (auto* addr : *mt_data_.propagation) if(addr) delete addr;
69 // }
70
71 // remove containers
73 mt_data_.superArcs.reset();
74 }
75 if(mt_data_.nodes) {
76 mt_data_.nodes.reset();
77 }
78 if(mt_data_.roots) {
79 mt_data_.roots.reset();
80 }
81 mt_data_.leaves.clear();
82 mt_data_.vert2tree.clear();
83 mt_data_.trunkSegments.clear();
84 mt_data_.visitOrder.clear();
85 mt_data_.ufs.clear();
86
87 if(mt_data_.states) {
88 mt_data_.states.reset();
89 }
90 mt_data_.propagation.clear();
91 mt_data_.valences.clear();
92 mt_data_.openedNodes.clear();
93
94#ifdef TTK_ENABLE_FTM_TREE_STATS_TIME
95 mt_data_.activeTasksStats.clear();
96#endif
97
98 this->params_.reset();
99 this->scalars_.reset();
100}
101
103
104 const idSuperArc nbArcs = mt_data_.superArcs->size();
105
106 // Make reserve
107
108 // SuperArc i correspond to segment i,
109 // one arc correspond to one segment
110 vector<SimplexId> sizes(nbArcs);
111
112 // get the size of each segment
113 const idSuperArc arcChunkSize = getChunkSize(nbArcs);
114 const idSuperArc arcChunkNb = getChunkCount(nbArcs);
115 for(idSuperArc arcChunkId = 0; arcChunkId < arcChunkNb; ++arcChunkId) {
116 // WHY shared(sizes) is needed ??
117#ifdef TTK_ENABLE_OPENMP
118#pragma omp task firstprivate(arcChunkId) shared(sizes) \
119 OPTIONAL_PRIORITY(isPrior())
120#endif
121 {
122 const idSuperArc lowerBound = arcChunkId * arcChunkSize;
123 const idSuperArc upperBound
124 = min(nbArcs, (arcChunkId + 1) * arcChunkSize);
125 for(idSuperArc a = lowerBound; a < upperBound; ++a) {
126 sizes[a]
127 = max(SimplexId{0}, (*mt_data_.superArcs)[a].getNbVertSeen() - 1);
128 }
129 }
130 }
131#ifdef TTK_ENABLE_OPENMP
132#pragma omp taskwait
133#endif
134
135 // change segments size using the created vector
137
138 Timer segmentsSet;
139
140 // Fill segments using vert2tree
141
142 // current status of the segmentation of this arc
143 vector<SimplexId> posSegm(nbArcs, 0);
144
145 // Segments are connex region of geometry forming
146 // the segmentation (sorted in ascending order)
147 const SimplexId nbVert = scalars_->size;
148 const SimplexId chunkSize = getChunkSize();
149 const SimplexId chunkNb = getChunkCount();
150 for(SimplexId chunkId = 0; chunkId < chunkNb; ++chunkId) {
151#ifdef TTK_ENABLE_OPENMP
152#pragma omp task firstprivate(chunkId) shared(posSegm) \
153 OPTIONAL_PRIORITY(isPrior())
154#endif
155 {
156 const SimplexId lowerBound = chunkId * chunkSize;
157 const SimplexId upperBound = min(nbVert, (chunkId + 1) * chunkSize);
158 for(SimplexId i = lowerBound; i < upperBound; ++i) {
159 const auto vert = scalars_->sortedVertices[i];
160 if(isCorrespondingArc(vert)) {
162 SimplexId vertToAdd;
163 if(mt_data_.visitOrder[vert] != nullVertex) {
164 // Opposite order for Split Tree
165 vertToAdd = mt_data_.visitOrder[vert];
166 if(isST())
167 vertToAdd = getSuperArc(sa)->getNbVertSeen() - vertToAdd - 2;
168 mt_data_.segments_[sa][vertToAdd] = vert;
169 } else if(mt_data_.trunkSegments.empty()) {
170 // MT computation
171#ifdef TTK_ENABLE_OPENMP
172#pragma omp atomic capture
173#endif
174 vertToAdd = posSegm[sa]++;
175 mt_data_.segments_[sa][vertToAdd] = vert;
176 }
177
178 } // end is arc
179 } // end for
180 } // end task
181 }
182#ifdef TTK_ENABLE_OPENMP
183#pragma omp taskwait
184#endif
185
186 printTime(segmentsSet, "segmentation set vertices", 4);
187
188 if(mt_data_.trunkSegments.empty()) {
189 // sort arc that have been filled by the trunk
190 // only for MT
191 Timer segmentsSortTime;
192 for(idSuperArc a = 0; a < nbArcs; ++a) {
193 if(posSegm[a]) {
194#ifdef TTK_ENABLE_OPENMP
195#pragma omp task firstprivate(a) OPTIONAL_PRIORITY(isPrior())
196#endif
197 mt_data_.segments_[a].sort(scalars_.get());
198 }
199 }
200#ifdef TTK_ENABLE_OPENMP
201#pragma omp taskwait
202#endif
203 printTime(segmentsSortTime, "segmentation sort vertices", 4);
204 } else {
205 // Contour tree: we create the arc segmentation for arcs in the trunk
206 Timer segmentsArcTime;
207 for(idSuperArc a = 0; a < nbArcs; ++a) {
208 // CT computation, we have already the vert list
209 if(!mt_data_.trunkSegments[a].empty()) {
210#ifdef TTK_ENABLE_OPENMP
211#pragma omp task firstprivate(a) OPTIONAL_PRIORITY(isPrior())
212#endif
213 mt_data_.segments_[a].createFromList(
216 }
217 }
218#ifdef TTK_ENABLE_OPENMP
219#pragma omp taskwait
220#endif
221
222 printTime(segmentsArcTime, "segmentation arcs lists", 4);
223 }
224
225 // Update SuperArc region
226
227 // ST have a segmentation which is in the reverse-order of its build
228 // ST have a segmentation sorted in ascending order as JT
229 for(idSuperArc arcChunkId = 0; arcChunkId < arcChunkNb; ++arcChunkId) {
230#ifdef TTK_ENABLE_OPENMP
231#pragma omp task firstprivate(arcChunkId) OPTIONAL_PRIORITY(isPrior())
232#endif
233 {
234 const idSuperArc lowerBound = arcChunkId * arcChunkSize;
235 const idSuperArc upperBound
236 = min(nbArcs, (arcChunkId + 1) * arcChunkSize);
237 for(idSuperArc a = lowerBound; a < upperBound; ++a) {
238 // avoid empty region
239 if(mt_data_.segments_[a].size()) {
240 (*mt_data_.superArcs)[a].concat(
241 mt_data_.segments_[a].begin(), mt_data_.segments_[a].end());
242 }
243 }
244 }
245 }
246#ifdef TTK_ENABLE_OPENMP
247#pragma omp taskwait
248#endif
249}
250
251std::shared_ptr<FTMTree_MT> FTMTree_MT::clone() const {
252 auto newMT
253 = std::make_shared<FTMTree_MT>(params_, scalars_, mt_data_.treeType);
254
255 newMT->mt_data_.superArcs = mt_data_.superArcs;
256 newMT->mt_data_.nodes = mt_data_.nodes;
257 newMT->mt_data_.leaves = mt_data_.leaves;
258 newMT->mt_data_.roots = mt_data_.roots;
259 newMT->mt_data_.vert2tree = mt_data_.vert2tree;
260
261 return newMT;
262}
263
264void FTMTree_MT::closeArcsUF(idNode closeNode, UF uf) {
265 for(const auto &sa : uf->find()->getOpenedArcs()) {
266 closeSuperArc(sa, closeNode);
267 }
268 uf->find()->clearOpenedArcs();
269}
270
271void FTMTree_MT::closeSuperArc(idSuperArc superArcId, idNode upNodeId) {
272#ifndef TTK_ENABLE_KAMIKAZE
273
274 if(superArcId >= getNumberOfSuperArcs()) {
275 cout << "[Merge Tree] closeSuperArc on a inexisting arc !" << endl;
276 return;
277 }
278
279 if(upNodeId >= getNumberOfNodes()) {
280 cout << "[Merge Tree] closeOpenedArc on a inexisting node !" << endl;
281 return;
282 }
283
284#endif
285 (*mt_data_.superArcs)[superArcId].setUpNodeId(upNodeId);
286 (*mt_data_.nodes)[upNodeId].addDownSuperArcId(superArcId);
287}
288
290 Node *mainNode = getNode(node);
291
292 if(mainNode->getNumberOfUpSuperArcs() == 0) {
293
294 // Root: No Superarc
295#ifndef TTK_ENABLE_KAMIKAZE
296 if(mainNode->getNumberOfDownSuperArcs() != 1) {
297 // Root with several children: impossible /\ .
298 cout << endl << "[FTMTree_MT]:delNode won't delete ";
299 cout << mainNode->getVertexId() << " (root) with ";
300 cout << static_cast<unsigned>(mainNode->getNumberOfDownSuperArcs())
301 << " down ";
302 cout << static_cast<unsigned>(mainNode->getNumberOfUpSuperArcs())
303 << " up ";
304 return;
305 }
306#endif
307
308 idSuperArc downArc = mainNode->getDownSuperArcId(0);
309 Node *downNode = getNode((*mt_data_.superArcs)[downArc].getDownNodeId());
310
311 downNode->removeUpSuperArc(downArc);
312 mainNode->clearDownSuperArcs();
313
314 } else if(mainNode->getNumberOfDownSuperArcs() < 2) {
315 // Have one up arc
316
317 // We delete the upArc of this node,
318 // if there is a down arc, we reattach it to the upNode
319
320 idSuperArc upArc = mainNode->getUpSuperArcId(0);
321 idNode upId = (*mt_data_.superArcs)[upArc].getUpNodeId();
322 Node *upNode = getNode(upId);
323
324 upNode->removeDownSuperArc(upArc);
325 mainNode->clearUpSuperArcs();
326
327 if(mainNode->getNumberOfDownSuperArcs()) {
328 // Have one down arc
329
330 // Reconnect
331 idSuperArc downArc = mainNode->getDownSuperArcId(0);
332 (*mt_data_.superArcs)[downArc].setUpNodeId(upId);
333 upNode->addDownSuperArcId(downArc);
334 mainNode->clearDownSuperArcs();
335
336 // Segmentation
337 (*mt_data_.superArcs)[downArc].concat((*mt_data_.superArcs)[upArc]);
338 }
339 }
340#ifndef TTK_ENABLE_KAMIKAZE
341 else
342 cerr << "delete node with multiple childrens " << endl;
343#endif
344}
345
347 for(auto &arc : *mt_data_.superArcs) {
348 arc.createSegmentation(scalars_.get());
349 }
350}
351
352tuple<SimplexId, SimplexId>
353 FTMTree_MT::getBoundsFromVerts(const vector<SimplexId> &trunkVerts) const {
354 SimplexId begin, stop;
355
356 if(isST()) {
357 begin = 0;
358 stop = scalars_->offsets[trunkVerts[0]];
359 } else {
360 begin = scalars_->offsets[trunkVerts[0]];
361 stop = scalars_->size;
362 }
363
364 return make_tuple(begin, stop);
365}
366
368 return &((*mt_data_.nodes)[a->getDownNodeId()]);
369}
370
372 return a->getDownNodeId();
373}
374
376 if(isST())
377 return getUpNode(a);
378
379 return getDownNode(a);
380}
381
383 if(isST())
384 return getUpNodeId(a);
385
386 return getDownNodeId(a);
387}
388
390 return &((*mt_data_.nodes)[a->getUpNodeId()]);
391}
392
394 return a->getUpNodeId();
395}
396
398 if(isST())
399 return getDownNode(a);
400
401 return getUpNode(a);
402}
403
405 if(isST())
406 return getDownNodeId(a);
407
408 return getUpNodeId(a);
409}
410
411idNode FTMTree_MT::getVertInRange(const vector<SimplexId> &range,
412 const SimplexId v,
413 const idNode last) const {
414 idNode idRes = last;
415 const idNode rangeSize = range.size();
416 while(idRes + 1 < rangeSize && comp_.vertLower(range[idRes + 1], v)) {
417 ++idRes;
418 }
419 return idRes;
420}
421
422idSuperArc FTMTree_MT::insertNode(Node *node, const bool segm) {
423 // Normal insert : existing arc stay below inserted (JT example)
424 // * - <- upNodeId
425 // | \ | <- newSA
426 // | * <- newNodeId
427 // | | <- currentSA
428 // - - -
429 // already present
430 if(isCorrespondingNode(node->getVertexId())) {
431 Node *myNode = vertex2Node(node->getVertexId());
432 // If it has been hidden / replaced we need to re-make it
433 idSuperArc correspondingArcId = myNode->getUpSuperArcId(0);
434 updateCorrespondingArc(myNode->getVertexId(), correspondingArcId);
435 }
436
437 idNode upNodeId, newNodeId;
438 idSuperArc currentSA, newSA;
439 SimplexId origin;
440
441 // Create new node
442 currentSA = getCorrespondingSuperArcId(node->getVertexId());
443 upNodeId = (*mt_data_.superArcs)[currentSA].getUpNodeId();
444 origin = (*mt_data_.nodes)[(*mt_data_.superArcs)[currentSA].getDownNodeId()]
445 .getOrigin();
446 newNodeId = makeNode(node, origin);
447
448 // Connectivity
449 // Insert only node inside the partition : created arc don t cross
450 newSA = makeSuperArc(newNodeId, upNodeId);
451
452 (*mt_data_.superArcs)[currentSA].setUpNodeId(newNodeId);
453 (*mt_data_.nodes)[upNodeId].removeDownSuperArc(currentSA);
454 (*mt_data_.nodes)[newNodeId].addDownSuperArcId(currentSA);
455
456 // cut the vertex list at the node position and
457 // give each arc its part.
458 if(segm) {
460 (*mt_data_.superArcs)[newSA].concat(
461 get<1>((*mt_data_.superArcs)[currentSA].splitBack(
462 node->getVertexId(), scalars_.get())));
463 } else {
464 (*mt_data_.superArcs)[newSA].concat(
465 get<1>((*mt_data_.superArcs)[currentSA].splitFront(
466 node->getVertexId(), scalars_.get())));
467 }
468 }
469
470 return newSA;
471}
472
474#ifndef TTK_ENABLE_KAMIKAZE
475 if(vertexId < 0 || vertexId >= scalars_->size) {
476 this->printMsg({{"make node, wrong vertex :", std::to_string(vertexId)},
477 {" on ", std::to_string(scalars_->size)}},
479 return -1;
480 }
481#endif
482
483 if(isCorrespondingNode(vertexId)) {
484 return getCorrespondingNodeId(vertexId);
485 }
486
487 idNode newNodeId = mt_data_.nodes->getNext();
488 (*mt_data_.nodes)[newNodeId].setVertexId(vertexId);
489 (*mt_data_.nodes)[newNodeId].setTermination(term);
490 updateCorrespondingNode(vertexId, newNodeId);
491
492 return newNodeId;
493}
494
496 return makeNode(n->getVertexId());
497}
498
500
501{
502 idSuperArc newSuperArcId = mt_data_.superArcs->getNext();
503 (*mt_data_.superArcs)[newSuperArcId].setDownNodeId(downNodeId);
504 (*mt_data_.superArcs)[newSuperArcId].setUpNodeId(upNodeId);
505
506 (*mt_data_.nodes)[downNodeId].addUpSuperArcId(newSuperArcId);
507 (*mt_data_.nodes)[upNodeId].addDownSuperArcId(newSuperArcId);
508
509 return newSuperArcId;
510}
511
513 // we already have common data
515 mt.mt_data_.superArcs.reset();
517 mt.mt_data_.nodes.reset();
518 mt_data_.leaves = std::move(mt.mt_data_.leaves);
520 mt.mt_data_.roots.reset();
521 mt_data_.vert2tree = std::move(mt.mt_data_.vert2tree);
522}
523
525 Timer normTime;
526 sortLeaves(true);
527 if(this->params_->treeType != TreeType::Contour) {
528 sortNodes();
529 sortArcs();
530 }
531
532 auto getNodeParentArcNb
533 = [&](const idNode curNode, const bool goUp) -> idSuperArc {
534 if(goUp) {
535 return getNode(curNode)->getNumberOfUpSuperArcs();
536 }
537
538 return getNode(curNode)->getNumberOfDownSuperArcs();
539 };
540
541 auto getNodeParentArc
542 = [&](const idNode curNode, const bool goUp, idSuperArc i) -> idSuperArc {
543 if(goUp) {
544 return getNode(curNode)->getUpSuperArcId(i);
545 }
546
547 return getNode(curNode)->getDownSuperArcId(i);
548 };
549
550 auto getArcParentNode
551 = [&](const idSuperArc curArc, const bool goUp) -> idNode {
552 if(goUp) {
553 return getSuperArc(curArc)->getUpNodeId();
554 }
555
556 return getSuperArc(curArc)->getDownNodeId();
557 };
558
559 std::queue<tuple<idNode, bool>> q;
560 std::stack<tuple<idNode, bool>> qr;
561 for(const idNode n : mt_data_.leaves) {
562 bool goUp = isJT() || isST() || getNode(n)->getNumberOfUpSuperArcs();
563 if(goUp)
564 q.emplace(make_tuple(n, goUp));
565 else
566 qr.emplace(make_tuple(n, goUp));
567 }
568
569 while(!qr.empty()) {
570 q.emplace(qr.top());
571 qr.pop();
572 }
573
574 // Normalized id
575 idSuperArc nIdMin = 0;
576 idSuperArc nIdMax = getNumberOfSuperArcs() - 1;
577
578 vector<bool> seenUp(getNumberOfSuperArcs(), false);
579 vector<bool> seenDown(getNumberOfSuperArcs(), false);
580
581 while(!q.empty()) {
582 bool goUp;
583 idNode curNodeId;
584 tie(curNodeId, goUp) = q.front();
585 q.pop();
586
587 if(goUp)
588 sortUpArcs(curNodeId);
589 else
590 sortDownArcs(curNodeId);
591
592 // Assign arc above
593 const idSuperArc nbArcParent = getNodeParentArcNb(curNodeId, goUp);
594 for(idSuperArc pid = 0; pid < nbArcParent; pid++) {
595 const idSuperArc currentArcId = getNodeParentArc(curNodeId, goUp, pid);
596 if(goUp) {
597 if(getSuperArc(currentArcId)->getNormalizedId() == nullSuperArc) {
598 getSuperArc(currentArcId)->setNormalizeIds(nIdMin++);
599 }
600 if(!seenUp[currentArcId]) {
601 q.emplace(make_tuple(getArcParentNode(currentArcId, goUp), goUp));
602 seenUp[currentArcId] = true;
603 }
604 } else {
605 if(getSuperArc(currentArcId)->getNormalizedId() == nullSuperArc) {
606 getSuperArc(currentArcId)->setNormalizeIds(nIdMax--);
607 }
608 if(!seenDown[currentArcId]) {
609 q.emplace(make_tuple(getArcParentNode(currentArcId, goUp), goUp));
610 seenDown[currentArcId] = true;
611 }
612 }
613 }
614 }
615
616#ifndef TTK_ENABLE_KAMIKAZE
617 if(std::abs((long)nIdMax - (long)nIdMin) > 1) {
618 this->printMsg({"error during normalize, tree compromised: ",
619 std::to_string(nIdMin), " ", std::to_string(nIdMax)},
621 }
622#endif
623
624 printTime(normTime, "normalize ids", 4);
625}
626
628#ifndef TTK_ENABLE_KAMIKAZE
629 if(downNodeId >= getNumberOfNodes()) {
630 this->printErr("openSuperArc on a inexisting node !");
631 return -2;
632 }
633#endif
634
635 idSuperArc newSuperArcId = mt_data_.superArcs->getNext();
636 (*mt_data_.superArcs)[newSuperArcId].setDownNodeId(downNodeId);
637 (*mt_data_.nodes)[downNodeId].addUpSuperArcId(newSuperArcId);
638
639 return newSuperArcId;
640}
641
643 const SuperArc *sa = getSuperArc(a);
644 stringstream res;
645 const SimplexId dv = getNode(sa->getDownNodeId())->getVertexId();
646 const SimplexId uv = getNode(sa->getUpNodeId())->getVertexId();
647 res << a;
648 res << " : ";
649 if(dv != nullVertex) {
650 res << dv << " -- ";
651 } else {
652 res << "XX -- ";
653 }
654 if(uv != nullVertex) {
655 res << uv;
656 } else {
657 res << "XX";
658 }
659
660 res.seekg(0, ios::end);
661 while(res.tellg() < 25) {
662 res << " ";
663 res.seekg(0, ios::end);
664 }
665 res.seekg(0, ios::beg);
666
667 res << "segm #" << sa->regionSize() << " / " << scalars_->size; // << " -> ";
668
669 res.seekg(0, ios::end);
670
671 while(res.tellg() < 45) {
672 res << " ";
673 res.seekg(0, ios::end);
674 }
675 res.seekg(0, ios::beg);
676
677 res << sa->printReg();
678 return res.str();
679}
680
682 const Node *node = getNode(n);
683 stringstream res;
684 res << n;
685 res << " : (";
686 res << node->getVertexId() << ") \\ ";
687
688 for(idSuperArc i = 0; i < node->getNumberOfDownSuperArcs(); ++i) {
689 res << "+";
690 res << node->getDownSuperArcId(i) << " ";
691 }
692
693 res << " / ";
694
695 for(idSuperArc i = 0; i < node->getNumberOfUpSuperArcs(); ++i) {
696 res << "+";
697 res << node->getUpSuperArcId(i) << " ";
698 }
699
700 return res.str();
701}
702
704 if(debugLevel_ > 1) {
705 if(debugLevel_ > 2) {
707 }
708 this->printMsg("number of threads : " + std::to_string(threadNumber_));
709 if(debugLevel_ > 2) {
710 this->printMsg("* debug lvl : " + std::to_string(debugLevel_));
711 string tt;
712 if(params_->treeType == TreeType::Contour) {
713 tt = "Contour";
714 } else if(params_->treeType == TreeType::Join) {
715 tt = "Join";
716 } else if(params_->treeType == TreeType::Split) {
717 tt = "Split";
718 } else if(params_->treeType == TreeType::Join_Split) {
719 tt = "Join + Split";
720 }
721 this->printMsg("* tree type : " + tt);
723 }
724 }
725}
726
728 const string &s,
729 const int debugLevel) const {
730
731 if(this->debugLevel_ >= debugLevel) {
732 stringstream st;
733
734 for(int i = 3; i < debugLevel; i++)
735 st << "-";
736 st << s;
737
738#ifdef TTK_ENABLE_FTM_TREE_PROCESS_SPEED
739 const auto nbScalars = scalars_->size;
740 int speed = nbScalars / t.getElapsedTime();
741 st << " at " << speed << " vert/s";
742#endif
743
744 this->printMsg(st.str(), 1, t.getElapsedTime(), this->threadNumber_);
745 }
746 return 1;
747}
748
750#ifdef TTK_ENABLE_OPENMP
751#pragma omp critical
752#endif
753 {
754 cout << "Nodes----------" << endl;
755 for(idNode nid = 0; nid < getNumberOfNodes(); nid++) {
756 cout << printNode(nid) << endl;
757 }
758
759 cout << "Arcs-----------" << endl;
760 for(idSuperArc said = 0; said < getNumberOfSuperArcs(); ++said) {
761 cout << printArc(said) << endl;
762 }
763
764 cout << "Leaves" << endl;
765 for(const auto &l : mt_data_.leaves)
766 cout << " " << (*mt_data_.nodes)[l].getVertexId();
767 cout << endl;
768
769 cout << "Roots" << endl;
770 for(const auto &r : *mt_data_.roots)
771 cout << " " << (*mt_data_.nodes)[r].getVertexId();
772 cout << endl;
773 }
774}
775
776void FTMTree_MT::sortLeaves(const bool para) {
777 auto indirect_sort = [&](const idNode a, const idNode b) {
778 return comp_.vertLower(
780 };
781
782 if(para) {
783 TTK_PSORT(this->threadNumber_, mt_data_.leaves.begin(),
784 mt_data_.leaves.end(), indirect_sort);
785 } else {
786 std::sort(mt_data_.leaves.begin(), mt_data_.leaves.end(), indirect_sort);
787 }
788}
789
791 std::vector<idNode> sortedNodes(this->mt_data_.nodes->size());
792 std::iota(sortedNodes.begin(), sortedNodes.end(), 0);
793
794 const auto direct_sort = [&](const Node &a, const Node &b) {
795 // sort according to scalar field
796 return this->comp_.vertLower(a.getVertexId(), b.getVertexId());
797 };
798
799 const auto indirect_sort = [&](const idNode a, const idNode b) {
800 return direct_sort(*this->getNode(a), *this->getNode(b));
801 };
802
803 TTK_PSORT(
804 this->threadNumber_, sortedNodes.begin(), sortedNodes.end(), indirect_sort);
805
806 TTK_PSORT(this->threadNumber_, this->mt_data_.nodes->begin(),
807 this->mt_data_.nodes->end(), direct_sort);
808
809 // reverse sortedNodes
810 std::vector<idNode> revSortedNodes(sortedNodes.size());
811 for(size_t i = 0; i < sortedNodes.size(); ++i) {
812 revSortedNodes[sortedNodes[i]] = i;
813 }
814
815 // update leaves
816 for(auto &leaf : this->mt_data_.leaves) {
817 leaf = revSortedNodes[leaf];
818 }
819
820 // update roots
821 for(auto &root : (*this->mt_data_.roots)) {
822 root = revSortedNodes[root];
823 }
824
825 // update arcs
826 for(auto &arc : (*this->mt_data_.superArcs)) {
827 arc.setDownNodeId(revSortedNodes[arc.getDownNodeId()]);
828 arc.setUpNodeId(revSortedNodes[arc.getUpNodeId()]);
829 }
830
831 // update vert2tree
832 for(size_t i = 0; i < sortedNodes.size(); ++i) {
833 const auto &node{(*this->mt_data_.nodes)[i]};
834 if(this->isCorrespondingNode(node.getVertexId())) {
835 this->updateCorrespondingNode(node.getVertexId(), i);
836 }
837 }
838}
839
841 std::vector<idNode> sortedArcs(this->mt_data_.superArcs->size());
842 std::iota(sortedArcs.begin(), sortedArcs.end(), 0);
843
844 const auto direct_sort = [&](const SuperArc &a, const SuperArc &b) {
845 // sort by NodeId (nodes should be already sorted with sortNodes)
846 const auto adn{a.getDownNodeId()};
847 const auto aun{a.getUpNodeId()};
848 const auto bdn{b.getDownNodeId()};
849 const auto bun{b.getUpNodeId()};
850 return std::tie(adn, aun) < std::tie(bdn, bun);
851 };
852
853 auto indirect_sort = [&](const idSuperArc &a, const idSuperArc &b) {
854 const auto aa{this->getSuperArc(a)};
855 const auto bb{this->getSuperArc(b)};
856 return direct_sort(*aa, *bb);
857 };
858
859 TTK_PSORT(
860 this->threadNumber_, sortedArcs.begin(), sortedArcs.end(), indirect_sort);
861
862 TTK_PSORT(this->threadNumber_, this->mt_data_.superArcs->begin(),
863 this->mt_data_.superArcs->end(), direct_sort);
864
865 // reverse sortedArcs
866 std::vector<idSuperArc> revSortedArcs(sortedArcs.size());
867 for(size_t i = 0; i < sortedArcs.size(); ++i) {
868 revSortedArcs[sortedArcs[i]] = i;
869 }
870
871 // update nodes
872 std::vector<idSuperArc> updatedArcs{};
873 for(auto &node : (*this->mt_data_.nodes)) {
874 {
875 const auto da{node.getNumberOfDownSuperArcs()};
876 updatedArcs.clear();
877 updatedArcs.resize(da);
878 for(idSuperArc i = 0; i < da; ++i) {
879 updatedArcs[i] = revSortedArcs[node.getDownSuperArcId(i)];
880 }
881 node.clearDownSuperArcs();
882 for(const auto &arc : updatedArcs) {
883 node.addDownSuperArcId(arc);
884 }
885 }
886 {
887 const auto ua{node.getNumberOfUpSuperArcs()};
888 updatedArcs.clear();
889 updatedArcs.resize(ua);
890 for(idSuperArc i = 0; i < ua; ++i) {
891 updatedArcs[i] = revSortedArcs[node.getUpSuperArcId(i)];
892 }
893 node.clearUpSuperArcs();
894 for(const auto &arc : updatedArcs) {
895 node.addUpSuperArcId(arc);
896 }
897 }
898 }
899
900 // update vert2tree
901 for(size_t i = 0; i < this->mt_data_.vert2tree.size(); ++i) {
902 if(this->isCorrespondingArc(i)) {
903 this->updateCorrespondingArc(
904 i, revSortedArcs[this->getCorrespondingSuperArcId(i)]);
905 }
906 }
907}
908
909vector<idNode> FTMTree_MT::sortedNodes(const bool para) {
910 vector<idNode> sortedNodes(mt_data_.nodes->size());
911 std::iota(sortedNodes.begin(), sortedNodes.end(), 0);
912
913 auto indirect_sort = [&](const idNode a, const idNode b) {
914 return comp_.vertLower(
916 };
917
918 if(para) {
919 TTK_PSORT(this->threadNumber_, sortedNodes.begin(), sortedNodes.end(),
920 indirect_sort);
921 } else {
922#ifdef TTK_ENABLE_OPENMP
923#pragma omp single
924#endif
925 { std::sort(sortedNodes.begin(), sortedNodes.end(), indirect_sort); }
926 }
927
928 return sortedNodes;
929}
930
931SimplexId FTMTree_MT::trunkCTSegmentation(const vector<SimplexId> &trunkVerts,
932 const SimplexId begin,
933 const SimplexId stop) {
934 const int nbTasksThreads = 40;
935 const auto sizeBackBone = abs(stop - begin);
936 const auto chunkSize = getChunkSize(sizeBackBone, nbTasksThreads);
937 const auto chunkNb = getChunkCount(sizeBackBone, nbTasksThreads);
938 // si pas efficace vecteur de la taille de node ici a la place de acc
939 idNode lastVertInRange = 0;
941 for(SimplexId chunkId = 0; chunkId < chunkNb; ++chunkId) {
942#ifdef TTK_ENABLE_OPENMP
943#pragma omp task firstprivate(chunkId, lastVertInRange) shared(trunkVerts) \
944 OPTIONAL_PRIORITY(isPrior())
945#endif
946 {
947 vector<SimplexId> regularList;
948 if(params_->segm) {
949 regularList.reserve(25);
950 }
951 const SimplexId lowerBound = begin + chunkId * chunkSize;
952 const SimplexId upperBound
953 = min(stop, (begin + (chunkId + 1) * chunkSize));
954 if(lowerBound != upperBound) {
955 const SimplexId pos = isST() ? upperBound - 1 : lowerBound;
956 lastVertInRange
957 = getVertInRange(trunkVerts, scalars_->sortedVertices[pos], 0);
958 }
959 for(SimplexId v = lowerBound; v < upperBound; ++v) {
960 const SimplexId s
961 = isST() ? scalars_->sortedVertices[lowerBound + upperBound - 1 - v]
962 : scalars_->sortedVertices[v];
963 if(isCorrespondingNull(s)) {
964 const idNode oldVertInRange = lastVertInRange;
965 lastVertInRange = getVertInRange(trunkVerts, s, lastVertInRange);
966 const idSuperArc thisArc = upArcFromVert(trunkVerts[lastVertInRange]);
967 updateCorrespondingArc(s, thisArc);
968
969 if(params_->segm) {
970 if(oldVertInRange == lastVertInRange) {
971 regularList.emplace_back(s);
972 } else {
973 // accumulated to have only one atomic update when needed
974 const idSuperArc oldArc
975 = upArcFromVert(trunkVerts[oldVertInRange]);
976 if(regularList.size()) {
977#ifdef TTK_ENABLE_OPENMP
978#pragma omp critical
979#endif
980 {
981 mt_data_.trunkSegments[oldArc].emplace_back(regularList);
982 regularList.clear();
983 }
984 }
985 // hand.vtu, sequential: 28554
986 regularList.emplace_back(s);
987 }
988 }
989 }
990 }
991 // force increment last arc
992 const idNode baseNode
993 = getCorrespondingNodeId(trunkVerts[lastVertInRange]);
994 const idSuperArc upArc = getNode(baseNode)->getUpSuperArcId(0);
995 if(regularList.size()) {
996#ifdef TTK_ENABLE_OPENMP
997#pragma omp critical
998#endif
999 {
1000 mt_data_.trunkSegments[upArc].emplace_back(regularList);
1001 regularList.clear();
1002 }
1003 }
1004 }
1005 }
1006#ifdef TTK_ENABLE_OPENMP
1007#pragma omp taskwait
1008#endif
1009 // count added
1010 SimplexId tot = 0;
1011#ifdef TTK_ENABLE_FTM_TREE_PROCESS_SPEED
1012 for(const auto &l : *mt_data_.trunkSegments) {
1013 SimplexId arcSize = 0;
1014 for(const auto &v : l) {
1015 arcSize += v.size();
1016 }
1017 tot += arcSize;
1018 }
1019#endif
1020 return tot;
1021}
1022
1023SimplexId FTMTree_MT::trunkSegmentation(const vector<SimplexId> &trunkVerts,
1024 const SimplexId begin,
1025 const SimplexId stop) {
1026 // Assign missing vert to the good arc
1027 // and also add the corresponding number for
1028 // futur arc reserve
1029 const int nbTasksThreads = 40;
1030 const auto sizeBackBone = abs(stop - begin);
1031 const auto chunkSize = getChunkSize(sizeBackBone, nbTasksThreads);
1032 const auto chunkNb = getChunkCount(sizeBackBone, nbTasksThreads);
1033 // si pas efficace vecteur de la taille de node ici a la place de acc
1034 SimplexId tot = 0;
1035 for(SimplexId chunkId = 0; chunkId < chunkNb; ++chunkId) {
1036#ifdef TTK_ENABLE_OPENMP
1037#pragma omp task firstprivate(chunkId) shared(trunkVerts, tot) \
1038 OPTIONAL_PRIORITY(isPrior())
1039#endif
1040 {
1041 idNode lastVertInRange = 0;
1042 SimplexId acc = 0;
1043
1044 const SimplexId lowerBound = begin + chunkId * chunkSize;
1045 const SimplexId upperBound
1046 = min(stop, (begin + (chunkId + 1) * chunkSize));
1047 for(SimplexId v = lowerBound; v < upperBound; ++v) {
1048 const SimplexId s
1049 = isST() ? scalars_->sortedVertices[lowerBound + upperBound - 1 - v]
1050 : scalars_->sortedVertices[v];
1051 if(isCorrespondingNull(s)) {
1052 const idNode oldVertInRange = lastVertInRange;
1053 lastVertInRange = getVertInRange(trunkVerts, s, lastVertInRange);
1054 const idSuperArc thisArc = upArcFromVert(trunkVerts[lastVertInRange]);
1055 updateCorrespondingArc(s, thisArc);
1056
1057 if(params_->segm) {
1058 if(oldVertInRange == lastVertInRange) {
1059 ++acc;
1060 } else {
1061 // accumulated to have only one atomic update when needed
1062 const idSuperArc oldArc
1063 = upArcFromVert(trunkVerts[oldVertInRange]);
1064 getSuperArc(oldArc)->atomicIncVisited(acc);
1065#ifdef TTK_ENABLE_FTM_TREE_PROCESS_SPEED
1066#ifdef TTK_ENABLE_OPENMP
1067#pragma omp atomic update
1068#endif
1069 tot += acc;
1070#endif
1071 acc = 1;
1072 }
1073 }
1074 }
1075 }
1076 // force increment last arc
1077 const idNode baseNode
1078 = getCorrespondingNodeId(trunkVerts[lastVertInRange]);
1079 const idSuperArc upArc = getNode(baseNode)->getUpSuperArcId(0);
1080 getSuperArc(upArc)->atomicIncVisited(acc);
1081#ifdef TTK_ENABLE_FTM_TREE_PROCESS_SPEED
1082#ifdef TTK_ENABLE_OPENMP
1083#pragma omp atomic update
1084#endif
1085 tot += acc;
1086#endif
1087 } // end task
1088 }
1089#ifdef TTK_ENABLE_OPENMP
1090#pragma omp taskwait
1091#endif
1092 return tot;
1093}
1094
1095std::ostream &ttk::ftm::operator<<(std::ostream &o,
1096 ttk::ftm::SuperArc const &a) {
1097 o << a.getDownNodeId() << " <>> " << a.getUpNodeId();
1098 return o;
1099}
1100
1101std::ostream &ttk::ftm::operator<<(std::ostream &o, ttk::ftm::Node const &n) {
1102 o << n.getNumberOfDownSuperArcs() << " .-. " << n.getNumberOfUpSuperArcs();
1103 return o;
1104}
#define TTK_PSORT(NTHREADS,...)
Parallel sort macro.
Definition: OpenMP.h:46
int threadNumber_
Definition: BaseClass.h:95
int debugLevel_
Definition: Debug.h:379
void setDebugMsgPrefix(const std::string &prefix)
Definition: Debug.h:364
int printMsg(const std::string &msg, const debug::Priority &priority=debug::Priority::INFO, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cout) const
Definition: Debug.h:118
int printErr(const std::string &msg, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cerr) const
Definition: Debug.h:149
double getElapsedTime()
Definition: Timer.h:15
FTMAtomicVector< idSuperArc > & getOpenedArcs()
Definition: FTMAtomicUF.h:86
void clearOpenedArcs()
Definition: FTMAtomicUF.h:90
AtomicUF * find()
Definition: FTMAtomicUF.h:38
Node * getUpperNode(const SuperArc *a)
Definition: FTMTree_MT.cpp:397
bool isCorrespondingNode(const SimplexId val) const
Definition: FTMTree_MT.h:449
std::shared_ptr< Params > params_
Definition: FTMTree_MT.h:86
~FTMTree_MT() override
Definition: FTMTree_MT.cpp:49
FTMTree_MT(const std::shared_ptr< Params > &params, const std::shared_ptr< Scalars > &scalars, TreeType type)
Definition: FTMTree_MT.cpp:39
std::string printNode(idNode n)
Definition: FTMTree_MT.cpp:681
SuperArc * getSuperArc(idSuperArc i)
Definition: FTMTree_MT.h:367
Node * getDownNode(const SuperArc *a)
Definition: FTMTree_MT.cpp:367
void printParams() const
Definition: FTMTree_MT.cpp:703
idNode getNumberOfNodes() const
Definition: FTMTree_MT.h:389
idNode getUpNodeId(const SuperArc *a)
Definition: FTMTree_MT.cpp:393
SimplexId getChunkSize(const SimplexId nbVerts=-1, const SimplexId nbtasks=100) const
Definition: FTMTree_MT.h:819
bool isCorrespondingNull(const SimplexId val) const
Definition: FTMTree_MT.h:453
void delNode(idNode node)
Definition: FTMTree_MT.cpp:289
std::string printArc(idSuperArc a)
Definition: FTMTree_MT.cpp:642
Node * vertex2Node(const SimplexId vert)
Definition: FTMTree_MT.h:487
void move(FTMTree_MT &mt)
Definition: FTMTree_MT.cpp:512
idSuperArc upArcFromVert(const SimplexId v)
Definition: FTMTree_MT.h:815
std::tuple< SimplexId, SimplexId > getBoundsFromVerts(const std::vector< SimplexId > &nodes) const
Definition: FTMTree_MT.cpp:353
Node * getLowerNode(const SuperArc *a)
Definition: FTMTree_MT.cpp:375
idNode getDownNodeId(const SuperArc *a)
Definition: FTMTree_MT.cpp:371
idSuperArc insertNode(Node *node, const bool segm=true)
Definition: FTMTree_MT.cpp:422
bool isCorrespondingArc(const SimplexId val) const
Definition: FTMTree_MT.h:445
void closeArcsUF(idNode closeNode, UF uf)
Definition: FTMTree_MT.cpp:264
idNode getLowerNodeId(const SuperArc *a)
Definition: FTMTree_MT.cpp:382
void sortUpArcs(const idNode nid)
Definition: FTMTree_MT.h:838
virtual SimplexId trunkSegmentation(const std::vector< SimplexId > &pendingNodesVerts, const SimplexId begin, const SimplexId stop)
void sortNodes()
Sort tree nodes according to vertex order.
Definition: FTMTree_MT.cpp:790
idNode getCorrespondingNodeId(const SimplexId val) const
Definition: FTMTree_MT.h:459
idSuperArc getNumberOfSuperArcs() const
Definition: FTMTree_MT.h:363
idNode getUpperNodeId(const SuperArc *a)
Definition: FTMTree_MT.cpp:404
bool isST() const
Definition: FTMTree_MT.h:293
void sortLeaves(const bool parallel=false)
Definition: FTMTree_MT.cpp:776
idNode getVertInRange(const std::vector< SimplexId > &range, const SimplexId v, const idNode last=0) const
Definition: FTMTree_MT.cpp:411
void sortDownArcs(const idNode nid)
Definition: FTMTree_MT.h:847
int printTime(Timer &t, const std::string &s, const int debugLevel=2) const
Definition: FTMTree_MT.cpp:727
SimplexId getChunkCount(const SimplexId nbVerts=-1, const SimplexId nbTasks=100) const
Definition: FTMTree_MT.h:832
SimplexId trunkCTSegmentation(const std::vector< SimplexId > &pendingNodesVerts, const SimplexId begin, const SimplexId stop)
Definition: FTMTree_MT.cpp:931
idSuperArc openSuperArc(idNode downNodeId)
Definition: FTMTree_MT.cpp:627
std::shared_ptr< FTMTree_MT > clone() const
Definition: FTMTree_MT.cpp:251
idNode makeNode(SimplexId vertexId, SimplexId linked=nullVertex)
Definition: FTMTree_MT.cpp:473
void buildSegmentation()
use vert2tree to compute the segmentation of the fresh built merge tree.
Definition: FTMTree_MT.cpp:102
idSuperArc getCorrespondingSuperArcId(const SimplexId val) const
Definition: FTMTree_MT.h:470
idSuperArc makeSuperArc(idNode downNodeId, idNode upNodeId)
Definition: FTMTree_MT.cpp:499
void updateCorrespondingNode(const SimplexId vert, const idNode node)
Definition: FTMTree_MT.h:498
Node * getUpNode(const SuperArc *a)
Definition: FTMTree_MT.cpp:389
bool isJT() const
Definition: FTMTree_MT.h:289
Node * getNode(idNode nodeId)
Definition: FTMTree_MT.h:393
void closeSuperArc(idSuperArc superArcId, idNode upNodeId)
Definition: FTMTree_MT.cpp:271
std::shared_ptr< Scalars > scalars_
Definition: FTMTree_MT.h:87
void sortArcs()
Sort tree arcs.
Definition: FTMTree_MT.cpp:840
Comparison comp_
Definition: FTMTree_MT.h:91
void updateCorrespondingArc(const SimplexId vert, const idSuperArc arc)
Definition: FTMTree_MT.h:493
std::vector< idNode > sortedNodes(const bool parallel=false)
Definition: FTMTree_MT.cpp:909
idSuperArc getUpSuperArcId(idSuperArc neighborId) const
Definition: FTMNode.h:105
idSuperArc clearUpSuperArcs()
Definition: FTMNode.h:133
void addDownSuperArcId(idSuperArc downSuperArcId)
Definition: FTMNode.h:119
idSuperArc getNumberOfDownSuperArcs() const
Definition: FTMNode.h:82
idSuperArc getDownSuperArcId(idSuperArc neighborId) const
Definition: FTMNode.h:94
void removeUpSuperArc(idSuperArc idSa)
Definition: FTMNode.h:158
idSuperArc clearDownSuperArcs()
Definition: FTMNode.h:127
void removeDownSuperArc(idSuperArc idSa)
Definition: FTMNode.h:146
SimplexId getVertexId() const
Definition: FTMNode.h:54
idSuperArc getNumberOfUpSuperArcs() const
Definition: FTMNode.h:86
idSegment size() const
void resize(const std::vector< SimplexId > &sizes)
void setNormalizeIds(const idSuperArc id)
Definition: FTMSuperArc.h:114
void atomicIncVisited(const SimplexId nb=1)
Definition: FTMSuperArc.h:95
idNode getUpNodeId() const
Definition: FTMSuperArc.h:68
SimplexId getNbVertSeen() const
Definition: FTMSuperArc.h:106
std::string printReg() const
Definition: FTMSuperArc.h:238
size_t regionSize() const
Definition: FTMSuperArc.h:172
idNode getDownNodeId() const
Definition: FTMSuperArc.h:72
long unsigned int idSuperArc
SuperArc index in vect_superArcs_.
Definition: FTMDataTypes.h:37
std::ostream & operator<<(std::ostream &o, Node const &n)
unsigned int idNode
Node index in vect_nodes_.
Definition: FTMDataTypes.h:39
The Topology ToolKit.
int SimplexId
Identifier type for simplices of any dimension.
Definition: DataTypes.h:22
Segments segments_
Definition: FTMTree_MT.h:71
std::shared_ptr< FTMAtomicVector< SuperArc > > superArcs
Definition: FTMTree_MT.h:46
std::shared_ptr< FTMAtomicVector< CurrentState > > states
Definition: FTMTree_MT.h:60
std::vector< std::list< std::vector< SimplexId > > > trunkSegments
Definition: FTMTree_MT.h:54
std::shared_ptr< FTMAtomicVector< Node > > nodes
Definition: FTMTree_MT.h:47
std::vector< SimplexId > visitOrder
Definition: FTMTree_MT.h:53
std::vector< UF > propagation
Definition: FTMTree_MT.h:59
std::vector< idCorresp > vert2tree
Definition: FTMTree_MT.h:52
std::vector< UF > ufs
Definition: FTMTree_MT.h:58
std::shared_ptr< FTMAtomicVector< idNode > > roots
Definition: FTMTree_MT.h:48
std::vector< valence > valences
Definition: FTMTree_MT.h:62
TreeType treeType
Definition: FTMTree_MT.h:43
std::vector< idNode > leaves
Definition: FTMTree_MT.h:49
std::vector< char > openedNodes
Definition: FTMTree_MT.h:64