TTK
Loading...
Searching...
No Matches
MergeTreeBase.h
Go to the documentation of this file.
1
11
12#pragma once
13
14#include <AssignmentSolver.h>
15#include <FTMNode.h>
16#include <FTMTree.h>
17#include <FTMTreePPUtils.h>
18#include <FTMTreeUtils.h>
19
20#include "MergeTreeUtils.h"
21
22namespace ttk {
23
24 class MergeTreeBase : virtual public Debug {
25 protected:
28 double epsilonTree1_ = 0;
29 double epsilonTree2_ = 0;
30 double epsilon2Tree1_ = 100;
31 double epsilon2Tree2_ = 100;
32 double epsilon3Tree1_ = 100;
33 double epsilon3Tree2_ = 100;
36 bool useMinMaxPair_ = true;
38
42 bool keepSubtree_ = false;
43
44 bool distanceSquaredRoot_ = true; // squared root
45 bool useFullMerge_ = false;
46
48 bool convertToDiagram_ = false;
49
50 // Double input
51 double mixtureCoefficient_ = 0.5;
52 bool useDoubleInput_ = false;
53
54 // Old
55 bool parallelize_ = true;
56 int nodePerTask_ = 32;
57 bool cleanTree_ = true;
58
59 // Clean correspondence
60 std::vector<std::vector<int>> treesNodeCorr_;
61
62 public:
65 "MergeTreeBase"); // inherited from Debug: prefix will be printed
66 // at the beginning of every msg
67 }
68
69 void setAssignmentSolver(int assignmentSolver) {
70 assignmentSolverID_ = assignmentSolver;
71 }
72
75 }
76
77 void setEpsilonTree1(double epsilon) {
78 epsilonTree1_ = epsilon;
79 }
80
81 void setEpsilonTree2(double epsilon) {
82 epsilonTree2_ = epsilon;
83 }
84
85 void setEpsilon2Tree1(double epsilon) {
86 epsilon2Tree1_ = epsilon;
87 }
88
89 void setEpsilon2Tree2(double epsilon) {
90 epsilon2Tree2_ = epsilon;
91 }
92
93 void setEpsilon3Tree1(double epsilon) {
94 epsilon3Tree1_ = epsilon;
95 }
96
97 void setEpsilon3Tree2(double epsilon) {
98 epsilon3Tree2_ = epsilon;
99 }
100
101 void setPersistenceThreshold(double pt) {
103 }
104
105 void setParallelize(bool para) {
106 parallelize_ = para;
107 }
108
109 void setNodePerTask(int npt) {
110 nodePerTask_ = npt;
111 }
112
113 void setBranchDecomposition(bool useBD) {
114 branchDecomposition_ = useBD;
115 }
116
117 void setNormalizedWasserstein(bool normalizedWasserstein) {
118 normalizedWasserstein_ = normalizedWasserstein;
119 }
120
121 void setKeepSubtree(bool keepSubtree) {
122 keepSubtree_ = keepSubtree;
123 }
124
125 void setBarycenterMergeTree(bool imt) {
127 }
128
129 void setDistanceSquaredRoot(bool distanceSquaredRoot) {
130 distanceSquaredRoot_ = distanceSquaredRoot;
131 }
132
133 void setUseMinMaxPair(bool useMinMaxPair) {
134 useMinMaxPair_ = useMinMaxPair;
135 }
136
137 void setDeleteMultiPersPairs(bool deleteMultiPersPairsT) {
138 deleteMultiPersPairs_ = deleteMultiPersPairsT;
139 }
140
141 void setCleanTree(bool clean) {
142 cleanTree_ = clean;
143 }
144
145 void setIsPersistenceDiagram(bool isPD) {
147 }
148
149 std::vector<std::vector<int>> getTreesNodeCorr() {
150 return treesNodeCorr_;
151 }
152
153 // ------------------------------------------------------------------------
154 // Double Input
155 // ------------------------------------------------------------------------
156 double mixDistancesMinMaxPairWeight(bool isFirstInput) {
157 return (
159 ? (isFirstInput ? mixtureCoefficient_ : (1.0 - mixtureCoefficient_))
160 : (isFirstInput ? 1.0 / std::pow(mixDistancesWeight(isFirstInput), 2)
161 : 0.0));
162 }
163
164 double mixDistancesWeight(bool isFirstInput) {
165 return (isFirstInput ? std::min(mixtureCoefficient_ * 2, 1.0)
166 : std::min(-mixtureCoefficient_ * 2 + 2, 1.0));
167 }
168
169 template <class dataType>
170 double mixDistances(dataType distance1, dataType distance2) {
171 return mixDistancesWeight(true) * distance1
172 + mixDistancesWeight(false) * distance2;
173 }
174
175 template <class dataType>
176 void
177 mixDistancesMatrix(std::vector<std::vector<dataType>> &distanceMatrix,
178 std::vector<std::vector<dataType>> &distanceMatrix2) {
179 for(unsigned int i = 0; i < distanceMatrix.size(); ++i)
180 for(unsigned int j = 0; j < distanceMatrix[i].size(); ++j)
181 distanceMatrix[i][j] = mixDistances<dataType>(
182 distanceMatrix[i][j], distanceMatrix2[i][j]);
183 }
184
185 // ------------------------------------------------------------------------
186 // Tree Preprocessing
187 // ------------------------------------------------------------------------
188 // Epsilon 1 processing
189 template <class dataType>
191 double epsilon,
192 std::vector<std::vector<ftm::idNode>> &treeNodeMerged,
193 bool mergeByPersistence = false) {
194 bool fullMerge = (epsilon == 100);
195 fullMerge &= useFullMerge_;
196
197 treeNodeMerged.clear();
198 treeNodeMerged.resize(tree->getNumberOfNodes());
199
200 if(mergeByPersistence)
201 ftm::computePersistencePairs<dataType>(
202 tree); // need to have the pairing (if merge by persistence)
203
204 // Compute epsilon value
205 dataType maxValue = tree->getValue<dataType>(0);
206 dataType minValue = tree->getValue<dataType>(0);
207 for(unsigned int i = 0; i < tree->getNumberOfNodes(); ++i) {
208 if(!tree->isRoot(i) and !tree->isLeaf(i)) {
209 dataType iValue = tree->getValue<dataType>(i);
210 if(mergeByPersistence) {
211 maxValue = (maxValue < iValue) ? iValue : maxValue;
212 minValue = (minValue > iValue) ? iValue : minValue;
213 } else {
214 ftm::idNode parent = tree->getParentSafe(i);
215 dataType parentValue = tree->getValue<dataType>(parent);
216 dataType tempMax = std::max(iValue, parentValue);
217 dataType tempMin = std::min(iValue, parentValue);
218 if((tempMax - tempMin) > (maxValue - minValue)) {
219 maxValue = tempMax;
220 minValue = tempMin;
221 }
222 }
223 }
224 }
225 double epsilonOri = epsilon;
226 epsilon = (maxValue - minValue) * epsilon / 100;
227
228 // For Farthest Saddle option
230 epsilon = tree->getMaximumPersistence<dataType>() * epsilonOri / 100;
231 bool isJT = tree->isJoinTree<dataType>();
232 auto isFarthest = [&](ftm::idNode a, ftm::idNode b) {
233 return (isJT
234 and tree->getValue<dataType>(a) > tree->getValue<dataType>(b))
235 or (not isJT
236 and tree->getValue<dataType>(a)
237 < tree->getValue<dataType>(b));
238 };
239 std::vector<ftm::idNode> farthestSaddle(tree->getNumberOfNodes());
240 for(unsigned int i = 0; i < farthestSaddle.size(); ++i)
241 farthestSaddle[i] = i;
242
243 // --- Merge saddle
244 // Create stack
245 std::stack<int> nodeStack;
246 std::queue<ftm::idNode> queue;
247 queue.emplace(tree->getRoot());
248 while(!queue.empty()) {
249 ftm::idNode node = queue.front();
250 queue.pop();
251 nodeStack.emplace(node);
252 std::vector<ftm::idNode> children;
253 tree->getChildren(node, children);
254 for(auto child : children)
255 queue.emplace(child);
256 }
257 // Iterate through nodes
258 while(!nodeStack.empty()) {
259 ftm::idNode nodeId = nodeStack.top();
260 nodeStack.pop();
261 if(!tree->isRoot(nodeId) and !tree->isLeaf(nodeId)) {
262 ftm::idNode parentNodeId = tree->getParentSafe(nodeId);
263 dataType nodeValue = tree->getValue<dataType>(nodeId);
265 nodeValue = tree->getValue<dataType>(farthestSaddle[nodeId]);
266 dataType parentNodeValue = tree->getValue<dataType>(parentNodeId);
267 dataType diffValue = std::max(nodeValue, parentNodeValue)
268 - std::min(nodeValue, parentNodeValue);
269 if(diffValue <= epsilon) {
270 ftm::idNode nodeIdToDelete, nodeIdToKeep;
271 if(mergeByPersistence) {
272 auto birthDeath1 = tree->getBirthDeath<dataType>(nodeId);
273 auto birthDeath2 = tree->getBirthDeath<dataType>(parentNodeId);
274 dataType pers1
275 = std::get<1>(birthDeath1) - std::get<0>(birthDeath1);
276 dataType pers2
277 = std::get<1>(birthDeath2) - std::get<0>(birthDeath2);
278 nodeIdToDelete = (pers1 > pers2) ? parentNodeId : nodeId;
279 nodeIdToKeep = (pers1 > pers2) ? nodeId : parentNodeId;
280 if(nodeIdToDelete == parentNodeId)
281 nodeStack.emplace(nodeId);
282 } else {
283 nodeIdToDelete = nodeId;
284 nodeIdToKeep = parentNodeId;
285 }
286 // Manage nodeMerged vector of vector
287 for(auto node : treeNodeMerged[nodeIdToDelete]) {
288 treeNodeMerged[nodeIdToKeep].push_back(node);
289 if(isFarthest(farthestSaddle[nodeIdToKeep],
290 tree->getNode(node)->getOrigin()))
291 farthestSaddle[nodeIdToKeep] = tree->getNode(node)->getOrigin();
292 }
293 treeNodeMerged[nodeIdToKeep].push_back(
294 tree->getNode(nodeIdToDelete)->getOrigin());
295 if(isFarthest(farthestSaddle[nodeIdToKeep], nodeIdToDelete))
296 farthestSaddle[nodeIdToKeep] = nodeIdToDelete;
297 treeNodeMerged[nodeIdToDelete].clear();
298 // Delete node
299 tree->deleteNode(nodeIdToDelete);
300 }
301 }
302 }
303
304 if(fullMerge) {
305 auto root = tree->getRoot();
306 tree->getNode(root)->setOrigin(root);
307 }
308 }
309
310 // Epsilon 2 and 3 processing
311 template <class dataType>
313 double epsilon2,
314 double epsilon3 = 100) {
315 bool fullMerge = (epsilon2 == 0);
316 fullMerge &= useFullMerge_;
317 epsilon2 /= 100;
318 epsilon3 /= 100;
319 dataType maxPers = tree->getMaximumPersistence<dataType>();
320
321 std::queue<ftm::idNode> queue;
322 queue.emplace(tree->getRoot());
323 while(!queue.empty()) {
324 ftm::idNode node = queue.front();
325 queue.pop();
326 ftm::idNode nodeParent = tree->getParentSafe(node);
327 if(!tree->isRoot(node)) {
328 const double nodePers = tree->getNodePersistence<dataType>(node);
329 const double nodeParentPers
330 = tree->getNodePersistence<dataType>(nodeParent);
331 if(nodePers / nodeParentPers > epsilon2
332 and nodePers / maxPers < epsilon3)
333 tree->setParent(node, tree->getParentSafe(nodeParent));
334 }
335 std::vector<ftm::idNode> children;
336 tree->getChildren(node, children);
337 for(auto child : children)
338 queue.emplace(child);
339 }
340
341 if(fullMerge) {
342 auto root = tree->getRoot();
343 if(tree->getNode(root)->getOrigin() != (int)root) {
344 tree->setParent(tree->getNode(root)->getOrigin(), root);
345 tree->getNode(root)->setOrigin(root);
346 }
347 }
348 }
349
350 template <class dataType>
351 void keepMostImportantPairs(ftm::FTMTree_MT *tree, int n, bool useBD) {
352 std::vector<std::tuple<ftm::idNode, ftm::idNode, dataType>> pairs;
353 tree->getPersistencePairsFromTree(pairs, useBD);
354 n = std::max(n, 2); // keep at least 2 pairs
355 int index = std::max((int)(pairs.size() - n), 0);
356 dataType threshold = std::get<2>(pairs[index]) * (1.0 - 1e-6)
357 / tree->getMaximumPersistence<dataType>() * 100.0;
358 persistenceThresholding<dataType>(tree, threshold);
359 }
360
361 template <class dataType>
363 double persistenceThresholdT,
364 std::vector<ftm::idNode> &deletedNodes) {
365 ftm::idNode treeRoot = tree->getRoot();
366 dataType maxPers = tree->getMaximumPersistence<dataType>();
367 dataType threshold = persistenceThresholdT / 100 * maxPers;
368
369 dataType secondMax = tree->getSecondMaximumPersistence<dataType>();
370 bool keepOneZeroPersistencePair = (secondMax == 0 or maxPers == 0);
371 if(threshold >= secondMax)
372 threshold = (1.0 - 1e-6) * secondMax;
373
374 for(unsigned int i = 0; i < tree->getNumberOfNodes(); ++i) {
375 if(tree->isRoot(i))
376 continue;
377 dataType nodePers = tree->getNodePersistence<dataType>(i);
378 if(nodePers == 0 and keepOneZeroPersistencePair
379 and tree->getParentSafe(i) == treeRoot) {
380 keepOneZeroPersistencePair = false;
381 continue;
382 }
383 if((nodePers == 0 or nodePers <= threshold
384 or not tree->isNodeOriginDefined(i))) {
385 tree->deleteNode(i);
386 deletedNodes.push_back(i);
387 ftm::idNode nodeOrigin = tree->getNode(i)->getOrigin();
388 if(tree->isNodeOriginDefined(i)
389 and tree->getNode(nodeOrigin)->getOrigin() == (int)i) {
390 tree->deleteNode(nodeOrigin);
391 deletedNodes.push_back(nodeOrigin);
392 }
393 }
394 }
395 }
396
397 template <class dataType>
399 std::vector<ftm::idNode> &deletedNodes) {
400 persistenceThresholding<dataType>(
401 tree, persistenceThreshold_, deletedNodes);
402 }
403
404 template <class dataType>
406 double persistenceThresholdT) {
407 std::vector<ftm::idNode> deletedNodes;
408 persistenceThresholding<dataType>(
409 tree, persistenceThresholdT, deletedNodes);
410 }
411
412 template <class dataType>
414 std::vector<ftm::idNode> deletedNodes;
415 persistenceThresholding<dataType>(
416 tree, persistenceThreshold_, deletedNodes);
417 }
418
419 template <class dataType>
421 for(unsigned int i = 0; i < tree->getNumberOfNodes(); ++i)
422 if(not tree->isNodeAlone(i) and not tree->isNodeOriginDefined(i)) {
423 std::stringstream ss;
424 std::vector<ftm::idNode> children;
425 tree->getChildren(i, children);
426 ss << i << " has no origin (scalar=" << tree->getValue<dataType>(i)
427 << ", noChildren=" << children.size()
428 << ", parent=" << tree->getParentSafe(i) << ")";
429 printMsg(ss.str());
430 if(!tree->isRoot(i))
431 tree->deleteNode(i);
432 else {
433 std::stringstream ss2;
434 ss2 << "the root has no origin!";
435 printErr(ss2.str());
436 }
437 }
438 }
439
440 template <class dataType>
442 bool deleteInconsistentNodes = true) {
443 if(deleteInconsistentNodes) {
444 // Manage inconsistent critical points
445 // Critical points with same scalar value than parent
446 for(unsigned int i = 0; i < tree->getNumberOfNodes(); ++i)
447 if(!tree->isNodeAlone(i) and !tree->isRoot(i)
448 and tree->getValue<dataType>(tree->getParentSafe(i))
449 == tree->getValue<dataType>(i)) {
450 /*printMsg("[preprocessTree] " + std::to_string(i)
451 + " has same scalar value than parent (will be
452 deleted).");*/
453 tree->deleteNode(i);
454 }
455 // Valence 2 nodes
456 for(unsigned int i = 0; i < tree->getNumberOfNodes(); ++i)
457 if(tree->getNode(i)->getNumberOfUpSuperArcs() == 1
458 and tree->getNode(i)->getNumberOfDownSuperArcs() == 1) {
459 /*printMsg("[preprocessTree] " + std::to_string(i)
460 + " has 1 up arc and 1 down arc (will be deleted).");*/
461 tree->deleteNode(i);
462 }
463 }
464
465 // Compute persistence pairs
467 auto pairs = ftm::computePersistencePairs<dataType>(tree);
468 // Verify pairs
469 verifyOrigins<dataType>(tree);
470 }
471 }
472
473 template <class dataType>
475 ftm::FTMTree_MT *tree,
476 std::vector<std::vector<ftm::idNode>> &treeNodeMerged) {
477 ftm::FTMTree_MT *treeNew = tree;
478
479 ftm::idNode root = treeNew->getRoot();
480
481 // Manage when there is only one pair
483 ftm::idNode rootOrigin = treeNew->getNode(root)->getOrigin();
484 treeNew->getNode(rootOrigin)->setOrigin(rootOrigin);
485 return treeNew;
486 }
487
488 // Manage multi persistence pairing
489 std::vector<std::vector<ftm::idNode>> treeMultiPers;
490 tree->getMultiPersOriginsVectorFromTree(treeMultiPers);
491
492 // General case
493 std::vector<bool> nodeDone(tree->getNumberOfNodes(), false);
494 std::queue<ftm::idNode> queueNodes;
495 queueNodes.emplace(root);
496 while(!queueNodes.empty()) {
497 ftm::idNode node = queueNodes.front();
498 queueNodes.pop();
499 ftm::idNode nodeOrigin = treeNew->getNode(node)->getOrigin();
500 if(node == nodeOrigin
501 or treeNew->getNodeLevel(node) > treeNew->getNodeLevel(nodeOrigin))
502 continue;
503
504 // Init vector with all origins
505 std::vector<std::tuple<ftm::idNode, int>> vecOrigins;
506 for(auto nodeMergedOrigin : treeNodeMerged[node]) {
507 vecOrigins.emplace_back(nodeMergedOrigin, 0);
508 for(auto multiPersOrigin :
509 treeMultiPers[tree->getNode(nodeMergedOrigin)->getOrigin()])
510 vecOrigins.emplace_back(multiPersOrigin, 1);
511 }
512 if(not tree->isNodeMerged(node))
513 for(auto multiPersOrigin : treeMultiPers[node])
514 vecOrigins.emplace_back(multiPersOrigin, 1);
515 vecOrigins.emplace_back(nodeOrigin, 2);
516
517 bool splitRoot = (vecOrigins.size() != 1 and treeNew->isRoot(node));
518 splitRoot = false; // disabled
519
520 // Process each origin
521 for(auto stackTuple : vecOrigins) {
522 ftm::idNode nodeOriginT = std::get<0>(stackTuple);
523 int nodeOriginTID = std::get<1>(stackTuple);
524 if(nodeDone[nodeOriginT]
525 and nodeDone[tree->getNode(nodeOriginT)->getOrigin()])
526 continue;
527 nodeDone[nodeOriginT] = true;
528 nodeDone[tree->getNode(nodeOriginT)->getOrigin()] = true;
529
530 // Manage new parent
531 ftm::idNode newParent = node;
532 // - if merged node
533 if(nodeOriginTID == 0) {
534 newParent = treeNew->getNode(nodeOriginT)->getOrigin();
535 treeNew->setParent(newParent, treeNew->getParentSafe(node));
536 // - if multi pers node or nodeOrigin and splitRoot
537 } else if(nodeOriginTID == 1 or (nodeOriginTID == 2 and splitRoot)) {
538 newParent = nodeOriginT;
539 }
540
541 // Set nodes in the branch as childrens of the node
542 ftm::idNode parentNodeOrigin = treeNew->getParentSafe(nodeOriginT);
543 while(parentNodeOrigin != node) {
544 ftm::idNode oldParentNodeOrigin
545 = treeNew->getParentSafe(parentNodeOrigin);
546 treeNew->setParent(parentNodeOrigin, newParent);
547 parentNodeOrigin = oldParentNodeOrigin;
548 }
549
550 if(nodeOriginTID == 1 or (nodeOriginTID == 2 and splitRoot))
551 treeNew->setParent(newParent, treeNew->getParentSafe(node));
552 else // if(nodeOriginTID != 1) // if not a multi pers node
553 // Delete the other node of the pair
554 treeNew->deleteNode(nodeOriginT);
555 if(nodeOriginTID == 2 and splitRoot)
556 tree->getNode(node)->setOrigin(node);
557
558 // Push childrens of the node to the stack to process them
559 std::vector<ftm::idNode> childrenNode;
560 treeNew->getChildren(newParent, childrenNode);
561 for(ftm::idNode children : childrenNode)
562 if(!treeNew->isLeaf(children))
563 queueNodes.emplace(children);
564 }
565 }
566
567 // Verify inconsistency
568 // verifyBranchDecompositionInconsistency<dataType>(treeNew);
569
570 return treeNew;
571 }
572
573 template <class dataType>
575 ftm::idNode treeRoot = tree->getRoot();
576 // Full merge case, search for the origin
577 if(tree->getNode(treeRoot)->getOrigin() == (int)treeRoot) {
578 ftm::idNode nodeIdToDelete = tree->getMergedRootOrigin<dataType>();
579 if(nodeIdToDelete != treeRoot
580 and not tree->isNodeIdInconsistent(nodeIdToDelete)) {
582 tree->getNode(nodeIdToDelete)->setOrigin(nodeIdToDelete);
583 else
584 tree->deleteNode(nodeIdToDelete);
585 }
586 // Classic case
587 } else {
588 ftm::idNode rootOrigin = tree->getNode(treeRoot)->getOrigin();
590 tree->getNode(rootOrigin)->setOrigin(rootOrigin);
591 else
592 tree->deleteNode(rootOrigin);
593 }
594
595 tree->getNode(treeRoot)->setOrigin(treeRoot);
596 }
597
599 int cptBug = 0;
600 for(unsigned int i = 0; i < tree->getNumberOfNodes(); ++i) {
601 if(not tree->isNodeOriginDefined(i)) {
602 std::stringstream ss;
603 ss << i << " _ " << tree->getNode(i)->getOrigin() << " / "
604 << tree->getNumberOfNodes();
605 printMsg(ss.str());
606 if(tree->isNodeAlone(i))
607 printMsg("alone");
608 cptBug++;
609 }
610 }
611 std::stringstream ss;
612 ss << cptBug;
613 printMsg(ss.str());
614 }
615
616 template <class dataType>
617 void deleteMultiPersPairs(ftm::FTMTree_MT *tree, bool useBD) {
618 auto multiPersOrigins = tree->getMultiPersOrigins<dataType>(useBD);
619 for(auto origin : multiPersOrigins)
620 tree->deleteNode(origin);
621 }
622
623 template <class dataType>
625 double epsilonTree,
626 double epsilon2Tree,
627 double epsilon3Tree,
628 bool branchDecompositionT,
629 bool useMinMaxPairT,
630 bool cleanTreeT,
631 double persistenceThreshold,
632 std::vector<int> &nodeCorr,
633 bool deleteInconsistentNodes = true) {
634 Timer t_proc;
635
636 ftm::FTMTree_MT *tree = &(mTree.tree);
637
638 preprocessTree<dataType>(tree, deleteInconsistentNodes);
639
640 // - Delete null persistence pairs and persistence thresholding
641 persistenceThresholding<dataType>(tree, persistenceThreshold);
642
643 // - Merge saddle points according epsilon
644 std::vector<std::vector<ftm::idNode>> treeNodeMerged(
645 tree->getNumberOfNodes());
647 if(epsilonTree != 0)
648 mergeSaddle<dataType>(tree, epsilonTree, treeNodeMerged);
649 }
650
651 // - Compute branch decomposition
652 // verifyPairsTree(tree);
653 if(branchDecompositionT
655 tree = computeBranchDecomposition<dataType>(tree, treeNodeMerged);
656
657 // - Delete multi pers pairs
659 deleteMultiPersPairs<dataType>(tree, branchDecompositionT);
660
661 // - Remove min max pair
662 // verifyPairsTree(tree);
663 if(not useMinMaxPairT)
664 dontUseMinMaxPair<dataType>(tree);
665
666 // - Epsilon 2 and 3 processing
667 if(branchDecompositionT and not isPersistenceDiagram_)
668 persistenceMerging<dataType>(tree, epsilon2Tree, epsilon3Tree);
669
670 // - Tree cleaning (remove unused nodes)
671 if(cleanTreeT) {
672 ftm::cleanMergeTree<dataType>(mTree, nodeCorr, branchDecompositionT);
673 tree = &(mTree.tree);
674 reverseNodeCorr(tree, nodeCorr);
675 }
676
677 // - Root number verification
678 if(tree->getNumberOfRoot() != 1)
679 printErr("preprocessingPipeline tree->getNumberOfRoot() != 1");
680
681 // - Time printing
682 // verifyPairsTree(tree);
683 auto t_preproc_time = t_proc.getElapsedTime();
684 std::stringstream ss;
685 ss << "TIME PREPROC. = " << t_preproc_time;
687 }
688
689 template <class dataType>
691 double epsilonTree,
692 double epsilon2Tree,
693 double epsilon3Tree,
694 bool branchDecompositionT,
695 bool useMinMaxPairT,
696 bool cleanTreeT,
697 std::vector<int> &nodeCorr,
698 bool deleteInconsistentNodes = true) {
699 preprocessingPipeline<dataType>(
700 mTree, epsilonTree, epsilon2Tree, epsilon3Tree, branchDecompositionT,
701 useMinMaxPairT, cleanTreeT, persistenceThreshold_, nodeCorr,
702 deleteInconsistentNodes);
703 }
704
705 void reverseNodeCorr(ftm::FTMTree_MT *tree, std::vector<int> &nodeCorr) {
706 std::vector<int> newNodeCorr(tree->getNumberOfNodes());
707 for(unsigned int i = 0; i < nodeCorr.size(); ++i)
708 if(nodeCorr[i] >= 0 && nodeCorr[i] < (int)newNodeCorr.size())
709 newNodeCorr[nodeCorr[i]] = i;
710 nodeCorr = newNodeCorr;
711 }
712
713 template <class dataType>
715 ftm::FTMTree_MT *tree = &(mt.tree);
716 ttk::ftm::computePersistencePairs<dataType>(tree);
717 persistenceThresholding<dataType>(tree);
718 std::vector<std::vector<ftm::idNode>> treeNodeMerged;
719 mergeSaddle<dataType>(tree, 100.0, treeNodeMerged);
720 computeBranchDecomposition<dataType>(tree, treeNodeMerged);
721 }
722
723 template <class dataType>
724 void mtsFlattening(std::vector<ftm::MergeTree<dataType>> &mts) {
725 for(auto &mt : mts)
726 mtFlattening(mt);
727 }
728
729 double getSizeLimitMetric(std::vector<ftm::FTMTree_MT *> &trees) {
730 std::array<double, 3> stats;
731 getTreesStats(trees, stats);
732 auto meanNodes = stats[0];
733 unsigned int n = trees.size();
734 return meanNodes * n;
735 }
736
737 // ------------------------------------------------------------------------
738 // Tree Postprocessing
739 // ------------------------------------------------------------------------
740 template <class dataType>
743 bool setOrigins = false) {
744 // Get min max pair
745 ftm::FTMTree_MT *tree1 = &(mTree1.tree);
746 ftm::idNode root = tree1->getRoot();
747 dataType newMax = tree1->getValue<dataType>(root);
748 ftm::idNode rootOrigin = tree1->getNode(root)->getOrigin();
749 dataType newMin = tree1->getValue<dataType>(rootOrigin);
750
751 // Update tree
752 ftm::idNode root2 = mTree2.tree.getRoot();
753 std::vector<dataType> newScalarsVector;
754 ftm::getTreeScalars<dataType>(mTree2, newScalarsVector);
755 newScalarsVector[root2] = newMax;
756
757 auto root2Origin = mTree2.tree.getNode(root2)->getOrigin();
758 if(root2Origin == (int)root2)
759 root2Origin = mTree2.tree.template getMergedRootOrigin<dataType>();
760 if(mTree2.tree.isNodeIdInconsistent(root2Origin))
761 newScalarsVector.push_back(newMin);
762 else
763 newScalarsVector[root2Origin] = newMin;
764
765 // Set new scalars
766 ftm::setTreeScalars<dataType>(mTree2, newScalarsVector);
767
768 // Create root origin if not already there
769 ftm::FTMTree_MT *treeNew = &(mTree2.tree);
770 if(mTree2.tree.isNodeIdInconsistent(root2Origin)) {
771 root2Origin = treeNew->getNumberOfNodes();
772 treeNew->makeNode(root2Origin);
773 }
774
775 // Manage new origins
776 if(setOrigins) {
777 treeNew->getNode(root2Origin)->setOrigin(root2);
778 treeNew->getNode(root2)->setOrigin(root2Origin);
779 }
780 }
781
782 template <class dataType>
783 std::tuple<int, dataType> fixMergedRootOrigin(ftm::FTMTree_MT *tree) {
784 if(not tree->isFullMerge())
785 return std::make_tuple(-1, -1);
786
787 // Get node of the min max pair
788 int maxIndex = tree->getMergedRootOrigin<dataType>();
789
790 // Link node of the min max pair with the root
791 ftm::idNode treeRoot = tree->getRoot();
792 dataType oldOriginValue
793 = tree->getValue<dataType>(tree->getNode(maxIndex)->getOrigin());
794 tree->getNode(maxIndex)->setOrigin(treeRoot);
795
796 return std::make_tuple(maxIndex, oldOriginValue);
797 }
798
799 // TODO fix bug when one multi pers. pairs is moved up with epsilon 2 and 3
800 // but not its brothers
801 template <class dataType>
803 ftm::idNode treeRoot = tree->getRoot();
804
805 // Get original tree message
806 std::stringstream oriPrintTree = tree->printTree();
807 std::stringstream oriPrintPairs
808 = tree->printPairsFromTree<dataType>(true);
809 std::stringstream oriPrintMultiPers
810 = tree->printMultiPersPairsFromTree<dataType>(true);
811
812 // One pair case
814 ftm::idNode treeRootOrigin = tree->getNode(treeRoot)->getOrigin();
815 tree->getNode(treeRootOrigin)->setOrigin(treeRoot);
816 return;
817 }
818
819 // Manage full merge and dontuseMinMaxPair_
820 bool isFM = tree->isFullMerge();
821 if(isFM) {
822 ftm::idNode mergedRootOrigin = tree->getMergedRootOrigin<dataType>();
823 if(not tree->isNodeIdInconsistent(mergedRootOrigin)
824 and mergedRootOrigin != treeRoot)
825 tree->getNode(treeRoot)->setOrigin(mergedRootOrigin);
826 else {
827 printErr("branchDecompositionToTree mergedRootOrigin inconsistent");
828 }
829 }
830
831 // Some functions
832 bool isJT = tree->isJoinTree<dataType>();
833 auto comp = [&](const std::tuple<ftm::idNode, dataType> &a,
834 const std::tuple<ftm::idNode, dataType> &b) {
835 return isJT ? std::get<1>(a) > std::get<1>(b)
836 : std::get<1>(a) < std::get<1>(b);
837 };
838 auto getIndexNotMultiPers = [&](int index, ftm::FTMTree_MT *treeT,
839 std::vector<ftm::idNode> &children) {
840 while(index >= 0 and treeT->isMultiPersPair(children[index]))
841 --index;
842 return index;
843 };
844
845 // Branch Decomposition To Tree
846 std::vector<std::tuple<ftm::idNode, ftm::idNode>> nodeParent;
847 std::queue<ftm::idNode> queue;
848 queue.emplace(treeRoot);
849 while(!queue.empty()) {
850 ftm::idNode node = queue.front();
851 queue.pop();
852 auto nodeOrigin = tree->getNode(node)->getOrigin();
853 if(tree->isLeaf(node)) {
854 if(tree->isNodeAlone(nodeOrigin)) {
855 if(not isFM)
856 nodeParent.emplace_back(nodeOrigin, node);
857 else
858 nodeParent.emplace_back(node, nodeOrigin);
859 } else if(tree->isMultiPersPair(node)) {
860 nodeParent.emplace_back(node, nodeOrigin);
861 }
862 continue;
863 }
864
865 // Get children and sort them by scalar values
866 std::vector<ftm::idNode> childrenOri;
867 tree->getChildren(node, childrenOri);
868 std::vector<ftm::idNode> children = childrenOri;
869 std::vector<std::tuple<ftm::idNode, dataType>> childrenScalars;
870 for(unsigned int i = 0; i < children.size(); ++i) {
871 if(isFM and (int) children[i] != nodeOrigin)
872 children[i] = tree->getNode(children[i])->getOrigin();
873 childrenScalars.push_back(std::make_tuple(
874 children[i], tree->getValue<dataType>(children[i])));
875 }
876 std::sort(std::begin(childrenScalars), std::end(childrenScalars), comp);
877 children.clear();
878 for(unsigned int i = 0; i < childrenScalars.size(); ++i)
879 children.push_back(std::get<0>(childrenScalars[i]));
880
881 // Get new parent of children
882 for(unsigned int i = 1; i < children.size(); ++i) {
883 if(tree->isMultiPersPair(children[i]))
884 continue;
885 int index = getIndexNotMultiPers(i - 1, tree, children);
886 if(index >= 0)
887 nodeParent.emplace_back(children[i], children[index]);
888 }
889
890 bool multiPersPair
891 = tree->getNode(nodeOrigin)->getOrigin() != (int)node;
892 if(not multiPersPair) {
893 if(not isFM) {
894 int index
895 = getIndexNotMultiPers(children.size() - 1, tree, children);
896 nodeParent.emplace_back(nodeOrigin, children[index]);
897 } else
898 nodeParent.emplace_back(children[0], node);
899 } else {
900 // std::cout << "branchDecompositionToTree multiPersPair" <<
901 // std::endl;
902 nodeParent.emplace_back(children[0], nodeOrigin);
903 int index = getIndexNotMultiPers(children.size() - 1, tree, children);
904 if(index < 0) { // should not be possible
905 printErr("[branchDecompositionToTree] index < 0");
906 index = 0;
907 }
908 nodeParent.emplace_back(node, children[index]);
909 }
910
911 // Push children to the queue
912 for(auto child : childrenOri)
913 queue.emplace(child);
914 }
915
916 // Set new parents for each node
917 for(auto nodeParentT : nodeParent)
918 tree->setParent(std::get<0>(nodeParentT), std::get<1>(nodeParentT));
919
920 // Verify that the tree is correct
921 for(unsigned int i = 0; i < tree->getNumberOfNodes(); ++i)
922 if(tree->getNode(i)->getNumberOfDownSuperArcs() == 1
923 and tree->getNode(i)->getNumberOfUpSuperArcs() == 1) {
924 printMsg(oriPrintPairs.str());
925 printMsg(oriPrintMultiPers.str());
926 printMsg(oriPrintTree.str());
927 printMsg(tree->printTree().str());
928 std::stringstream ss;
929 auto iOrigin = tree->getNode(i)->getOrigin();
930 ss << i << " _ " << iOrigin;
931 if(tree->getNode(iOrigin)->getOrigin() != int(i))
932 ss << " _ " << tree->getNode(iOrigin)->getOrigin() << " _ "
933 << tree->getNode(tree->getNode(iOrigin)->getOrigin())
934 ->getOrigin();
935 printMsg(ss.str());
936 printErr("[branchDecompositionToTree] 1 up arc and 1 down arc");
937 }
938 }
939
940 // For not branch decomposition tree
941 template <class dataType>
943 bool isJT = tree->isJoinTree<dataType>();
944 std::queue<ftm::idNode> queue;
945 queue.emplace(tree->getRoot());
946 while(!queue.empty()) {
947 ftm::idNode node = queue.front();
948 queue.pop();
949 ftm::idNode nodeOrigin = tree->getNode(node)->getOrigin();
950 if(!tree->isLeaf(node)) {
951 std::vector<ftm::idNode> children;
952 tree->getChildren(node, children);
953 std::vector<ftm::idNode> lowestNodes;
954 ftm::idNode branchOrigin = nodeOrigin;
955 for(auto child : children) {
956 ftm::idNode lowestNode = tree->getLowestNode<dataType>(child);
957 lowestNodes.push_back(lowestNode);
958 ftm::idNode lowestNodeOrigin
959 = tree->getNode(lowestNode)->getOrigin();
960 if(not tree->isNodeAlone(lowestNodeOrigin)
961 and lowestNodeOrigin != node)
962 branchOrigin = lowestNode;
963 }
964 for(size_t i = 0; i < children.size(); ++i) {
965 ftm::idNode lowestNodeOrigin
966 = tree->getNode(lowestNodes[i])->getOrigin();
967 if(branchOrigin == lowestNodes[i] or lowestNodeOrigin == node)
968 continue;
969 dataType lowestNodeOriginVal
970 = tree->getValue<dataType>(lowestNodeOrigin);
971 ftm::idNode branchOriginT = branchOrigin;
972 ftm::idNode branchRoot = tree->getNode(branchOrigin)->getOrigin();
973 while(branchRoot != branchOriginT) {
974 dataType val
975 = tree->getValue<dataType>(tree->getParentSafe(branchOriginT));
976 if((val > lowestNodeOriginVal and isJT)
977 or (val < lowestNodeOriginVal and not isJT))
978 break;
979 branchOriginT = tree->getParentSafe(branchOriginT);
980 }
981 tree->setParent(
982 lowestNodeOrigin, tree->getParentSafe(branchOriginT));
983 tree->setParent(branchOriginT, lowestNodeOrigin);
984 tree->setParent(children[i], lowestNodeOrigin);
985 }
986 }
987 std::vector<ftm::idNode> children;
988 tree->getChildren(node, children);
989 for(auto child : children)
990 queue.emplace(child);
991 }
992 }
993
994 template <class dataType>
996 // if(not branchDecomposition_ or not useMinMaxPair)
997 // fixMergedRootOrigin<dataType>(tree);
998 if(tree->isFullMerge()) {
999 auto mergedRootOrigin = tree->getMergedRootOrigin<dataType>();
1000 if(not tree->isNodeIdInconsistent(mergedRootOrigin))
1001 tree->getNode(tree->getRoot())->setOrigin(mergedRootOrigin);
1002 else
1003 printErr(
1004 "[postprocessingPipeline] mergedRootOrigin inconsistent id.");
1005 }
1007 if(not isPersistenceDiagram_ and tree->getRealNumberOfNodes() != 0)
1008 branchDecompositionToTree<dataType>(tree);
1009 } else
1010 putBackMergedNodes<dataType>(tree);
1011 }
1012
1013 // ------------------------------------------------------------------------
1014 // Output Matching
1015 // ------------------------------------------------------------------------
1016 template <class dataType>
1018 ftm::FTMTree_MT *tree1,
1019 ftm::FTMTree_MT *tree2,
1020 std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>
1021 &outputMatching) {
1022 std::vector<std::tuple<ftm::idNode, ftm::idNode, double>> toAdd;
1023 for(auto mTuple : outputMatching) {
1024 ftm::idNode node1 = std::get<0>(mTuple);
1025 ftm::idNode node2 = std::get<1>(mTuple);
1026 double cost = std::get<2>(mTuple);
1027 ftm::idNode node1Origin = tree1->getNode(node1)->getOrigin();
1028 ftm::idNode node2Origin = tree2->getNode(node2)->getOrigin();
1029
1030 int node1Level = tree1->getNodeLevel(node1);
1031 int node1OriginLevel = tree1->getNodeLevel(node1Origin);
1032 int node2Level = tree2->getNodeLevel(node2);
1033 int node2OriginLevel = tree2->getNodeLevel(node2Origin);
1034
1035 ftm::idNode node1Higher
1036 = (node1Level > node1OriginLevel) ? node1 : node1Origin;
1037 ftm::idNode node1Lower
1038 = (node1Level > node1OriginLevel) ? node1Origin : node1;
1039 ftm::idNode node2Higher
1040 = (node2Level > node2OriginLevel) ? node2 : node2Origin;
1041 ftm::idNode node2Lower
1042 = (node2Level > node2OriginLevel) ? node2Origin : node2;
1043
1044 if(((tree1->isRoot(node1Higher) and tree1->isFullMerge())
1045 or (tree2->isRoot(node2Higher) and tree2->isFullMerge())))
1046 continue;
1047
1048 if(!tree1->isNodeAlone(node1Higher)
1049 and !tree2->isNodeAlone(node2Higher))
1050 toAdd.emplace_back(node1Higher, node2Higher, cost);
1051 if(!tree1->isNodeAlone(node1Lower) and !tree2->isNodeAlone(node2Lower))
1052 toAdd.emplace_back(node1Lower, node2Lower, cost);
1053 }
1054 outputMatching.clear();
1055 outputMatching.insert(outputMatching.end(), toAdd.begin(), toAdd.end());
1056 }
1057
1058 template <class dataType>
1060 ftm::FTMTree_MT *tree1,
1061 ftm::FTMTree_MT *tree2,
1062 std::vector<std::tuple<ftm::idNode, ftm::idNode>> &outputMatching) {
1063 std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>
1064 realOutputMatching(outputMatching.size());
1065 for(size_t i = 0; i < outputMatching.size(); ++i) {
1066 const auto &tup{outputMatching[i]};
1067 realOutputMatching[i] = {std::get<0>(tup), std::get<1>(tup), 0.0};
1068 }
1069
1070 convertBranchDecompositionMatching<dataType>(
1071 tree1, tree2, realOutputMatching);
1072
1073 outputMatching.clear();
1074 for(auto tup : realOutputMatching)
1075 outputMatching.emplace_back(std::get<0>(tup), std::get<1>(tup));
1076 }
1077
1078 template <class dataType>
1080 ftm::FTMTree_MT *tree1,
1081 ftm::FTMTree_MT *tree2,
1082 std::vector<std::tuple<ftm::idNode, ftm::idNode>> &outputMatching,
1083 std::vector<std::tuple<ftm::idNode, ftm::idNode, bool>> &realMatching) {
1084 for(std::tuple<ftm::idNode, ftm::idNode> mTuple : outputMatching) {
1085 ftm::idNode tree1Node = std::get<0>(mTuple);
1086 ftm::idNode tree2Node = std::get<1>(mTuple);
1087 dataType relabelCostVal
1088 = relabelCostOnly<dataType>(tree1, tree1Node, tree2, tree2Node);
1089 dataType deleteInsertCostVal = deleteCost<dataType>(tree1, tree1Node)
1090 + insertCost<dataType>(tree2, tree2Node);
1091 bool isRealMatching = (relabelCostVal <= deleteInsertCostVal);
1092 realMatching.emplace_back(tree1Node, tree2Node, isRealMatching);
1093 }
1094 }
1095
1096 // ------------------------------------------------------------------------
1097 // Edit Costs
1098 // ------------------------------------------------------------------------
1099 template <class dataType>
1101 dataType x1, dataType x2, dataType y1, dataType y2, double power = 2) {
1102 if(power <= 0)
1103 return std::max(
1104 std::abs((double)(x1 - y1)), std::abs((double)(x2 - y2)));
1105 else
1106 return std::pow(std::abs((double)(x1 - y1)), power)
1107 + std::pow(std::abs((double)(x2 - y2)), power);
1108 }
1109
1110 template <class dataType>
1111 dataType deleteCost(ftm::FTMTree_MT *tree, ftm::idNode nodeId) {
1112 dataType cost = 0;
1113 dataType newMin = 0.0, newMax = 1.0;
1114 // Get birth/death
1115 auto birthDeath
1117 ? getNormalizedBirthDeath<dataType>(tree, nodeId, newMin, newMax)
1118 : tree->getBirthDeath<dataType>(nodeId);
1119 dataType birth = std::get<0>(birthDeath);
1120 dataType death = std::get<1>(birthDeath);
1121 dataType projec = (birth + death) / 2;
1122 // Compute delete cost
1123 cost = computeDistance<dataType>(
1124 birth, death, projec, projec, wassersteinPower_);
1125 // Divide cost by two if not branch decomposition and not merged
1126 /*if(! branchDecomposition_ and ! tree->isNodeMerged(nodeId))
1127 cost /= 2;*/
1128
1129 return cost;
1130 }
1131
1132 template <class dataType>
1133 dataType insertCost(ftm::FTMTree_MT *tree, ftm::idNode nodeId) {
1134 return deleteCost<dataType>(tree, nodeId);
1135 }
1136
1137 template <class dataType>
1139 ftm::idNode nodeId1,
1140 ftm::FTMTree_MT *tree2,
1141 ftm::idNode nodeId2) {
1142 dataType cost = 0;
1143 dataType newMin = 0.0, newMax = 1.0;
1144 // Get birth/death of the first tree
1145 auto birthDeath1
1147 ? getNormalizedBirthDeath<dataType>(tree1, nodeId1, newMin, newMax)
1148 : tree1->getBirthDeath<dataType>(nodeId1);
1149 dataType birth1 = std::get<0>(birthDeath1);
1150 dataType death1 = std::get<1>(birthDeath1);
1151 // Get birth/death of the second tree
1152 auto birthDeath2
1154 ? getNormalizedBirthDeath<dataType>(tree2, nodeId2, newMin, newMax)
1155 : tree2->getBirthDeath<dataType>(nodeId2);
1156 dataType birth2 = std::get<0>(birthDeath2);
1157 dataType death2 = std::get<1>(birthDeath2);
1158 // Compute relabel cost
1159 cost = computeDistance<dataType>(
1160 birth1, death1, birth2, death2, wassersteinPower_);
1161 // Divide cost by two if not branch decomposition and not merged
1162 /*bool merged = isNodeMerged(tree1, nodeId1) or isNodeMerged(tree2,
1163 nodeId2); if(! branchDecomposition_ and ! merged) cost /= 2;*/
1164
1165 return cost;
1166 }
1167
1168 template <class dataType>
1170 ftm::idNode nodeId1,
1171 ftm::FTMTree_MT *tree2,
1172 ftm::idNode nodeId2) {
1173 // Full merge case and only one persistence pair case
1174 if(tree1->getNode(nodeId1)->getOrigin() == (int)nodeId1
1175 or tree2->getNode(nodeId2)->getOrigin() == (int)nodeId2)
1176 return 0;
1177
1178 // Compute relabel cost
1179 dataType cost = relabelCostOnly<dataType>(tree1, nodeId1, tree2, nodeId2);
1180
1181 if(keepSubtree_) {
1182 // Compute deleteInsert cost
1183 dataType deleteInsertCost = deleteCost<dataType>(tree1, nodeId1)
1184 + insertCost<dataType>(tree2, nodeId2);
1185 if(deleteInsertCost < cost)
1186 cost = deleteInsertCost;
1187 }
1188
1189 return cost;
1190 }
1191
1192 // ------------------------------------------------------------------------
1193 // Utils
1194 // ------------------------------------------------------------------------
1195 void getParamNames(std::vector<std::string> &paramNames) {
1196 paramNames = std::vector<std::string>{"epsilon1",
1197 "epsilon2",
1198 "epsilon3",
1199 "persistenceThreshold",
1200 "branchDecomposition",
1201 "normalizedWasserstein",
1202 "keepSubtree",
1203 "isPersistenceDiagram",
1204 "deleteMultiPersPairs",
1205 "epsilon1UseFarthestSaddle",
1206 "mixtureCoefficient"};
1207 }
1208
1209 double getParamValueFromName(std::string &paramName) {
1210 double value = 0.0;
1211 if(paramName == "epsilon1")
1212 value = epsilonTree1_;
1213 else if(paramName == "epsilon2")
1214 value = epsilon2Tree1_;
1215 else if(paramName == "epsilon3")
1216 value = epsilon3Tree1_;
1217 else if(paramName == "persistenceThreshold")
1218 value = persistenceThreshold_;
1219 else if(paramName == "branchDecomposition")
1220 value = branchDecomposition_;
1221 else if(paramName == "normalizedWasserstein")
1222 value = normalizedWasserstein_;
1223 else if(paramName == "keepSubtree")
1224 value = keepSubtree_;
1225 else if(paramName == "isPersistenceDiagram")
1226 value = isPersistenceDiagram_;
1227 else if(paramName == "deleteMultiPersPairs")
1228 value = deleteMultiPersPairs_;
1229 else if(paramName == "epsilon1UseFarthestSaddle")
1231 else if(paramName == "mixtureCoefficient")
1232 value = mixtureCoefficient_;
1233 return value;
1234 }
1235
1236 void setParamValueFromName(std::string &paramName, double value) {
1237 if(paramName == "epsilon1")
1238 epsilonTree1_ = value;
1239 else if(paramName == "epsilon2")
1240 epsilon2Tree1_ = value;
1241 else if(paramName == "epsilon3")
1242 epsilon3Tree1_ = value;
1243 else if(paramName == "persistenceThreshold")
1244 persistenceThreshold_ = value;
1245 else if(paramName == "branchDecomposition")
1246 branchDecomposition_ = value;
1247 else if(paramName == "normalizedWasserstein")
1248 normalizedWasserstein_ = value;
1249 else if(paramName == "keepSubtree")
1250 keepSubtree_ = value;
1251 else if(paramName == "isPersistenceDiagram")
1252 isPersistenceDiagram_ = value;
1253 else if(paramName == "deleteMultiPersPairs")
1254 deleteMultiPersPairs_ = value;
1255 else if(paramName == "epsilon1UseFarthestSaddle")
1257 else if(paramName == "mixtureCoefficient")
1258 mixtureCoefficient_ = value;
1259 }
1260
1261 void getTreesStats(std::vector<ftm::FTMTree_MT *> &trees,
1262 std::array<double, 3> &stats) {
1263 double avgNodes = 0, avgNodesT = 0;
1264 double avgDepth = 0;
1265 for(unsigned int i = 0; i < trees.size(); ++i) {
1266 auto noNodesT = trees[i]->getNumberOfNodes();
1267 auto noNodes = trees[i]->getRealNumberOfNodes();
1268 avgNodes += noNodes;
1269 avgNodesT += noNodesT;
1270 avgDepth += trees[i]->getTreeDepth();
1271 }
1272 avgNodes /= trees.size();
1273 avgNodesT /= trees.size();
1274 avgDepth /= trees.size();
1275
1276 stats = {avgNodes, avgNodesT, avgDepth};
1277 }
1278
1279 void printTreesStats(std::vector<ftm::FTMTree_MT *> &trees) {
1280 std::array<double, 3> stats;
1281 getTreesStats(trees, stats);
1282 int avgNodes = stats[0], avgNodesT = stats[1];
1283 double avgDepth = stats[2];
1284 std::stringstream ss;
1285 ss << trees.size() << " trees average [node: " << avgNodes << " / "
1286 << avgNodesT << ", depth: " << avgDepth << "]";
1287 printMsg(ss.str());
1288 }
1289
1290 template <class dataType>
1291 void printTreesStats(std::vector<ftm::MergeTree<dataType>> &trees) {
1292 std::vector<ftm::FTMTree_MT *> treesT;
1293 ftm::mergeTreeToFTMTree<dataType>(trees, treesT);
1294 printTreesStats(treesT);
1295 }
1296
1297 template <class dataType>
1298 void printTableVector(std::vector<std::vector<dataType>> &table) {
1299 std::streamsize ssize = std::cout.precision();
1300 std::stringstream ss;
1301 ss << " ";
1302 for(unsigned int j = 0; j < table[0].size(); ++j)
1303 ss << j - 1 << " ";
1304 printMsg(ss.str());
1305 ss.str("");
1306 ss.clear();
1307 for(unsigned int i = 0; i < table.size(); ++i) {
1308 ss << std::setw(3) << std::setfill('0') << std::internal << i - 1
1309 << " | ";
1310 for(unsigned int j = 0; j < table[0].size(); ++j) {
1311 ss << std::fixed << std::setprecision(2) << table[i][j] << " ";
1312 }
1313 printMsg(ss.str());
1314 printMsg("");
1315 }
1316 std::cout.precision(ssize);
1318 }
1319
1320 template <class dataType>
1321 void printTable(dataType *table, int nRows, int nCols) {
1322 std::vector<std::vector<dataType>> vec(nRows, std::vector<dataType>());
1323 for(int i = 0; i < nRows; ++i)
1324 for(int j = 0; j < nCols; ++j)
1325 vec[i].push_back(table[i * nCols + j]);
1326 printTableVector<dataType>(vec);
1327 }
1328
1329 void printMatching(std::vector<MatchingType> &matchings) {
1331 for(const auto &mTuple : matchings) {
1332 std::stringstream ss;
1333 ss << std::get<0>(mTuple) << " - " << std::get<1>(mTuple) << " - "
1334 << std::get<2>(mTuple);
1335 printMsg(ss.str());
1336 }
1338 }
1339
1341 std::vector<std::tuple<ftm::idNode, ftm::idNode, double>> &matchings) {
1343 for(auto mTuple : matchings) {
1344 std::stringstream ss;
1345 ss << std::get<0>(mTuple) << " - " << std::get<1>(mTuple);
1346 printMsg(ss.str());
1347 }
1349 }
1350
1352 std::vector<std::tuple<ftm::idNode, ftm::idNode>> &matchings) {
1353 std::vector<std::tuple<ftm::idNode, ftm::idNode, double>> matchingsT(
1354 matchings.size());
1355 for(size_t i = 0; i < matchings.size(); ++i) {
1356 const auto &tup{matchings[i]};
1357 matchingsT[i] = {std::get<0>(tup), std::get<1>(tup), 0.0};
1358 }
1359 printMatching(matchingsT);
1360 }
1361
1362 template <class dataType>
1364 std::vector<std::tuple<SimplexId, SimplexId, dataType>> &treePairs) {
1365 for(auto pair : treePairs) {
1366 std::stringstream ss;
1367 ss << std::get<0>(pair) << " _ " << std::get<1>(pair) << " _ "
1368 << std::get<2>(pair);
1369 printMsg(ss.str());
1370 }
1372 }
1373
1374 template <class dataType>
1376 std::vector<std::tuple<ftm::idNode, ftm::idNode>> &outputMatching,
1377 ftm::FTMTree_MT *tree1,
1378 ftm::FTMTree_MT *tree2,
1379 bool computeCosts = true) {
1380 dataType cost = 0;
1381 std::vector<bool> tree1Done(tree1->getNumberOfNodes(), false);
1382 std::vector<bool> tree2Done(tree2->getNumberOfNodes(), false);
1383 std::stringstream ss;
1384 for(std::tuple<ftm::idNode, ftm::idNode> matching : outputMatching) {
1385 ftm::idNode node0 = std::get<0>(matching);
1386 ftm::idNode node1 = std::get<1>(matching);
1387 ftm::idNode node0Origin = tree1->getNode(node0)->getOrigin();
1388 ftm::idNode node1Origin = tree2->getNode(node1)->getOrigin();
1389 ss << node0 << " - " << node1 << " _ [ ";
1390 ss << "f(" << node0 << ")=" << tree1->getValue<dataType>(node0)
1391 << " _ ";
1392 ss << "g(" << node1 << ")=" << tree2->getValue<dataType>(node1) << " ]"
1393 << " _ [ ";
1394 ss << "f(" << node0Origin
1395 << ")=" << tree1->getValue<dataType>(node0Origin) << " _ ";
1396 ss << "g(" << node1Origin
1397 << ")=" << tree2->getValue<dataType>(node1Origin) << " ] ";
1398
1399 if(computeCosts) {
1400 dataType tempCost = relabelCost<dataType>(tree1, node0, tree2, node1);
1401 dataType tempCost2
1402 = relabelCostOnly<dataType>(tree1, node0, tree2, node1);
1403 ss << "cost = " << tempCost << " (" << tempCost2 << ")" << std::endl;
1404 cost += tempCost;
1405 } else
1406 ss << std::endl;
1407 tree1Done[node0] = true;
1408 tree2Done[node1] = true;
1409 }
1410
1411 for(unsigned int i = 0; i < tree1->getNumberOfNodes(); ++i)
1412 if(not tree1Done[i] and not tree1->isNodeAlone(i)) {
1413 ftm::idNode nodeOrigin = tree1->getNode(i)->getOrigin();
1414 ss << "T1 " << i << " _ [ f(" << i
1415 << ") = " << tree1->getValue<dataType>(i);
1416 ss << "_ f(" << nodeOrigin
1417 << ") = " << tree1->getValue<dataType>(nodeOrigin);
1418 ss << "]";
1419 if(computeCosts) {
1420 dataType tempCost = deleteCost<dataType>(tree1, i);
1421 ss << " _ cost = " << tempCost << std::endl;
1422 cost += tempCost;
1423 } else
1424 ss << std::endl;
1425 }
1426 for(unsigned int i = 0; i < tree2->getNumberOfNodes(); ++i)
1427 if(not tree2Done[i] and not tree2->isNodeAlone(i)) {
1428 ftm::idNode nodeOrigin = tree2->getNode(i)->getOrigin();
1429 ss << "T2 " << i << " _ [ g(" << i
1430 << ") = " << tree2->getValue<dataType>(i);
1431 ss << "_ g(" << nodeOrigin
1432 << ") = " << tree2->getValue<dataType>(nodeOrigin);
1433 ss << "]";
1434 if(computeCosts) {
1435 dataType tempCost = deleteCost<dataType>(tree2, i);
1436 ss << " _ cost = " << tempCost << std::endl;
1437 cost += tempCost;
1438 } else
1439 ss << std::endl;
1440 }
1441 if(computeCosts)
1442 ss << "total cost = " << cost << " (" << std::sqrt(cost) << ")"
1443 << std::endl;
1444
1445 printMsg(ss.str());
1447 }
1448 }; // MergeTreeBase class
1449
1450} // namespace ttk
Minimalist debugging class.
Definition: Debug.h:88
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
void printTable(dataType *table, int nRows, int nCols)
void setBranchDecomposition(bool useBD)
void setNormalizedWasserstein(bool normalizedWasserstein)
void setDistanceSquaredRoot(bool distanceSquaredRoot)
double mixtureCoefficient_
Definition: MergeTreeBase.h:51
void getTreesStats(std::vector< ftm::FTMTree_MT * > &trees, std::array< double, 3 > &stats)
void setParamValueFromName(std::string &paramName, double value)
bool epsilon1UseFarthestSaddle_
Definition: MergeTreeBase.h:27
void printTreesStats(std::vector< ftm::MergeTree< dataType > > &trees)
void setEpsilon3Tree1(double epsilon)
Definition: MergeTreeBase.h:93
void setEpsilonTree1(double epsilon)
Definition: MergeTreeBase.h:77
void setAssignmentSolver(int assignmentSolver)
Definition: MergeTreeBase.h:69
void persistenceThresholding(ftm::FTMTree_MT *tree)
dataType computeDistance(dataType x1, dataType x2, dataType y1, dataType y2, double power=2)
void deleteMultiPersPairs(ftm::FTMTree_MT *tree, bool useBD)
void printOutputMatching(std::vector< std::tuple< ftm::idNode, ftm::idNode > > &outputMatching, ftm::FTMTree_MT *tree1, ftm::FTMTree_MT *tree2, bool computeCosts=true)
void mtFlattening(ftm::MergeTree< dataType > &mt)
void mergeSaddle(ftm::FTMTree_MT *tree, double epsilon, std::vector< std::vector< ftm::idNode > > &treeNodeMerged, bool mergeByPersistence=false)
void preprocessingPipeline(ftm::MergeTree< dataType > &mTree, double epsilonTree, double epsilon2Tree, double epsilon3Tree, bool branchDecompositionT, bool useMinMaxPairT, bool cleanTreeT, double persistenceThreshold, std::vector< int > &nodeCorr, bool deleteInconsistentNodes=true)
void keepMostImportantPairs(ftm::FTMTree_MT *tree, int n, bool useBD)
double mixDistancesWeight(bool isFirstInput)
dataType relabelCostOnly(ftm::FTMTree_MT *tree1, ftm::idNode nodeId1, ftm::FTMTree_MT *tree2, ftm::idNode nodeId2)
void setNodePerTask(int npt)
void convertBranchDecompositionMatching(ftm::FTMTree_MT *tree1, ftm::FTMTree_MT *tree2, std::vector< std::tuple< ftm::idNode, ftm::idNode, double > > &outputMatching)
std::vector< std::vector< int > > getTreesNodeCorr()
void getParamNames(std::vector< std::string > &paramNames)
void putBackMergedNodes(ftm::FTMTree_MT *tree)
void dontUseMinMaxPair(ftm::FTMTree_MT *tree)
void setEpsilon2Tree1(double epsilon)
Definition: MergeTreeBase.h:85
void setEpsilonTree2(double epsilon)
Definition: MergeTreeBase.h:81
void setBarycenterMergeTree(bool imt)
ftm::FTMTree_MT * computeBranchDecomposition(ftm::FTMTree_MT *tree, std::vector< std::vector< ftm::idNode > > &treeNodeMerged)
void printMatching(std::vector< std::tuple< ftm::idNode, ftm::idNode, double > > &matchings)
void verifyOrigins(ftm::FTMTree_MT *tree)
double mixDistances(dataType distance1, dataType distance2)
void printMatching(std::vector< std::tuple< ftm::idNode, ftm::idNode > > &matchings)
void persistenceThresholding(ftm::FTMTree_MT *tree, std::vector< ftm::idNode > &deletedNodes)
void branchDecompositionToTree(ftm::FTMTree_MT *tree)
void persistenceThresholding(ftm::FTMTree_MT *tree, double persistenceThresholdT)
double getSizeLimitMetric(std::vector< ftm::FTMTree_MT * > &trees)
dataType insertCost(ftm::FTMTree_MT *tree, ftm::idNode nodeId)
void preprocessingPipeline(ftm::MergeTree< dataType > &mTree, double epsilonTree, double epsilon2Tree, double epsilon3Tree, bool branchDecompositionT, bool useMinMaxPairT, bool cleanTreeT, std::vector< int > &nodeCorr, bool deleteInconsistentNodes=true)
void setPersistenceThreshold(double pt)
void printTreesStats(std::vector< ftm::FTMTree_MT * > &trees)
void postprocessingPipeline(ftm::FTMTree_MT *tree)
void printTableVector(std::vector< std::vector< dataType > > &table)
void verifyPairsTree(ftm::FTMTree_MT *tree)
void printMatching(std::vector< MatchingType > &matchings)
void printPairs(std::vector< std::tuple< SimplexId, SimplexId, dataType > > &treePairs)
void copyMinMaxPair(ftm::MergeTree< dataType > &mTree1, ftm::MergeTree< dataType > &mTree2, bool setOrigins=false)
dataType deleteCost(ftm::FTMTree_MT *tree, ftm::idNode nodeId)
std::vector< std::vector< int > > treesNodeCorr_
Definition: MergeTreeBase.h:60
void preprocessTree(ftm::FTMTree_MT *tree, bool deleteInconsistentNodes=true)
void setCleanTree(bool clean)
void reverseNodeCorr(ftm::FTMTree_MT *tree, std::vector< int > &nodeCorr)
void identifyRealMatching(ftm::FTMTree_MT *tree1, ftm::FTMTree_MT *tree2, std::vector< std::tuple< ftm::idNode, ftm::idNode > > &outputMatching, std::vector< std::tuple< ftm::idNode, ftm::idNode, bool > > &realMatching)
void setEpsilon2Tree2(double epsilon)
Definition: MergeTreeBase.h:89
void setKeepSubtree(bool keepSubtree)
double persistenceThreshold_
Definition: MergeTreeBase.h:34
void persistenceThresholding(ftm::FTMTree_MT *tree, double persistenceThresholdT, std::vector< ftm::idNode > &deletedNodes)
dataType relabelCost(ftm::FTMTree_MT *tree1, ftm::idNode nodeId1, ftm::FTMTree_MT *tree2, ftm::idNode nodeId2)
void persistenceMerging(ftm::FTMTree_MT *tree, double epsilon2, double epsilon3=100)
void mtsFlattening(std::vector< ftm::MergeTree< dataType > > &mts)
void setEpsilon1UseFarthestSaddle(bool b)
Definition: MergeTreeBase.h:73
void setDeleteMultiPersPairs(bool deleteMultiPersPairsT)
void setUseMinMaxPair(bool useMinMaxPair)
void setEpsilon3Tree2(double epsilon)
Definition: MergeTreeBase.h:97
double mixDistancesMinMaxPairWeight(bool isFirstInput)
void setParallelize(bool para)
double getParamValueFromName(std::string &paramName)
void setIsPersistenceDiagram(bool isPD)
void convertBranchDecompositionMatching(ftm::FTMTree_MT *tree1, ftm::FTMTree_MT *tree2, std::vector< std::tuple< ftm::idNode, ftm::idNode > > &outputMatching)
std::tuple< int, dataType > fixMergedRootOrigin(ftm::FTMTree_MT *tree)
void mixDistancesMatrix(std::vector< std::vector< dataType > > &distanceMatrix, std::vector< std::vector< dataType > > &distanceMatrix2)
double getElapsedTime()
Definition: Timer.h:15
std::vector< ftm::idNode > getMultiPersOrigins(bool useBD)
std::stringstream printMultiPersPairsFromTree(bool useBD=false, bool printPairs=true, bool doPrint=true)
const scalarType & getValue(SimplexId nodeId) const
Definition: FTMTree_MT.h:339
bool isNodeIdInconsistent(idNode nodeId)
dataType getNodePersistence(idNode nodeId)
idNode getNumberOfNodes() const
Definition: FTMTree_MT.h:389
void setParent(idNode nodeId, idNode newParentNodeId)
bool isNodeMerged(idNode nodeId)
std::tuple< dataType, dataType > getBirthDeath(idNode nodeId)
bool isRoot(idNode nodeId)
void getMultiPersOriginsVectorFromTree(std::vector< std::vector< idNode > > &res)
idNode getParentSafe(idNode nodeId)
bool isNodeOriginDefined(idNode nodeId)
int getNodeLevel(idNode nodeId)
void getPersistencePairsFromTree(std::vector< std::tuple< ftm::idNode, ftm::idNode, dataType > > &pairs, bool useBD)
void getChildren(idNode nodeId, std::vector< idNode > &res)
void deleteNode(idNode nodeId)
bool isMultiPersPair(idNode nodeId)
std::stringstream printPairsFromTree(bool useBD=false, bool printPairs=true, bool doPrint=true)
idNode makeNode(SimplexId vertexId, SimplexId linked=nullVertex)
Definition: FTMTree_MT.cpp:473
bool isLeaf(idNode nodeId)
bool isNodeAlone(idNode nodeId)
idNode getLowestNode(idNode nodeStart)
Node * getNode(idNode nodeId)
Definition: FTMTree_MT.h:393
std::stringstream printTree(bool doPrint=true)
bool isThereOnlyOnePersistencePair()
idSuperArc getNumberOfDownSuperArcs() const
Definition: FTMNode.h:82
void setOrigin(SimplexId linked)
Definition: FTMNode.h:72
SimplexId getOrigin() const
Definition: FTMNode.h:64
idSuperArc getNumberOfUpSuperArcs() const
Definition: FTMNode.h:86
unsigned int idNode
Node index in vect_nodes_.
Definition: FTMDataTypes.h:39
The Topology ToolKit.
ftm::FTMTree_MT tree
Definition: FTMTree_MT.h:901