TTK
Loading...
Searching...
No Matches
MergeTreeBarycenter.h
Go to the documentation of this file.
1
14
15#pragma once
16
17#include <random>
18
19// ttk common includes
20#include <Debug.h>
21#include <Triangulation.h>
22
23#include "MergeTreeBase.h"
24#include "MergeTreeDistance.h"
25
26namespace ttk {
27
32 class MergeTreeBarycenter : virtual public Debug, public MergeTreeBase {
33
34 protected:
35 double tol_ = 0.0;
36 bool addNodes_ = true;
37 bool deterministic_ = true;
38 bool isCalled_ = false;
41 double alpha_ = 0.5;
44
45 double allDistanceTime_ = 0;
46
48
49 bool preprocess_ = true;
50 bool postprocess_ = true;
51
52 // Output
53 std::vector<double> finalDistances_;
54
55 public:
58 "MergeTreeBarycenter"); // inherited from Debug: prefix will be printed
59 // at the beginning of every msg
60#ifdef TTK_ENABLE_OPENMP
61 omp_set_nested(1);
62#endif
63 }
64 ~MergeTreeBarycenter() override = default;
65
66 void setTol(double tolT) {
67 tol_ = tolT;
68 }
69
70 void setAddNodes(bool addNodesT) {
71 addNodes_ = addNodesT;
72 }
73
74 void setDeterministic(bool deterministicT) {
75 deterministic_ = deterministicT;
76 }
77
78 void setProgressiveBarycenter(bool progressive) {
79 progressiveBarycenter_ = progressive;
80 }
81
82 void setProgressiveSpeedDivisor(double progSpeed) {
83 progressiveSpeedDivisor_ = progSpeed;
84 }
85
86 void setIsCalled(bool ic) {
87 isCalled_ = ic;
88 }
89
91 return allDistanceTime_;
92 }
93
96 }
97
98 void setAlpha(double alpha) {
99 alpha_ = alpha;
100 }
101
102 void setBarycenterMaximumNumberOfPairs(unsigned int maxi) {
104 }
105
106 void setBarycenterSizeLimitPercent(double percent) {
108 }
109
110 void setPreprocess(bool preproc) {
111 preprocess_ = preproc;
112 }
113
114 void setPostprocess(bool postproc) {
115 postprocess_ = postproc;
116 }
117
118 std::vector<double> getFinalDistances() {
119 return finalDistances_;
120 }
121
125 // ------------------------------------------------------------------------
126 // Initialization
127 // ------------------------------------------------------------------------
128 template <class dataType>
129 void getDistanceMatrix(std::vector<ftm::FTMTree_MT *> &trees,
130 std::vector<ftm::FTMTree_MT *> &trees2,
131 std::vector<std::vector<double>> &distanceMatrix,
132 bool useDoubleInput = false,
133 bool isFirstInput = true) {
134 distanceMatrix.clear();
135 distanceMatrix.resize(trees.size(), std::vector<double>(trees.size(), 0));
136#ifdef TTK_ENABLE_OPENMP
137#pragma omp parallel for schedule(dynamic) \
138 num_threads(this->threadNumber_) if(parallelize_)
139#endif
140 for(unsigned int i = 0; i < trees.size(); ++i)
141 for(unsigned int j = i + 1; j < trees.size(); ++j) {
142 std::vector<std::tuple<ftm::idNode, ftm::idNode, double>> matching;
143 dataType distance;
144 computeOneDistance<dataType>(trees[i], trees2[j], matching, distance,
145 useDoubleInput, isFirstInput);
146 distanceMatrix[i][j] = distance;
147 distanceMatrix[j][i] = distance;
148 }
149 }
150
151 template <class dataType>
152 void getDistanceMatrix(std::vector<ftm::FTMTree_MT *> &trees,
153 std::vector<std::vector<double>> &distanceMatrix,
154 bool useDoubleInput = false,
155 bool isFirstInput = true) {
156 getDistanceMatrix<dataType>(
157 trees, trees, distanceMatrix, useDoubleInput, isFirstInput);
158 }
159
160 template <class dataType>
162 std::vector<ftm::FTMTree_MT *> &trees,
163 unsigned int barycenterMaximumNumberOfPairs,
164 double sizeLimitPercent,
165 std::vector<ftm::MergeTree<dataType>> &mTreesLimited) {
166 mTreesLimited.resize(trees.size());
167 for(unsigned int i = 0; i < trees.size(); ++i) {
168 mTreesLimited[i] = ftm::copyMergeTree<dataType>(trees[i]);
169 limitSizeBarycenter(mTreesLimited[i], trees,
170 barycenterMaximumNumberOfPairs, sizeLimitPercent);
171 ftm::cleanMergeTree<dataType>(mTreesLimited[i]);
172 }
173 }
174
175 template <class dataType>
177 std::vector<ftm::FTMTree_MT *> &trees,
178 std::vector<std::vector<double>> &distanceMatrix,
179 unsigned int barycenterMaximumNumberOfPairs,
180 double sizeLimitPercent,
181 bool useDoubleInput = false,
182 bool isFirstInput = true) {
183 std::vector<ftm::MergeTree<dataType>> mTreesLimited;
184 getSizeLimitedTrees<dataType>(
185 trees, barycenterMaximumNumberOfPairs, sizeLimitPercent, mTreesLimited);
186 std::vector<ftm::FTMTree_MT *> treesLimited;
187 ftm::mergeTreeToFTMTree<dataType>(mTreesLimited, treesLimited);
188 getDistanceMatrix<dataType>(
189 trees, treesLimited, distanceMatrix, useDoubleInput, isFirstInput);
190 }
191
192 template <class dataType>
194 std::vector<ftm::FTMTree_MT *> &trees,
195 std::vector<std::vector<double>> &distanceMatrix,
196 unsigned int barycenterMaximumNumberOfPairs,
197 double sizeLimitPercent,
198 bool useDoubleInput = false,
199 bool isFirstInput = true) {
200 if(barycenterMaximumNumberOfPairs <= 0 and sizeLimitPercent <= 0.0)
201 getDistanceMatrix<dataType>(
202 trees, distanceMatrix, useDoubleInput, isFirstInput);
203 else
204 getSizeLimitedDistanceMatrix<dataType>(
205 trees, distanceMatrix, barycenterMaximumNumberOfPairs,
206 sizeLimitPercent, useDoubleInput, isFirstInput);
207 }
208
209 template <class dataType>
210 int getBestInitTreeIndex(std::vector<ftm::FTMTree_MT *> &trees,
211 std::vector<ftm::FTMTree_MT *> &trees2,
212 unsigned int barycenterMaximumNumberOfPairs,
213 double sizeLimitPercent,
214 bool distMinimizer = true) {
215 std::vector<std::vector<double>> distanceMatrix, distanceMatrix2;
216 bool useDoubleInput = (trees2.size() != 0);
217 getParametrizedDistanceMatrix<dataType>(trees, distanceMatrix,
218 barycenterMaximumNumberOfPairs,
219 sizeLimitPercent, useDoubleInput);
220 if(trees2.size() != 0)
221 getParametrizedDistanceMatrix<dataType>(
222 trees2, distanceMatrix2, barycenterMaximumNumberOfPairs,
223 sizeLimitPercent, useDoubleInput, false);
224
225 int bestIndex = -1;
226 dataType bestValue
227 = distMinimizer ? std::numeric_limits<dataType>::max() : 0;
228 std::vector<int> sizes(trees.size());
229 for(unsigned int i = 0; i < trees.size(); ++i) {
230 dataType value = 0;
231 for(unsigned int j = 0; j < distanceMatrix[i].size(); ++j)
232 value += (not useDoubleInput ? distanceMatrix[i][j]
233 : mixDistances(distanceMatrix[i][j],
234 distanceMatrix2[i][j]));
235 if((distMinimizer and value < bestValue)
236 or (not distMinimizer and value > bestValue)) {
237 bestIndex = i;
238 bestValue = value;
239 }
240 sizes[i] = -value;
241 sizes[i] *= (distMinimizer) ? 1 : -1;
242 }
243 if(not deterministic_) {
244 std::random_device rd;
245 std::default_random_engine generator(rd());
246 std::discrete_distribution<int> distribution(
247 sizes.begin(), sizes.end());
248 bestIndex = distribution(generator);
249 }
250 return bestIndex;
251 }
252
253 template <class dataType>
254 int getBestInitTreeIndex(std::vector<ftm::FTMTree_MT *> &trees,
255 std::vector<ftm::FTMTree_MT *> &trees2,
256 double sizeLimitPercent,
257 bool distMinimizer = true) {
258 return getBestInitTreeIndex<dataType>(trees, trees2,
260 sizeLimitPercent, distMinimizer);
261 }
262
263 template <class dataType>
264 int getBestInitTreeIndex(std::vector<ftm::FTMTree_MT *> &trees,
265 bool distMinimizer = true) {
266 std::vector<ftm::FTMTree_MT *> trees2;
267 return getBestInitTreeIndex<dataType>(
268 trees, trees2, barycenterMaximumNumberOfPairs_,
269 barycenterSizeLimitPercent_, distMinimizer);
270 }
271
272 template <class dataType>
273 void initBarycenterTree(std::vector<ftm::FTMTree_MT *> &trees,
274 ftm::MergeTree<dataType> &baryTree,
275 bool distMinimizer = true) {
276 int bestIndex = getBestInitTreeIndex<dataType>(trees, distMinimizer);
277 baryTree = ftm::copyMergeTree<dataType>(trees[bestIndex], true);
278 limitSizeBarycenter(baryTree, trees);
279 }
280
281 // ------------------------------------------------------------------------
282 // Update
283 // ------------------------------------------------------------------------
284 template <class dataType>
287 ftm::idNode nodeId1,
288 ftm::FTMTree_MT *tree2,
289 ftm::idNode nodeId2,
290 std::vector<dataType> &newScalarsVector,
291 std::vector<std::tuple<ftm::idNode, ftm::idNode, int>> &nodesToProcess,
292 ftm::idNode nodeCpt,
293 int i) {
294 // Get nodes and scalars to add
295 std::queue<std::tuple<ftm::idNode, ftm::idNode>> queue;
296 queue.emplace(std::make_tuple(nodeId2, nodeId1));
297 nodesToProcess.emplace_back(nodeId2, nodeId1, i);
298 while(!queue.empty()) {
299 auto queueTuple = queue.front();
300 queue.pop();
301 ftm::idNode node = std::get<0>(queueTuple);
302 // Get scalars
303 newScalarsVector.push_back(
304 tree2->getValue<dataType>(tree2->getNode(node)->getOrigin()));
305 newScalarsVector.push_back(tree2->getValue<dataType>(node));
306 // Process children
307 std::vector<ftm::idNode> children;
308 tree2->getChildren(node, children);
309 for(auto child : children) {
310 queue.emplace(std::make_tuple(child, nodeCpt + 1));
311 nodesToProcess.emplace_back(child, nodeCpt + 1, i);
312 }
313 nodeCpt += 2; // we will add two nodes (birth and death)
314 }
315
316 return nodeCpt;
317 }
318
319 template <class dataType>
322 int noTrees,
323 std::vector<std::tuple<ftm::idNode, ftm::idNode, int>> &nodesToProcess,
324 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode>>>
325 &nodesProcessed) {
326 ftm::FTMTree_MT *tree1 = &(mTree1.tree);
327
328 // Add nodes
329 nodesProcessed.clear();
330 nodesProcessed.resize(noTrees);
331 for(auto processTuple : nodesToProcess) {
332 ftm::idNode parent = std::get<1>(processTuple);
333 ftm::idNode nodeTree1 = tree1->getNumberOfNodes();
334 int index = std::get<2>(processTuple);
335 nodesProcessed[index].push_back(
336 std::make_tuple(nodeTree1 + 1, std::get<0>(processTuple)));
337 // Make node and its origin
338 tree1->makeNode(nodeTree1);
339 tree1->makeNode(nodeTree1 + 1);
340 tree1->setParent(nodeTree1 + 1, parent);
341 tree1->getNode(nodeTree1)->setOrigin(nodeTree1 + 1);
342 tree1->getNode(nodeTree1 + 1)->setOrigin(nodeTree1);
343 }
344 }
345
346 template <class dataType>
349 int noTrees,
350 std::vector<std::tuple<ftm::idNode, ftm::idNode, int>> &nodesToProcess,
351 std::vector<dataType> &newScalarsVector,
352 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode>>>
353 &nodesProcessed) {
354 ftm::FTMTree_MT *tree1 = &(mTree1.tree);
355
356 // Create new tree
358 = ftm::createEmptyMergeTree<dataType>(newScalarsVector.size());
359 ftm::setTreeScalars<dataType>(mTreeNew, newScalarsVector);
360 ftm::FTMTree_MT *treeNew = &(mTreeNew.tree);
361
362 // Copy the old tree structure
363 treeNew->copyMergeTreeStructure(tree1);
364
365 // Add nodes in the other trees
366 addNodes<dataType>(mTreeNew, noTrees, nodesToProcess, nodesProcessed);
367
368 // Copy new tree
369 mTree1 = mTreeNew;
370 }
371
372 template <class dataType>
374 std::vector<ftm::FTMTree_MT *> &trees,
375 ftm::MergeTree<dataType> &baryMergeTree,
376 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
377 &matchings) {
378 ftm::FTMTree_MT *baryTree = &(baryMergeTree.tree);
379 ftm::idNode baryTreeRoot = baryTree->getRoot();
380
381 // Init matching matrix
382 // m[i][j] contains the node in the barycenter matched to the jth node of
383 // the ith tree
384 std::vector<std::vector<ftm::idNode>> matrixMatchings(trees.size());
385 std::vector<bool> baryMatched(baryTree->getNumberOfNodes(), false);
386 for(unsigned int i = 0; i < matchings.size(); ++i) {
387 auto matching = matchings[i];
388 matrixMatchings[i].resize(trees[i]->getNumberOfNodes(),
389 std::numeric_limits<ftm::idNode>::max());
390 for(auto match : matching) {
391 matrixMatchings[i][std::get<1>(match)] = std::get<0>(match);
392 baryMatched[std::get<0>(match)] = true;
393 }
394 }
395
396 // Iterate through trees to get the nodes to add in the barycenter
397 std::vector<std::vector<ftm::idNode>> nodesToAdd(trees.size());
398 for(unsigned int i = 0; i < trees.size(); ++i) {
399 ftm::idNode root = trees[i]->getRoot();
400 std::queue<ftm::idNode> queue;
401 queue.emplace(root);
402 while(!queue.empty()) {
403 ftm::idNode node = queue.front();
404 queue.pop();
405 bool processChildren = true;
406 // if node in trees[i] is not matched
407 if(matrixMatchings[i][node]
408 == std::numeric_limits<ftm::idNode>::max()) {
409 if(not keepSubtree_) {
410 processChildren = false;
411 nodesToAdd[i].push_back(node);
412 } else {
413 // not todo manage if keepSubtree=true (not important since it is
414 // not a valid merge tree)
415 printErr(
416 "barycenter with keepSubtree_=true is not implemented yet");
417 }
418 }
419 if(processChildren) {
420 std::vector<ftm::idNode> children;
421 trees[i]->getChildren(node, children);
422 for(auto child : children)
423 if(not(trees[i]->isThereOnlyOnePersistencePair()
424 and trees[i]->isLeaf(child)))
425 queue.emplace(child);
426 }
427 }
428 }
429
430 bool foundRootNotMatched = false;
431 for(unsigned int i = 0; i < trees.size(); ++i)
432 foundRootNotMatched |= baryTree->isNodeIdInconsistent(
433 matrixMatchings[i][trees[i]->getRoot()]);
434 if(foundRootNotMatched)
435 printWrn("[updateBarycenterTreeStructure] an input tree has its root "
436 "not matched.");
437
438 // Delete nodes that are not matched in the barycenter
439 for(unsigned int i = 0; i < baryTree->getNumberOfNodes(); ++i)
440 if(not baryMatched[i])
441 baryTree->deleteNode(i);
442
443 if(not keepSubtree_) {
444 // Add scalars and nodes not present in the barycenter
445 ftm::idNode nodeCpt = baryTree->getNumberOfNodes();
446 std::vector<std::tuple<ftm::idNode, ftm::idNode, int>> nodesToProcess;
447 std::vector<dataType> newScalarsVector;
448 ftm::getTreeScalars<dataType>(baryMergeTree, newScalarsVector);
449 for(unsigned int i = 0; i < nodesToAdd.size(); ++i) {
450 for(auto node : nodesToAdd[i]) {
451 ftm::idNode parent
452 = matrixMatchings[i][trees[i]->getParentSafe(node)];
453 if(matchings[i].size() == 0)
454 parent = baryTreeRoot;
455
456 if((baryTree->isNodeIdInconsistent(parent)
457 or baryTree->isNodeAlone(parent))
458 and matchings[i].size() != 0) {
459 std::stringstream ss;
460 ss << trees[i]->getParentSafe(node) << " _ " << node;
461 printMsg(ss.str());
462 printMsg(trees[i]->printTree().str());
463 printMsg(trees[i]->printPairsFromTree<dataType>(true).str());
464 printMatching(matchings[i]);
465 std::stringstream ss2;
466 ss2 << "parent " << parent;
467 printMsg(ss2.str());
468 }
469 /*if(isRoot(trees[i], node))
470 parent = baryTree->getRoot();*/
471 std::vector<dataType> addedScalars;
472 nodeCpt = getNodesAndScalarsToAdd<dataType>(
473 baryMergeTree, parent, trees[i], node, addedScalars,
474 nodesToProcess, nodeCpt, i);
475 newScalarsVector.insert(
476 newScalarsVector.end(), addedScalars.begin(), addedScalars.end());
477 }
478 }
479 if(addNodes_) {
480 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode>>>
481 nodesProcessed;
482 updateNodesAndScalars<dataType>(baryMergeTree, trees.size(),
483 nodesToProcess, newScalarsVector,
484 nodesProcessed);
485 for(unsigned int i = 0; i < matchings.size(); ++i) {
486 std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>
487 nodesProcessedT;
488 for(auto tup : nodesProcessed[i])
489 nodesProcessedT.emplace_back(
490 std::get<0>(tup), std::get<1>(tup), -1);
491 matchings[i].insert(matchings[i].end(), nodesProcessedT.begin(),
492 nodesProcessedT.end());
493 }
494 }
495 } else {
496 // not todo manage if keepSubtree=true (not important since it is not a
497 // valid merge tree)
498 printErr("barycenter with keepSubtree_=true is not implemented yet");
499 }
500 }
501
502 template <class dataType>
503 std::tuple<dataType, dataType>
505 std::tuple<dataType, dataType> birthDeath;
506 // Normalized Wasserstein
508 birthDeath = getNormalizedBirthDeathDouble<dataType>(tree1, nodeId1);
509 // Classical Wasserstein
510 else
511 birthDeath = tree1->getBirthDeath<dataType>(nodeId1);
512 return birthDeath;
513 }
514
515 template <class dataType>
516 std::tuple<dataType, dataType>
518 ftm::idNode nodeId,
519 std::vector<dataType> &newScalarsVector,
520 std::vector<ftm::FTMTree_MT *> &trees,
521 std::vector<ftm::idNode> &nodes,
522 std::vector<double> &alphas) {
523 ftm::FTMTree_MT *baryTree = &(baryMergeTree.tree);
524 dataType mu_max = getMinMaxLocalFromVector<dataType>(
525 baryTree, nodeId, newScalarsVector, false);
526 dataType mu_min = getMinMaxLocalFromVector<dataType>(
527 baryTree, nodeId, newScalarsVector);
528 double newBirth = 0, newDeath = 0;
529
530 // Compute projection
531 double tempBirth = 0, tempDeath = 0;
532 double alphaSum = 0;
533 for(unsigned int i = 0; i < trees.size(); ++i)
534 if(nodes[i] != std::numeric_limits<ftm::idNode>::max())
535 alphaSum += alphas[i];
536 for(unsigned int i = 0; i < trees.size(); ++i) {
537 // if node is matched in trees[i]
538 if(nodes[i] != std::numeric_limits<ftm::idNode>::max()) {
539 auto iBirthDeath
540 = getParametrizedBirthDeath<dataType>(trees[i], nodes[i]);
541 double tTempBirth = 0, tTempDeath = 0;
542 tTempBirth += std::get<0>(iBirthDeath);
543 tTempDeath += std::get<1>(iBirthDeath);
544 tempBirth += tTempBirth * alphas[i] / alphaSum;
545 tempDeath += tTempDeath * alphas[i] / alphaSum;
546 }
547 }
548 double projec = (tempBirth + tempDeath) / 2;
549
550 // Compute newBirth and newDeath
551 for(unsigned int i = 0; i < trees.size(); ++i) {
552 double iBirth = projec, iDeath = projec;
553 // if node is matched in trees[i]
554 if(nodes[i] != std::numeric_limits<ftm::idNode>::max()) {
555 auto iBirthDeath
556 = getParametrizedBirthDeath<dataType>(trees[i], nodes[i]);
557 iBirth = std::get<0>(iBirthDeath);
558 iDeath = std::get<1>(iBirthDeath);
559 }
560 newBirth += alphas[i] * iBirth;
561 newDeath += alphas[i] * iDeath;
562 }
564 newBirth = newBirth * (mu_max - mu_min) + mu_min;
565 newDeath = newDeath * (mu_max - mu_min) + mu_min;
566 }
567
568 return std::make_tuple(newBirth, newDeath);
569 }
570
571 template <class dataType>
572 std::tuple<dataType, dataType>
574 ftm::idNode nodeId,
575 double alpha,
576 ftm::MergeTree<dataType> &baryMergeTree,
577 ftm::idNode nodeB,
578 std::vector<dataType> &newScalarsVector) {
579 ftm::FTMTree_MT *baryTree = &(baryMergeTree.tree);
580 dataType mu_max = getMinMaxLocalFromVector<dataType>(
581 baryTree, nodeB, newScalarsVector, false);
582 dataType mu_min
583 = getMinMaxLocalFromVector<dataType>(baryTree, nodeB, newScalarsVector);
584
585 auto birthDeath = getParametrizedBirthDeath<dataType>(tree, nodeId);
586 double newBirth = std::get<0>(birthDeath);
587 double newDeath = std::get<1>(birthDeath);
588 double projec = (newBirth + newDeath) / 2;
589
590 newBirth = alpha * newBirth + (1 - alpha) * projec;
591 newDeath = alpha * newDeath + (1 - alpha) * projec;
592
594 newBirth = newBirth * (mu_max - mu_min) + mu_min;
595 newDeath = newDeath * (mu_max - mu_min) + mu_min;
596 }
597
598 dataType newBirthT = newBirth;
599 dataType newDeathT = newDeath;
600 return std::make_tuple(newBirthT, newDeathT);
601 }
602
603 template <class dataType>
605 std::vector<ftm::FTMTree_MT *> &trees,
606 ftm::MergeTree<dataType> &baryMergeTree,
607 std::vector<double> &alphas,
608 unsigned int indexAddedNodes,
609 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
610 &matchings) {
611 ftm::FTMTree_MT *baryTree = &(baryMergeTree.tree);
612 bool isJT = baryTree->isJoinTree<dataType>();
613
614 // Init matching matrix
615 // m[i][j] contains the node in trees[j] matched to the node i in the
616 // barycenter
617 std::vector<std::vector<ftm::idNode>> baryMatching(
618 baryTree->getNumberOfNodes(),
619 std::vector<ftm::idNode>(
620 trees.size(), std::numeric_limits<ftm::idNode>::max()));
621 std::vector<int> nodesAddedTree(baryTree->getNumberOfNodes(), -1);
622 for(unsigned int i = 0; i < matchings.size(); ++i) {
623 auto matching = matchings[i];
624 for(auto match : matching) {
625 baryMatching[std::get<0>(match)][i] = std::get<1>(match);
626 if(std::get<0>(match)
627 >= indexAddedNodes) // get the tree of this added node
628 nodesAddedTree[std::get<0>(match)] = i;
629 }
630 }
631
632 // Interpolate scalars
633 std::vector<dataType> newScalarsVector(baryTree->getNumberOfNodes());
634 ftm::idNode root = baryTree->getRoot();
635 std::queue<ftm::idNode> queue;
636 queue.emplace(root);
637 while(!queue.empty()) {
638 ftm::idNode node = queue.front();
639 queue.pop();
640 std::tuple<dataType, dataType> newBirthDeath;
641 if(node < indexAddedNodes) {
642 newBirthDeath
643 = interpolation<dataType>(baryMergeTree, node, newScalarsVector,
644 trees, baryMatching[node], alphas);
645 } else {
646 int i = nodesAddedTree[node];
647 ftm::idNode nodeT = baryMatching[node][i];
648 newBirthDeath = interpolationAdded<dataType>(
649 trees[i], nodeT, alphas[i], baryMergeTree, node, newScalarsVector);
650 }
651 dataType nodeScalar
652 = (isJT ? std::get<1>(newBirthDeath) : std::get<0>(newBirthDeath));
653 dataType nodeOriginScalar
654 = (isJT ? std::get<0>(newBirthDeath) : std::get<1>(newBirthDeath));
655 newScalarsVector[node] = nodeScalar;
656 newScalarsVector[baryTree->getNode(node)->getOrigin()]
657 = nodeOriginScalar;
658 std::vector<ftm::idNode> children;
659 baryTree->getChildren(node, children);
660 for(auto child : children)
661 queue.emplace(child);
662 }
663
664 if(baryMergeTree.tree.isFullMerge()) {
665 auto mergedRootOrigin = baryTree->getMergedRootOrigin<dataType>();
666 dataType mergedRootOriginScalar = 0.0;
667 for(unsigned int i = 0; i < trees.size(); ++i)
668 mergedRootOriginScalar += trees[i]->getValue<dataType>(
669 trees[i]->getMergedRootOrigin<dataType>());
670 mergedRootOriginScalar /= trees.size();
671 newScalarsVector[mergedRootOrigin] = mergedRootOriginScalar;
672 }
673
674 setTreeScalars(baryMergeTree, newScalarsVector);
675
676 std::vector<ftm::idNode> deletedNodesT;
677 persistenceThresholding<dataType>(
678 &(baryMergeTree.tree), 0, deletedNodesT);
679 limitSizeBarycenter(baryMergeTree, trees);
680 ftm::cleanMergeTree<dataType>(baryMergeTree);
681 }
682
683 template <class dataType>
685 std::vector<ftm::FTMTree_MT *> &trees,
686 ftm::MergeTree<dataType> &baryMergeTree,
687 std::vector<double> &alphas,
688 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
689 &matchings) {
690 int indexAddedNodes = baryMergeTree.tree.getNumberOfNodes();
691 updateBarycenterTreeStructure<dataType>(trees, baryMergeTree, matchings);
692 updateBarycenterTreeScalars<dataType>(
693 trees, baryMergeTree, alphas, indexAddedNodes, matchings);
694 }
695
696 // ------------------------------------------------------------------------
697 // Assignment
698 // ------------------------------------------------------------------------
699 template <class dataType>
701 ftm::FTMTree_MT *tree,
702 ftm::FTMTree_MT *baryTree,
703 std::vector<std::tuple<ftm::idNode, ftm::idNode, double>> &matching,
704 dataType &distance,
705 bool useDoubleInput = false,
706 bool isFirstInput = true) {
707 // Timer t_distance;
708 MergeTreeDistance mergeTreeDistance;
709 mergeTreeDistance.setDebugLevel(std::min(debugLevel_, 2));
710 mergeTreeDistance.setPreprocess(false);
711 mergeTreeDistance.setPostprocess(false);
712 mergeTreeDistance.setBranchDecomposition(true);
714 mergeTreeDistance.setKeepSubtree(keepSubtree_);
715 mergeTreeDistance.setAssignmentSolver(assignmentSolverID_);
716 mergeTreeDistance.setIsCalled(true);
717 mergeTreeDistance.setThreadNumber(this->threadNumber_);
718 mergeTreeDistance.setDistanceSquaredRoot(true); // squared root
719 mergeTreeDistance.setNodePerTask(nodePerTask_);
720 if(useDoubleInput) {
721 double weight = mixDistancesMinMaxPairWeight(isFirstInput);
722 mergeTreeDistance.setMinMaxPairWeight(weight);
723 }
724 /*if(progressiveBarycenter_){
725 mergeTreeDistance.setAuctionNoRounds(1);
726 mergeTreeDistance.setAuctionEpsilonDiviser(NoIteration-1);
727 }*/
728 distance
729 = mergeTreeDistance.computeDistance<dataType>(baryTree, tree, matching);
730 std::stringstream ss, ss2;
731 ss << "distance tree : " << distance;
733 ss2 << "distanceĀ²tree : " << distance * distance;
735
736 // auto t_distance_time = t_distance.getElapsedTime();
737 // allDistanceTime_ += t_distance_time;
738 }
739
740 template <class dataType>
742 ftm::FTMTree_MT *tree,
743 ftm::MergeTree<dataType> &baryMergeTree,
744 std::vector<std::tuple<ftm::idNode, ftm::idNode, double>> &matching,
745 dataType &distance,
746 bool useDoubleInput = false,
747 bool isFirstInput = true) {
748 computeOneDistance<dataType>(tree, &(baryMergeTree.tree), matching,
749 distance, useDoubleInput, isFirstInput);
750 }
751
752 template <class dataType>
754 ftm::MergeTree<dataType> &baryMergeTree,
755 ftm::MergeTree<dataType> &baryMergeTree2,
756 std::vector<std::tuple<ftm::idNode, ftm::idNode, double>> &matching,
757 dataType &distance,
758 bool useDoubleInput = false,
759 bool isFirstInput = true) {
760 computeOneDistance<dataType>(&(baryMergeTree.tree), baryMergeTree2,
761 matching, distance, useDoubleInput,
762 isFirstInput);
763 }
764
765 template <class dataType>
767 std::vector<ftm::FTMTree_MT *> &trees,
768 ftm::MergeTree<dataType> &baryMergeTree,
769 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
770 &matchings,
771 std::vector<dataType> &distances,
772 bool useDoubleInput = false,
773 bool isFirstInput = true) {
774 if(not isCalled_)
775 assignmentPara(trees, baryMergeTree, matchings, distances,
776 useDoubleInput, isFirstInput);
777 else
778 assignmentTask(trees, baryMergeTree, matchings, distances,
779 useDoubleInput, isFirstInput);
780 }
781
782 template <class dataType>
784 std::vector<ftm::FTMTree_MT *> &trees,
785 ftm::MergeTree<dataType> &baryMergeTree,
786 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
787 &matchings,
788 std::vector<dataType> &distances,
789 bool useDoubleInput = false,
790 bool isFirstInput = true) {
791#ifdef TTK_ENABLE_OPENMP
792#pragma omp parallel num_threads(this->threadNumber_) \
793 shared(baryMergeTree) if(parallelize_)
794 {
795#pragma omp single nowait
796#endif
797 assignmentTask(trees, baryMergeTree, matchings, distances,
798 useDoubleInput, isFirstInput);
799#ifdef TTK_ENABLE_OPENMP
800 } // pragma omp parallel
801#endif
802 }
803
804 template <class dataType>
806 std::vector<ftm::FTMTree_MT *> &trees,
807 ftm::MergeTree<dataType> &baryMergeTree,
808 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
809 &matchings,
810 std::vector<dataType> &distances,
811 bool useDoubleInput = false,
812 bool isFirstInput = true) {
813 for(unsigned int i = 0; i < trees.size(); ++i)
814#ifdef TTK_ENABLE_OPENMP
815#pragma omp task firstprivate(i) UNTIED() \
816 shared(baryMergeTree, matchings, distances)
817#endif
818 computeOneDistance<dataType>(trees[i], baryMergeTree, matchings[i],
819 distances[i], useDoubleInput,
820 isFirstInput);
821#ifdef TTK_ENABLE_OPENMP
822#pragma omp taskwait
823#endif
824 }
825
826 // ------------------------------------------------------------------------
827 // Progressivity
828 // ------------------------------------------------------------------------
829 template <class dataType>
830 unsigned int
831 persistenceScaling(std::vector<ftm::FTMTree_MT *> &trees,
832 std::vector<ftm::MergeTree<dataType>> &mergeTrees,
833 std::vector<ftm::FTMTree_MT *> &oriTrees,
834 int iterationNumber,
835 std::vector<std::vector<ftm::idNode>> &deletedNodes) {
836 deletedNodes.clear();
837 deletedNodes.resize(oriTrees.size());
838 unsigned int noTreesUnscaled = 0;
839
840 // Scale trees
841 for(unsigned int i = 0; i < oriTrees.size(); ++i) {
842 double persistenceThreshold = 50.0;
843 if(iterationNumber != -1) {
844 // Get number of pairs in scaled merge tree
845 int noPairs = mergeTrees[i].tree.getRealNumberOfNodes();
846
847 // Get pairs in original merge tree
848 std::vector<std::tuple<ftm::idNode, ftm::idNode, dataType>> pairs;
849 oriTrees[i]->getPersistencePairsFromTree<dataType>(
850 pairs, branchDecomposition_);
851
852 // Compute new persistence threshold
853 double multiplier = (progressiveSpeedDivisor_ < 1e-6
854 ? 1.
855 : iterationNumber / progressiveSpeedDivisor_);
856 int decrement = multiplier * pairs.size() / 10;
857 int thresholdIndex = pairs.size() - noPairs - std::max(decrement, 2);
858 thresholdIndex = std::max(thresholdIndex, 0);
859 const double persistence = std::get<2>(pairs[thresholdIndex]);
860 persistenceThreshold
861 = persistence / std::get<2>(pairs.back()) * 100.0;
862 if(thresholdIndex == 0) {
863 persistenceThreshold = 0.;
864 ++noTreesUnscaled;
865 }
866 }
867 if(persistenceThreshold != 0.) {
869 = ftm::copyMergeTree<dataType>(oriTrees[i]);
870 persistenceThresholding<dataType>(
871 &(mt.tree), persistenceThreshold, deletedNodes[i]);
872 if(mergeTrees.size() == 0)
873 mergeTrees.resize(oriTrees.size());
874 mergeTrees[i] = mt;
875 trees[i] = &(mt.tree);
876 } else {
877 trees[i] = oriTrees[i];
878 }
879 }
880
881 printTreesStats(trees);
882
883 return noTreesUnscaled;
884 }
885
886 template <class dataType>
888 std::vector<ftm::FTMTree_MT *> &oriTrees,
889 std::vector<std::vector<ftm::idNode>> &deletedNodes,
890 std::vector<dataType> &distances) {
891 for(unsigned int i = 0; i < oriTrees.size(); ++i)
892 for(auto node : deletedNodes[i])
893 distances[i] += deleteCost<dataType>(oriTrees[i], node);
894 }
895
896 // ------------------------------------------------------------------------
897 // Main Functions
898 // ------------------------------------------------------------------------
899 template <class dataType>
901 std::vector<ftm::FTMTree_MT *> &trees,
902 ftm::MergeTree<dataType> &baryMergeTree,
903 std::vector<double> &alphas,
904 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
905 &finalMatchings,
906 bool finalAsgnDoubleInput = false,
907 bool finalAsgnFirstInput = true) {
908 Timer t_bary;
909
910 ftm::FTMTree_MT *baryTree = &(baryMergeTree.tree);
911
912 // Persistence scaling
913 std::vector<ftm::FTMTree_MT *> oriTrees;
914 std::vector<ftm::MergeTree<dataType>> scaledMergeTrees;
915 std::vector<std::vector<ftm::idNode>> deletedNodes;
917 oriTrees.insert(oriTrees.end(), trees.begin(), trees.end());
918 persistenceScaling<dataType>(
919 trees, scaledMergeTrees, oriTrees, -1, deletedNodes);
920 std::vector<ftm::idNode> deletedNodesT;
921 persistenceThresholding<dataType>(baryTree, 50, deletedNodesT);
922 }
923 bool treesUnscaled = false;
924
925 // Print bary stats
926 printBaryStats(baryTree);
927
928 // Run
929 bool converged = false;
930 dataType frechetEnergy = -1;
931 dataType minFrechet = std::numeric_limits<dataType>::max();
932 int cptBlocked = 0;
933 int NoIteration = 0;
934 while(not converged) {
935 ++NoIteration;
936
938 std::stringstream ss;
939 ss << "Iteration " << NoIteration;
940 printMsg(ss.str());
941
942 // --- Assignment
943 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
944 matchings(trees.size());
945 std::vector<dataType> distances(trees.size(), -1);
946 Timer t_assignment;
947 assignment<dataType>(trees, baryMergeTree, matchings, distances);
948 Timer t_addDeletedNodes;
950 addScaledDeletedNodesCost<dataType>(
951 oriTrees, deletedNodes, distances);
952 addDeletedNodesTime_ += t_addDeletedNodes.getElapsedTime();
953 auto t_assignment_time
954 = t_assignment.getElapsedTime() - t_addDeletedNodes.getElapsedTime();
955 printMsg("Assignment", 1, t_assignment_time, this->threadNumber_,
957
958 // --- Update
959 Timer t_update;
960 updateBarycenterTree<dataType>(trees, baryMergeTree, alphas, matchings);
961 auto t_update_time = t_update.getElapsedTime();
962 baryTree = &(baryMergeTree.tree);
963 printMsg("Update", 1, t_update_time, this->threadNumber_,
965
966 // --- Check convergence
967 dataType currentFrechetEnergy = 0;
968 for(unsigned int i = 0; i < trees.size(); ++i)
969 currentFrechetEnergy += alphas[i] * distances[i] * distances[i];
970 auto frechetDiff
971 = std::abs((double)(frechetEnergy - currentFrechetEnergy));
972 converged = (frechetDiff <= tol_);
973 converged = converged and (not progressiveBarycenter_ or treesUnscaled);
974 frechetEnergy = currentFrechetEnergy;
975 tol_ = frechetEnergy / 125.0;
976
977 std::stringstream ss4;
978 auto barycenterTime = t_bary.getElapsedTime() - addDeletedNodesTime_;
979 printMsg("Total", 1, barycenterTime, this->threadNumber_,
981 printBaryStats(baryTree);
982 ss4 << "Frechet energy : " << frechetEnergy;
983 printMsg(ss4.str());
984
985 minFrechet = std::min(minFrechet, frechetEnergy);
986 if(not converged and (not progressiveBarycenter_ or treesUnscaled)) {
987 cptBlocked = (minFrechet < frechetEnergy) ? cptBlocked + 1 : 0;
988 converged = (cptBlocked >= 10);
989 }
990
991 // --- Persistence scaling
993 unsigned int noTreesUnscaled = persistenceScaling<dataType>(
994 trees, scaledMergeTrees, oriTrees, NoIteration, deletedNodes);
995 treesUnscaled = (noTreesUnscaled == oriTrees.size());
996 }
997 }
998
999 // Final processing
1001 printMsg("Final assignment");
1002
1003 std::vector<dataType> distances(trees.size(), -1);
1004 assignment<dataType>(trees, baryMergeTree, finalMatchings, distances,
1005 finalAsgnDoubleInput, finalAsgnFirstInput);
1006 for(auto dist : distances)
1007 finalDistances_.push_back(dist);
1008 dataType currentFrechetEnergy = 0;
1009 for(unsigned int i = 0; i < trees.size(); ++i)
1010 currentFrechetEnergy += alphas[i] * distances[i] * distances[i];
1011
1012 std::stringstream ss, ss2;
1013 ss << "Frechet energy : " << currentFrechetEnergy;
1014 printMsg(ss.str());
1015 auto barycenterTime = t_bary.getElapsedTime() - addDeletedNodesTime_;
1016 printMsg("Total", 1, barycenterTime, this->threadNumber_,
1018 // std::cout << "Bary Distance Time = " << allDistanceTime_ << std::endl;
1019
1020 if(trees.size() == 2 and not isCalled_)
1021 verifyBarycenterTwoTrees<dataType>(
1022 trees, baryMergeTree, finalMatchings, distances);
1023
1024 // Persistence (un)scaling
1026 scaledMergeTrees.clear();
1027 trees.clear();
1028 trees.insert(trees.end(), oriTrees.begin(), oriTrees.end());
1029 }
1030 }
1031
1032 template <class dataType>
1034 std::vector<ftm::MergeTree<dataType>> &trees,
1035 std::vector<double> &alphas,
1036 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
1037 &finalMatchings,
1038 ftm::MergeTree<dataType> &baryMergeTree,
1039 bool finalAsgnDoubleInput = false,
1040 bool finalAsgnFirstInput = true) {
1041 // --- Preprocessing
1042 if(preprocess_) {
1043 treesNodeCorr_.resize(trees.size());
1044 for(unsigned int i = 0; i < trees.size(); ++i)
1045 preprocessingPipeline<dataType>(trees[i], epsilonTree2_,
1049 printTreesStats(trees);
1050 }
1051
1052 // --- Init barycenter
1053 std::vector<ftm::FTMTree_MT *> treesT;
1054 ftm::mergeTreeToFTMTree<dataType>(trees, treesT);
1055 initBarycenterTree<dataType>(treesT, baryMergeTree);
1056
1057 // --- Execute
1058 computeBarycenter<dataType>(treesT, baryMergeTree, alphas, finalMatchings,
1059 finalAsgnDoubleInput, finalAsgnFirstInput);
1060
1061 // --- Postprocessing
1062 if(postprocess_) {
1063 std::vector<int> allRealNodes(trees.size());
1064 for(unsigned int i = 0; i < trees.size(); ++i) {
1065 postprocessingPipeline<dataType>(treesT[i]);
1066 }
1067
1068 // fixMergedRootOriginBarycenter<dataType>(baryMergeTree);
1069 postprocessingPipeline<dataType>(&(baryMergeTree.tree));
1070 for(unsigned int i = 0; i < trees.size(); ++i) {
1071 convertBranchDecompositionMatching<dataType>(
1072 &(baryMergeTree.tree), treesT[i], finalMatchings[i]);
1073 }
1074 }
1075 }
1076
1077 template <class dataType>
1079 std::vector<ftm::MergeTree<dataType>> &trees,
1080 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
1081 &finalMatchings,
1082 ftm::MergeTree<dataType> &baryMergeTree,
1083 bool finalAsgnDoubleInput = false,
1084 bool finalAsgnFirstInput = true) {
1085 std::vector<double> alphas;
1086 if(trees.size() != 2) {
1087 for(unsigned int i = 0; i < trees.size(); ++i)
1088 alphas.push_back(1.0 / trees.size());
1089 } else {
1090 alphas.push_back(alpha_);
1091 alphas.push_back(1 - alpha_);
1092 }
1093
1094 execute<dataType>(trees, alphas, finalMatchings, baryMergeTree,
1095 finalAsgnDoubleInput, finalAsgnFirstInput);
1096 }
1097
1098 // ------------------------------------------------------------------------
1099 // Preprocessing
1100 // ------------------------------------------------------------------------
1101 template <class dataType>
1103 std::vector<ftm::FTMTree_MT *> &trees,
1104 double percent,
1105 bool useBD) {
1106 auto metric = getSizeLimitMetric(trees);
1107 unsigned int newNoNodes = metric * percent / 100.0;
1108 keepMostImportantPairs<dataType>(&(bary.tree), newNoNodes, useBD);
1109
1110 unsigned int noNodesAfter = bary.tree.getRealNumberOfNodes();
1111 if(bary.tree.isFullMerge() and noNodesAfter > newNoNodes * 1.1 + 1
1112 and noNodesAfter > 3) {
1113 std::cout << "metric = " << metric << std::endl;
1114 std::cout << "newNoNodes = " << newNoNodes << std::endl;
1115 std::cout << "noNodesAfter = " << noNodesAfter << std::endl;
1116 }
1117 }
1118
1119 template <class dataType>
1121 std::vector<ftm::FTMTree_MT *> &trees,
1122 unsigned int barycenterMaximumNumberOfPairs,
1123 double percent,
1124 bool useBD = true) {
1125 if(barycenterMaximumNumberOfPairs > 0)
1126 keepMostImportantPairs<dataType>(
1127 &(bary.tree), barycenterMaximumNumberOfPairs, useBD);
1128 if(percent > 0)
1129 limitSizePercent(bary, trees, percent, useBD);
1130 }
1131 template <class dataType>
1133 std::vector<ftm::FTMTree_MT *> &trees,
1134 double percent,
1135 bool useBD = true) {
1137 bary, trees, barycenterMaximumNumberOfPairs_, percent, useBD);
1138 }
1139 template <class dataType>
1141 std::vector<ftm::FTMTree_MT *> &trees,
1142 bool useBD = true) {
1145 }
1146
1147 // ------------------------------------------------------------------------
1148 // Postprocessing
1149 // ------------------------------------------------------------------------
1150 template <class dataType>
1152 if(not barycenter.tree.isFullMerge())
1153 return;
1154
1155 ftm::FTMTree_MT *tree = &(barycenter.tree);
1156 auto tup = fixMergedRootOrigin<dataType>(tree);
1157 int maxIndex = std::get<0>(tup);
1158 dataType oldOriginValue = std::get<1>(tup);
1159
1160 // Verify that scalars are consistent
1161 ftm::idNode treeRoot = tree->getRoot();
1162 std::vector<dataType> newScalarsVector;
1163 ftm::getTreeScalars<dataType>(tree, newScalarsVector);
1164 bool isJT = tree->isJoinTree<dataType>();
1165 if((isJT and tree->getValue<dataType>(maxIndex) > oldOriginValue)
1166 or (not isJT
1167 and tree->getValue<dataType>(maxIndex) < oldOriginValue)) {
1168 newScalarsVector[treeRoot] = newScalarsVector[maxIndex];
1169 newScalarsVector[maxIndex] = oldOriginValue;
1170 } else
1171 newScalarsVector[treeRoot] = oldOriginValue;
1172 setTreeScalars(barycenter, newScalarsVector);
1173 }
1174
1175 // ------------------------------------------------------------------------
1176 // Utils
1177 // ------------------------------------------------------------------------
1179 const debug::Priority &priority
1181 auto noNodesT = baryTree->getNumberOfNodes();
1182 auto noNodes = baryTree->getRealNumberOfNodes();
1183 std::stringstream ss;
1184 ss << "Barycenter number of nodes : " << noNodes << " / " << noNodesT;
1185 printMsg(ss.str(), priority);
1186 }
1187
1188 // ------------------------------------------------------------------------
1189 // Testing
1190 // ------------------------------------------------------------------------
1191 template <class dataType>
1193 std::vector<ftm::FTMTree_MT *> &trees,
1194 ftm::MergeTree<dataType> &baryMergeTree,
1195 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
1196 &finalMatchings,
1197 std::vector<dataType> distances) {
1198 std::vector<std::tuple<ftm::idNode, ftm::idNode, double>> matching;
1199 dataType distance;
1200 computeOneDistance(trees[0], trees[1], matching, distance);
1201 if(distance != (distances[0] + distances[1])) {
1202 std::stringstream ss, ss2, ss3, ss4;
1203 ss << "distance T1 T2 : " << distance;
1204 printMsg(ss.str());
1205 ss2 << "distance T1 T' T2 : " << distances[0] + distances[1];
1206 printMsg(ss2.str());
1207 ss3 << "distance T1 T' : " << distances[0];
1208 printMsg(ss3.str());
1209 ss4 << "distance T' T2 : " << distances[1];
1210 printMsg(ss4.str());
1211 }
1212 return;
1213
1214 auto baryTree = &(baryMergeTree.tree);
1215 std::vector<std::vector<ftm::idNode>> baryMatched(
1216 baryTree->getNumberOfNodes(),
1217 std::vector<ftm::idNode>(
1218 trees.size(), std::numeric_limits<ftm::idNode>::max()));
1219 for(unsigned int i = 0; i < finalMatchings.size(); ++i)
1220 for(auto match : finalMatchings[i])
1221 baryMatched[std::get<0>(match)][i] = std::get<1>(match);
1222
1223 std::queue<ftm::idNode> queue;
1224 queue.emplace(baryTree->getRoot());
1225 while(!queue.empty()) {
1226 auto node = queue.front();
1227 queue.pop();
1228 std::vector<dataType> costs(trees.size());
1229 for(unsigned int i = 0; i < trees.size(); ++i)
1230 if(baryMatched[node][i] != std::numeric_limits<ftm::idNode>::max())
1231 costs[i] = relabelCost<dataType>(
1232 baryTree, node, trees[i], baryMatched[node][i]);
1233 else
1234 costs[i] = deleteCost<dataType>(baryTree, node);
1235 dataType cost = 0;
1236 if(baryMatched[node][0] != std::numeric_limits<ftm::idNode>::max()
1237 and baryMatched[node][1] != std::numeric_limits<ftm::idNode>::max())
1238 cost = relabelCost<dataType>(
1239 trees[0], baryMatched[node][0], trees[1], baryMatched[node][1]);
1240 else if(baryMatched[node][0] == std::numeric_limits<ftm::idNode>::max())
1241 cost = deleteCost<dataType>(trees[1], baryMatched[node][1]);
1242 else if(baryMatched[node][1] == std::numeric_limits<ftm::idNode>::max())
1243 cost = deleteCost<dataType>(trees[0], baryMatched[node][0]);
1244 else
1245 printErr("problem");
1246 costs[0] = std::sqrt(costs[0]);
1247 costs[1] = std::sqrt(costs[1]);
1248 cost = std::sqrt(cost);
1249 if(std::abs((double)(costs[0] - costs[1])) > 1e-7) {
1251 std::stringstream ss, ss2, ss3, ss4;
1252 ss << "cost T' T0 : " << costs[0];
1253 printMsg(ss.str());
1254 ss2 << "cost T' T1 : " << costs[1];
1255 printMsg(ss2.str());
1256 ss3 << "cost T0 T1 : " << cost;
1257 printMsg(ss2.str());
1258 ss4 << "cost T0 T' T1 : " << costs[0] + costs[1];
1259 printMsg(ss4.str());
1260 if(std::abs((double)((costs[0] + costs[1]) - cost)) > 1e-7) {
1261 std::stringstream ss5;
1262 ss5 << "diff : "
1263 << std::abs((double)((costs[0] + costs[1]) - cost));
1264 printMsg(ss5.str());
1265 }
1266 std::stringstream ss6;
1267 ss6 << "diff2 : " << std::abs((double)(costs[0] - costs[1]));
1268 printMsg(ss.str());
1269 // baryTree->printNode2<dataType>(node);
1270 // baryTree->printNode2<dataType>(baryTree->getParentSafe(node));
1271 for(unsigned int i = 0; i < 2; ++i)
1272 if(baryMatched[node][i]
1273 != std::numeric_limits<ftm::idNode>::max()) {
1274 printMsg(
1275 trees[i]->printNode2<dataType>(baryMatched[node][i]).str());
1276 printMsg(trees[i]
1277 ->printNode2<dataType>(
1278 trees[i]->getParentSafe(baryMatched[node][i]))
1279 .str());
1280 }
1281 }
1282 std::vector<ftm::idNode> children;
1283 baryTree->getChildren(node, children);
1284 for(auto child : children)
1285 queue.emplace(child);
1286 }
1287 }
1288
1289 }; // MergeTreeBarycenter class
1290
1291} // namespace ttk
#define ttkNotUsed(x)
Mark function/method parameters that are not used in the function body at all.
Definition: BaseClass.h:47
#define UNTIED()
Definition: FTMDataTypes.h:28
int threadNumber_
Definition: BaseClass.h:95
virtual int setThreadNumber(const int threadNumber)
Definition: BaseClass.h:80
Minimalist debugging class.
Definition: Debug.h:88
int debugLevel_
Definition: Debug.h:379
int printWrn(const std::string &msg, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cerr) const
Definition: Debug.h:159
void setDebugMsgPrefix(const std::string &prefix)
Definition: Debug.h:364
virtual int setDebugLevel(const int &debugLevel)
Definition: Debug.cpp:147
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
int getBestInitTreeIndex(std::vector< ftm::FTMTree_MT * > &trees, std::vector< ftm::FTMTree_MT * > &trees2, unsigned int barycenterMaximumNumberOfPairs, double sizeLimitPercent, bool distMinimizer=true)
void limitSizeBarycenter(ftm::MergeTree< dataType > &bary, std::vector< ftm::FTMTree_MT * > &trees, unsigned int barycenterMaximumNumberOfPairs, double percent, bool useBD=true)
ftm::idNode getNodesAndScalarsToAdd(ftm::MergeTree< dataType > &ttkNotUsed(mTree1), ftm::idNode nodeId1, ftm::FTMTree_MT *tree2, ftm::idNode nodeId2, std::vector< dataType > &newScalarsVector, std::vector< std::tuple< ftm::idNode, ftm::idNode, int > > &nodesToProcess, ftm::idNode nodeCpt, int i)
std::tuple< dataType, dataType > getParametrizedBirthDeath(ftm::FTMTree_MT *tree1, ftm::idNode nodeId1)
void getParametrizedDistanceMatrix(std::vector< ftm::FTMTree_MT * > &trees, std::vector< std::vector< double > > &distanceMatrix, unsigned int barycenterMaximumNumberOfPairs, double sizeLimitPercent, bool useDoubleInput=false, bool isFirstInput=true)
void verifyBarycenterTwoTrees(std::vector< ftm::FTMTree_MT * > &trees, ftm::MergeTree< dataType > &baryMergeTree, std::vector< std::vector< std::tuple< ftm::idNode, ftm::idNode, double > > > &finalMatchings, std::vector< dataType > distances)
void computeOneDistance(ftm::FTMTree_MT *tree, ftm::FTMTree_MT *baryTree, std::vector< std::tuple< ftm::idNode, ftm::idNode, double > > &matching, dataType &distance, bool useDoubleInput=false, bool isFirstInput=true)
void updateNodesAndScalars(ftm::MergeTree< dataType > &mTree1, int noTrees, std::vector< std::tuple< ftm::idNode, ftm::idNode, int > > &nodesToProcess, std::vector< dataType > &newScalarsVector, std::vector< std::vector< std::tuple< ftm::idNode, ftm::idNode > > > &nodesProcessed)
unsigned int persistenceScaling(std::vector< ftm::FTMTree_MT * > &trees, std::vector< ftm::MergeTree< dataType > > &mergeTrees, std::vector< ftm::FTMTree_MT * > &oriTrees, int iterationNumber, std::vector< std::vector< ftm::idNode > > &deletedNodes)
void fixMergedRootOriginBarycenter(ftm::MergeTree< dataType > &barycenter)
void setAddNodes(bool addNodesT)
void setPreprocess(bool preproc)
void computeOneDistance(ftm::MergeTree< dataType > &baryMergeTree, ftm::MergeTree< dataType > &baryMergeTree2, std::vector< std::tuple< ftm::idNode, ftm::idNode, double > > &matching, dataType &distance, bool useDoubleInput=false, bool isFirstInput=true)
void getDistanceMatrix(std::vector< ftm::FTMTree_MT * > &trees, std::vector< ftm::FTMTree_MT * > &trees2, std::vector< std::vector< double > > &distanceMatrix, bool useDoubleInput=false, bool isFirstInput=true)
void limitSizeBarycenter(ftm::MergeTree< dataType > &bary, std::vector< ftm::FTMTree_MT * > &trees, double percent, bool useBD=true)
std::tuple< dataType, dataType > interpolation(ftm::MergeTree< dataType > &baryMergeTree, ftm::idNode nodeId, std::vector< dataType > &newScalarsVector, std::vector< ftm::FTMTree_MT * > &trees, std::vector< ftm::idNode > &nodes, std::vector< double > &alphas)
int getBestInitTreeIndex(std::vector< ftm::FTMTree_MT * > &trees, bool distMinimizer=true)
void computeBarycenter(std::vector< ftm::FTMTree_MT * > &trees, ftm::MergeTree< dataType > &baryMergeTree, std::vector< double > &alphas, std::vector< std::vector< std::tuple< ftm::idNode, ftm::idNode, double > > > &finalMatchings, bool finalAsgnDoubleInput=false, bool finalAsgnFirstInput=true)
void assignmentPara(std::vector< ftm::FTMTree_MT * > &trees, ftm::MergeTree< dataType > &baryMergeTree, std::vector< std::vector< std::tuple< ftm::idNode, ftm::idNode, double > > > &matchings, std::vector< dataType > &distances, bool useDoubleInput=false, bool isFirstInput=true)
void setPostprocess(bool postproc)
std::tuple< dataType, dataType > interpolationAdded(ftm::FTMTree_MT *tree, ftm::idNode nodeId, double alpha, ftm::MergeTree< dataType > &baryMergeTree, ftm::idNode nodeB, std::vector< dataType > &newScalarsVector)
unsigned int barycenterMaximumNumberOfPairs_
void setDeterministic(bool deterministicT)
~MergeTreeBarycenter() override=default
void updateBarycenterTreeScalars(std::vector< ftm::FTMTree_MT * > &trees, ftm::MergeTree< dataType > &baryMergeTree, std::vector< double > &alphas, unsigned int indexAddedNodes, std::vector< std::vector< std::tuple< ftm::idNode, ftm::idNode, double > > > &matchings)
void addNodes(ftm::MergeTree< dataType > &mTree1, int noTrees, std::vector< std::tuple< ftm::idNode, ftm::idNode, int > > &nodesToProcess, std::vector< std::vector< std::tuple< ftm::idNode, ftm::idNode > > > &nodesProcessed)
void initBarycenterTree(std::vector< ftm::FTMTree_MT * > &trees, ftm::MergeTree< dataType > &baryTree, bool distMinimizer=true)
void assignmentTask(std::vector< ftm::FTMTree_MT * > &trees, ftm::MergeTree< dataType > &baryMergeTree, std::vector< std::vector< std::tuple< ftm::idNode, ftm::idNode, double > > > &matchings, std::vector< dataType > &distances, bool useDoubleInput=false, bool isFirstInput=true)
void execute(std::vector< ftm::MergeTree< dataType > > &trees, std::vector< std::vector< std::tuple< ftm::idNode, ftm::idNode, double > > > &finalMatchings, ftm::MergeTree< dataType > &baryMergeTree, bool finalAsgnDoubleInput=false, bool finalAsgnFirstInput=true)
void setProgressiveSpeedDivisor(double progSpeed)
void addScaledDeletedNodesCost(std::vector< ftm::FTMTree_MT * > &oriTrees, std::vector< std::vector< ftm::idNode > > &deletedNodes, std::vector< dataType > &distances)
void updateBarycenterTreeStructure(std::vector< ftm::FTMTree_MT * > &trees, ftm::MergeTree< dataType > &baryMergeTree, std::vector< std::vector< std::tuple< ftm::idNode, ftm::idNode, double > > > &matchings)
std::vector< double > finalDistances_
void getSizeLimitedTrees(std::vector< ftm::FTMTree_MT * > &trees, unsigned int barycenterMaximumNumberOfPairs, double sizeLimitPercent, std::vector< ftm::MergeTree< dataType > > &mTreesLimited)
void printBaryStats(ftm::FTMTree_MT *baryTree, const debug::Priority &priority=debug::Priority::INFO)
void setProgressiveBarycenter(bool progressive)
void limitSizeBarycenter(ftm::MergeTree< dataType > &bary, std::vector< ftm::FTMTree_MT * > &trees, bool useBD=true)
void assignment(std::vector< ftm::FTMTree_MT * > &trees, ftm::MergeTree< dataType > &baryMergeTree, std::vector< std::vector< std::tuple< ftm::idNode, ftm::idNode, double > > > &matchings, std::vector< dataType > &distances, bool useDoubleInput=false, bool isFirstInput=true)
void setBarycenterMaximumNumberOfPairs(unsigned int maxi)
void computeOneDistance(ftm::FTMTree_MT *tree, ftm::MergeTree< dataType > &baryMergeTree, std::vector< std::tuple< ftm::idNode, ftm::idNode, double > > &matching, dataType &distance, bool useDoubleInput=false, bool isFirstInput=true)
void setAlpha(double alpha)
void setBarycenterSizeLimitPercent(double percent)
void getSizeLimitedDistanceMatrix(std::vector< ftm::FTMTree_MT * > &trees, std::vector< std::vector< double > > &distanceMatrix, unsigned int barycenterMaximumNumberOfPairs, double sizeLimitPercent, bool useDoubleInput=false, bool isFirstInput=true)
void updateBarycenterTree(std::vector< ftm::FTMTree_MT * > &trees, ftm::MergeTree< dataType > &baryMergeTree, std::vector< double > &alphas, std::vector< std::vector< std::tuple< ftm::idNode, ftm::idNode, double > > > &matchings)
std::vector< double > getFinalDistances()
void limitSizePercent(ftm::MergeTree< dataType > &bary, std::vector< ftm::FTMTree_MT * > &trees, double percent, bool useBD)
void getDistanceMatrix(std::vector< ftm::FTMTree_MT * > &trees, std::vector< std::vector< double > > &distanceMatrix, bool useDoubleInput=false, bool isFirstInput=true)
int getBestInitTreeIndex(std::vector< ftm::FTMTree_MT * > &trees, std::vector< ftm::FTMTree_MT * > &trees2, double sizeLimitPercent, bool distMinimizer=true)
void execute(std::vector< ftm::MergeTree< dataType > > &trees, std::vector< double > &alphas, std::vector< std::vector< std::tuple< ftm::idNode, ftm::idNode, double > > > &finalMatchings, ftm::MergeTree< dataType > &baryMergeTree, bool finalAsgnDoubleInput=false, bool finalAsgnFirstInput=true)
void setBranchDecomposition(bool useBD)
void setNormalizedWasserstein(bool normalizedWasserstein)
void setDistanceSquaredRoot(bool distanceSquaredRoot)
void setAssignmentSolver(int assignmentSolver)
Definition: MergeTreeBase.h:69
void setNodePerTask(int npt)
double mixDistances(dataType distance1, dataType distance2)
double getSizeLimitMetric(std::vector< ftm::FTMTree_MT * > &trees)
void printTreesStats(std::vector< ftm::FTMTree_MT * > &trees)
void printMatching(std::vector< MatchingType > &matchings)
std::vector< std::vector< int > > treesNodeCorr_
Definition: MergeTreeBase.h:60
void setKeepSubtree(bool keepSubtree)
double mixDistancesMinMaxPairWeight(bool isFirstInput)
dataType computeDistance(ftm::FTMTree_MT *tree1, ftm::FTMTree_MT *tree2, std::vector< std::tuple< ftm::idNode, ftm::idNode, double > > &outputMatching)
void setPreprocess(bool preproc)
void setPostprocess(bool postproc)
void setMinMaxPairWeight(double weight)
double getElapsedTime()
Definition: Timer.h:15
const scalarType & getValue(SimplexId nodeId) const
Definition: FTMTree_MT.h:339
bool isNodeIdInconsistent(idNode nodeId)
idNode getNumberOfNodes() const
Definition: FTMTree_MT.h:389
void setParent(idNode nodeId, idNode newParentNodeId)
std::tuple< dataType, dataType > getBirthDeath(idNode nodeId)
void getChildren(idNode nodeId, std::vector< idNode > &res)
void deleteNode(idNode nodeId)
idNode makeNode(SimplexId vertexId, SimplexId linked=nullVertex)
Definition: FTMTree_MT.cpp:473
bool isNodeAlone(idNode nodeId)
void copyMergeTreeStructure(FTMTree_MT *tree)
Node * getNode(idNode nodeId)
Definition: FTMTree_MT.h:393
void setOrigin(SimplexId linked)
Definition: FTMNode.h:72
SimplexId getOrigin() const
Definition: FTMNode.h:64
Priority
Definition: Debug.h:43
unsigned int idNode
Node index in vect_nodes_.
Definition: FTMDataTypes.h:39
The Topology ToolKit.
ftm::FTMTree_MT tree
Definition: FTMTree_MT.h:901