58 "MergeTreeBarycenter");
60#ifdef TTK_ENABLE_OPENMP4
128 template <
class dataType>
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_OPENMP4
137#pragma omp parallel for schedule(dynamic) \
138 num_threads(this->threadNumber_) if(parallelize_)
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;
144 computeOneDistance<dataType>(trees[i], trees2[j], matching, distance,
145 useDoubleInput, isFirstInput);
146 distanceMatrix[i][j] = distance;
147 distanceMatrix[j][i] = distance;
151 template <
class dataType>
153 std::vector<std::vector<double>> &distanceMatrix,
154 bool useDoubleInput =
false,
155 bool isFirstInput =
true) {
156 getDistanceMatrix<dataType>(
157 trees, trees, distanceMatrix, useDoubleInput, isFirstInput);
160 template <
class dataType>
162 std::vector<ftm::FTMTree_MT *> &trees,
163 unsigned int barycenterMaximumNumberOfPairs,
164 double sizeLimitPercent,
166 mTreesLimited.resize(trees.size());
167 for(
unsigned int i = 0; i < trees.size(); ++i) {
168 mTreesLimited[i] = ftm::copyMergeTree<dataType>(trees[i]);
170 barycenterMaximumNumberOfPairs, sizeLimitPercent);
171 ftm::cleanMergeTree<dataType>(mTreesLimited[i]);
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);
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);
204 getSizeLimitedDistanceMatrix<dataType>(
205 trees, distanceMatrix, barycenterMaximumNumberOfPairs,
206 sizeLimitPercent, useDoubleInput, isFirstInput);
209 template <
class dataType>
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 const 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);
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) {
231 for(
unsigned int j = 0; j < distanceMatrix[i].size(); ++j)
232 value += (not useDoubleInput ? distanceMatrix[i][j]
234 distanceMatrix2[i][j]));
235 if((distMinimizer and value < bestValue)
236 or (not distMinimizer and value > bestValue)) {
241 sizes[i] *= (distMinimizer) ? 1 : -1;
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);
253 template <
class dataType>
255 std::vector<ftm::FTMTree_MT *> &trees2,
256 double sizeLimitPercent,
257 bool distMinimizer =
true) {
258 return getBestInitTreeIndex<dataType>(trees, trees2,
260 sizeLimitPercent, distMinimizer);
263 template <
class dataType>
265 bool distMinimizer =
true) {
266 std::vector<ftm::FTMTree_MT *> trees2;
267 return getBestInitTreeIndex<dataType>(
272 template <
class dataType>
275 bool distMinimizer =
true) {
277 = getBestInitTreeIndex<dataType>(trees, distMinimizer);
278 baryTree = ftm::copyMergeTree<dataType>(trees[bestIndex],
true);
285 template <
class dataType>
291 std::vector<dataType> &newScalarsVector,
292 std::vector<std::tuple<ftm::idNode, ftm::idNode, int>> &nodesToProcess,
296 std::queue<std::tuple<ftm::idNode, ftm::idNode>> queue;
297 queue.emplace(nodeId2, nodeId1);
298 nodesToProcess.emplace_back(nodeId2, nodeId1, i);
299 while(!queue.empty()) {
300 auto queueTuple = queue.front();
304 newScalarsVector.push_back(
306 newScalarsVector.push_back(tree2->
getValue<dataType>(node));
308 std::vector<ftm::idNode> children;
310 for(
auto child : children) {
311 queue.emplace(child, nodeCpt + 1);
312 nodesToProcess.emplace_back(child, nodeCpt + 1, i);
320 template <
class dataType>
324 std::vector<std::tuple<ftm::idNode, ftm::idNode, int>> &nodesToProcess,
325 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode>>>
330 nodesProcessed.
clear();
331 nodesProcessed.resize(noTrees);
332 for(
auto processTuple : nodesToProcess) {
333 ftm::idNode const parent = std::get<1>(processTuple);
335 int const index = std::get<2>(processTuple);
336 nodesProcessed[index].emplace_back(
337 nodeTree1 + 1, std::get<0>(processTuple));
347 template <
class dataType>
351 std::vector<std::tuple<ftm::idNode, ftm::idNode, int>> &nodesToProcess,
352 std::vector<dataType> &newScalarsVector,
353 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode>>>
359 = ftm::createEmptyMergeTree<dataType>(newScalarsVector.size());
360 ftm::setTreeScalars<dataType>(mTreeNew, newScalarsVector);
367 addNodes<dataType>(mTreeNew, noTrees, nodesToProcess, nodesProcessed);
373 template <
class dataType>
375 std::vector<ftm::FTMTree_MT *> &trees,
377 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
385 std::vector<std::vector<ftm::idNode>> matrixMatchings(trees.size());
387 for(
unsigned int i = 0; i < matchings.size(); ++i) {
388 auto matching = matchings[i];
389 matrixMatchings[i].resize(trees[i]->getNumberOfNodes(),
390 std::numeric_limits<ftm::idNode>::max());
391 for(
auto match : matching) {
392 matrixMatchings[i][std::get<1>(match)] = std::get<0>(match);
393 baryMatched[std::get<0>(match)] =
true;
398 std::vector<std::vector<ftm::idNode>> nodesToAdd(trees.size());
399 for(
unsigned int i = 0; i < trees.size(); ++i) {
401 std::queue<ftm::idNode> queue;
403 while(!queue.empty()) {
406 bool processChildren =
true;
408 if(matrixMatchings[i][node]
409 == std::numeric_limits<ftm::idNode>::max()) {
411 processChildren =
false;
412 nodesToAdd[i].push_back(node);
417 "barycenter with keepSubtree_=true is not implemented yet");
420 if(processChildren) {
421 std::vector<ftm::idNode> children;
422 trees[i]->getChildren(node, children);
423 for(
auto child : children)
424 if(not(trees[i]->isThereOnlyOnePersistencePair()
425 and trees[i]->isLeaf(child)))
426 queue.emplace(child);
431 bool foundRootNotMatched =
false;
432 for(
unsigned int i = 0; i < trees.size(); ++i)
434 matrixMatchings[i][trees[i]->getRoot()]);
435 if(foundRootNotMatched)
436 printWrn(
"[updateBarycenterTreeStructure] an input tree has its root "
441 if(not baryMatched[i])
447 std::vector<std::tuple<ftm::idNode, ftm::idNode, int>> nodesToProcess;
448 std::vector<dataType> newScalarsVector;
449 ftm::getTreeScalars<dataType>(baryMergeTree, newScalarsVector);
450 for(
unsigned int i = 0; i < nodesToAdd.size(); ++i) {
451 for(
auto node : nodesToAdd[i]) {
453 = matrixMatchings[i][trees[i]->getParentSafe(node)];
454 if(matchings[i].size() == 0)
455 parent = baryTreeRoot;
459 and matchings[i].size() != 0) {
460 std::stringstream ss;
461 ss << trees[i]->getParentSafe(node) <<
" _ " << node;
463 printMsg(trees[i]->printTree().str());
464 printMsg(trees[i]->printPairsFromTree<dataType>(
true).str());
466 std::stringstream ss2;
467 ss2 <<
"parent " << parent;
472 std::vector<dataType> addedScalars;
473 nodeCpt = getNodesAndScalarsToAdd<dataType>(
474 baryMergeTree, parent, trees[i], node, addedScalars,
475 nodesToProcess, nodeCpt, i);
476 newScalarsVector.insert(
477 newScalarsVector.end(), addedScalars.begin(), addedScalars.end());
481 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode>>>
483 updateNodesAndScalars<dataType>(baryMergeTree, trees.size(),
484 nodesToProcess, newScalarsVector,
486 for(
unsigned int i = 0; i < matchings.size(); ++i) {
487 std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>
489 for(
auto tup : nodesProcessed[i])
490 nodesProcessedT.emplace_back(
491 std::get<0>(tup), std::get<1>(tup), -1);
492 matchings[i].insert(matchings[i].
end(), nodesProcessedT.begin(),
493 nodesProcessedT.end());
499 printErr(
"barycenter with keepSubtree_=true is not implemented yet");
503 template <
class dataType>
504 std::tuple<dataType, dataType>
506 std::tuple<dataType, dataType> birthDeath;
509 birthDeath = getNormalizedBirthDeathDouble<dataType>(tree1, nodeId1);
516 template <
class dataType>
517 std::tuple<dataType, dataType>
520 std::vector<dataType> &newScalarsVector,
521 std::vector<ftm::FTMTree_MT *> &trees,
522 std::vector<ftm::idNode> &nodes,
523 std::vector<double> &alphas) {
525 dataType mu_max = getMinMaxLocalFromVector<dataType>(
526 baryTree, nodeId, newScalarsVector,
false);
527 dataType mu_min = getMinMaxLocalFromVector<dataType>(
528 baryTree, nodeId, newScalarsVector);
529 double newBirth = 0, newDeath = 0;
532 double tempBirth = 0, tempDeath = 0;
534 for(
unsigned int i = 0; i < trees.size(); ++i)
535 if(nodes[i] != std::numeric_limits<ftm::idNode>::max())
536 alphaSum += alphas[i];
537 for(
unsigned int i = 0; i < trees.size(); ++i) {
539 if(nodes[i] != std::numeric_limits<ftm::idNode>::max()) {
541 = getParametrizedBirthDeath<dataType>(trees[i], nodes[i]);
542 double tTempBirth = 0, tTempDeath = 0;
543 tTempBirth += std::get<0>(iBirthDeath);
544 tTempDeath += std::get<1>(iBirthDeath);
545 tempBirth += tTempBirth * alphas[i] / alphaSum;
546 tempDeath += tTempDeath * alphas[i] / alphaSum;
549 double const projec = (tempBirth + tempDeath) / 2;
552 for(
unsigned int i = 0; i < trees.size(); ++i) {
553 double iBirth = projec, iDeath = projec;
555 if(nodes[i] != std::numeric_limits<ftm::idNode>::max()) {
557 = getParametrizedBirthDeath<dataType>(trees[i], nodes[i]);
558 iBirth = std::get<0>(iBirthDeath);
559 iDeath = std::get<1>(iBirthDeath);
561 newBirth += alphas[i] * iBirth;
562 newDeath += alphas[i] * iDeath;
565 newBirth = newBirth * (mu_max - mu_min) + mu_min;
566 newDeath = newDeath * (mu_max - mu_min) + mu_min;
569 return std::make_tuple(newBirth, newDeath);
572 template <
class dataType>
573 std::tuple<dataType, dataType>
579 std::vector<dataType> &newScalarsVector) {
581 dataType mu_max = getMinMaxLocalFromVector<dataType>(
582 baryTree, nodeB, newScalarsVector,
false);
584 = getMinMaxLocalFromVector<dataType>(baryTree, nodeB, newScalarsVector);
586 auto birthDeath = getParametrizedBirthDeath<dataType>(tree, nodeId);
587 double newBirth = std::get<0>(birthDeath);
588 double newDeath = std::get<1>(birthDeath);
589 double const projec = (newBirth + newDeath) / 2;
591 newBirth = alpha * newBirth + (1 - alpha) * projec;
592 newDeath = alpha * newDeath + (1 - alpha) * projec;
595 newBirth = newBirth * (mu_max - mu_min) + mu_min;
596 newDeath = newDeath * (mu_max - mu_min) + mu_min;
599 dataType newBirthT = newBirth;
600 dataType newDeathT = newDeath;
601 return std::make_tuple(newBirthT, newDeathT);
604 template <
class dataType>
606 std::vector<ftm::FTMTree_MT *> &trees,
608 std::vector<double> &alphas,
609 unsigned int indexAddedNodes,
610 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
613 bool const isJT = baryTree->
isJoinTree<dataType>();
618 std::vector<std::vector<ftm::idNode>> baryMatching(
620 std::vector<ftm::idNode>(
621 trees.size(), std::numeric_limits<ftm::idNode>::max()));
623 for(
unsigned int i = 0; i < matchings.size(); ++i) {
624 auto matching = matchings[i];
625 for(
auto match : matching) {
626 baryMatching[std::get<0>(match)][i] = std::get<1>(match);
627 if(std::get<0>(match)
629 nodesAddedTree[std::get<0>(match)] = i;
636 std::queue<ftm::idNode> queue;
638 while(!queue.empty()) {
641 std::tuple<dataType, dataType> newBirthDeath;
642 if(node < indexAddedNodes) {
644 = interpolation<dataType>(baryMergeTree, node, newScalarsVector,
645 trees, baryMatching[node], alphas);
647 int const i = nodesAddedTree[node];
649 newBirthDeath = interpolationAdded<dataType>(
650 trees[i], nodeT, alphas[i], baryMergeTree, node, newScalarsVector);
653 = (isJT ? std::get<1>(newBirthDeath) : std::get<0>(newBirthDeath));
654 dataType nodeOriginScalar
655 = (isJT ? std::get<0>(newBirthDeath) : std::get<1>(newBirthDeath));
656 newScalarsVector[node] = nodeScalar;
659 std::vector<ftm::idNode> children;
661 for(
auto child : children)
662 queue.emplace(child);
667 dataType mergedRootOriginScalar = 0.0;
668 for(
unsigned int i = 0; i < trees.size(); ++i)
669 mergedRootOriginScalar += trees[i]->getValue<dataType>(
670 trees[i]->getMergedRootOrigin<dataType>());
671 mergedRootOriginScalar /= trees.size();
672 newScalarsVector[mergedRootOrigin] = mergedRootOriginScalar;
675 setTreeScalars(baryMergeTree, newScalarsVector);
677 std::vector<ftm::idNode> deletedNodesT;
678 persistenceThresholding<dataType>(
679 &(baryMergeTree.
tree), 0, deletedNodesT);
681 ftm::cleanMergeTree<dataType>(baryMergeTree);
684 template <
class dataType>
686 std::vector<ftm::FTMTree_MT *> &trees,
688 std::vector<double> &alphas,
689 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
692 updateBarycenterTreeStructure<dataType>(trees, baryMergeTree, matchings);
693 updateBarycenterTreeScalars<dataType>(
694 trees, baryMergeTree, alphas, indexAddedNodes, matchings);
700 template <
class dataType>
704 std::vector<std::tuple<ftm::idNode, ftm::idNode, double>> &matching,
706 bool useDoubleInput =
false,
707 bool isFirstInput =
true) {
730 = mergeTreeDistance.
computeDistance<dataType>(baryTree, tree, matching);
731 std::stringstream ss, ss2;
732 ss <<
"distance tree : " << distance;
734 ss2 <<
"distance²tree : " << distance * distance;
741 template <
class dataType>
745 std::vector<std::tuple<ftm::idNode, ftm::idNode, double>> &matching,
747 bool useDoubleInput =
false,
748 bool isFirstInput =
true) {
749 computeOneDistance<dataType>(tree, &(baryMergeTree.
tree), matching,
750 distance, useDoubleInput, isFirstInput);
753 template <
class dataType>
757 std::vector<std::tuple<ftm::idNode, ftm::idNode, double>> &matching,
759 bool useDoubleInput =
false,
760 bool isFirstInput =
true) {
761 computeOneDistance<dataType>(&(baryMergeTree.
tree), baryMergeTree2,
762 matching, distance, useDoubleInput,
766 template <
class dataType>
768 std::vector<ftm::FTMTree_MT *> &trees,
770 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
772 std::vector<dataType> &distances,
773 bool useDoubleInput =
false,
774 bool isFirstInput =
true) {
777 useDoubleInput, isFirstInput);
780 useDoubleInput, isFirstInput);
783 template <
class dataType>
785 std::vector<ftm::FTMTree_MT *> &trees,
787 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
789 std::vector<dataType> &distances,
790 bool useDoubleInput =
false,
791 bool isFirstInput =
true) {
792#ifdef TTK_ENABLE_OPENMP4
793#pragma omp parallel num_threads(this->threadNumber_) \
794 shared(baryMergeTree) if(parallelize_)
796#pragma omp single nowait
799 useDoubleInput, isFirstInput);
800#ifdef TTK_ENABLE_OPENMP4
805 template <
class dataType>
807 std::vector<ftm::FTMTree_MT *> &trees,
809 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
811 std::vector<dataType> &distances,
812 bool useDoubleInput =
false,
813 bool isFirstInput =
true) {
814 for(
unsigned int i = 0; i < trees.size(); ++i)
815#ifdef TTK_ENABLE_OPENMP4
816#pragma omp task firstprivate(i)
UNTIED() \
817 shared(baryMergeTree, matchings, distances)
819 computeOneDistance<dataType>(trees[i], baryMergeTree, matchings[i],
820 distances[i], useDoubleInput,
822#ifdef TTK_ENABLE_OPENMP4
830 template <
class dataType>
834 std::vector<ftm::FTMTree_MT *> &oriTrees,
836 std::vector<std::vector<ftm::idNode>> &deletedNodes) {
837 deletedNodes.clear();
838 deletedNodes.resize(oriTrees.size());
839 unsigned int noTreesUnscaled = 0;
842 for(
unsigned int i = 0; i < oriTrees.size(); ++i) {
843 double persistenceThreshold = 50.0;
844 if(iterationNumber != -1) {
846 int const noPairs = mergeTrees[i].tree.getRealNumberOfNodes();
849 std::vector<std::tuple<ftm::idNode, ftm::idNode, dataType>> pairs;
850 oriTrees[i]->getPersistencePairsFromTree<dataType>(
854 double const multiplier
858 int const decrement = multiplier * pairs.size() / 10;
859 int thresholdIndex = pairs.size() - noPairs - std::max(decrement, 2);
860 thresholdIndex = std::max(thresholdIndex, 0);
861 const double persistence = std::get<2>(pairs[thresholdIndex]);
863 = persistence / std::get<2>(pairs.back()) * 100.0;
864 if(thresholdIndex == 0) {
865 persistenceThreshold = 0.;
869 if(persistenceThreshold != 0.) {
871 = ftm::copyMergeTree<dataType>(oriTrees[i]);
872 persistenceThresholding<dataType>(
873 &(mt.
tree), persistenceThreshold, deletedNodes[i]);
874 if(mergeTrees.size() == 0)
875 mergeTrees.resize(oriTrees.size());
877 trees[i] = &(mt.
tree);
879 trees[i] = oriTrees[i];
885 return noTreesUnscaled;
888 template <
class dataType>
890 std::vector<ftm::FTMTree_MT *> &oriTrees,
891 std::vector<std::vector<ftm::idNode>> &deletedNodes,
892 std::vector<dataType> &distances) {
893 for(
unsigned int i = 0; i < oriTrees.size(); ++i)
894 for(
auto node : deletedNodes[i])
895 distances[i] += deleteCost<dataType>(oriTrees[i], node);
901 template <
class dataType>
903 std::vector<ftm::FTMTree_MT *> &trees,
905 std::vector<double> &alphas,
906 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
908 bool finalAsgnDoubleInput =
false,
909 bool finalAsgnFirstInput =
true) {
915 std::vector<ftm::FTMTree_MT *> oriTrees;
916 std::vector<ftm::MergeTree<dataType>> scaledMergeTrees;
917 std::vector<std::vector<ftm::idNode>> deletedNodes;
919 oriTrees.insert(oriTrees.end(), trees.begin(), trees.end());
920 persistenceScaling<dataType>(
921 trees, scaledMergeTrees, oriTrees, -1, deletedNodes);
922 std::vector<ftm::idNode> deletedNodesT;
923 persistenceThresholding<dataType>(baryTree, 50, deletedNodesT);
925 bool treesUnscaled =
false;
931 bool converged =
false;
932 dataType frechetEnergy = -1;
933 dataType minFrechet = std::numeric_limits<dataType>::max();
936 while(not converged) {
940 std::stringstream ss;
941 ss <<
"Iteration " << NoIteration;
945 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
946 matchings(trees.size());
947 std::vector<dataType> distances(trees.size(), -1);
949 assignment<dataType>(trees, baryMergeTree, matchings, distances);
950 Timer t_addDeletedNodes;
952 addScaledDeletedNodesCost<dataType>(
953 oriTrees, deletedNodes, distances);
955 auto t_assignment_time
962 updateBarycenterTree<dataType>(trees, baryMergeTree, alphas, matchings);
964 baryTree = &(baryMergeTree.
tree);
969 dataType currentFrechetEnergy = 0;
970 for(
unsigned int i = 0; i < trees.size(); ++i)
971 currentFrechetEnergy += alphas[i] * distances[i] * distances[i];
973 = std::abs((
double)(frechetEnergy - currentFrechetEnergy));
974 converged = (frechetDiff <=
tol_);
976 frechetEnergy = currentFrechetEnergy;
977 tol_ = frechetEnergy / 125.0;
979 std::stringstream ss4;
984 ss4 <<
"Frechet energy : " << frechetEnergy;
987 minFrechet = std::min(minFrechet, frechetEnergy);
989 cptBlocked = (minFrechet < frechetEnergy) ? cptBlocked + 1 : 0;
990 converged = (cptBlocked >= 10);
995 unsigned int const noTreesUnscaled = persistenceScaling<dataType>(
996 trees, scaledMergeTrees, oriTrees, NoIteration, deletedNodes);
997 treesUnscaled = (noTreesUnscaled == oriTrees.size());
1005 std::vector<dataType> distances(trees.size(), -1);
1006 assignment<dataType>(trees, baryMergeTree, finalMatchings, distances,
1007 finalAsgnDoubleInput, finalAsgnFirstInput);
1008 for(
auto dist : distances)
1010 dataType currentFrechetEnergy = 0;
1011 for(
unsigned int i = 0; i < trees.size(); ++i)
1012 currentFrechetEnergy += alphas[i] * distances[i] * distances[i];
1014 std::stringstream ss, ss2;
1015 ss <<
"Frechet energy : " << currentFrechetEnergy;
1023 verifyBarycenterTwoTrees<dataType>(
1024 trees, baryMergeTree, finalMatchings, distances);
1028 scaledMergeTrees.clear();
1030 trees.insert(trees.end(), oriTrees.begin(), oriTrees.end());
1034 template <
class dataType>
1037 std::vector<double> &alphas,
1038 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
1041 bool finalAsgnDoubleInput =
false,
1042 bool finalAsgnFirstInput =
true) {
1046 for(
unsigned int i = 0; i < trees.size(); ++i)
1055 std::vector<ftm::FTMTree_MT *> treesT;
1056 ftm::mergeTreeToFTMTree<dataType>(trees, treesT);
1057 initBarycenterTree<dataType>(treesT, baryMergeTree);
1060 computeBarycenter<dataType>(treesT, baryMergeTree, alphas, finalMatchings,
1061 finalAsgnDoubleInput, finalAsgnFirstInput);
1065 std::vector<int>
const allRealNodes(trees.size());
1066 for(
unsigned int i = 0; i < trees.size(); ++i) {
1067 postprocessingPipeline<dataType>(treesT[i]);
1071 postprocessingPipeline<dataType>(&(baryMergeTree.
tree));
1072 for(
unsigned int i = 0; i < trees.size(); ++i) {
1073 convertBranchDecompositionMatching<dataType>(
1074 &(baryMergeTree.
tree), treesT[i], finalMatchings[i]);
1079 template <
class dataType>
1082 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
1085 bool finalAsgnDoubleInput =
false,
1086 bool finalAsgnFirstInput =
true) {
1087 std::vector<double> alphas;
1088 if(trees.size() != 2) {
1089 for(
unsigned int i = 0; i < trees.size(); ++i)
1090 alphas.push_back(1.0 / trees.size());
1092 alphas.push_back(
alpha_);
1093 alphas.push_back(1 -
alpha_);
1096 execute<dataType>(trees, alphas, finalMatchings, baryMergeTree,
1097 finalAsgnDoubleInput, finalAsgnFirstInput);
1103 template <
class dataType>
1105 std::vector<ftm::FTMTree_MT *> &trees,
1109 unsigned int const newNoNodes = metric * percent / 100.0;
1110 keepMostImportantPairs<dataType>(&(bary.
tree), newNoNodes, useBD);
1114 and noNodesAfter > 3) {
1115 std::cout <<
"metric = " << metric << std::endl;
1116 std::cout <<
"newNoNodes = " << newNoNodes << std::endl;
1117 std::cout <<
"noNodesAfter = " << noNodesAfter << std::endl;
1121 template <
class dataType>
1123 std::vector<ftm::FTMTree_MT *> &trees,
1124 unsigned int barycenterMaximumNumberOfPairs,
1126 bool useBD =
true) {
1127 if(barycenterMaximumNumberOfPairs > 0)
1128 keepMostImportantPairs<dataType>(
1129 &(bary.
tree), barycenterMaximumNumberOfPairs, useBD);
1133 template <
class dataType>
1135 std::vector<ftm::FTMTree_MT *> &trees,
1137 bool useBD =
true) {
1141 template <
class dataType>
1143 std::vector<ftm::FTMTree_MT *> &trees,
1144 bool useBD =
true) {
1152 template <
class dataType>
1158 auto tup = fixMergedRootOrigin<dataType>(tree);
1159 int maxIndex = std::get<0>(tup);
1160 dataType oldOriginValue = std::get<1>(tup);
1164 std::vector<dataType> newScalarsVector;
1165 ftm::getTreeScalars<dataType>(tree, newScalarsVector);
1167 if((isJT and tree->
getValue<dataType>(maxIndex) > oldOriginValue)
1169 and tree->
getValue<dataType>(maxIndex) < oldOriginValue)) {
1170 newScalarsVector[treeRoot] = newScalarsVector[maxIndex];
1171 newScalarsVector[maxIndex] = oldOriginValue;
1173 newScalarsVector[treeRoot] = oldOriginValue;
1174 setTreeScalars(barycenter, newScalarsVector);
1185 std::stringstream ss;
1186 ss <<
"Barycenter number of nodes : " << noNodes <<
" / " << noNodesT;
1193 template <
class dataType>
1195 std::vector<ftm::FTMTree_MT *> &trees,
1197 std::vector<std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>>
1199 std::vector<dataType> distances) {
1200 std::vector<std::tuple<ftm::idNode, ftm::idNode, double>> matching;
1203 if(distance != (distances[0] + distances[1])) {
1204 std::stringstream ss, ss2, ss3, ss4;
1205 ss <<
"distance T1 T2 : " << distance;
1207 ss2 <<
"distance T1 T' T2 : " << distances[0] + distances[1];
1209 ss3 <<
"distance T1 T' : " << distances[0];
1211 ss4 <<
"distance T' T2 : " << distances[1];
1216 auto baryTree = &(baryMergeTree.
tree);
1217 std::vector<std::vector<ftm::idNode>> baryMatched(
1218 baryTree->getNumberOfNodes(),
1219 std::vector<ftm::idNode>(
1220 trees.size(), std::numeric_limits<ftm::idNode>::max()));
1221 for(
unsigned int i = 0; i < finalMatchings.size(); ++i)
1222 for(
auto match : finalMatchings[i])
1223 baryMatched[std::get<0>(match)][i] = std::get<1>(match);
1225 std::queue<ftm::idNode> queue;
1226 queue.emplace(baryTree->getRoot());
1227 while(!queue.empty()) {
1228 auto node = queue.front();
1230 std::vector<dataType> costs(trees.size());
1231 for(
unsigned int i = 0; i < trees.size(); ++i)
1232 if(baryMatched[node][i] != std::numeric_limits<ftm::idNode>::max())
1233 costs[i] = relabelCost<dataType>(
1234 baryTree, node, trees[i], baryMatched[node][i]);
1236 costs[i] = deleteCost<dataType>(baryTree, node);
1238 if(baryMatched[node][0] != std::numeric_limits<ftm::idNode>::max()
1239 and baryMatched[node][1] != std::numeric_limits<ftm::idNode>::max())
1240 cost = relabelCost<dataType>(
1241 trees[0], baryMatched[node][0], trees[1], baryMatched[node][1]);
1242 else if(baryMatched[node][0] == std::numeric_limits<ftm::idNode>::max())
1243 cost = deleteCost<dataType>(trees[1], baryMatched[node][1]);
1244 else if(baryMatched[node][1] == std::numeric_limits<ftm::idNode>::max())
1245 cost = deleteCost<dataType>(trees[0], baryMatched[node][0]);
1248 costs[0] = std::sqrt(costs[0]);
1249 costs[1] = std::sqrt(costs[1]);
1250 cost = std::sqrt(cost);
1251 if(std::abs((
double)(costs[0] - costs[1])) > 1e-7) {
1253 std::stringstream ss, ss2, ss3, ss4;
1254 ss <<
"cost T' T0 : " << costs[0];
1256 ss2 <<
"cost T' T1 : " << costs[1];
1258 ss3 <<
"cost T0 T1 : " << cost;
1260 ss4 <<
"cost T0 T' T1 : " << costs[0] + costs[1];
1262 if(std::abs((
double)((costs[0] + costs[1]) - cost)) > 1e-7) {
1263 std::stringstream ss5;
1265 << std::abs((
double)((costs[0] + costs[1]) - cost));
1268 std::stringstream ss6;
1269 ss6 <<
"diff2 : " << std::abs((
double)(costs[0] - costs[1]));
1273 for(
unsigned int i = 0; i < 2; ++i)
1274 if(baryMatched[node][i]
1275 != std::numeric_limits<ftm::idNode>::max()) {
1277 trees[i]->printNode2<dataType>(baryMatched[node][i]).str());
1279 ->printNode2<dataType>(
1280 trees[i]->getParentSafe(baryMatched[node][i]))
1284 std::vector<ftm::idNode> children;
1285 baryTree->getChildren(node, children);
1286 for(
auto child : children)
1287 queue.emplace(child);
#define ttkNotUsed(x)
Mark function/method parameters that are not used in the function body at all.
virtual int setThreadNumber(const int threadNumber)
Minimalist debugging class.
int printWrn(const std::string &msg, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cerr) const
void setDebugMsgPrefix(const std::string &prefix)
virtual int setDebugLevel(const int &debugLevel)
int printErr(const std::string &msg, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cerr) const
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)
double getAddDeletedNodesTime()
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 setIsCalled(bool ic)
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)
double barycenterSizeLimitPercent_
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_
double progressiveSpeedDivisor_
double getAllDistanceTime()
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_
bool progressiveBarycenter_
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)
double addDeletedNodesTime_
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)
void setNodePerTask(int npt)
bool normalizedWasserstein_
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_
void setKeepSubtree(bool keepSubtree)
double mixDistancesMinMaxPairWeight(bool isFirstInput)
bool branchDecomposition_
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)
void setIsCalled(bool ic)
const scalarType & getValue(SimplexId nodeId) const
bool isNodeIdInconsistent(idNode nodeId)
idNode getNumberOfNodes() const
void setParent(idNode nodeId, idNode newParentNodeId)
std::tuple< dataType, dataType > getBirthDeath(idNode nodeId)
idNode getMergedRootOrigin()
void getChildren(idNode nodeId, std::vector< idNode > &res)
void deleteNode(idNode nodeId)
idNode makeNode(SimplexId vertexId, SimplexId linked=nullVertex)
int getRealNumberOfNodes()
bool isNodeAlone(idNode nodeId)
void copyMergeTreeStructure(FTMTree_MT *tree)
Node * getNode(idNode nodeId)
void setOrigin(SimplexId linked)
SimplexId getOrigin() const
unsigned int idNode
Node index in vect_nodes_.
T end(std::pair< T, T > &p)
printMsg(debug::output::BOLD+" | | | | | . \\ | | (__| | / __/| |_| / __/|__ _|"+debug::output::ENDCOLOR, debug::Priority::PERFORMANCE, debug::LineMode::NEW, stream)