TTK
Loading...
Searching...
No Matches
MergeTreeDistance.h
Go to the documentation of this file.
1
14
15#pragma once
16
17#include <stack>
18#include <thread>
19
20// ttk common includes
21#include <Debug.h>
22
23#include "MergeTreeBase.h"
24#include <AssignmentAuction.h>
26#include <AssignmentMunkres.h>
27#include <AssignmentSolver.h>
28
29namespace ttk {
30
35 class MergeTreeDistance : virtual public Debug, public MergeTreeBase {
36
37 private:
38 double t_assignment_time_ = 0;
39
40 bool preprocess_ = true;
41 bool postprocess_ = true;
42 bool saveTree_ = false;
43 bool onlyEmptyTreeDistance_ = false;
44
45 bool isCalled_ = false;
46
47 double auctionEpsilon_ = -1;
48 double auctionEpsilonDiviser_ = 0;
49 int auctionRound_ = -1;
50
51 double minMaxPairWeight_ = 1.0;
52
53 // Just to get some stats about run
54 // std::map<int, int> assignmentProblemSize, assignmentProblemIter;
55
56 bool testing_ = true;
57
58 // Parallel version data
59 std::vector<std::vector<ftm::idNode>> tree2LevelToNode_;
60 std::vector<int> tree1Level_, tree2Level_;
61
62 public:
65 "MergeTreeDistance"); // inherited from Debug: prefix will be printed at
66 // the beginning of every msg
67#ifdef TTK_ENABLE_OPENMP4
68 omp_set_nested(1);
69#endif
70 }
71 ~MergeTreeDistance() override = default;
72
73 void setIsCalled(bool ic) {
74 isCalled_ = ic;
75 }
76
77 void setPreprocess(bool preproc) {
78 preprocess_ = preproc;
79 }
80
81 void setPostprocess(bool postproc) {
82 postprocess_ = postproc;
83 }
84
85 void setTesting(bool test) {
86 testing_ = test;
87 }
88
89 void setSaveTree(bool save) {
90 saveTree_ = save;
91 }
92
93 void setAuctionEpsilon(double aucEpsilon) {
94 auctionEpsilon_ = aucEpsilon;
95 }
96
97 void setAuctionEpsilonDiviser(double aucEpsilonDiviser) {
98 auctionEpsilonDiviser_ = aucEpsilonDiviser;
99 }
100
101 void setAuctionNoRounds(double aucNoRounds) {
102 auctionRound_ = aucNoRounds;
103 }
104
105 void setOnlyEmptyTreeDistance(double only) {
106 onlyEmptyTreeDistance_ = only;
107 }
108
109 void setMinMaxPairWeight(double weight) {
110 minMaxPairWeight_ = weight;
111 }
112
117 // ------------------------------------------------------------------------
118 // Assignment Problem
119 // ------------------------------------------------------------------------
120 template <class dataType>
121 void
122 runAssignmentProblemSolver(std::vector<std::vector<dataType>> &costMatrix,
123 std::vector<MatchingType> &matchings) {
124 AssignmentSolver<dataType> *assignmentSolver;
125 AssignmentExhaustive<dataType> solverExhaustive;
126 AssignmentMunkres<dataType> solverMunkres;
127 AssignmentAuction<dataType> solverAuction;
128
129 int const nRows = costMatrix.size() - 1;
130 int const nCols = costMatrix[0].size() - 1;
131 int const max_dim = std::max(nRows, nCols);
132 int const min_dim = std::min(nRows, nCols);
133
134 int assignmentSolverID = assignmentSolverID_;
135 if((min_dim <= 2 and max_dim <= 2) or (min_dim <= 1 and max_dim <= 6))
136 assignmentSolverID = 1;
137
138 switch(assignmentSolverID) {
139 case 1:
140 solverExhaustive = AssignmentExhaustive<dataType>();
141 assignmentSolver = &solverExhaustive;
142 break;
143 case 2:
144 solverMunkres = AssignmentMunkres<dataType>();
145 assignmentSolver = &solverMunkres;
146 break;
147 case 0:
148 default:
149 solverAuction = AssignmentAuction<dataType>();
150 solverAuction.setEpsilon(auctionEpsilon_);
151 solverAuction.setEpsilonDiviserMultiplier(auctionEpsilonDiviser_);
152 solverAuction.setNumberOfRounds(auctionRound_);
153 assignmentSolver = &solverAuction;
154 }
155 assignmentSolver->setInput(costMatrix);
156 assignmentSolver->setBalanced(false);
157 assignmentSolver->run(matchings);
158 }
159
160 template <class dataType>
161 void createCostMatrix(std::vector<std::vector<dataType>> &treeTable,
162 std::vector<ftm::idNode> &children1,
163 std::vector<ftm::idNode> &children2,
164 std::vector<std::vector<dataType>> &costMatrix) {
165 unsigned int nRows = children1.size(), nCols = children2.size();
166 for(unsigned int i = 0; i < nRows; ++i) {
167 int const forestTableI = children1[i] + 1;
168 for(unsigned int j = 0; j < nCols; ++j) {
169 int const forestTableJ = children2[j] + 1;
170 // Cost of assigning i and j
171 costMatrix[i][j] = treeTable[forestTableI][forestTableJ];
172 if(tree1Level_[children1[i]] != tree2Level_[children2[j]]
173 and not keepSubtree_)
174 printErr("different levels!"); // should be impossible
175 }
176 // Cost of not assigning i
177 costMatrix[i][nCols] = treeTable[forestTableI][0];
178 }
179 for(unsigned int j = 0; j < nCols; ++j) {
180 int const forestTableJ = children2[j] + 1;
181 // Cost of not assigning j
182 costMatrix[nRows][j] = treeTable[0][forestTableJ];
183 }
184 costMatrix[nRows][nCols] = 0;
185 }
186
187 template <class dataType>
189 std::vector<MatchingType> &matchings,
190 std::vector<ftm::idNode> &children1,
191 std::vector<ftm::idNode> &children2,
192 std::vector<std::tuple<int, int>> &forestAssignment) {
193 dataType cost = 0;
194 for(const auto &mTuple : matchings) {
195 cost += std::get<2>(mTuple);
196 if(std::get<0>(mTuple) >= (int)children1.size()
197 || std::get<1>(mTuple) >= (int)children2.size())
198 continue;
199 int const tableId1 = children1[std::get<0>(mTuple)] + 1;
200 int const tableId2 = children2[std::get<1>(mTuple)] + 1;
201 forestAssignment.emplace_back(tableId1, tableId2);
202 }
203 return cost;
204 }
205
206 template <class dataType>
210 std::vector<std::vector<dataType>> &treeTable,
211 std::vector<ftm::idNode> &children1,
212 std::vector<ftm::idNode> &children2,
213 std::vector<std::tuple<int, int>> &forestAssignment) {
214 // --- Create cost matrix
215 int nRows = children1.size(), nCols = children2.size();
216 std::vector<std::vector<dataType>> costMatrix(
217 nRows + 1, std::vector<dataType>(nCols + 1));
218 createCostMatrix(treeTable, children1, children2, costMatrix);
219
220 // assignmentProblemSize[costMatrix.size()*costMatrix[0].size()]++;
221
222 // --- Solve assignment problem
223 std::vector<MatchingType> matchings;
224 runAssignmentProblemSolver(costMatrix, matchings);
225
226 // --- Postprocess matching to create output assignment
227 dataType cost = postprocessAssignment<dataType>(
228 matchings, children1, children2, forestAssignment);
229
230 return cost;
231 }
232
233 template <class dataType>
235 ftm::FTMTree_MT *tree1,
236 ftm::FTMTree_MT *tree2,
237 int i,
238 int j,
239 std::vector<std::vector<dataType>> &treeTable,
240 std::vector<std::vector<dataType>> &forestTable,
241 std::vector<std::vector<std::vector<std::tuple<int, int>>>>
242 &forestBackTable,
243 std::vector<ftm::idNode> &children1,
244 std::vector<ftm::idNode> &children2) {
245 if(children1.size() != 0 && children2.size() != 0) {
246 dataType forestTerm3;
247
248 // Term 3
249 Timer t_assignment;
250 std::vector<std::tuple<int, int>> forestAssignment;
251 forestTerm3 = forestAssignmentProblem<dataType>(
252 tree1, tree2, treeTable, children1, children2, forestAssignment);
253 if(not parallelize_)
254 t_assignment_time_ += t_assignment.getElapsedTime();
255
256 if(not keepSubtree_) {
257 // Compute table value
258 forestTable[i][j] = forestTerm3;
259 // Add backtracking information
260 forestBackTable[i][j] = forestAssignment;
261 } else {
262 dataType forestTerm1, forestTerm2;
263 std::tuple<dataType, ftm::idNode> forestCoTerm1, forestCoTerm2;
264
265 // Term 1
266 forestCoTerm1
267 = computeTerm1_2<dataType>(children2, i, forestTable, true);
268 forestTerm1 = forestTable[0][j] + std::get<0>(forestCoTerm1);
269
270 // Term2
271 forestCoTerm2
272 = computeTerm1_2<dataType>(children1, j, forestTable, false);
273 forestTerm2 = forestTable[i][0] + std::get<0>(forestCoTerm2);
274
275 // Compute table value
276 forestTable[i][j]
277 = std::min(std::min(forestTerm1, forestTerm2), forestTerm3);
278
279 // Add backtracking information
280 if(forestTable[i][j] == forestTerm3) {
281 forestBackTable[i][j] = forestAssignment;
282 } else if(forestTable[i][j] == forestTerm2) {
283 forestBackTable[i][j].push_back(
284 std::make_tuple(std::get<1>(forestCoTerm2), j));
285 } else {
286 forestBackTable[i][j].push_back(
287 std::make_tuple(i, std::get<1>(forestCoTerm1)));
288 }
289 }
290 } else {
291 // If one of the forest is empty we get back to equation 8 or 10
292 forestTable[i][j]
293 = (children1.size() == 0) ? forestTable[0][j] : forestTable[i][0];
294 }
295 }
296
297 // ------------------------------------------------------------------------
298 // Edit Distance Dynamic Programming Equations
299 // ------------------------------------------------------------------------
300 template <class dataType>
302 ftm::FTMTree_MT *tree1,
303 ftm::idNode nodeI,
304 int i,
305 std::vector<std::vector<dataType>> &treeTable,
306 std::vector<std::vector<dataType>> &forestTable) {
307 std::vector<ftm::idNode> children;
308 tree1->getChildren(nodeI, children);
309 forestTable[i][0] = 0;
310 for(ftm::idNode const child : children)
311 forestTable[i][0] += treeTable[child + 1][0];
312 }
313
314 template <class dataType>
316 ftm::FTMTree_MT *tree1,
317 ftm::idNode nodeI,
318 int i,
319 std::vector<std::vector<dataType>> &treeTable,
320 std::vector<std::vector<dataType>> &forestTable) {
321 treeTable[i][0] = forestTable[i][0] + deleteCost<dataType>(tree1, nodeI);
322 }
323
324 template <class dataType>
326 ftm::FTMTree_MT *tree2,
327 ftm::idNode nodeJ,
328 int j,
329 std::vector<std::vector<dataType>> &treeTable,
330 std::vector<std::vector<dataType>> &forestTable) {
331 std::vector<ftm::idNode> children;
332 tree2->getChildren(nodeJ, children);
333 forestTable[0][j] = 0;
334 for(ftm::idNode const child : children)
335 forestTable[0][j] += treeTable[0][child + 1];
336 }
337
338 template <class dataType>
340 ftm::FTMTree_MT *tree2,
341 ftm::idNode nodeJ,
342 int j,
343 std::vector<std::vector<dataType>> &treeTable,
344 std::vector<std::vector<dataType>> &forestTable) {
345 treeTable[0][j] = forestTable[0][j] + insertCost<dataType>(tree2, nodeJ);
346 }
347
348 // Compute first or second term of forests and subtrees distance
349 template <class dataType>
350 std::tuple<dataType, ftm::idNode>
351 computeTerm1_2(std::vector<ftm::idNode> &childrens,
352 int ind,
353 std::vector<std::vector<dataType>> &table,
354 bool computeTerm1) {
355 dataType tempMin = (childrens.size() == 0)
356 ? ((computeTerm1) ? table[ind][0] : table[0][ind])
357 : std::numeric_limits<dataType>::max();
358 ftm::idNode bestIdNode = 0;
359 for(ftm::idNode children : childrens) {
360 children += 1;
361 dataType temp;
362 if(computeTerm1) {
363 temp = table[ind][children] - table[0][children];
364 } else {
365 temp = table[children][ind] - table[children][0];
366 }
367 if(temp < tempMin) {
368 tempMin = temp;
369 bestIdNode = children;
370 }
371 }
372 return std::make_tuple(tempMin, bestIdNode);
373 }
374
375 template <class dataType>
377 ftm::FTMTree_MT *tree1,
378 ftm::FTMTree_MT *tree2,
379 int i,
380 int j,
381 ftm::idNode nodeI,
382 ftm::idNode nodeJ,
383 std::vector<std::vector<dataType>> &treeTable,
384 std::vector<std::vector<dataType>> &forestTable,
385 std::vector<std::vector<std::tuple<int, int>>> &treeBackTable,
386 std::vector<ftm::idNode> &children1,
387 std::vector<ftm::idNode> &children2) {
388 dataType treeTerm3;
389
390 // Term 3
391 treeTerm3
392 = forestTable[i][j] + relabelCost<dataType>(tree1, nodeI, tree2, nodeJ);
393
394 if(not keepSubtree_) {
395 // Compute table value
396 treeTable[i][j] = treeTerm3;
397 // Add backtracking information
398 treeBackTable[i][j] = std::make_tuple(i, j);
399 } else {
400 dataType treeTerm1, treeTerm2;
401 std::tuple<dataType, ftm::idNode> treeCoTerm1, treeCoTerm2;
402
403 // Term 1
404 treeCoTerm1 = computeTerm1_2<dataType>(children2, i, treeTable, true);
405 treeTerm1 = treeTable[0][j] + std::get<0>(treeCoTerm1);
406
407 // Term 2
408 treeCoTerm2 = computeTerm1_2<dataType>(children1, j, treeTable, false);
409 treeTerm2 = treeTable[i][0] + std::get<0>(treeCoTerm2);
410
411 // Compute table value
412 treeTable[i][j] = std::min(std::min(treeTerm1, treeTerm2), treeTerm3);
413
414 // Add backtracking information
415 if(treeTable[i][j] == treeTerm3) {
416 treeBackTable[i][j] = std::make_tuple(i, j);
417 } else if(treeTable[i][j] == treeTerm2) {
418 treeBackTable[i][j] = std::make_tuple(std::get<1>(treeCoTerm2), j);
419 } else {
420 treeBackTable[i][j] = std::make_tuple(i, std::get<1>(treeCoTerm1));
421 }
422 }
423 }
424
425 // --------------------------------------------------------------------------------
426 // Output Matching
427 // --------------------------------------------------------------------------------
428 template <class dataType>
430 ftm::FTMTree_MT *tree1,
431 ftm::FTMTree_MT *tree2,
432 std::vector<std::vector<std::tuple<int, int>>> &treeBackTable,
433 std::vector<std::vector<std::vector<std::tuple<int, int>>>>
434 &forestBackTable,
435 std::vector<std::tuple<ftm::idNode, ftm::idNode, double>> &outputMatching,
436 int startR,
437 int startC) {
438 outputMatching.clear();
439 std::queue<std::tuple<int, int, bool>> backQueue;
440 backQueue.emplace(startR, startC, true);
441 while(!backQueue.empty()) {
442 std::tuple<int, int, bool> elem = backQueue.front();
443 backQueue.pop();
444 bool useTreeTable = std::get<2>(elem);
445 int const i = std::get<0>(elem);
446 int const j = std::get<1>(elem);
447
448 if(useTreeTable) {
449 int const tupleI = std::get<0>(treeBackTable[i][j]);
450 int const tupleJ = std::get<1>(treeBackTable[i][j]);
451 if(tupleI != 0 && tupleJ != 0) {
452 useTreeTable = (tupleI != i || tupleJ != j);
453 backQueue.emplace(tupleI, tupleJ, useTreeTable);
454 if(not useTreeTable) { // We have matched i and j
455 ftm::idNode const tree1Node = tupleI - 1;
456 ftm::idNode const tree2Node = tupleJ - 1;
457 double cost = 0;
458 dataType costT
459 = relabelCost<dataType>(tree1, tree1Node, tree2, tree2Node);
460 cost = static_cast<double>(costT);
461 outputMatching.emplace_back(tree1Node, tree2Node, cost);
462 }
463 }
464 } else {
465 for(std::tuple<int, int> forestBackElem : forestBackTable[i][j]) {
466 int const tupleI = std::get<0>(forestBackElem);
467 int const tupleJ = std::get<1>(forestBackElem);
468 if(tupleI != 0 && tupleJ != 0) {
469 useTreeTable = (tupleI != i && tupleJ != j);
470 backQueue.emplace(tupleI, tupleJ, useTreeTable);
471 }
472 }
473 }
474 }
475 }
476
477 // ------------------------------------------------------------------------
478 // Main Functions
479 // ------------------------------------------------------------------------
480 template <class dataType>
481 dataType
483 ftm::FTMTree_MT *tree2,
484 std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>
485 &outputMatching) {
486 // ---------------------
487 // ----- Init dynamic programming tables
488 // --------------------
489 size_t const nRows = tree1->getNumberOfNodes() + 1;
490 size_t const nCols = tree2->getNumberOfNodes() + 1;
491 std::vector<std::vector<dataType>> treeTable(
492 nRows, std::vector<dataType>(nCols));
493 std::vector<std::vector<dataType>> forestTable(
494 nRows, std::vector<dataType>(nCols));
495
496 // Backtracking tables (output matching)
497 std::vector<std::vector<std::tuple<int, int>>> treeBackTable(
498 nRows, std::vector<std::tuple<int, int>>(nCols));
499 std::vector<std::vector<std::vector<std::tuple<int, int>>>>
500 forestBackTable(
501 nRows, std::vector<std::vector<std::tuple<int, int>>>(nCols));
502
503 int const indR = tree1->getRoot() + 1;
504 int const indC = tree2->getRoot() + 1;
505
506 tree1->getAllNodeLevel(tree1Level_);
507 tree2->getAllNodeLevel(tree2Level_);
508 tree2->getLevelToNode(tree2LevelToNode_);
509
510 // ---------------------
511 // ----- Compute edit distance
512 // --------------------
513 computeEditDistance(tree1, tree2, treeTable, forestTable, treeBackTable,
514 forestBackTable, nRows, nCols);
515 dataType distance = treeTable[indR][indC];
516 if(onlyEmptyTreeDistance_)
517 distance = treeTable[indR][0];
519 if(not useMinMaxPair_) {
520 if(onlyEmptyTreeDistance_)
521 distance -= deleteCost<dataType>(tree1, tree1->getRoot());
522 else
523 distance -= relabelCost<dataType>(
524 tree1, tree1->getRoot(), tree2, tree2->getRoot());
525 } else {
526 if(minMaxPairWeight_ != 1.0) {
527 auto cost = relabelCost<dataType>(
528 tree1, tree1->getRoot(), tree2, tree2->getRoot());
529 distance = distance - cost + minMaxPairWeight_ * cost;
530 }
531 }
532 }
534 distance = std::sqrt(distance);
535
536 // ---------------------
537 // ----- Compute matching
538 // --------------------
539 computeMatching<dataType>(tree1, tree2, treeBackTable, forestBackTable,
540 outputMatching, indR, indC);
541
542 return distance;
543 }
544
545 template <class dataType>
547 ftm::FTMTree_MT *tree1,
548 ftm::FTMTree_MT *tree2,
549 std::vector<std::tuple<ftm::idNode, ftm::idNode>> &outputMatching) {
550 std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>
551 realOutputMatching;
552 dataType res
553 = computeDistance<dataType>(tree1, tree2, realOutputMatching);
554 for(auto tup : realOutputMatching)
555 outputMatching.emplace_back(std::get<0>(tup), std::get<1>(tup));
556 return res;
557 }
558
559 template <class dataType>
562 std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>
563 &outputMatching) {
564 Memory m;
565 Timer t_total;
566
567 // ---------------------
568 // ----- Testing
569 // --------------------
570 testing_ = false;
571
572 // ---------------------
573 // ----- Preprocessing
574 // --------------------
575 ftm::MergeTree<dataType> mTree1Copy;
576 ftm::MergeTree<dataType> mTree2Copy;
577 if(saveTree_) {
578 mTree1Copy = ftm::copyMergeTree<dataType>(mTree1);
579 mTree2Copy = ftm::copyMergeTree<dataType>(mTree2);
580 }
581 ftm::MergeTree<dataType> &mTree1Int = (saveTree_ ? mTree1Copy : mTree1);
582 ftm::MergeTree<dataType> &mTree2Int = (saveTree_ ? mTree2Copy : mTree2);
583 ftm::FTMTree_MT *tree1 = &(mTree1Int.tree);
584 ftm::FTMTree_MT *tree2 = &(mTree2Int.tree);
585 if(not isCalled_ and not isPersistenceDiagram_) {
586 verifyMergeTreeStructure<dataType>(tree1);
587 verifyMergeTreeStructure<dataType>(tree2);
588 }
589 if(preprocess_) {
590 treesNodeCorr_.resize(2);
591 preprocessingPipeline<dataType>(
594 preprocessingPipeline<dataType>(
597 }
598 tree1 = &(mTree1Int.tree);
599 tree2 = &(mTree2Int.tree);
600
601 // ---------------------
602 // ----- Compute Distance
603 // --------------------
604 dataType distance
605 = computeDistance<dataType>(tree1, tree2, outputMatching);
606
607 // ---------------------
608 // ----- Postprocessing
609 // --------------------
610 if(postprocess_) {
611 postprocessingPipeline<dataType>(tree1);
612 postprocessingPipeline<dataType>(tree2);
614 convertBranchDecompositionMatching<dataType>(
615 tree1, tree2, outputMatching);
616 }
617
618 // std::cout << "TIME COMP.MATCH. = " << t_match_time << std::endl;
619 printMsg("Total", 1, t_total.getElapsedTime(), this->threadNumber_,
622 std::stringstream ss2;
623 ss2 << "DISTANCE² = "
624 << (distanceSquaredRoot_ ? distance * distance : distance);
625 printMsg(ss2.str());
626 std::stringstream ss3;
627 ss3 << "DISTANCE = "
628 << (distanceSquaredRoot_ ? distance : std::sqrt(distance));
629 printMsg(ss3.str());
631 std::stringstream ss4;
632 ss4 << "MEMORY = " << m.getElapsedUsage();
633 printMsg(ss4.str());
635
636 return distance;
637 }
638
639 template <class dataType>
640 dataType execute(
643 std::vector<std::tuple<ftm::idNode, ftm::idNode>> &outputMatching) {
644 std::vector<std::tuple<ftm::idNode, ftm::idNode, double>>
645 realOutputMatching;
646 dataType res = execute<dataType>(tree1, tree2, realOutputMatching);
647 for(auto tup : realOutputMatching)
648 outputMatching.emplace_back(std::get<0>(tup), std::get<1>(tup));
649 return res;
650 }
651
652 template <class dataType>
654 ftm::FTMTree_MT *tree1,
655 ftm::FTMTree_MT *tree2,
656 std::vector<std::vector<dataType>> &treeTable,
657 std::vector<std::vector<dataType>> &forestTable,
658 std::vector<std::vector<std::tuple<int, int>>> &treeBackTable,
659 std::vector<std::vector<std::vector<std::tuple<int, int>>>>
660 &forestBackTable,
661 int nRows,
662 int nCols) {
663 Timer t_dyn;
664 t_assignment_time_ = 0;
665
666 if(parallelize_) {
667 parallelEditDistance(tree1, tree2, treeTable, forestTable,
668 treeBackTable, forestBackTable, nRows, nCols);
669 } else {
670 // Distance T1 to empty tree
671 classicEditDistance(tree1, tree2, true, true, tree1->getRoot(),
672 tree2->getRoot(), treeTable, forestTable,
673 treeBackTable, forestBackTable, nRows, nCols);
674 if(onlyEmptyTreeDistance_)
675 return;
676 // Distance T2 to empty tree
677 classicEditDistance(tree1, tree2, false, true, tree1->getRoot(),
678 tree2->getRoot(), treeTable, forestTable,
679 treeBackTable, forestBackTable, nRows, nCols);
680 // Distance T1 to T2
681 classicEditDistance(tree1, tree2, true, false, tree1->getRoot(),
682 tree2->getRoot(), treeTable, forestTable,
683 treeBackTable, forestBackTable, nRows, nCols);
684 }
685
686 printMsg("Dynamic programing", 1, t_dyn.getElapsedTime(),
687 this->threadNumber_, debug::LineMode::NEW,
689 if(not parallelize_)
690 printMsg("Assignment problems", 1, t_assignment_time_,
693 }
694
695 template <class dataType>
697 ftm::FTMTree_MT *tree1,
698 ftm::FTMTree_MT *tree2,
699 bool processTree1,
700 bool computeEmptyTree,
701 ftm::idNode nodeI,
702 ftm::idNode nodeJ,
703 std::vector<std::vector<dataType>> &treeTable,
704 std::vector<std::vector<dataType>> &forestTable,
705 std::vector<std::vector<std::tuple<int, int>>> &treeBackTable,
706 std::vector<std::vector<std::vector<std::tuple<int, int>>>>
707 &forestBackTable,
708 int nRows,
709 int nCols) {
710 if(processTree1) {
711 std::vector<ftm::idNode> childrens;
712 tree1->getChildren(nodeI, childrens);
713 for(auto children : childrens)
714 classicEditDistance(tree1, tree2, processTree1, computeEmptyTree,
715 children, nodeJ, treeTable, forestTable,
716 treeBackTable, forestBackTable, nRows, nCols);
717 } else {
718 std::vector<ftm::idNode> childrens;
719 tree2->getChildren(nodeJ, childrens);
720 for(auto children : childrens)
721 classicEditDistance(tree1, tree2, processTree1, computeEmptyTree,
722 nodeI, children, treeTable, forestTable,
723 treeBackTable, forestBackTable, nRows, nCols);
724 }
725
726 if(processTree1) {
727 if(computeEmptyTree) {
728 int const i = nodeI + 1;
729 // --- Forest to empty tree distance
730 computeForestToEmptyDistance(tree1, nodeI, i, treeTable, forestTable);
731
732 // --- Subtree to empty tree distance
734 tree1, nodeI, i, treeTable, forestTable);
735 } else
736 classicEditDistance(tree1, tree2, false, false, nodeI,
737 tree2->getRoot(), treeTable, forestTable,
738 treeBackTable, forestBackTable, nRows, nCols);
739 } else {
740 int const j = nodeJ + 1;
741 if(computeEmptyTree) {
742 // --- Empty tree to forest distance
743 computeEmptyToForestDistance(tree2, nodeJ, j, treeTable, forestTable);
744
745 // --- Empty tree to subtree distance
747 tree2, nodeJ, j, treeTable, forestTable);
748 //}else{
749 } else if(keepSubtree_ or tree1Level_[nodeI] == tree2Level_[nodeJ]) {
750 int const i = nodeI + 1;
751 std::vector<ftm::idNode> children1;
752 tree1->getChildren(nodeI, children1);
753 std::vector<ftm::idNode> children2;
754 tree2->getChildren(nodeJ, children2);
755 // --- Forests distance
756 computeForestsDistance(tree1, tree2, i, j, treeTable, forestTable,
757 forestBackTable, children1, children2);
758
759 // --- Subtrees distance
760 computeSubtreesDistance(tree1, tree2, i, j, nodeI, nodeJ, treeTable,
761 forestTable, treeBackTable, children1,
762 children2);
763 }
764 }
765 }
766
767 // ------------------------------------------------------------------------
768 // Parallel version
769 // ------------------------------------------------------------------------
770 template <class dataType>
772 ftm::FTMTree_MT *tree1,
773 ftm::FTMTree_MT *tree2,
774 std::vector<std::vector<dataType>> &treeTable,
775 std::vector<std::vector<dataType>> &forestTable,
776 std::vector<std::vector<std::tuple<int, int>>> &treeBackTable,
777 std::vector<std::vector<std::vector<std::tuple<int, int>>>>
778 &forestBackTable,
779 int ttkNotUsed(nRows),
780 int ttkNotUsed(nCols)) {
781 std::vector<int> tree1NodeChildSize, tree2NodeChildSize;
782 for(unsigned int i = 0; i < tree1->getNumberOfNodes(); ++i) {
783 std::vector<ftm::idNode> children;
784 tree1->getChildren(i, children);
785 tree1NodeChildSize.push_back(children.size());
786 }
787 for(unsigned int j = 0; j < tree2->getNumberOfNodes(); ++j) {
788 std::vector<ftm::idNode> children;
789 tree2->getChildren(j, children);
790 tree2NodeChildSize.push_back(children.size());
791 }
792
793 // Get trees data
794 std::vector<ftm::idNode> tree1Leaves;
795 tree1->getLeavesFromTree(tree1Leaves);
796 std::vector<ftm::idNode> tree2Leaves;
797 tree2->getLeavesFromTree(tree2Leaves);
798
799 // Distance T1 to empty tree
800 parallelEmptyTreeDistance_v2(tree1, true, tree1Leaves, tree1NodeChildSize,
801 treeTable, forestTable, treeBackTable,
802 forestBackTable);
803 if(onlyEmptyTreeDistance_)
804 return;
805 // Distance T2 to empty tree
806 parallelEmptyTreeDistance_v2(tree2, false, tree2Leaves,
807 tree2NodeChildSize, treeTable, forestTable,
808 treeBackTable, forestBackTable);
809 // Distance T1 to T2
810 parallelTreeDistance_v2(tree1, tree2, true, 0, tree1Leaves,
811 tree1NodeChildSize, tree2Leaves,
812 tree2NodeChildSize, treeTable, forestTable,
813 treeBackTable, forestBackTable, true);
814 }
815
816 // Forests and subtrees distances
817 template <class dataType>
819 ftm::FTMTree_MT *tree1,
820 ftm::FTMTree_MT *tree2,
821 bool isTree1,
822 int i,
823 std::vector<ftm::idNode> &tree1Leaves,
824 std::vector<int> &tree1NodeChildSize,
825 std::vector<ftm::idNode> &tree2Leaves,
826 std::vector<int> &tree2NodeChildSize,
827 std::vector<std::vector<dataType>> &treeTable,
828 std::vector<std::vector<dataType>> &forestTable,
829 std::vector<std::vector<std::tuple<int, int>>> &treeBackTable,
830 std::vector<std::vector<std::vector<std::tuple<int, int>>>>
831 &forestBackTable,
832 bool firstCall = false) {
833 ftm::idNode const nodeT = -1;
834 ftm::FTMTree_MT *treeT = (isTree1) ? tree1 : tree2;
835 std::vector<int> treeChildDone(treeT->getNumberOfNodes(), 0);
836 std::vector<bool> treeNodeDone(treeT->getNumberOfNodes(), false);
837 std::queue<ftm::idNode> treeQueue;
838
839 if(isTree1)
840 for(ftm::idNode const leaf : tree1Leaves)
841 treeQueue.emplace(leaf);
842 else if(keepSubtree_)
843 for(ftm::idNode const leaf : tree2Leaves)
844 treeQueue.emplace(leaf);
845 else if(tree1Level_[i - 1] < (int)tree2LevelToNode_.size())
846 for(ftm::idNode const node : tree2LevelToNode_[tree1Level_[i - 1]])
847 treeQueue.emplace(node);
848
849 if(not isCalled_) // and firstCall)
850 parallelTreeDistancePara(tree1, tree2, isTree1, i, tree1Leaves,
851 tree1NodeChildSize, tree2Leaves,
852 tree2NodeChildSize, treeTable, forestTable,
853 treeBackTable, forestBackTable, firstCall,
854 nodeT, treeChildDone, treeNodeDone, treeQueue);
855 else
856 parallelTreeDistanceTask(tree1, tree2, isTree1, i, tree1Leaves,
857 tree1NodeChildSize, tree2Leaves,
858 tree2NodeChildSize, treeTable, forestTable,
859 treeBackTable, forestBackTable, nodeT,
860 treeChildDone, treeNodeDone, treeQueue);
861 }
862
863 // (isCalled_=false)
864 template <class dataType>
866 ftm::FTMTree_MT *tree1,
867 ftm::FTMTree_MT *tree2,
868 bool isTree1,
869 int i,
870 std::vector<ftm::idNode> &tree1Leaves,
871 std::vector<int> &tree1NodeChildSize,
872 std::vector<ftm::idNode> &tree2Leaves,
873 std::vector<int> &tree2NodeChildSize,
874 std::vector<std::vector<dataType>> &treeTable,
875 std::vector<std::vector<dataType>> &forestTable,
876 std::vector<std::vector<std::tuple<int, int>>> &treeBackTable,
877 std::vector<std::vector<std::vector<std::tuple<int, int>>>>
878 &forestBackTable,
879 bool firstCall,
880 ftm::idNode nodeT,
881 std::vector<int> &treeChildDone,
882 std::vector<bool> &treeNodeDone,
883 std::queue<ftm::idNode> &treeQueue) {
884#ifdef TTK_ENABLE_OPENMP4
885#pragma omp parallel num_threads(this->threadNumber_) if(firstCall)
886 {
887#pragma omp single nowait
888#endif
889 parallelTreeDistanceTask(tree1, tree2, isTree1, i, tree1Leaves,
890 tree1NodeChildSize, tree2Leaves,
891 tree2NodeChildSize, treeTable, forestTable,
892 treeBackTable, forestBackTable, nodeT,
893 treeChildDone, treeNodeDone, treeQueue);
894#ifdef TTK_ENABLE_OPENMP4
895 } // pragma omp parallel
896#endif
897
898 TTK_FORCE_USE(firstCall);
899 }
900
901 template <class dataType>
903 ftm::FTMTree_MT *tree1,
904 ftm::FTMTree_MT *tree2,
905 bool isTree1,
906 int i,
907 std::vector<ftm::idNode> &tree1Leaves,
908 std::vector<int> &tree1NodeChildSize,
909 std::vector<ftm::idNode> &tree2Leaves,
910 std::vector<int> &tree2NodeChildSize,
911 std::vector<std::vector<dataType>> &treeTable,
912 std::vector<std::vector<dataType>> &forestTable,
913 std::vector<std::vector<std::tuple<int, int>>> &treeBackTable,
914 std::vector<std::vector<std::vector<std::tuple<int, int>>>>
915 &forestBackTable,
916 ftm::idNode nodeT,
917 std::vector<int> &treeChildDone,
918 std::vector<bool> &treeNodeDone,
919 std::queue<ftm::idNode> &treeQueue) {
920 int nodePerTask = nodePerTask_;
921 while(!treeQueue.empty()) {
922 std::queue<ftm::idNode> taskQueue;
923 nodePerTask = nodePerTask > (int)treeQueue.size() ? treeQueue.size()
924 : nodePerTask;
925 for(int j = 0; j < nodePerTask; ++j) {
926 nodeT = treeQueue.front();
927 treeQueue.pop();
928 taskQueue.emplace(nodeT);
929 }
930#ifdef TTK_ENABLE_OPENMP4
931#pragma omp task firstprivate(taskQueue, nodeT) UNTIED() \
932 shared(treeTable, forestTable, treeBackTable, forestBackTable, \
933 treeChildDone, treeNodeDone) if(isTree1)
934 {
935#endif
936 ftm::FTMTree_MT *treeT = (isTree1) ? tree1 : tree2;
937 // while(nodeT != -1){
938 while(!taskQueue.empty()) {
939 nodeT = taskQueue.front();
940 taskQueue.pop();
941 int const t = nodeT + 1;
942 ftm::idNode const nodeI = i - 1;
943
944 if(isTree1) {
946 tree1, tree2, false, t, tree1Leaves, tree1NodeChildSize,
947 tree2Leaves, tree2NodeChildSize, treeTable, forestTable,
948 treeBackTable, forestBackTable, false);
949 //}else{
950 } else if(keepSubtree_
951 or tree1Level_[nodeI] == tree2Level_[nodeT]) {
952 int const j = nodeT + 1;
953 std::vector<ftm::idNode> children1;
954 tree1->getChildren(nodeI, children1);
955 std::vector<ftm::idNode> children2;
956 tree2->getChildren(nodeT, children2);
957 // --- Forests distance
958 computeForestsDistance(tree1, tree2, i, j, treeTable, forestTable,
959 forestBackTable, children1, children2);
960
961 // --- Subtrees distance
962 computeSubtreesDistance(tree1, tree2, i, j, nodeI, nodeT,
963 treeTable, forestTable, treeBackTable,
964 children1, children2);
965 }
966
967 if(not isTree1 and not keepSubtree_
968 and tree1Level_[nodeI] == tree2Level_[nodeT])
969 continue;
970
971 // Manage parent
972 ftm::idNode const nodeTParent = treeT->getParentSafe(nodeT);
973 int const childSize = (isTree1) ? tree1NodeChildSize[nodeTParent]
974 : tree2NodeChildSize[nodeTParent];
975 int oldTreeChildDone;
976#ifdef TTK_ENABLE_OPENMP4
977#pragma omp atomic capture
978 {
979#endif
980 oldTreeChildDone = treeChildDone[nodeTParent];
981 treeChildDone[nodeTParent]++;
982#ifdef TTK_ENABLE_OPENMP4
983 } // pragma omp atomic capture
984#endif
985 if(not treeNodeDone[nodeTParent]
986 and oldTreeChildDone + 1 == childSize) {
987 // nodeT = nodeTParent;
988 taskQueue.emplace(nodeTParent);
989 treeNodeDone[nodeTParent] = true;
990#ifdef TTK_ENABLE_OPENMP4
991#pragma omp taskyield
992#endif
993 } else
994 nodeT = -1;
995
996 } // while nodeI loop
997#ifdef TTK_ENABLE_OPENMP4
998 } // pragma omp task
999#endif
1000 } // while treeQueue loop
1001#ifdef TTK_ENABLE_OPENMP4
1002#pragma omp taskwait
1003#endif
1004 }
1005
1006 // Subtree/Forest with empty tree distances
1007 template <class dataType>
1009 ftm::FTMTree_MT *tree,
1010 bool isTree1,
1011 std::vector<ftm::idNode> &treeLeaves,
1012 std::vector<int> &treeNodeChildSize,
1013 std::vector<std::vector<dataType>> &treeTable,
1014 std::vector<std::vector<dataType>> &forestTable,
1015 std::vector<std::vector<std::tuple<int, int>>> &treeBackTable,
1016 std::vector<std::vector<std::vector<std::tuple<int, int>>>>
1017 &forestBackTable) {
1018 ftm::idNode const nodeT = -1;
1019 std::vector<int> treeChildDone(tree->getNumberOfNodes(), 0);
1020 std::vector<bool> treeNodeDone(tree->getNumberOfNodes(), false);
1021 std::queue<ftm::idNode> treeQueue;
1022 for(ftm::idNode const leaf : treeLeaves)
1023 treeQueue.emplace(leaf);
1024 if(not isCalled_)
1025 parallelEmptyTreeDistancePara(tree, isTree1, treeLeaves,
1026 treeNodeChildSize, treeTable, forestTable,
1027 treeBackTable, forestBackTable, nodeT,
1028 treeChildDone, treeNodeDone, treeQueue);
1029 else
1030 parallelEmptyTreeDistanceTask(tree, isTree1, treeLeaves,
1031 treeNodeChildSize, treeTable, forestTable,
1032 treeBackTable, forestBackTable, nodeT,
1033 treeChildDone, treeNodeDone, treeQueue);
1034 }
1035
1036 template <class dataType>
1038 ftm::FTMTree_MT *tree,
1039 bool isTree1,
1040 std::vector<ftm::idNode> &treeLeaves,
1041 std::vector<int> &treeNodeChildSize,
1042 std::vector<std::vector<dataType>> &treeTable,
1043 std::vector<std::vector<dataType>> &forestTable,
1044 std::vector<std::vector<std::tuple<int, int>>> &treeBackTable,
1045 std::vector<std::vector<std::vector<std::tuple<int, int>>>>
1046 &forestBackTable,
1047 ftm::idNode nodeT,
1048 std::vector<int> &treeChildDone,
1049 std::vector<bool> &treeNodeDone,
1050 std::queue<ftm::idNode> &treeQueue) {
1051#ifdef TTK_ENABLE_OPENMP4
1052#pragma omp parallel num_threads(this->threadNumber_)
1053 {
1054#pragma omp single nowait
1055#endif
1056 parallelEmptyTreeDistanceTask(tree, isTree1, treeLeaves,
1057 treeNodeChildSize, treeTable, forestTable,
1058 treeBackTable, forestBackTable, nodeT,
1059 treeChildDone, treeNodeDone, treeQueue);
1060#ifdef TTK_ENABLE_OPENMP4
1061 } // pragma omp parallel
1062#endif
1063 }
1064
1065 template <class dataType>
1067 ftm::FTMTree_MT *tree,
1068 bool isTree1,
1069 std::vector<ftm::idNode> &ttkNotUsed(treeLeaves),
1070 std::vector<int> &treeNodeChildSize,
1071 std::vector<std::vector<dataType>> &treeTable,
1072 std::vector<std::vector<dataType>> &forestTable,
1073 std::vector<std::vector<std::tuple<int, int>>> &treeBackTable,
1074 std::vector<std::vector<std::vector<std::tuple<int, int>>>>
1075 &forestBackTable,
1076 ftm::idNode nodeT,
1077 std::vector<int> &treeChildDone,
1078 std::vector<bool> &treeNodeDone,
1079 std::queue<ftm::idNode> &treeQueue) {
1080 while(!treeQueue.empty()) {
1081 nodeT = treeQueue.front();
1082 treeQueue.pop();
1083
1084#ifdef TTK_ENABLE_OPENMP4
1085#pragma omp task firstprivate(nodeT) UNTIED() \
1086 shared(treeTable, forestTable, treeBackTable, forestBackTable, \
1087 treeChildDone, treeNodeDone)
1088 {
1089#endif
1090 while((int)nodeT != -1) {
1091 if(isTree1) {
1092 int const i = nodeT + 1;
1093 // --- Forest to empty tree distance
1095 tree, nodeT, i, treeTable, forestTable);
1096
1097 // --- Subtree to empty tree distance
1099 tree, nodeT, i, treeTable, forestTable);
1100 } else {
1101 int const j = nodeT + 1;
1102 // --- Empty tree to forest distance
1104 tree, nodeT, j, treeTable, forestTable);
1105
1106 // --- Empty tree to subtree distance
1108 tree, nodeT, j, treeTable, forestTable);
1109 }
1110
1111 // Manage parent
1112 ftm::idNode const nodeTParent = tree->getParentSafe(nodeT);
1113 int oldTreeChildDone;
1114#ifdef TTK_ENABLE_OPENMP4
1115#pragma omp atomic capture
1116 {
1117#endif
1118 oldTreeChildDone = treeChildDone[nodeTParent];
1119 treeChildDone[nodeTParent]++;
1120#ifdef TTK_ENABLE_OPENMP4
1121 } // pragma omp atomic capture
1122#endif
1123 if(not treeNodeDone[nodeTParent]
1124 and oldTreeChildDone + 1 == treeNodeChildSize[nodeTParent]) {
1125 nodeT = nodeTParent;
1126 treeNodeDone[nodeTParent] = true;
1127#ifdef TTK_ENABLE_OPENMP4
1128#pragma omp taskyield
1129#endif
1130 } else
1131 nodeT = -1;
1132
1133 } // while nodeI loop
1134#ifdef TTK_ENABLE_OPENMP4
1135 } // pragma omp task
1136#endif
1137 } // while treeQueue loop
1138#ifdef TTK_ENABLE_OPENMP4
1139#pragma omp taskwait
1140#endif
1141
1142 TTK_FORCE_USE(treeBackTable);
1143 TTK_FORCE_USE(forestBackTable);
1144 }
1145
1146 // ------------------------------------------------------------------------
1147 // Utils
1148 // ------------------------------------------------------------------------
1149 void printMapIntInt(std::map<int, int> theMap) {
1150 for(auto itr = theMap.begin(); itr != theMap.end(); ++itr) {
1151 std::stringstream ss;
1152 ss << '\t' << itr->first << '\t' << itr->second;
1153 printMsg(ss.str());
1154 }
1155 printMsg("");
1156 }
1157
1158 template <class dataType>
1160 bool problem = false;
1161
1162 bool const isJT = tree->isJoinTree<dataType>();
1163 std::vector<std::tuple<ftm::idNode, ftm::idNode>> problemNodes;
1164 std::queue<ftm::idNode> queue;
1165 queue.emplace(tree->getRoot());
1166 while(!queue.empty()) {
1167 ftm::idNode const node = queue.front();
1168 queue.pop();
1169
1170 if(!tree->isRoot(node)) {
1171 bool thisProblem;
1172 if(isJT)
1173 thisProblem = tree->getValue<dataType>(node)
1174 > tree->getValue<dataType>(tree->getParentSafe(node));
1175 else
1176 thisProblem = tree->getValue<dataType>(node)
1177 < tree->getValue<dataType>(tree->getParentSafe(node));
1178
1179 if(thisProblem)
1180 problemNodes.emplace_back(node, tree->getParentSafe(node));
1181
1182 problem |= thisProblem;
1183 }
1184
1185 std::vector<ftm::idNode> children;
1186 tree->getChildren(node, children);
1187 for(auto c : children)
1188 queue.emplace(c);
1189 }
1190
1191 if(problem) {
1192 printErr("merge tree in input is not valid");
1193 for(auto tup : problemNodes) {
1194 std::stringstream ss;
1195 ss << std::get<0>(tup) << " _ " << std::get<1>(tup);
1196 printMsg(ss.str());
1197 }
1198 printMsg(tree->printTree().str());
1199 printMsg(tree->printTreeScalars<dataType>().str());
1200 }
1201 }
1202
1203 // ------------------------------------------------------------------------
1204 // Testing
1205 // ------------------------------------------------------------------------
1206 template <class dataType>
1208 ftm::FTMTree_MT *tree2) {
1209 std::vector<std::tuple<ftm::idNode, ftm::idNode, dataType>> pairs1,
1210 pairs2;
1211 tree1->getPersistencePairsFromTree(pairs1);
1212 tree2->getPersistencePairsFromTree(pairs2);
1213 std::vector<std::vector<dataType>> costMatrix(
1214 pairs1.size() + 1, std::vector<dataType>(pairs2.size() + 1));
1215 std::stringstream const ss;
1216 ss << costMatrix.size() << " _ " << costMatrix[0].size();
1217 printMsg(ss.str());
1218 for(unsigned int i = 0; i < costMatrix.size() - 1; ++i) {
1219 dataType nodeIValue = tree1->getValue<dataType>(std::get<0>(pairs1[i]));
1220 dataType nodeIOriginValue
1221 = tree1->getValue<dataType>(std::get<1>(pairs1[i]));
1222 for(unsigned int j = 0; j < costMatrix[0].size() - 1; ++j) {
1223 dataType nodeJValue
1224 = tree2->getValue<dataType>(std::get<0>(pairs2[j]));
1225 dataType nodeJOriginValue
1226 = tree2->getValue<dataType>(std::get<1>(pairs2[j]));
1227 costMatrix[i][j] = std::pow(nodeIValue - nodeJValue, 2)
1228 + std::pow(nodeIOriginValue - nodeJOriginValue, 2);
1229 }
1230 costMatrix[i][costMatrix[0].size() - 1]
1231 = 2 * std::pow(std::get<2>(pairs1[i]), 2) / (std::pow(2, 2));
1232 }
1233 for(unsigned int j = 0; j < costMatrix[0].size() - 1; ++j)
1234 costMatrix[costMatrix.size() - 1][j]
1235 = 2 * std::pow(std::get<2>(pairs2[j]), 2) / (std::pow(2, 2));
1236 std::vector<MatchingType> matchings;
1237 forestAssignmentProblemMunkres(costMatrix, matchings);
1238 dataType cost = 0;
1239 for(auto tuple : matchings)
1240 cost += std::get<2>(tuple);
1241 std::stringstream ss2;
1242 ss2 << "cost = " << cost;
1243 printMsg(ss2.str());
1244 std::stringstream ss3;
1245 ss3 << "cost sqrt = " << std::sqrt(cost);
1246 printMsg(ss3.str());
1247 }
1248
1249 }; // MergeTreeDistance class
1250
1251} // namespace ttk
#define TTK_FORCE_USE(x)
Force the compiler to use the function/method parameter.
Definition BaseClass.h:57
#define ttkNotUsed(x)
Mark function/method parameters that are not used in the function body at all.
Definition BaseClass.h:47
void setEpsilon(double eps)
void setEpsilonDiviserMultiplier(double div)
void setNumberOfRounds(int noRounds)
virtual int run(std::vector< MatchingType > &matchings)=0
virtual int setInput(std::vector< std::vector< dataType > > &C_)
virtual void setBalanced(bool balanced)
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
float getElapsedUsage()
Definition Os.h:112
std::vector< std::vector< int > > treesNodeCorr_
std::tuple< dataType, ftm::idNode > computeTerm1_2(std::vector< ftm::idNode > &childrens, int ind, std::vector< std::vector< dataType > > &table, bool computeTerm1)
void parallelTreeDistanceTask(ftm::FTMTree_MT *tree1, ftm::FTMTree_MT *tree2, bool isTree1, int i, std::vector< ftm::idNode > &tree1Leaves, std::vector< int > &tree1NodeChildSize, std::vector< ftm::idNode > &tree2Leaves, std::vector< int > &tree2NodeChildSize, std::vector< std::vector< dataType > > &treeTable, std::vector< std::vector< dataType > > &forestTable, std::vector< std::vector< std::tuple< int, int > > > &treeBackTable, std::vector< std::vector< std::vector< std::tuple< int, int > > > > &forestBackTable, ftm::idNode nodeT, std::vector< int > &treeChildDone, std::vector< bool > &treeNodeDone, std::queue< ftm::idNode > &treeQueue)
dataType computeDistance(ftm::FTMTree_MT *tree1, ftm::FTMTree_MT *tree2, std::vector< std::tuple< ftm::idNode, ftm::idNode, double > > &outputMatching)
dataType computeDistance(ftm::FTMTree_MT *tree1, ftm::FTMTree_MT *tree2, std::vector< std::tuple< ftm::idNode, ftm::idNode > > &outputMatching)
void parallelEmptyTreeDistance_v2(ftm::FTMTree_MT *tree, bool isTree1, std::vector< ftm::idNode > &treeLeaves, std::vector< int > &treeNodeChildSize, std::vector< std::vector< dataType > > &treeTable, std::vector< std::vector< dataType > > &forestTable, std::vector< std::vector< std::tuple< int, int > > > &treeBackTable, std::vector< std::vector< std::vector< std::tuple< int, int > > > > &forestBackTable)
void setOnlyEmptyTreeDistance(double only)
void setPreprocess(bool preproc)
void computeEmptyToForestDistance(ftm::FTMTree_MT *tree2, ftm::idNode nodeJ, int j, std::vector< std::vector< dataType > > &treeTable, std::vector< std::vector< dataType > > &forestTable)
void computeForestToEmptyDistance(ftm::FTMTree_MT *tree1, ftm::idNode nodeI, int i, std::vector< std::vector< dataType > > &treeTable, std::vector< std::vector< dataType > > &forestTable)
void classicEditDistance(ftm::FTMTree_MT *tree1, ftm::FTMTree_MT *tree2, bool processTree1, bool computeEmptyTree, ftm::idNode nodeI, ftm::idNode nodeJ, std::vector< std::vector< dataType > > &treeTable, std::vector< std::vector< dataType > > &forestTable, std::vector< std::vector< std::tuple< int, int > > > &treeBackTable, std::vector< std::vector< std::vector< std::tuple< int, int > > > > &forestBackTable, int nRows, int nCols)
void runAssignmentProblemSolver(std::vector< std::vector< dataType > > &costMatrix, std::vector< MatchingType > &matchings)
void computeEmptyToSubtreeDistance(ftm::FTMTree_MT *tree2, ftm::idNode nodeJ, int j, std::vector< std::vector< dataType > > &treeTable, std::vector< std::vector< dataType > > &forestTable)
void parallelEmptyTreeDistancePara(ftm::FTMTree_MT *tree, bool isTree1, std::vector< ftm::idNode > &treeLeaves, std::vector< int > &treeNodeChildSize, std::vector< std::vector< dataType > > &treeTable, std::vector< std::vector< dataType > > &forestTable, std::vector< std::vector< std::tuple< int, int > > > &treeBackTable, std::vector< std::vector< std::vector< std::tuple< int, int > > > > &forestBackTable, ftm::idNode nodeT, std::vector< int > &treeChildDone, std::vector< bool > &treeNodeDone, std::queue< ftm::idNode > &treeQueue)
void setPostprocess(bool postproc)
void printMapIntInt(std::map< int, int > theMap)
dataType forestAssignmentProblem(ftm::FTMTree_MT *ttkNotUsed(tree1), ftm::FTMTree_MT *ttkNotUsed(tree2), std::vector< std::vector< dataType > > &treeTable, std::vector< ftm::idNode > &children1, std::vector< ftm::idNode > &children2, std::vector< std::tuple< int, int > > &forestAssignment)
void setAuctionEpsilonDiviser(double aucEpsilonDiviser)
void parallelTreeDistance_v2(ftm::FTMTree_MT *tree1, ftm::FTMTree_MT *tree2, bool isTree1, int i, std::vector< ftm::idNode > &tree1Leaves, std::vector< int > &tree1NodeChildSize, std::vector< ftm::idNode > &tree2Leaves, std::vector< int > &tree2NodeChildSize, std::vector< std::vector< dataType > > &treeTable, std::vector< std::vector< dataType > > &forestTable, std::vector< std::vector< std::tuple< int, int > > > &treeBackTable, std::vector< std::vector< std::vector< std::tuple< int, int > > > > &forestBackTable, bool firstCall=false)
void computeEditDistance(ftm::FTMTree_MT *tree1, ftm::FTMTree_MT *tree2, std::vector< std::vector< dataType > > &treeTable, std::vector< std::vector< dataType > > &forestTable, std::vector< std::vector< std::tuple< int, int > > > &treeBackTable, std::vector< std::vector< std::vector< std::tuple< int, int > > > > &forestBackTable, int nRows, int nCols)
void computeMatching(ftm::FTMTree_MT *tree1, ftm::FTMTree_MT *tree2, std::vector< std::vector< std::tuple< int, int > > > &treeBackTable, std::vector< std::vector< std::vector< std::tuple< int, int > > > > &forestBackTable, std::vector< std::tuple< ftm::idNode, ftm::idNode, double > > &outputMatching, int startR, int startC)
void setSaveTree(bool save)
void computeForestsDistance(ftm::FTMTree_MT *tree1, ftm::FTMTree_MT *tree2, int i, int j, std::vector< std::vector< dataType > > &treeTable, std::vector< std::vector< dataType > > &forestTable, std::vector< std::vector< std::vector< std::tuple< int, int > > > > &forestBackTable, std::vector< ftm::idNode > &children1, std::vector< ftm::idNode > &children2)
void setAuctionEpsilon(double aucEpsilon)
void parallelEmptyTreeDistanceTask(ftm::FTMTree_MT *tree, bool isTree1, std::vector< ftm::idNode > &ttkNotUsed(treeLeaves), std::vector< int > &treeNodeChildSize, std::vector< std::vector< dataType > > &treeTable, std::vector< std::vector< dataType > > &forestTable, std::vector< std::vector< std::tuple< int, int > > > &treeBackTable, std::vector< std::vector< std::vector< std::tuple< int, int > > > > &forestBackTable, ftm::idNode nodeT, std::vector< int > &treeChildDone, std::vector< bool > &treeNodeDone, std::queue< ftm::idNode > &treeQueue)
void parallelEditDistance(ftm::FTMTree_MT *tree1, ftm::FTMTree_MT *tree2, std::vector< std::vector< dataType > > &treeTable, std::vector< std::vector< dataType > > &forestTable, std::vector< std::vector< std::tuple< int, int > > > &treeBackTable, std::vector< std::vector< std::vector< std::tuple< int, int > > > > &forestBackTable, int ttkNotUsed(nRows), int ttkNotUsed(nCols))
void setMinMaxPairWeight(double weight)
void computeSubtreeToEmptyDistance(ftm::FTMTree_MT *tree1, ftm::idNode nodeI, int i, std::vector< std::vector< dataType > > &treeTable, std::vector< std::vector< dataType > > &forestTable)
dataType execute(ftm::MergeTree< dataType > &tree1, ftm::MergeTree< dataType > &tree2, std::vector< std::tuple< ftm::idNode, ftm::idNode > > &outputMatching)
void parallelTreeDistancePara(ftm::FTMTree_MT *tree1, ftm::FTMTree_MT *tree2, bool isTree1, int i, std::vector< ftm::idNode > &tree1Leaves, std::vector< int > &tree1NodeChildSize, std::vector< ftm::idNode > &tree2Leaves, std::vector< int > &tree2NodeChildSize, std::vector< std::vector< dataType > > &treeTable, std::vector< std::vector< dataType > > &forestTable, std::vector< std::vector< std::tuple< int, int > > > &treeBackTable, std::vector< std::vector< std::vector< std::tuple< int, int > > > > &forestBackTable, bool firstCall, ftm::idNode nodeT, std::vector< int > &treeChildDone, std::vector< bool > &treeNodeDone, std::queue< ftm::idNode > &treeQueue)
void createCostMatrix(std::vector< std::vector< dataType > > &treeTable, std::vector< ftm::idNode > &children1, std::vector< ftm::idNode > &children2, std::vector< std::vector< dataType > > &costMatrix)
void verifyMergeTreeStructure(ftm::FTMTree_MT *tree)
dataType postprocessAssignment(std::vector< MatchingType > &matchings, std::vector< ftm::idNode > &children1, std::vector< ftm::idNode > &children2, std::vector< std::tuple< int, int > > &forestAssignment)
dataType execute(ftm::MergeTree< dataType > &mTree1, ftm::MergeTree< dataType > &mTree2, std::vector< std::tuple< ftm::idNode, ftm::idNode, double > > &outputMatching)
void computeSubtreesDistance(ftm::FTMTree_MT *tree1, ftm::FTMTree_MT *tree2, int i, int j, ftm::idNode nodeI, ftm::idNode nodeJ, std::vector< std::vector< dataType > > &treeTable, std::vector< std::vector< dataType > > &forestTable, std::vector< std::vector< std::tuple< int, int > > > &treeBackTable, std::vector< ftm::idNode > &children1, std::vector< ftm::idNode > &children2)
void classicalPersistenceAssignmentProblem(ftm::FTMTree_MT *tree1, ftm::FTMTree_MT *tree2)
void setAuctionNoRounds(double aucNoRounds)
~MergeTreeDistance() override=default
double getElapsedTime()
Definition Timer.h:15
void getLevelToNode(std::vector< std::vector< idNode > > &res)
const scalarType & getValue(SimplexId nodeId) const
Definition FTMTree_MT.h:339
idNode getNumberOfNodes() const
Definition FTMTree_MT.h:389
std::stringstream printTreeScalars(bool printNodeAlone=true, bool doPrint=true)
bool isRoot(idNode nodeId)
idNode getParentSafe(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 getLeavesFromTree(std::vector< idNode > &res)
void getAllNodeLevel(std::vector< int > &res)
std::stringstream printTree(bool doPrint=true)
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)