TTK
Loading...
Searching...
No Matches
MergeTreeVisualization.h
Go to the documentation of this file.
1
7
8#pragma once
9
10#include <FTMTree.h>
11
12#include <stack>
13
14namespace ttk {
15
16 class MergeTreeVisualization : virtual public Debug {
17 protected:
18 // Visualization parameters
20 double branchSpacing_ = 1.;
22 double importantPairs_ = 50.; // important pairs threshold
30
31 public:
33 ~MergeTreeVisualization() override = default;
34
35 // ==========================================================================
36 // Getter / Setter
37 // ==========================================================================
38 // Visualization parameters
41 }
42 void setBranchSpacing(double d) {
44 }
47 }
48 void setImportantPairs(double d) {
50 }
51 void setImportantPairsSpacing(double d) {
53 }
56 }
59 }
60 void setExcludeImportantPairsHigher(std::string &d) {
63 }
64 void setExcludeImportantPairsLower(std::string &d) {
67 }
68
69 // ==========================================================================
70 // Planar Layout
71 // ==========================================================================
72 // TODO manage multi pers pairs
73 template <class dataType>
75 ftm::FTMTree_MT *tree,
76 std::vector<float> &retVec,
77 std::vector<LongSimplexId> &treeSimplexId,
78 std::vector<ftm::idNode> &ttkNotUsed(branching),
79 std::vector<std::vector<ftm::idNode>> &nodeBranching) {
80 ftm::idNode treeRoot = tree->getRoot();
81 ftm::idNode treeRootOrigin = tree->getNode(treeRoot)->getOrigin();
82 float rootY = retVec[treeSimplexId[treeRoot] * 2 + 1];
83 float rootOriginY = retVec[treeSimplexId[treeRootOrigin] * 2 + 1];
84 float rootYmin = std::min(rootY, rootOriginY);
85 float rootYmax = std::max(rootY, rootOriginY);
86 dataType rootPers = tree->getNodePersistence<dataType>(treeRoot);
87 std::vector<std::tuple<float, float>> allNodeSpanX(
88 tree->getNumberOfNodes());
89 std::vector<std::tuple<float, float>> allNodeImportantSpanX(
90 tree->getNumberOfNodes());
91
92 // Compute gap
93 float nonImportantPairsGap
94 = (rootYmax - rootYmin) * 0.05 * nonImportantPairsSpacing_;
95 float importantPairsGap
96 = std::max(nonImportantPairsGap, (float)importantPairsSpacing_);
97
98 // Some functions
99 auto compLowerPers = [&](const ftm::idNode a, const ftm::idNode b) {
100 return tree->getNodePersistence<dataType>(a)
101 < tree->getNodePersistence<dataType>(b);
102 };
103 auto compEqUpperPers = [&](const ftm::idNode a, const ftm::idNode b) {
104 return not compLowerPers(a, b);
105 };
106
107 // Go
108 std::vector<ftm::idNode> leaves;
109 tree->getLeavesFromTree(leaves);
110 std::sort(leaves.begin(), leaves.end(), compLowerPers);
111 std::queue<ftm::idNode> queue;
112 for(auto node : leaves)
113 queue.emplace(node);
114 while(!queue.empty()) {
115 ftm::idNode node = queue.front();
116 queue.pop();
117 ftm::idNode nodeOrigin = tree->getNode(node)->getOrigin();
118
119 const double nodePers = tree->getNodePersistence<dataType>(node);
120 retVec[treeSimplexId[nodeOrigin] * 2] = 0;
121 retVec[treeSimplexId[nodeOrigin] * 2 + 1]
122 = nodePers / rootPers * (rootYmax - rootYmin) + rootYmin;
123
124 // Positioning nodes in the branch
125 if(tree->isBranchOrigin(nodeOrigin)) {
126 float prevX = 0;
127 std::vector<ftm::idNode> nodeBranchingVector;
128 for(size_t i = 1; i < nodeBranching[nodeOrigin].size(); ++i)
129 nodeBranchingVector.push_back(nodeBranching[nodeOrigin][i]);
130 std::sort(nodeBranchingVector.begin(), nodeBranchingVector.end(),
131 compEqUpperPers);
132
133 // Iterate through each node of the branch
134 int lastIndexImportant = -1;
135 for(size_t i = 0; i < nodeBranchingVector.size(); ++i) {
136 ftm::idNode nodeBranchingI = nodeBranchingVector[i];
137
138 // Get old node span X
139 float oldMin = std::get<0>(allNodeSpanX[nodeBranchingI]);
140 float oldMax = std::get<1>(allNodeSpanX[nodeBranchingI]);
141
142 // Get x spacing
143 float nodeSpacing = 0;
144 if(i > 0) {
145 if(tree->isImportantPair<dataType>(
146 nodeBranchingVector[i], importantPairs_,
149 nodeSpacing = importantPairsGap;
150 } else if(tree->isImportantPair<dataType>(
151 nodeBranchingVector[i - 1], importantPairs_,
154 nodeSpacing = nonImportantPairsProximity_;
155 // prevX =
156 } else {
157 nodeSpacing = nonImportantPairsGap;
158 }
159 } else if(not tree->isImportantPair<dataType>(
160 nodeBranchingVector[i], importantPairs_,
163 and tree->isImportantPair<dataType>(
164 nodeOrigin, importantPairs_,
167 nodeSpacing = nonImportantPairsProximity_;
168 float newMin = prevX + nodeSpacing;
169 float shiftX = newMin - oldMin;
170
171 // Set y coordinate according difference in persistence
172 dataType nodeBranchingIPers
173 = tree->getNodePersistence<dataType>(nodeBranchingI);
174 float shiftY = nodeBranchingIPers * branchSpacing_;
175 float diffY = retVec[treeSimplexId[nodeBranchingI] * 2 + 1];
176 retVec[treeSimplexId[nodeBranchingI] * 2 + 1]
177 = retVec[treeSimplexId[nodeOrigin] * 2 + 1] - shiftY;
178 diffY = retVec[treeSimplexId[nodeBranchingI] * 2 + 1] - diffY;
179
180 // Shift this branch
181 std::queue<ftm::idNode> queueBranching;
182 queueBranching.emplace(nodeBranchingI);
183 while(!queueBranching.empty()) {
184 ftm::idNode nodeBranchOrigin = queueBranching.front();
185 queueBranching.pop();
186 retVec[treeSimplexId[nodeBranchOrigin] * 2] += shiftX;
187 if(nodeBranchOrigin != nodeBranchingI)
188 retVec[treeSimplexId[nodeBranchOrigin] * 2 + 1] += diffY;
189 if(tree->isBranchOrigin(nodeBranchOrigin))
190 for(auto nodeB : nodeBranching[nodeBranchOrigin])
191 queueBranching.emplace(nodeB);
192 }
193
194 // Update node span X
195 allNodeSpanX[nodeBranchingI]
196 = std::make_tuple(oldMin + shiftX, oldMax + shiftX);
197 float oldMinImp
198 = std::get<0>(allNodeImportantSpanX[nodeBranchingI]);
199 float oldMaxImp
200 = std::get<1>(allNodeImportantSpanX[nodeBranchingI]);
201 allNodeImportantSpanX[nodeBranchingI]
202 = std::make_tuple(oldMinImp + shiftX, oldMaxImp + shiftX);
203
204 // Update x base for next iteration
205 prevX = std::get<1>(allNodeSpanX[nodeBranchingI]);
206 if(tree->isImportantPair<dataType>(
207 nodeBranchingVector[i], importantPairs_,
210 lastIndexImportant = i;
211 prevX = std::get<1>(allNodeImportantSpanX[nodeBranchingI]);
212 if(i < nodeBranchingVector.size() - 1
213 and not tree->isImportantPair<dataType>(
214 nodeBranchingVector[i + 1], importantPairs_,
217 float spanMin
218 = std::get<0>(allNodeSpanX[nodeBranchingVector[0]]);
219 float spanMax
220 = std::get<1>(allNodeImportantSpanX
221 [nodeBranchingVector[lastIndexImportant]]);
222 prevX = (spanMin + spanMax) / 2;
223 }
224 }
225 } // end for nodeBranching
226
227 // Update node span X
228 float spanMin = std::get<0>(allNodeSpanX[nodeBranchingVector[0]]);
229 if(lastIndexImportant != -1) {
230 float spanMaxImp = std::get<1>(
231 allNodeImportantSpanX[nodeBranchingVector[lastIndexImportant]]);
232 allNodeImportantSpanX[nodeOrigin]
233 = std::make_tuple(spanMin, spanMaxImp);
234 } else {
235 allNodeImportantSpanX[nodeOrigin] = std::make_tuple(0, 0);
236 spanMin = 0;
237 }
238 float spanMax = std::get<1>(
239 allNodeSpanX[nodeBranchingVector[nodeBranchingVector.size() - 1]]);
240 allNodeSpanX[nodeOrigin] = std::make_tuple(spanMin, spanMax);
241 } else {
242 allNodeSpanX[nodeOrigin] = std::make_tuple(0, 0);
243 allNodeImportantSpanX[nodeOrigin] = std::make_tuple(0, 0);
244 }
245
246 // Positioning of this node x coordinate
247 float spanMin = std::get<0>(allNodeImportantSpanX[nodeOrigin]);
248 float spanMax = std::get<1>(allNodeImportantSpanX[nodeOrigin]);
249 retVec[treeSimplexId[nodeOrigin] * 2] = (spanMin + spanMax) / 2;
250 }
251
252 // Copy coordinates of nodeOrigin
253 for(auto node : leaves)
254 queue.emplace(node);
255 while(!queue.empty()) {
256 ftm::idNode node = queue.front();
257 queue.pop();
258 ftm::idNode nodeOrigin = tree->getNode(node)->getOrigin();
259 retVec[treeSimplexId[node] * 2] = retVec[treeSimplexId[nodeOrigin] * 2];
260 retVec[treeSimplexId[node] * 2 + 1]
261 = retVec[treeSimplexId[nodeOrigin] * 2 + 1];
262 }
263 }
264
265 // TODO manage multi pers pairs
266 template <class dataType>
268 ftm::FTMTree_MT *tree,
269 std::tuple<double, double, double, double, double, double> oldBounds,
270 double ttkNotUsed(refPersistence),
271 std::vector<float> &retVec) {
273 printMsg("Planar Layout", debug::Priority::VERBOSE);
274
275 // ----------------------------------------------------
276 // Init internal parameters
277 // ----------------------------------------------------
278 Timer t_init;
279 printMsg("Init internal parameters", debug::Priority::VERBOSE);
280
281 auto nPoints = tree->getRealNumberOfNodes();
282 int outNumberOfPoints = nPoints * 2;
283 retVec.resize(outNumberOfPoints);
284
285 int cptNode = 0;
286 std::vector<LongSimplexId> treeSimplexId(tree->getNumberOfNodes());
287 std::vector<ftm::idNode> branching;
288 std::vector<int> branchingID;
289 std::vector<std::vector<ftm::idNode>> nodeBranching;
290 tree->getTreeBranching(branching, branchingID, nodeBranching);
291
292 std::stringstream ss;
293 ss << "INIT = " << t_init.getElapsedTime();
295
296 // ----------------------------------------------------
297 // Iterate through tree
298 // ----------------------------------------------------
299 Timer t_iterate;
300 printMsg("Iterate through tree", debug::Priority::VERBOSE);
301
302 std::queue<ftm::idNode> queue;
303 ftm::idNode treeRoot = tree->getRoot();
304 ftm::idNode treeRootOrigin = tree->getNode(treeRoot)->getOrigin();
305 queue.emplace(treeRoot);
306 while(!queue.empty()) {
307 ftm::idNode node = queue.front();
308 queue.pop();
309
310 // Get and insert point
311 treeSimplexId[node] = cptNode;
312 ++cptNode;
313
314 // Push children to the queue
315 std::vector<ftm::idNode> children;
316 tree->getChildren(node, children);
317 for(size_t i = 0; i < children.size(); ++i) {
318 auto child = children[i];
319 queue.emplace(child);
320 }
321 }
322
323 std::stringstream ss2;
324 ss2 << "ITERATE TREE = " << t_iterate.getElapsedTime();
326
327 // ----------------------------------------------------
328 // Prepositioning coordinates
329 // ----------------------------------------------------
330 std::queue<ftm::idNode> queue2;
331 queue2.emplace(treeRoot);
332 while(!queue2.empty()) {
333 ftm::idNode node = queue2.front();
334 queue2.pop();
335
336 retVec[treeSimplexId[node] * 2]
337 = tree->getValue<dataType>(branching[node]);
338 retVec[treeSimplexId[node] * 2 + 1] = tree->getValue<dataType>(node);
339
340 // Push children to the queue
341 std::vector<ftm::idNode> children;
342 tree->getChildren(node, children);
343 for(auto child : children)
344 queue2.emplace(child);
345 }
346
347 // ----------------------------------------------------
348 // Rescale coordinates
349 // ----------------------------------------------------
350 Timer t_rescale;
351 printMsg("Rescale coordinates ", debug::Priority::VERBOSE);
352
353 float x_min, y_min, x_max, y_max;
354 x_min = std::numeric_limits<float>::max();
355 y_min = std::numeric_limits<float>::max();
356 x_max = std::numeric_limits<float>::lowest();
357 y_max = std::numeric_limits<float>::lowest();
358 for(int i = 0; i < outNumberOfPoints; i += 2) {
359 x_min = std::min(x_min, retVec[i]);
360 x_max = std::max(x_max, retVec[i]);
361 y_min = std::min(y_min, retVec[i + 1]);
362 y_max = std::max(y_max, retVec[i + 1]);
363 }
364 auto newBounds = std::make_tuple(x_min, x_max, y_min, y_max, 0, 0);
365
366 // TODO correctly manage diff and offset if rescaleTreesIndividually_
367 double diff = std::max((std::get<1>(oldBounds) - std::get<0>(oldBounds)),
368 (std::get<3>(oldBounds) - std::get<2>(oldBounds)));
369 double offset = std::max(std::get<0>(oldBounds), std::get<2>(oldBounds));
371 // diff *= getNodePersistence<dataType>(tree, treeRoot) /
372 // refPersistence;
373 diff = tree->getNodePersistence<dataType>(treeRoot);
374 offset = tree->getBirth<dataType>(treeRoot);
375 }
376
377 for(int i = 0; i < outNumberOfPoints; i += 2) {
378 auto divisor1
379 = std::get<1>(newBounds) - std::get<0>(newBounds); // (x_max - x_min)
380 divisor1 = (divisor1 == 0 ? 1 : divisor1);
381 auto divisor2
382 = std::get<3>(newBounds) - std::get<2>(newBounds); // (y_max - y_min)
383 divisor2 = (divisor2 == 0 ? 1 : divisor2);
384
385 // x coordinate
386 retVec[i] = (retVec[i] - std::get<0>(newBounds)) / divisor1;
387 retVec[i] = retVec[i] * diff / 2 + offset;
388
389 // y coordinate
390 retVec[i + 1] = (retVec[i + 1] - std::get<2>(newBounds)) / divisor2;
391 retVec[i + 1] = retVec[i + 1] * diff + offset;
392 }
393
394 std::stringstream ss3;
395 ss3 << "RESCALE COORD. = " << t_rescale.getElapsedTime();
397
398 // ----------------------------------------------------
399 // Call Branch Decomposition Planar Layout if asked
400 // ----------------------------------------------------
402 treePlanarLayoutBDImpl<dataType>(
403 tree, retVec, treeSimplexId, branching, nodeBranching);
404 return;
405 }
406
407 // ----------------------------------------------------
408 // Move nodes given scalars
409 // ----------------------------------------------------
410 Timer t_move;
411 printMsg("Move nodes given scalars", debug::Priority::VERBOSE);
412
413 float rootY = retVec[treeSimplexId[treeRoot] * 2 + 1];
414 float rootOriginY = retVec[treeSimplexId[treeRootOrigin] * 2 + 1];
415 float rootYmin = std::min(rootY, rootOriginY);
416 float rootYmax = std::max(rootY, rootOriginY);
417 auto rootBirthDeath = tree->getBirthDeath<dataType>(treeRoot);
418 const double rootBirth = std::get<0>(rootBirthDeath);
419 const double rootDeath = std::get<1>(rootBirthDeath);
420 for(size_t i = 0; i < tree->getNumberOfNodes(); ++i) {
421 retVec[treeSimplexId[i] * 2 + 1]
422 = (tree->getValue<dataType>(i) - rootBirth) / (rootDeath - rootBirth);
423 retVec[treeSimplexId[i] * 2 + 1]
424 = retVec[treeSimplexId[i] * 2 + 1] * (rootYmax - rootYmin) + rootYmin;
425 }
426
427 std::stringstream ss4;
428 ss4 << "MOVE SCALAR = " << t_move.getElapsedTime();
430
431 // ----------------------------------------------------
432 // Scale pairs given persistence
433 // ----------------------------------------------------
434 Timer t_scale;
435 printMsg("Scale pairs given persistence", debug::Priority::VERBOSE);
436
437 dataType rootPers = tree->getNodePersistence<dataType>(treeRoot);
438
439 std::vector<ftm::idNode> leaves;
440 tree->getLeavesFromTree(leaves);
441 auto compLowerPers = [&](const ftm::idNode a, const ftm::idNode b) {
442 return tree->getNodePersistence<dataType>(a)
443 < tree->getNodePersistence<dataType>(b);
444 };
445 std::sort(leaves.begin(), leaves.end(), compLowerPers);
446 std::stack<ftm::idNode> stack;
447 for(auto node : leaves)
448 stack.emplace(node);
449 std::vector<bool> nodeDone(tree->getNumberOfNodes(), false);
450 while(!stack.empty()) {
451 ftm::idNode node = stack.top();
452 stack.pop();
453 nodeDone[node] = true;
454
455 if(node == treeRoot or node == treeRootOrigin
456 or tree->isNodeAlone(node))
457 continue;
458
459 dataType nodePers = tree->getNodePersistence<dataType>(node);
460 ftm::idNode nodeOrigin = tree->getNode(node)->getOrigin();
461
462 // Manage leaf
463 if(tree->isLeaf(node)) {
464 float nodeDiff = (retVec[treeSimplexId[node] * 2]
465 - retVec[treeSimplexId[nodeOrigin] * 2]);
466 const auto sign = nodeDiff / std::abs(nodeDiff);
467 auto inc = sign * nodePers / rootPers * (rootYmax - rootYmin) / 2;
468 retVec[treeSimplexId[node] * 2]
469 = retVec[treeSimplexId[nodeOrigin] * 2] + inc;
470
471 // Push nodes in the branch to the stack
472 ftm::idNode nodeParent = tree->getParentSafe(node);
473 ftm::idNode oldNodeParent = -1;
474 while(nodeParent != nodeOrigin) {
475 if(not nodeDone[nodeParent])
476 stack.emplace(nodeParent);
477 else
478 break;
479 oldNodeParent = nodeParent;
480 nodeParent = tree->getParentSafe(nodeParent);
481 if(oldNodeParent == nodeParent) {
482 std::stringstream ss5;
483 ss5 << "treePlanarLayoutImpl oldNodeParent == nodeParent";
485 break;
486 }
487 }
488 }
489
490 // Manage saddle
491 if(not tree->isLeaf(node) and not tree->isRoot(node)) {
492 float branchY
493 = retVec[treeSimplexId[tree->getNode(branching[node])->getOrigin()]
494 * 2];
495 retVec[treeSimplexId[node] * 2] = branchY;
496 }
497 }
498
499 std::stringstream ss5;
500 ss5 << "SCALE PERS. = " << t_scale.getElapsedTime();
502
503 // ----------------------------------------------------
504 // Branches positioning and avoid edges crossing
505 // ----------------------------------------------------
506 Timer t_avoid;
507 printMsg("Avoid edges crossing", debug::Priority::VERBOSE);
508
509 bool isJT = tree->isJoinTree<dataType>();
510 auto compValue = [&](const ftm::idNode a, const ftm::idNode b) {
511 return (isJT
512 ? tree->getValue<dataType>(a) < tree->getValue<dataType>(b)
513 : tree->getValue<dataType>(a) > tree->getValue<dataType>(b));
514 };
515 std::vector<std::tuple<float, float, float, float>> allBranchBounds(
516 tree->getNumberOfNodes());
517 std::vector<std::vector<ftm::idNode>> allBranchOrigins(
518 tree->getNumberOfNodes());
519 std::vector<int> allBranchOriginsSize(tree->getNumberOfNodes());
520 std::queue<ftm::idNode> queueCrossing;
521
522 // ----- Get important and non-important pairs gap and store saddle nodes
523 // of each branch
524 int maxSize = std::numeric_limits<int>::lowest();
525 for(auto leaf : leaves)
526 queueCrossing.emplace(leaf);
527 while(!queueCrossing.empty()) {
528 ftm::idNode node = queueCrossing.front();
529 queueCrossing.pop();
530 ftm::idNode nodeOrigin = tree->getNode(node)->getOrigin();
531
532 // Get saddle nodes in the branch
533 std::tuple<std::vector<ftm::idNode>, std::vector<ftm::idNode>>
534 tupBranchOrigins;
535 tree->getBranchOriginsFromThisBranch(nodeOrigin, tupBranchOrigins);
536 allBranchOrigins[nodeOrigin] = std::get<0>(tupBranchOrigins);
537 std::vector<ftm::idNode> nonBranchOrigins
538 = std::get<1>(tupBranchOrigins);
539 allBranchOrigins[nodeOrigin].insert(allBranchOrigins[nodeOrigin].end(),
540 nonBranchOrigins.begin(),
541 nonBranchOrigins.end());
542 std::sort(allBranchOrigins[nodeOrigin].begin(),
543 allBranchOrigins[nodeOrigin].end(), compValue);
544 allBranchOriginsSize[nodeOrigin] = allBranchOrigins[nodeOrigin].size();
545
546 // Get sizes of sub-branches if they are non-important
547 for(size_t i = 0; i < allBranchOrigins[nodeOrigin].size(); ++i) {
548 ftm::idNode branchNodeOrigin = allBranchOrigins[nodeOrigin][i];
549 bool isSubBranchImportant = tree->isImportantPair<dataType>(
550 branchNodeOrigin, importantPairs_,
553 if(not isSubBranchImportant)
554 allBranchOriginsSize[nodeOrigin]
555 += allBranchOriginsSize[branchNodeOrigin];
556 }
557
558 if(tree->isImportantPair<dataType>(nodeOrigin, importantPairs_,
561 maxSize = std::max(maxSize, allBranchOriginsSize[nodeOrigin]);
562 }
563 double nonImportantPairsGap
564 = (rootYmax - rootYmin) * 0.005 * nonImportantPairsSpacing_;
565 double importantPairsGap = (maxSize)*nonImportantPairsGap * 1.05;
566 bool customimportantPairsSpacing_
567 = importantPairsGap < importantPairsSpacing_;
568 if(customimportantPairsSpacing_)
569 importantPairsGap = importantPairsSpacing_;
570
571 // ----- Positioning of branches and avoid conflict
572 for(auto leaf : leaves)
573 queueCrossing.emplace(leaf);
574 while(!queueCrossing.empty()) {
575 ftm::idNode node = queueCrossing.front();
576 queueCrossing.pop();
577 ftm::idNode nodeOrigin = tree->getNode(node)->getOrigin();
578
579 // Prepositioning of branches
580 // auto restrictedBounds = getBranchBounds(retVec, treeSimplexId,
581 // branching, tree, nodeOrigin, true);
582 auto restrictedBounds
583 = std::make_tuple(retVec[treeSimplexId[node] * 2],
584 retVec[treeSimplexId[node] * 2], 0, 0);
585 for(size_t i = 0; i < allBranchOrigins[nodeOrigin].size(); ++i) {
586 ftm::idNode branchNodeOrigin = allBranchOrigins[nodeOrigin][i];
587 ftm::idNode branchNode = tree->getNode(branchNodeOrigin)->getOrigin();
588
589 bool isSubBranchImportant = tree->isImportantPair<dataType>(
590 branchNodeOrigin, importantPairs_,
593 bool toLeft = not isSubBranchImportant;
594
595 // float branchNodeOriginXmin =
596 // std::get<0>(allBranchBounds[branchNodeOrigin]);
597 float branchNodeOriginXmax
598 = std::get<1>(allBranchBounds[branchNodeOrigin]);
599 float shift
600 = toLeft ? std::get<0>(restrictedBounds) - branchNodeOriginXmax :
601 // std::get<1>(restrictedBounds) - branchNodeOriginXmin;
602 std::get<1>(restrictedBounds)
603 - retVec[treeSimplexId[branchNode] * 2];
604 shift += (toLeft ? -1 : 1)
605 * (isSubBranchImportant ? importantPairsGap
606 : nonImportantPairsGap);
607 // shift += (toLeft ? -1 : 1) * nonImportantPairsGap;
608 shiftBranchBounds(retVec, treeSimplexId, branching, allBranchBounds,
609 allBranchOrigins[branchNodeOrigin], tree,
610 branchNodeOrigin, shift);
611 }
612
613 // Shift a branch if conflict with another one
614 for(size_t i = 1; i < allBranchOrigins[nodeOrigin].size(); ++i) {
615 ftm::idNode branchNodeOrigin = allBranchOrigins[nodeOrigin][i];
616 ftm::idNode branchNode = tree->getNode(branchNodeOrigin)->getOrigin();
617 for(size_t j = 0; j < i; ++j) {
618 auto first = allBranchBounds[branchNodeOrigin];
619 ftm::idNode previousBranchNodeOrigin
620 = allBranchOrigins[nodeOrigin][j];
621 auto second = allBranchBounds[previousBranchNodeOrigin];
622
623 bool branchConflict = isConflictingBranchAndBound(
624 first, second, tree, previousBranchNodeOrigin, retVec,
625 treeSimplexId);
626 if(isConflictingBounds(first, second) or branchConflict) {
627
628 // Get left or right orientation given the branch
629 int lastIndex = nodeBranching[branchNodeOrigin].size() - 1;
630 bool isLeft
631 = (retVec
632 [treeSimplexId[nodeBranching[branchNodeOrigin][lastIndex]]
633 * 2]
634 //< retVec[treeSimplexId[nodeOrigin]*2]);
635 < retVec[treeSimplexId[node] * 2]);
636
637 // Get shift
638 float branchNodeOriginXmax = std::get<1>(first);
639 float previousbranchNodeOriginXmin = std::get<0>(second);
640 // float branchNodeOriginXmin = std::get<0>(first);
641 float previousbranchNodeOriginXmax = std::get<1>(second);
642 float shift
643 = isLeft ? previousbranchNodeOriginXmin - branchNodeOriginXmax :
644 // previousbranchNodeOriginXmax - branchNodeOriginXmin;
645 previousbranchNodeOriginXmax
646 - retVec[treeSimplexId[branchNode] * 2];
647 bool isSubBranchImportant = tree->isImportantPair<dataType>(
648 branchNodeOrigin, importantPairs_,
651 shift += (isLeft ? -1 : 1)
652 * (isSubBranchImportant ? importantPairsGap
653 : nonImportantPairsGap);
654 // shift += (isLeft ? -1 : 1) * nonImportantPairsGap;
655
656 // Shift bounds
657 shiftBranchBounds(retVec, treeSimplexId, branching,
658 allBranchBounds,
659 allBranchOrigins[branchNodeOrigin], tree,
660 branchNodeOrigin, shift);
661 }
662 }
663 } // end for
664
665 // TODO optimize get branch bounds by using results previously computed
666 // Get branch x and y bounds
667 allBranchBounds[nodeOrigin]
668 = getBranchBounds(retVec, treeSimplexId, branching, tree, nodeOrigin);
669 } // end while
670
671 // ----- Correction of important/non-important pairs gap
672 // TODO the gap between important pairs can be higher than the minimum gap
673 // needed to avoid conflict. The gap is computed using the maximum number
674 // of non-important pairs attached to an inmportant pairs Unfortunately
675 // the real gap can only be computed here, after the conflicts has been
676 // avoided. The maximum real gap must be calculated and propagated to all
677 // important branches and we also need to manage to avoid conflict with
678 // this new gap. Get real gap
679 double realImportantPairsGap = std::numeric_limits<double>::lowest();
680 /*if(customimportantPairsSpacing_)
681 realImportantPairsGap = importantPairsGap;
682 else{
683 for(auto leaf : leaves)
684 queueCrossing.emplace(leaf);
685 while(!queueCrossing.empty()){
686 ftm::idNode node = queueCrossing.front();
687 queueCrossing.pop();
688 ftm::idNode nodeOrigin = tree->getNode(node)->getOrigin();
689 //if(isRoot(tree, nodeOrigin)) continue; // TODO manage root gap and
690 gap for the others
691
692 bool isBranchImportant = isImportantPair<dataType>(tree, nodeOrigin,
693 importantPairs_); if(not isBranchImportant) continue;
694
695 double gap = retVec[treeSimplexId[node]*2] -
696 std::get<0>(allBranchBounds[nodeOrigin]); realImportantPairsGap =
697 std::max(gap, realImportantPairsGap);
698 }
699 realImportantPairsGap *= 1.05;
700 }*/
701 realImportantPairsGap = importantPairsGap;
702
703 // Shift given real gap
704 for(auto leaf : leaves)
705 queueCrossing.emplace(leaf);
706 while(!queueCrossing.empty()) {
707 ftm::idNode node = queueCrossing.front();
708 queueCrossing.pop();
709 ftm::idNode nodeOrigin = tree->getNode(node)->getOrigin();
710
711 bool isBranchImportant = tree->isImportantPair<dataType>(
714 if(not isBranchImportant)
715 continue;
716
717 for(size_t i = 0; i < allBranchOrigins[nodeOrigin].size(); ++i) {
718 ftm::idNode branchNodeOrigin = allBranchOrigins[nodeOrigin][i];
719 bool isSubBranchImportant = tree->isImportantPair<dataType>(
720 branchNodeOrigin, importantPairs_,
723 double shift = 0;
724 if(not isSubBranchImportant) {
725 double gap = retVec[treeSimplexId[node] * 2]
726 - std::get<0>(allBranchBounds[nodeOrigin]);
727 shift
728 = -(realImportantPairsGap - gap) * nonImportantPairsProximity_;
729 } else {
730 shift = -(importantPairsGap
731 - realImportantPairsGap); // TODO multi shift depending on
732 // conflict
733 }
734 shiftBranchBounds(retVec, treeSimplexId, branching, allBranchBounds,
735 allBranchOrigins[branchNodeOrigin], tree,
736 branchNodeOrigin, shift);
737 }
738 }
739
740 std::stringstream ss6;
741 ss6 << "AVOID CROSSING = " << t_avoid.getElapsedTime();
744 }
745
746 template <class dataType>
748 ftm::FTMTree_MT *tree,
749 std::tuple<double, double, double, double, double, double> oldBounds,
750 double refPersistence,
751 std::vector<float> &res) {
752 treePlanarLayoutImpl<dataType>(tree, oldBounds, refPersistence, res);
753 }
754
755 template <class dataType>
757 std::vector<float> &res) {
758 res.resize(tree->getRealNumberOfNodes() * 2);
759 int cptNode = 0;
760 std::queue<ftm::idNode> queue;
761 ftm::idNode treeRoot = tree->getRoot();
762 queue.emplace(treeRoot);
763 while(!queue.empty()) {
764 ftm::idNode node = queue.front();
765 queue.pop();
766
767 // Get and insert point
768 auto birthDeath = tree->getBirthDeath<dataType>(node);
769 res[cptNode * 2] = std::get<0>(birthDeath);
770 res[cptNode * 2 + 1] = std::get<1>(birthDeath);
771 ++cptNode;
772
773 // Push children to the queue
774 std::vector<ftm::idNode> children;
775 tree->getChildren(node, children);
776 for(auto child : children)
777 queue.emplace(child);
778 }
779 }
780
781 // ==========================================================================
782 // Bounds Utils
783 // ==========================================================================
784 void printTuple(std::tuple<float, float, float, float> tup) {
786 std::stringstream ss;
787 ss << std::get<0>(tup) << " _ " << std::get<1>(tup) << " _ "
788 << std::get<2>(tup) << " _ " << std::get<3>(tup) << " _ ";
790 }
791
792 // Branchroot must be a non-leaf node
793 std::tuple<float, float, float, float>
794 getBranchBounds(std::vector<float> &retVec,
795 std::vector<LongSimplexId> &treeSimplexId,
796 std::vector<ftm::idNode> &branching,
797 ftm::FTMTree_MT *tree,
798 ftm::idNode branchRoot,
799 bool restricted = false) {
800 float x_min = std::numeric_limits<float>::max();
801 float y_min = std::numeric_limits<float>::max();
802 float x_max = std::numeric_limits<float>::lowest();
803 float y_max = std::numeric_limits<float>::lowest();
804
805 std::queue<ftm::idNode> queue;
806 queue.emplace(branchRoot);
807 while(!queue.empty()) {
808 ftm::idNode node = queue.front();
809 queue.pop();
810
811 // Skip if we go in the branch in which is branchRoot
812 if(branching[node] != branchRoot
813 and tree->getParentSafe(node) == branchRoot and node != branchRoot)
814 continue;
815
816 // Skip if restricted
817 if(restricted and !tree->isLeaf(node) and branching[node] != branchRoot
818 and node != branchRoot)
819 continue;
820
821 y_min = std::min(y_min, retVec[treeSimplexId[node] * 2 + 1]);
822 y_max = std::max(y_max, retVec[treeSimplexId[node] * 2 + 1]);
823 if(node != branchRoot) {
824 x_min = std::min(x_min, retVec[treeSimplexId[node] * 2]);
825 x_max = std::max(x_max, retVec[treeSimplexId[node] * 2]);
826 }
827
828 std::vector<ftm::idNode> children;
829 tree->getChildren(node, children);
830 for(auto child : children)
831 queue.emplace(child);
832 }
833
834 return std::make_tuple(x_min, x_max, y_min, y_max);
835 }
836
838 std::tuple<float, float, float, float> first,
839 std::tuple<float, float, float, float> second) {
840 return (std::get<0>(first) <= std::get<0>(second) + 1e-6
841 and std::get<0>(second) <= std::get<1>(first) + 1e-6)
842 or (std::get<0>(first) <= std::get<1>(second) + 1e-6
843 and std::get<1>(second) <= std::get<1>(first) + 1e-6);
844 }
845
846 bool isConflictingBoundsX(std::tuple<float, float, float, float> first,
847 std::tuple<float, float, float, float> second) {
848 return isConflictingBoundsXOneWay(first, second)
849 or isConflictingBoundsXOneWay(second, first);
850 }
851
853 std::tuple<float, float, float, float> first,
854 std::tuple<float, float, float, float> second) {
855 return (std::get<2>(first) <= std::get<2>(second) + 1e-6
856 and std::get<2>(second) <= std::get<3>(first) + 1e-6)
857 or (std::get<2>(first) <= std::get<3>(second) + 1e-6
858 and std::get<3>(second) <= std::get<3>(first) + 1e-6);
859 }
860
861 bool isConflictingBoundsY(std::tuple<float, float, float, float> first,
862 std::tuple<float, float, float, float> second) {
863 return isConflictingBoundsYOneWay(first, second)
864 or isConflictingBoundsYOneWay(second, first);
865 }
866
867 bool isConflictingBounds(std::tuple<float, float, float, float> first,
868 std::tuple<float, float, float, float> second) {
869 return isConflictingBoundsX(first, second)
870 and isConflictingBoundsY(first, second);
871 }
872
873 bool
874 isConflictingBranchAndBound(std::tuple<float, float, float, float> first,
875 std::tuple<float, float, float, float> second,
876 ftm::FTMTree_MT *tree,
877 ftm::idNode branchNodeOrigin,
878 std::vector<float> &retVec,
879 std::vector<LongSimplexId> &treeSimplexId) {
880 float xBranchNodeOrigin = retVec[treeSimplexId[branchNodeOrigin] * 2];
881 float xBranchNode
882 = retVec[treeSimplexId[tree->getNode(branchNodeOrigin)->getOrigin()]
883 * 2];
884 float myMin = std::min(xBranchNode, xBranchNodeOrigin);
885 float myMax = std::max(xBranchNode, xBranchNodeOrigin);
886 auto branchBounds = std::make_tuple(myMin, myMax, 0, 0);
887 return isConflictingBoundsX(first, branchBounds)
888 and isConflictingBoundsY(first, second);
889 }
890
891 std::tuple<float, float, float, float>
892 shiftBranchBoundsTuple(std::tuple<float, float, float, float> branchBound,
893 float realShift) {
894 return std::make_tuple(std::get<0>(branchBound) + realShift,
895 std::get<1>(branchBound) + realShift,
896 std::get<2>(branchBound),
897 std::get<3>(branchBound));
898 }
899
901 std::vector<float> &retVec,
902 std::vector<LongSimplexId> &treeSimplexId,
903 std::vector<ftm::idNode> &branching,
904 std::vector<std::tuple<float, float, float, float>> &allBranchBounds,
905 std::vector<ftm::idNode> &branchOrigins,
906 ftm::FTMTree_MT *tree,
907 ftm::idNode branchRoot,
908 float shift) {
909 std::queue<ftm::idNode> queue;
910 queue.emplace(branchRoot);
911 while(!queue.empty()) {
912 ftm::idNode node = queue.front();
913 queue.pop();
914
915 if(branching[node] != branchRoot
916 and tree->getParentSafe(node) == branchRoot and node != branchRoot)
917 continue;
918
919 if(node != branchRoot)
920 retVec[treeSimplexId[node] * 2] += shift;
921
922 std::vector<ftm::idNode> children;
923 tree->getChildren(node, children);
924 for(auto child : children)
925 queue.emplace(child);
926 }
927 allBranchBounds[branchRoot]
928 = shiftBranchBoundsTuple(allBranchBounds[branchRoot], shift);
929 for(auto node : branchOrigins)
930 allBranchBounds[node]
931 = shiftBranchBoundsTuple(allBranchBounds[node], shift);
932 }
933
935 std::tuple<double, double, double, double, double, double> &tup,
936 std::vector<double> &vec) {
937 vec = std::vector<double>{std::get<0>(tup), std::get<1>(tup),
938 std::get<2>(tup), std::get<3>(tup),
939 std::get<4>(tup), std::get<5>(tup)};
940 }
941
942 std::tuple<double, double, double, double, double, double>
943 vectorToTuple(std::vector<double> &vec) {
944 return std::make_tuple(vec[0], vec[1], vec[2], vec[3], vec[4], vec[5]);
945 }
946
947 std::tuple<double, double, double, double, double, double> getMaximalBounds(
948 std::vector<std::tuple<double, double, double, double, double, double>>
949 &allBounds,
950 std::vector<int> &clusteringAssignmentT,
951 int clusterID) {
952 double x_min = std::numeric_limits<double>::max();
953 double y_min = std::numeric_limits<double>::max();
954 double z_min = std::numeric_limits<double>::max();
955 double x_max = std::numeric_limits<double>::lowest();
956 double y_max = std::numeric_limits<double>::lowest();
957 double z_max = std::numeric_limits<double>::lowest();
958 for(size_t i = 0; i < allBounds.size(); ++i)
959 if(clusteringAssignmentT[i] == clusterID) {
960 x_min = std::min(x_min, std::get<0>(allBounds[i]));
961 x_max = std::max(x_max, std::get<1>(allBounds[i]));
962 y_min = std::min(y_min, std::get<2>(allBounds[i]));
963 y_max = std::max(y_max, std::get<3>(allBounds[i]));
964 z_min = std::min(z_min, std::get<4>(allBounds[i]));
965 z_max = std::max(z_max, std::get<5>(allBounds[i]));
966 }
967 return std::make_tuple(x_min, x_max, y_min, y_max, z_min, z_max);
968 }
969
970 // ==========================================================================
971 // Utils
972 // ==========================================================================
973 void parseExcludeImportantPairsString(std::string &excludeString,
974 std::vector<double> &excludeVector) {
975 excludeVector.clear();
976 if(excludeString.empty())
977 return;
978 std::string s{excludeString};
979 std::string delimiter = ",";
980
981 size_t pos = 0;
982 std::string token;
983 while((pos = s.find(delimiter)) != std::string::npos) {
984 token = s.substr(0, pos);
985 excludeVector.emplace_back(std::stod(token));
986 s.erase(0, pos + delimiter.length());
987 }
988 excludeVector.emplace_back(std::stod(s));
989 }
990 };
991
992} // namespace ttk
#define ttkNotUsed(x)
Mark function/method parameters that are not used in the function body at all.
Definition: BaseClass.h:47
Minimalist debugging class.
Definition: Debug.h:88
int printMsg(const std::string &msg, const debug::Priority &priority=debug::Priority::INFO, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cout) const
Definition: Debug.h:118
bool isConflictingBoundsY(std::tuple< float, float, float, float > first, std::tuple< float, float, float, float > second)
void tupleToVector(std::tuple< double, double, double, double, double, double > &tup, std::vector< double > &vec)
std::tuple< float, float, float, float > shiftBranchBoundsTuple(std::tuple< float, float, float, float > branchBound, float realShift)
void treePlanarLayoutBDImpl(ftm::FTMTree_MT *tree, std::vector< float > &retVec, std::vector< LongSimplexId > &treeSimplexId, std::vector< ftm::idNode > &ttkNotUsed(branching), std::vector< std::vector< ftm::idNode > > &nodeBranching)
void shiftBranchBounds(std::vector< float > &retVec, std::vector< LongSimplexId > &treeSimplexId, std::vector< ftm::idNode > &branching, std::vector< std::tuple< float, float, float, float > > &allBranchBounds, std::vector< ftm::idNode > &branchOrigins, ftm::FTMTree_MT *tree, ftm::idNode branchRoot, float shift)
void printTuple(std::tuple< float, float, float, float > tup)
std::tuple< float, float, float, float > getBranchBounds(std::vector< float > &retVec, std::vector< LongSimplexId > &treeSimplexId, std::vector< ftm::idNode > &branching, ftm::FTMTree_MT *tree, ftm::idNode branchRoot, bool restricted=false)
bool isConflictingBranchAndBound(std::tuple< float, float, float, float > first, std::tuple< float, float, float, float > second, ftm::FTMTree_MT *tree, ftm::idNode branchNodeOrigin, std::vector< float > &retVec, std::vector< LongSimplexId > &treeSimplexId)
void setExcludeImportantPairsLower(std::string &d)
bool isConflictingBounds(std::tuple< float, float, float, float > first, std::tuple< float, float, float, float > second)
std::vector< double > excludeImportantPairsLowerValues_
void treePlanarLayoutImpl(ftm::FTMTree_MT *tree, std::tuple< double, double, double, double, double, double > oldBounds, double ttkNotUsed(refPersistence), std::vector< float > &retVec)
std::tuple< double, double, double, double, double, double > vectorToTuple(std::vector< double > &vec)
void setExcludeImportantPairsHigher(std::string &d)
void persistenceDiagramPlanarLayout(ftm::FTMTree_MT *tree, std::vector< float > &res)
std::vector< double > excludeImportantPairsHigherValues_
bool isConflictingBoundsYOneWay(std::tuple< float, float, float, float > first, std::tuple< float, float, float, float > second)
bool isConflictingBoundsXOneWay(std::tuple< float, float, float, float > first, std::tuple< float, float, float, float > second)
void parseExcludeImportantPairsString(std::string &excludeString, std::vector< double > &excludeVector)
std::tuple< double, double, double, double, double, double > getMaximalBounds(std::vector< std::tuple< double, double, double, double, double, double > > &allBounds, std::vector< int > &clusteringAssignmentT, int clusterID)
bool isConflictingBoundsX(std::tuple< float, float, float, float > first, std::tuple< float, float, float, float > second)
void treePlanarLayout(ftm::FTMTree_MT *tree, std::tuple< double, double, double, double, double, double > oldBounds, double refPersistence, std::vector< float > &res)
~MergeTreeVisualization() override=default
double getElapsedTime()
Definition: Timer.h:15
const scalarType & getValue(SimplexId nodeId) const
Definition: FTMTree_MT.h:339
dataType getNodePersistence(idNode nodeId)
idNode getNumberOfNodes() const
Definition: FTMTree_MT.h:389
std::tuple< dataType, dataType > getBirthDeath(idNode nodeId)
void getTreeBranching(std::vector< idNode > &branching, std::vector< int > &branchingID, std::vector< std::vector< idNode > > &nodeBranching)
bool isRoot(idNode nodeId)
idNode getParentSafe(idNode nodeId)
bool isImportantPair(idNode nodeId, double threshold, std::vector< double > &excludeLower, std::vector< double > &excludeHigher)
void getChildren(idNode nodeId, std::vector< idNode > &res)
bool isLeaf(idNode nodeId)
bool isNodeAlone(idNode nodeId)
bool isBranchOrigin(idNode nodeId)
void getBranchOriginsFromThisBranch(idNode node, std::tuple< std::vector< idNode >, std::vector< idNode > > &res)
void getLeavesFromTree(std::vector< idNode > &res)
Node * getNode(idNode nodeId)
Definition: FTMTree_MT.h:393
dataType getBirth(idNode nodeId)
SimplexId getOrigin() const
Definition: FTMNode.h:64
unsigned int idNode
Node index in vect_nodes_.
Definition: FTMDataTypes.h:39
The Topology ToolKit.