TTK
Loading...
Searching...
No Matches
PathMappingDistance.h
Go to the documentation of this file.
1
13
14#pragma once
15
16#include <set>
17#include <vector>
18
19#include <algorithm>
20#include <cfloat>
21#include <chrono>
22#include <cmath>
23#include <iostream>
24#include <limits>
25#include <set>
26#include <stack>
27#include <tuple>
28#include <vector>
29
30// ttk common includes
31#include <AssignmentAuction.h>
32#include <AssignmentExhaustive.h>
33#include <AssignmentMunkres.h>
34#include <Debug.h>
35#include <FTMTree_MT.h>
36
37namespace ttk {
38
39 class PathMappingDistance : virtual public Debug {
40
41 private:
42 int baseMetric_ = 0;
43 int assignmentSolverID_ = 0;
44 bool squared_ = false;
45 bool computeMapping_ = false;
46
47 template <class dataType>
48 inline dataType editCost_Persistence(int n1,
49 int p1,
50 int n2,
51 int p2,
52 ftm::FTMTree_MT *tree1,
53 ftm::FTMTree_MT *tree2) {
54 dataType d;
55 if(n1 < 0) {
56 dataType b1 = tree2->getValue<dataType>(n2);
57 dataType d1 = tree2->getValue<dataType>(p2);
58 d = (d1 > b1) ? (d1 - b1) : (b1 - d1);
59 } else if(n2 < 0) {
60 dataType b1 = tree1->getValue<dataType>(n1);
61 dataType d1 = tree1->getValue<dataType>(p1);
62 d = (d1 > b1) ? (d1 - b1) : (b1 - d1);
63 } else {
64 dataType b1 = tree1->getValue<dataType>(n1);
65 dataType d1 = tree1->getValue<dataType>(p1);
66 dataType b2 = tree2->getValue<dataType>(n2);
67 dataType d2 = tree2->getValue<dataType>(p2);
68 dataType dist1 = (d1 > b1) ? (d1 - b1) : (b1 - d1);
69 dataType dist2 = (d2 > b2) ? (d2 - b2) : (b2 - d2);
70 d = (dist1 > dist2) ? (dist1 - dist2) : (dist2 - dist1);
71 }
72 return squared_ ? d * d : d;
73 }
74
75 template <class dataType>
76 void traceMapping_path(
77 ftm::FTMTree_MT *tree1,
78 ftm::FTMTree_MT *tree2,
79 int curr1,
80 int l1,
81 int curr2,
82 int l2,
83 std::vector<std::vector<int>> &predecessors1,
84 std::vector<std::vector<int>> &predecessors2,
85 int depth1,
86 int depth2,
87 dataType *memT,
88 std::vector<std::pair<std::pair<ftm::idNode, ftm::idNode>,
89 std::pair<ftm::idNode, ftm::idNode>>> &mapping) {
90
91 //===============================================================================
92 // If both trees not empty, find optimal edit operation
93 std::vector<ftm::idNode> children1;
94 tree1->getChildren(curr1, children1);
95 std::vector<ftm::idNode> children2;
96 tree2->getChildren(curr2, children2);
97 int parent1 = predecessors1[curr1][predecessors1[curr1].size() - l1];
98 int parent2 = predecessors2[curr2][predecessors2[curr2].size() - l2];
99
100 size_t const nn1 = tree1->getNumberOfNodes();
101 size_t const nn2 = tree2->getNumberOfNodes();
102 size_t const dim1 = 1;
103 size_t const dim2 = (nn1 + 1) * dim1;
104 size_t const dim3 = (depth1 + 1) * dim2;
105 size_t const dim4 = (nn2 + 1) * dim3;
106
107 //---------------------------------------------------------------------------
108 // If both trees only have one branch, return edit cost between
109 // the two branches
110 if(tree1->getNumberOfChildren(curr1) == 0
111 and tree2->getNumberOfChildren(curr2) == 0) {
112 mapping.emplace_back(
113 std::make_pair(curr1, parent1), std::make_pair(curr2, parent2));
114 return;
115 }
116 //---------------------------------------------------------------------------
117 // If first tree only has one branch, try all decompositions of
118 // second tree
119 else if(tree1->getNumberOfChildren(curr1) == 0) {
120 for(auto child2_mb : children2) {
121 dataType d_
122 = memT[curr1 + l1 * dim2 + child2_mb * dim3 + (l2 + 1) * dim4];
123 for(auto child2 : children2) {
124 if(child2 == child2_mb) {
125 continue;
126 }
127 d_ += memT[nn1 + 0 * dim2 + child2 * dim3 + 1 * dim4];
128 }
129 if(memT[curr1 + l1 * dim2 + curr2 * dim3 + l2 * dim4] == d_) {
130 traceMapping_path(tree1, tree2, curr1, l1, child2_mb, l2 + 1,
131 predecessors1, predecessors2, depth1, depth2,
132 memT, mapping);
133 return;
134 }
135 }
136 }
137 //---------------------------------------------------------------------------
138 // If second tree only has one branch, try all decompositions of
139 // first tree
140 else if(tree2->getNumberOfChildren(curr2) == 0) {
141 dataType d = std::numeric_limits<dataType>::max();
142 for(auto child1_mb : children1) {
143 dataType d_
144 = memT[child1_mb + (l1 + 1) * dim2 + curr2 * dim3 + l2 * dim4];
145 for(auto child1 : children1) {
146 if(child1 == child1_mb) {
147 continue;
148 }
149 d_ += memT[child1 + 1 * dim2 + nn2 * dim3 + 0 * dim4];
150 }
151 d = std::min(d, d_);
152 if(memT[curr1 + l1 * dim2 + curr2 * dim3 + l2 * dim4] == d_) {
153 traceMapping_path(tree1, tree2, child1_mb, l1 + 1, curr2, l2,
154 predecessors1, predecessors2, depth1, depth2,
155 memT, mapping);
156 return;
157 }
158 }
159 }
160 //---------------------------------------------------------------------------
161 // If both trees have more than one branch, try all decompositions
162 // of both trees
163 else {
164 //-----------------------------------------------------------------------
165 // Try all possible main branches of first tree (child1_mb) and
166 // all possible main branches of second tree (child2_mb) Then
167 // try all possible matchings of subtrees
168 if(tree1->getNumberOfChildren(curr1) == 2
169 && tree2->getNumberOfChildren(curr2) == 2) {
170 int child11 = children1[0];
171 int child12 = children1[1];
172 int child21 = children2[0];
173 int child22 = children2[1];
174 if(memT[curr1 + l1 * dim2 + curr2 * dim3 + l2 * dim4]
175 == memT[child11 + 1 * dim2 + child21 * dim3 + 1 * dim4]
176 + memT[child12 + 1 * dim2 + child22 * dim3 + 1 * dim4]
177 + editCost_Persistence<dataType>(
178 curr1, parent1, curr2, parent2, tree1, tree2)) {
179 mapping.emplace_back(
180 std::make_pair(curr1, parent1), std::make_pair(curr2, parent2));
181 traceMapping_path(tree1, tree2, child11, 1, child21, 1,
182 predecessors1, predecessors2, depth1, depth2,
183 memT, mapping);
184 traceMapping_path(tree1, tree2, child12, 1, child22, 1,
185 predecessors1, predecessors2, depth1, depth2,
186 memT, mapping);
187 }
188 if(memT[curr1 + l1 * dim2 + curr2 * dim3 + l2 * dim4]
189 == memT[child11 + 1 * dim2 + child22 * dim3 + 1 * dim4]
190 + memT[child12 + 1 * dim2 + child21 * dim3 + 1 * dim4]
191 + editCost_Persistence<dataType>(
192 curr1, parent1, curr2, parent2, tree1, tree2)) {
193 mapping.emplace_back(
194 std::make_pair(curr1, parent1), std::make_pair(curr2, parent2));
195 traceMapping_path(tree1, tree2, child11, 1, child22, 1,
196 predecessors1, predecessors2, depth1, depth2,
197 memT, mapping);
198 traceMapping_path(tree1, tree2, child12, 1, child21, 1,
199 predecessors1, predecessors2, depth1, depth2,
200 memT, mapping);
201 return;
202 }
203 } else {
204 auto f = [&](int r, int c) {
205 size_t const c1
206 = r < tree1->getNumberOfChildren(curr1) ? children1[r] : nn1;
207 size_t const c2
208 = c < tree2->getNumberOfChildren(curr2) ? children2[c] : nn2;
209 int const l1_ = c1 == nn1 ? 0 : 1;
210 int const l2_ = c2 == nn2 ? 0 : 1;
211 return memT[c1 + l1_ * dim2 + c2 * dim3 + l2_ * dim4];
212 };
213 int size = std::max(tree1->getNumberOfChildren(curr1),
214 tree2->getNumberOfChildren(curr2))
215 + 1;
216 auto costMatrix = std::vector<std::vector<dataType>>(
217 size, std::vector<dataType>(size, 0));
218 std::vector<MatchingType> matching;
219 for(int r = 0; r < size; r++) {
220 for(int c = 0; c < size; c++) {
221 costMatrix[r][c] = f(r, c);
222 }
223 }
224
225 AssignmentSolver<dataType> *assignmentSolver;
226 AssignmentExhaustive<dataType> solverExhaustive;
227 AssignmentMunkres<dataType> solverMunkres;
228 AssignmentAuction<dataType> solverAuction;
229 switch(assignmentSolverID_) {
230 case 1:
231 solverExhaustive = AssignmentExhaustive<dataType>();
232 assignmentSolver = &solverExhaustive;
233 break;
234 case 2:
235 solverMunkres = AssignmentMunkres<dataType>();
236 assignmentSolver = &solverMunkres;
237 break;
238 case 0:
239 default:
240 solverAuction = AssignmentAuction<dataType>();
241 assignmentSolver = &solverAuction;
242 }
243 assignmentSolver->setInput(costMatrix);
244 assignmentSolver->setBalanced(true);
245 assignmentSolver->run(matching);
246 dataType d_ = editCost_Persistence<dataType>(
247 curr1, parent1, curr2, parent2, tree1, tree2);
248 for(auto m : matching)
249 d_ += std::get<2>(m);
250 if(memT[curr1 + l1 * dim2 + curr2 * dim3 + l2 * dim4] == d_) {
251 mapping.emplace_back(
252 std::make_pair(curr1, parent1), std::make_pair(curr2, parent2));
253 for(auto m : matching) {
254 int n1 = std::get<0>(m) < tree1->getNumberOfChildren(curr1)
255 ? children1[std::get<0>(m)]
256 : -1;
257 int n2 = std::get<1>(m) < tree2->getNumberOfChildren(curr2)
258 ? children2[std::get<1>(m)]
259 : -1;
260 if(n1 >= 0 && n2 >= 0)
261 traceMapping_path(tree1, tree2, n1, 1, n2, 1, predecessors1,
262 predecessors2, depth1, depth2, memT, mapping);
263 }
264 return;
265 }
266 }
267 //-----------------------------------------------------------------------
268 // Try to continue main branch on one child of first tree and
269 // delete all other subtrees Then match continued branch to
270 // current branch in second tree
271 for(auto child1_mb : children1) {
272 dataType d_
273 = memT[child1_mb + (l1 + 1) * dim2 + curr2 * dim3 + l2 * dim4];
274 for(auto child1 : children1) {
275 if(child1 == child1_mb) {
276 continue;
277 }
278 d_ += memT[child1 + 1 * dim2 + nn2 * dim3 + 0 * dim4];
279 }
280 if(memT[curr1 + l1 * dim2 + curr2 * dim3 + l2 * dim4] == d_) {
281 traceMapping_path(tree1, tree2, child1_mb, l1 + 1, curr2, l2,
282 predecessors1, predecessors2, depth1, depth2,
283 memT, mapping);
284 return;
285 }
286 }
287 //-----------------------------------------------------------------------
288 // Try to continue main branch on one child of second tree and
289 // delete all other subtrees Then match continued branch to
290 // current branch in first tree
291 for(auto child2_mb : children2) {
292 dataType d_
293 = memT[curr1 + l1 * dim2 + child2_mb * dim3 + (l2 + 1) * dim4];
294 for(auto child2 : children2) {
295 if(child2 == child2_mb) {
296 continue;
297 }
298 d_ += memT[nn1 + 0 * dim2 + child2 * dim3 + 1 * dim4];
299 }
300 if(memT[curr1 + l1 * dim2 + curr2 * dim3 + l2 * dim4] == d_) {
301 traceMapping_path(tree1, tree2, curr1, l1, child2_mb, l2 + 1,
302 predecessors1, predecessors2, depth1, depth2,
303 memT, mapping);
304 return;
305 }
306 }
307 }
308 }
309
310 public:
311 PathMappingDistance() {
312 this->setDebugMsgPrefix(
313 "MergeTreeDistance"); // inherited from Debug: prefix will be printed at
314 // the beginning of every msg
315 }
316 ~PathMappingDistance() override = default;
317
318 void setBaseMetric(int m) {
319 baseMetric_ = m;
320 }
321
322 void setAssignmentSolver(int assignmentSolver) {
323 assignmentSolverID_ = assignmentSolver;
324 }
325
326 void setSquared(bool s) {
327 squared_ = s;
328 }
329
330 void setComputeMapping(bool m) {
331 computeMapping_ = m;
332 }
333
334 template <class dataType>
335 dataType editDistance_path(ftm::FTMTree_MT *tree1, ftm::FTMTree_MT *tree2) {
336
337 // initialize memoization tables
338
339 std::vector<std::vector<int>> predecessors1(tree1->getNumberOfNodes());
340 std::vector<std::vector<int>> predecessors2(tree2->getNumberOfNodes());
341 int const rootID1 = tree1->getRoot();
342 int const rootID2 = tree2->getRoot();
343 std::vector<int> preorder1(tree1->getNumberOfNodes());
344 std::vector<int> preorder2(tree2->getNumberOfNodes());
345
346 int depth1 = 0;
347 int depth2 = 0;
348 std::stack<int> stack;
349 stack.push(rootID1);
350 int count = tree1->getNumberOfNodes() - 1;
351 while(!stack.empty()) {
352 int const nIdx = stack.top();
353 stack.pop();
354 preorder1[count] = nIdx;
355 count--;
356 depth1 = std::max((int)predecessors1[nIdx].size(), depth1);
357 std::vector<ftm::idNode> children;
358 tree1->getChildren(nIdx, children);
359 for(int const cIdx : children) {
360 stack.push(cIdx);
361 predecessors1[cIdx].reserve(predecessors1[nIdx].size() + 1);
362 predecessors1[cIdx].insert(predecessors1[cIdx].end(),
363 predecessors1[nIdx].begin(),
364 predecessors1[nIdx].end());
365 predecessors1[cIdx].push_back(nIdx);
366 }
367 }
368 stack.push(rootID2);
369 count = tree2->getNumberOfNodes() - 1;
370 while(!stack.empty()) {
371 int const nIdx = stack.top();
372 stack.pop();
373 preorder2[count] = nIdx;
374 count--;
375 depth2 = std::max((int)predecessors2[nIdx].size(), depth2);
376 std::vector<ftm::idNode> children;
377 tree2->getChildren(nIdx, children);
378 for(int const cIdx : children) {
379 stack.push(cIdx);
380 predecessors2[cIdx].reserve(predecessors2[nIdx].size() + 1);
381 predecessors2[cIdx].insert(predecessors2[cIdx].end(),
382 predecessors2[nIdx].begin(),
383 predecessors2[nIdx].end());
384 predecessors2[cIdx].push_back(nIdx);
385 }
386 }
387
388 size_t nn1 = tree1->getNumberOfNodes();
389 size_t nn2 = tree2->getNumberOfNodes();
390 size_t const dim1 = 1;
391 size_t const dim2 = (nn1 + 1) * dim1;
392 size_t const dim3 = (depth1 + 1) * dim2;
393 size_t const dim4 = (nn2 + 1) * dim3;
394
395 std::vector<dataType> memT((nn1 + 1) * (depth1 + 1) * (nn2 + 1)
396 * (depth2 + 1));
397
398 memT[nn1 + 0 * dim2 + nn2 * dim3 + 0 * dim4] = 0;
399 for(size_t i = 0; i < nn1; i++) {
400 int curr1 = preorder1[i];
401 std::vector<ftm::idNode> children1;
402 tree1->getChildren(curr1, children1);
403 for(size_t l = 1; l <= predecessors1[preorder1[i]].size(); l++) {
404 int parent1 = predecessors1[preorder1[i]]
405 [predecessors1[preorder1[i]].size() - l];
406
407 //-----------------------------------------------------------------------
408 // Delete curr path and full subtree rooted in path
409 memT[curr1 + l * dim2 + nn2 * dim3 + 0 * dim4]
410 = editCost_Persistence<dataType>(
411 curr1, parent1, -1, -1, tree1, tree2);
412 for(auto child1 : children1) {
413 memT[curr1 + l * dim2 + nn2 * dim3 + 0 * dim4]
414 += memT[child1 + 1 * dim2 + nn2 * dim3 + 0 * dim4];
415 }
416 }
417 }
418 for(size_t j = 0; j < nn2; j++) {
419 int curr2 = preorder2[j];
420 std::vector<ftm::idNode> children2;
421 tree2->getChildren(curr2, children2);
422 for(size_t l = 1; l <= predecessors2[preorder2[j]].size(); l++) {
423 int parent2 = predecessors2[preorder2[j]]
424 [predecessors2[preorder2[j]].size() - l];
425
426 //-----------------------------------------------------------------------
427 // Delete curr path and full subtree rooted in path
428 memT[nn1 + 0 * dim2 + curr2 * dim3 + l * dim4]
429 = editCost_Persistence<dataType>(
430 -1, -1, curr2, parent2, tree1, tree2);
431 for(auto child2 : children2) {
432 memT[nn1 + 0 * dim2 + curr2 * dim3 + l * dim4]
433 += memT[nn1 + 0 * dim2 + child2 * dim3 + 1 * dim4];
434 }
435 }
436 }
437
438 for(size_t i = 0; i < nn1; i++) {
439 int curr1 = preorder1[i];
440 std::vector<ftm::idNode> children1;
441 tree1->getChildren(curr1, children1);
442 for(size_t j = 0; j < nn2; j++) {
443 int curr2 = preorder2[j];
444 std::vector<ftm::idNode> children2;
445 tree2->getChildren(curr2, children2);
446 for(size_t l1 = 1; l1 <= predecessors1[preorder1[i]].size(); l1++) {
447 int parent1
448 = predecessors1[preorder1[i]]
449 [predecessors1[preorder1[i]].size() - l1];
450 for(size_t l2 = 1; l2 <= predecessors2[preorder2[j]].size(); l2++) {
451 int parent2
452 = predecessors2[preorder2[j]]
453 [predecessors2[preorder2[j]].size() - l2];
454
455 //===============================================================================
456 // If both trees not empty, find optimal edit operation
457
458 //---------------------------------------------------------------------------
459 // If both trees only have one branch, return edit cost between
460 // the two branches
461 if(tree1->getNumberOfChildren(curr1) == 0
462 and tree2->getNumberOfChildren(curr2) == 0) {
463 memT[curr1 + l1 * dim2 + curr2 * dim3 + l2 * dim4]
464 = editCost_Persistence<dataType>(
465 curr1, parent1, curr2, parent2, tree1, tree2);
466 }
467 //---------------------------------------------------------------------------
468 // If first tree only has one branch, try all decompositions of
469 // second tree
470 else if(tree1->getNumberOfChildren(curr1) == 0) {
471 dataType d = std::numeric_limits<dataType>::max();
472 for(auto child2_mb : children2) {
473 dataType d_ = memT[curr1 + l1 * dim2 + child2_mb * dim3
474 + (l2 + 1) * dim4];
475 for(auto child2 : children2) {
476 if(child2 == child2_mb) {
477 continue;
478 }
479 d_ += memT[nn1 + 0 * dim2 + child2 * dim3 + 1 * dim4];
480 }
481 d = std::min(d, d_);
482 }
483 memT[curr1 + l1 * dim2 + curr2 * dim3 + l2 * dim4] = d;
484 }
485 //---------------------------------------------------------------------------
486 // If second tree only has one branch, try all decompositions of
487 // first tree
488 else if(tree2->getNumberOfChildren(curr2) == 0) {
489 dataType d = std::numeric_limits<dataType>::max();
490 for(auto child1_mb : children1) {
491 dataType d_ = memT[child1_mb + (l1 + 1) * dim2 + curr2 * dim3
492 + l2 * dim4];
493 for(auto child1 : children1) {
494 if(child1 == child1_mb) {
495 continue;
496 }
497 d_ += memT[child1 + 1 * dim2 + nn2 * dim3 + 0 * dim4];
498 }
499 d = std::min(d, d_);
500 }
501 memT[curr1 + l1 * dim2 + curr2 * dim3 + l2 * dim4] = d;
502 }
503 //---------------------------------------------------------------------------
504 // If both trees have more than one branch, try all decompositions
505 // of both trees
506 else {
507 dataType d = std::numeric_limits<dataType>::max();
508 //-----------------------------------------------------------------------
509 // Try all possible main branches of first tree (child1_mb) and
510 // all possible main branches of second tree (child2_mb) Then
511 // try all possible matchings of subtrees
512 if(tree1->getNumberOfChildren(curr1) == 2
513 && tree2->getNumberOfChildren(curr2) == 2) {
514 int const child11 = children1[0];
515 int const child12 = children1[1];
516 int const child21 = children2[0];
517 int const child22 = children2[1];
518 d = std::min<dataType>(
519 d, memT[child11 + 1 * dim2 + child21 * dim3 + 1 * dim4]
520 + memT[child12 + 1 * dim2 + child22 * dim3 + 1 * dim4]
521 + editCost_Persistence<dataType>(
522 curr1, parent1, curr2, parent2, tree1, tree2));
523 d = std::min<dataType>(
524 d, memT[child11 + 1 * dim2 + child22 * dim3 + 1 * dim4]
525 + memT[child12 + 1 * dim2 + child21 * dim3 + 1 * dim4]
526 + editCost_Persistence<dataType>(
527 curr1, parent1, curr2, parent2, tree1, tree2));
528 } else {
529 auto f = [&](int r, int c) {
530 size_t const c1 = r < tree1->getNumberOfChildren(curr1)
531 ? children1[r]
532 : nn1;
533 size_t const c2 = c < tree2->getNumberOfChildren(curr2)
534 ? children2[c]
535 : nn2;
536 int const l1_ = c1 == nn1 ? 0 : 1;
537 int const l2_ = c2 == nn2 ? 0 : 1;
538 return memT[c1 + l1_ * dim2 + c2 * dim3 + l2_ * dim4];
539 };
540 int size = std::max(tree1->getNumberOfChildren(curr1),
541 tree2->getNumberOfChildren(curr2))
542 + 1;
543 auto costMatrix = std::vector<std::vector<dataType>>(
544 size, std::vector<dataType>(size, 0));
545 std::vector<MatchingType> matching;
546 for(int r = 0; r < size; r++) {
547 for(int c = 0; c < size; c++) {
548 costMatrix[r][c] = f(r, c);
549 }
550 }
551
552 AssignmentSolver<dataType> *assignmentSolver;
553 AssignmentExhaustive<dataType> solverExhaustive;
554 AssignmentMunkres<dataType> solverMunkres;
555 AssignmentAuction<dataType> solverAuction;
556 switch(assignmentSolverID_) {
557 case 1:
558 solverExhaustive = AssignmentExhaustive<dataType>();
559 assignmentSolver = &solverExhaustive;
560 break;
561 case 2:
562 solverMunkres = AssignmentMunkres<dataType>();
563 assignmentSolver = &solverMunkres;
564 break;
565 case 0:
566 default:
567 solverAuction = AssignmentAuction<dataType>();
568 assignmentSolver = &solverAuction;
569 }
570 assignmentSolver->setInput(costMatrix);
571 assignmentSolver->setBalanced(true);
572 assignmentSolver->run(matching);
573 dataType d_ = editCost_Persistence<dataType>(
574 curr1, parent1, curr2, parent2, tree1, tree2);
575 for(auto m : matching)
576 d_ += std::get<2>(m);
577 d = std::min(d, d_);
578 }
579 //-----------------------------------------------------------------------
580 // Try to continue main branch on one child of first tree and
581 // delete all other subtrees Then match continued branch to
582 // current branch in second tree
583 for(auto child1_mb : children1) {
584 dataType d_ = memT[child1_mb + (l1 + 1) * dim2 + curr2 * dim3
585 + l2 * dim4];
586 for(auto child1 : children1) {
587 if(child1 == child1_mb) {
588 continue;
589 }
590 d_ += memT[child1 + 1 * dim2 + nn2 * dim3 + 0 * dim4];
591 }
592 d = std::min(d, d_);
593 }
594 //-----------------------------------------------------------------------
595 // Try to continue main branch on one child of second tree and
596 // delete all other subtrees Then match continued branch to
597 // current branch in first tree
598 for(auto child2_mb : children2) {
599 dataType d_ = memT[curr1 + l1 * dim2 + child2_mb * dim3
600 + (l2 + 1) * dim4];
601 for(auto child2 : children2) {
602 if(child2 == child2_mb) {
603 continue;
604 }
605 d_ += memT[nn1 + 0 * dim2 + child2 * dim3 + 1 * dim4];
606 }
607 d = std::min(d, d_);
608 }
609 memT[curr1 + l1 * dim2 + curr2 * dim3 + l2 * dim4] = d;
610 }
611 }
612 }
613 }
614 }
615
616 std::vector<ftm::idNode> children1;
617 tree1->getChildren(rootID1, children1);
618 std::vector<ftm::idNode> children2;
619 tree2->getChildren(rootID2, children2);
620
621 dataType res
622 = memT[children1[0] + 1 * dim2 + children2[0] * dim3 + 1 * dim4];
623
624 return squared_ ? std::sqrt(res) : res;
625 }
626 };
627} // namespace ttk
FTMTree_MT.h
ttk::AssignmentSolver::run
virtual int run(std::vector< MatchingType > &matchings)=0
ttk::AssignmentSolver::setInput
virtual int setInput(std::vector< std::vector< dataType > > &C_)
Definition AssignmentSolver.h:43
ttk::AssignmentSolver::setBalanced
virtual void setBalanced(bool balanced)
Definition AssignmentSolver.h:54
ttk::Debug
Minimalist debugging class.
Definition Debug.h:88
ttk::Debug::setDebugMsgPrefix
void setDebugMsgPrefix(const std::string &prefix)
Definition Debug.h:364
ttk::PathMappingDistance::setAssignmentSolver
void setAssignmentSolver(int assignmentSolver)
Definition PathMappingDistance.h:322
ttk::PathMappingDistance::~PathMappingDistance
~PathMappingDistance() override=default
ttk::PathMappingDistance::editDistance_path
dataType editDistance_path(ftm::FTMTree_MT *tree1, ftm::FTMTree_MT *tree2)
Definition PathMappingDistance.h:335
ttk::ftm::FTMTree_MT
Definition FTMTree_MT.h:83
ttk::ftm::FTMTree_MT::getValue
const scalarType & getValue(SimplexId nodeId) const
Definition FTMTree_MT.h:339
ttk::ftm::FTMTree_MT::getNumberOfNodes
idNode getNumberOfNodes() const
Definition FTMTree_MT.h:389
ttk::ftm::FTMTree_MT::getNumberOfChildren
int getNumberOfChildren(idNode nodeId)
Definition FTMTreeUtils.cpp:223
ttk::ftm::FTMTree_MT::getRoot
idNode getRoot()
Definition FTMTreeUtils.cpp:97
ttk::ftm::FTMTree_MT::getChildren
void getChildren(idNode nodeId, std::vector< idNode > &res)
Definition FTMTreeUtils.cpp:114
ttk
The Topology ToolKit.
Definition AbstractTriangulation.h:51
end
T end(std::pair< T, T > &p)
Definition ripserpy.cpp:483
Generated on Thu Sep 26 2024 06:50:18 for TTK by doxygen 1.9.8