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