TTK
Loading...
Searching...
No Matches
FTMTreeUtils.cpp
Go to the documentation of this file.
1#include <FTMTree.h>
2#include <FTMTreeUtils.h>
3#include <iostream>
4
5void ttk::ftm::printTreesStats(std::vector<FTMTree_MT *> &trees) {
6 for(auto tree : trees)
7 tree->printTreeStats();
8}
9
10namespace ttk {
11 namespace ftm {
12
13 // --------------------
14 // Is
15 // --------------------
17 unsigned int origin = (unsigned int)this->getNode(nodeId)->getOrigin();
18 return origin != nullNodes && origin < this->getNumberOfNodes();
19 }
20
22 return this->getNode(nodeId)->getNumberOfUpSuperArcs() == 0;
23 }
24
26 return this->getNode(nodeId)->getNumberOfDownSuperArcs() == 0;
27 }
28
30 return this->isRoot(nodeId) and this->isLeaf(nodeId);
31 }
32
34 idNode treeRoot = this->getRoot();
35 return (unsigned int)this->getNode(treeRoot)->getOrigin() == treeRoot;
36 }
37
39 return this->getParentSafe(this->getNode(nodeId)->getOrigin()) != nodeId;
40 }
41
43 bool merged = this->isNodeAlone(nodeId)
44 or this->isNodeAlone(this->getNode(nodeId)->getOrigin());
45 auto nodeIdOrigin = this->getNode(nodeId)->getOrigin();
46 merged
47 = merged or nodeIdOrigin == this->getNode(nodeIdOrigin)->getOrigin();
48 return merged;
49 }
50
52 return nodeId >= this->getNumberOfNodes();
53 }
54
56 idNode treeRoot = this->getRoot();
57 unsigned int cptNodeAlone = 0;
58 idNode otherNode = treeRoot;
59 for(unsigned int i = 0; i < this->getNumberOfNodes(); ++i)
60 if(this->isNodeAlone(i))
61 cptNodeAlone++;
62 else if(i != treeRoot)
63 otherNode = i;
64 // unsigned int origin = (unsigned
65 // int)tree->getNode(otherNode)->getOrigin();
66 idNode treeRootOrigin = this->getNode(treeRoot)->getOrigin();
67 return (otherNode != treeRoot
68 and this->getNumberOfNodes() - cptNodeAlone == 2
69 and (treeRootOrigin == otherNode or treeRootOrigin == treeRoot));
70 /*return (otherNode != treeRoot and cptNodeAlone ==
71 tree->getNumberOfNodes()-2 and (origin == treeRoot or otherNode ==
72 origin));*/
73 }
74
75 // Do not normalize node is if root or son of a merged root
77 auto nodeIdParent = this->getParentSafe(nodeId);
78 return this->isRoot(nodeId)
79 or (this->isRoot(nodeIdParent)
80 and nodeIdParent
81 == (unsigned int)this->getNode(nodeIdParent)
82 ->getOrigin());
83 // and nodeIdOrigin == nodeIdParent) )
84 }
85
87 auto nodeOriginOrigin
88 = (unsigned int)this->getNode(this->getNode(nodeId)->getOrigin())
89 ->getOrigin();
90 return nodeOriginOrigin != nodeId;
91 }
92
93 // --------------------
94 // Get
95 // --------------------
97 for(idNode node = 0; node < this->getNumberOfNodes(); ++node)
98 if(this->isRoot(node) and !this->isLeaf(node))
99 return node;
100 return nullNodes;
101 }
102
104 if(!this->isRoot(nodeId)) {
105 // _ Nodes in merge trees should have only one parent
106 idSuperArc arcId = this->getNode(nodeId)->getUpSuperArcId(0);
107 idNode parentNodeId = this->getSuperArc(arcId)->getUpNodeId();
108 return parentNodeId;
109 }
110 return nodeId;
111 }
112
114 std::vector<idNode> &childrens) {
115 childrens.clear();
116 for(idSuperArc i = 0;
117 i < this->getNode(nodeId)->getNumberOfDownSuperArcs(); ++i) {
118 idSuperArc arcId = this->getNode(nodeId)->getDownSuperArcId(i);
119 childrens.push_back(this->getSuperArc(arcId)->getDownNodeId());
120 }
121 }
122
123 void FTMTree_MT::getLeavesFromTree(std::vector<idNode> &treeLeaves) {
124 treeLeaves.clear();
125 for(idNode i = 0; i < this->getNumberOfNodes(); ++i) {
126 if(this->isLeaf(i) and !this->isRoot(i))
127 treeLeaves.push_back(i);
128 }
129 }
130
132 auto leaves = this->getLeaves();
133 return leaves.size();
134 }
135
137 int cpt = 0;
138 for(idNode i = 0; i < this->getNumberOfNodes(); ++i)
139 cpt += this->isNodeAlone(i) ? 1 : 0;
140 return cpt;
141 }
142
144 return this->getNumberOfNodes() - this->getNumberOfNodeAlone();
145 }
146
148 idNode node, std::tuple<std::vector<idNode>, std::vector<idNode>> &res) {
149 std::vector<idNode> branchOrigins, nonBranchOrigins;
150
151 idNode nodeOrigin = this->getNode(node)->getOrigin();
152 idNode nodeParent = this->getParentSafe(nodeOrigin);
153 while(nodeParent != node) {
154 if(this->isBranchOrigin(nodeParent))
155 branchOrigins.push_back(nodeParent);
156 else
157 nonBranchOrigins.push_back(nodeParent);
158 nodeParent = this->getParentSafe(nodeParent);
159 }
160
161 res = std::make_tuple(branchOrigins, nonBranchOrigins);
162 }
163
165 std::vector<idNode> &branching,
166 std::vector<int> &branchingID,
167 std::vector<std::vector<idNode>> &nodeBranching) {
168 branching = std::vector<idNode>(this->getNumberOfNodes());
169 branchingID = std::vector<int>(this->getNumberOfNodes(), -1);
170 nodeBranching
171 = std::vector<std::vector<idNode>>(this->getNumberOfNodes());
172 int branchID = 0;
173 std::queue<idNode> queue;
174 queue.emplace(this->getRoot());
175 while(!queue.empty()) {
176 idNode node = queue.front();
177 queue.pop();
178 if(this->isLeaf(node))
179 continue;
180 auto nodeOrigin = this->getNode(node)->getOrigin();
181 idNode parentNodeOrigin = nodeOrigin;
182 while(parentNodeOrigin != node) {
183 branching[parentNodeOrigin] = node;
184 branchingID[parentNodeOrigin] = branchID;
185 nodeBranching[node].push_back(parentNodeOrigin);
186 parentNodeOrigin = this->getParentSafe(parentNodeOrigin);
187 }
188 if(this->isRoot(node)) {
189 branching[node] = node;
190 branchingID[node] = branchID;
191 }
192 ++branchID;
193 std::vector<idNode> children;
194 this->getChildren(node, children);
195 for(idNode child : children)
196 queue.emplace(child);
197 }
198 }
199
200 void FTMTree_MT::getTreeBranching(std::vector<idNode> &branching,
201 std::vector<int> &branchingID) {
202 std::vector<std::vector<idNode>> nodeBranching;
203 this->getTreeBranching(branching, branchingID, nodeBranching);
204 }
205
206 void FTMTree_MT::getAllRoots(std::vector<idNode> &roots) {
207 roots.clear();
208 for(idNode node = 0; node < this->getNumberOfNodes(); ++node)
209 if(this->isRoot(node) and !this->isLeaf(node))
210 roots.push_back(node);
211 }
212
214 int noRoot = 0;
215 for(idNode node = 0; node < this->getNumberOfNodes(); ++node)
216 if(this->isRoot(node) and !this->isLeaf(node))
217 ++noRoot;
218 return noRoot;
219 }
220
222 return this->getNode(nodeId)->getNumberOfDownSuperArcs();
223 }
224
226 int maxDepth = 0;
227 std::queue<std::tuple<idNode, int>> queue;
228 queue.push(std::make_tuple(this->getRoot(), 0));
229 while(!queue.empty()) {
230 auto tup = queue.front();
231 queue.pop();
232 idNode node = std::get<0>(tup);
233 int depth = std::get<1>(tup);
234 maxDepth = std::max(maxDepth, depth);
235 std::vector<idNode> children;
236 this->getChildren(node, children);
237 for(idNode child : children)
238 queue.push(std::make_tuple(child, depth + 1));
239 }
240 return maxDepth;
241 }
242
244 int level = 0;
245 auto root = this->getRoot();
246 int noRoot = this->getNumberOfRoot();
247 if(noRoot != 1) {
248 std::stringstream ss;
249 ss << "problem, there is " << noRoot << " root(s)";
250 printErr(ss.str());
251 this->printTree2();
252 this->printTree();
253 }
254 if(this->isNodeAlone(nodeId))
255 return 0;
256 while(nodeId != root) {
257 nodeId = this->getParentSafe(nodeId);
258 ++level;
259 }
260 return level;
261 }
262
263 void FTMTree_MT::getAllNodeLevel(std::vector<int> &allNodeLevel) {
264 allNodeLevel = std::vector<int>(this->getNumberOfNodes());
265 std::queue<std::tuple<idNode, int>> queue;
266 queue.push(std::make_tuple(this->getRoot(), 0));
267 while(!queue.empty()) {
268 auto tup = queue.front();
269 queue.pop();
270 idNode node = std::get<0>(tup);
271 int level = std::get<1>(tup);
272 allNodeLevel[node] = level;
273 std::vector<idNode> children;
274 this->getChildren(node, children);
275 for(idNode child : children)
276 queue.push(std::make_tuple(child, level + 1));
277 }
278 }
279
281 std::vector<std::vector<idNode>> &levelToNode) {
282 std::vector<int> allNodeLevel;
283 this->getAllNodeLevel(allNodeLevel);
284 int maxLevel = *max_element(allNodeLevel.begin(), allNodeLevel.end());
285 levelToNode = std::vector<std::vector<idNode>>(maxLevel + 1);
286 for(unsigned int i = 0; i < allNodeLevel.size(); ++i) {
287 levelToNode[allNodeLevel[i]].push_back(i);
288 }
289 }
290
291 void FTMTree_MT::getBranchSubtree(std::vector<idNode> &branching,
292 idNode branchRoot,
293 std::vector<idNode> &branchSubtree) {
294 branchSubtree.clear();
295 std::queue<idNode> queue;
296 queue.push(branchRoot);
297 while(!queue.empty()) {
298 idNode node = queue.front();
299 queue.pop();
300
301 if(branching[node] != branchRoot
302 and this->getParentSafe(node) == branchRoot and node != branchRoot)
303 continue;
304
305 branchSubtree.push_back(node);
306 std::vector<idNode> children;
307 this->getChildren(node, children);
308 for(idNode child : children)
309 queue.push(child);
310 }
311 }
312
313 // --------------------
314 // Persistence
315 // --------------------
317 std::vector<std::vector<idNode>> &treeMultiPers) {
318 treeMultiPers
319 = std::vector<std::vector<idNode>>(this->getNumberOfNodes());
320 for(unsigned int i = 0; i < this->getNumberOfNodes(); ++i)
321 if(this->isLeaf(i) and this->isNodeOriginDefined(i)
322 and not this->isNodeAlone(i)
323 and this->getNode(this->getNode(i)->getOrigin())->getOrigin()
324 != (int)i)
325 treeMultiPers[this->getNode(i)->getOrigin()].push_back(i);
326 }
327
328 // --------------------
329 // Set
330 // --------------------
331 void FTMTree_MT::setParent(idNode nodeId, idNode newParentNodeId) {
332 this->deleteParent(nodeId);
333 this->makeSuperArc(nodeId, newParentNodeId);
334 }
335
336 // --------------------
337 // Delete
338 // --------------------
339 // Delete node by keeping subtree
341 if(this->isRoot(nodeId) and !this->isLeaf(nodeId))
342 printErr("deletion of root!");
343
344 idNode parentNodeId = this->getParentSafe(nodeId);
345 if(!this->isRoot(nodeId)) {
346 // Delete down arc from parent node
347 // _ Nodes in trees should have only one parent
348 idSuperArc nodeArcId = this->getNode(nodeId)->getUpSuperArcId(0);
349 this->getNode(parentNodeId)->removeDownSuperArc(nodeArcId);
350 }
351 // Delete up arc from child nodes
352 for(idSuperArc i = 0;
353 i < this->getNode(nodeId)->getNumberOfDownSuperArcs(); ++i) {
354 idSuperArc arcId = this->getNode(nodeId)->getDownSuperArcId(i);
355 idNode childNodeId = this->getSuperArc(arcId)->getDownNodeId();
356 this->getNode(childNodeId)->removeUpSuperArc(arcId);
357 if(!this->isRoot(nodeId))
358 this->makeSuperArc(childNodeId, parentNodeId);
359 }
360 // Reset deleted node
361 this->getNode(nodeId)->clearDownSuperArcs();
362 this->getNode(nodeId)->clearUpSuperArcs();
363 }
364
365 void FTMTree_MT::deleteIthUpArc(idNode nodeId, int arcIth) {
366 idSuperArc nodeArcId = this->getNode(nodeId)->getUpSuperArcId(arcIth);
367 // Delete down arc from old parent
368 idNode parentNodeId = this->getSuperArc(nodeArcId)->getUpNodeId();
369 this->getNode(parentNodeId)->removeDownSuperArc(nodeArcId);
370 // Delete up arc from node
371 this->getNode(nodeId)->removeUpSuperArc(nodeArcId);
372 }
373
375 if(!this->isRoot(nodeId)) {
376 // _ Nodes in trees should have only one parent
377 this->deleteIthUpArc(nodeId, 0);
378 }
379 }
380
382 std::queue<idNode> queue;
383 queue.push(nodeId);
384 while(!queue.empty()) {
385 idNode node = queue.front();
386 queue.pop();
387 std::vector<idNode> children;
388 this->getChildren(node, children);
389 for(idNode child : children)
390 queue.push(child);
391 this->deleteNode(node);
392 }
393 }
394
395 // --------------------
396 // Create/Delete/Modify Tree
397 // --------------------
399 // Add Nodes
400 for(unsigned int i = 0; i < tree->getNumberOfNodes(); ++i)
401 this->makeNode(i);
402 for(unsigned int i = 0; i < tree->getNumberOfNodes(); ++i)
403 this->getNode(i)->setOrigin(tree->getNode(i)->getOrigin());
404
405 // Add Arcs
406 for(unsigned int i = 0; i < tree->getNumberOfNodes(); ++i) {
407 for(unsigned int j = 0;
408 j < tree->getNode(i)->getNumberOfDownSuperArcs(); ++j) {
409 auto superArcId = tree->getNode(i)->getDownSuperArcId(j);
410 this->makeSuperArc(tree->getSuperArc(superArcId)->getDownNodeId(), i);
411 }
412 }
413 }
414
415 // --------------------
416 // Utils
417 // --------------------
418 void FTMTree_MT::printNodeSS(idNode node, std::stringstream &ss) {
419 ss << "(" << node << ") \\ ";
420
421 std::vector<idNode> children;
422 this->getChildren(node, children);
423 for(idNode child : children)
424 ss << "+" << child << " ";
425
426 if(!this->isRoot(node))
427 ss << " / +" << this->getParentSafe(node);
428 ss << std::endl;
429 }
430
431 std::stringstream FTMTree_MT::printTree(bool doPrint) {
432 std::stringstream ss;
433 std::vector<idNode> allRoots;
434 this->getAllRoots(allRoots);
435 if(allRoots.size() != 1)
436 ss << allRoots.size() << " roots" << std::endl;
437 for(unsigned int i = 0; i < allRoots.size(); ++i) {
438 if(allRoots.size() != 1)
439 ss << i << " _ ";
440 ss << "Nodes----------" << std::endl;
441 std::queue<idNode> queue;
442 queue.push(allRoots[i]);
443 while(!queue.empty()) {
444 idNode node = queue.front();
445 queue.pop();
446
447 printNodeSS(node, ss);
448
449 std::vector<idNode> children;
450 this->getChildren(node, children);
451 for(idNode child : children)
452 queue.push(child);
453 }
454 }
455 if(allRoots.size() == 0)
456 for(unsigned int i = 0; i < this->getNumberOfNodes(); ++i)
457 // if(not tree->isNodeAlone(i))
458 printNodeSS(i, ss);
459
460 if(doPrint)
461 printMsg(ss.str());
462 return ss;
463 }
464
465 std::stringstream FTMTree_MT::printTreeStats(bool doPrint) {
466 auto noNodesT = this->getNumberOfNodes();
467 auto noNodes = this->getRealNumberOfNodes();
468 std::stringstream ss;
469 ss << "tree [node: " << noNodes << " / " << noNodesT;
470 ss << ", depth: " << this->getTreeDepth() << "]";
471 if(doPrint)
472 printMsg(ss.str());
473 return ss;
474 }
475
476 std::stringstream
478 std::stringstream ss;
479 std::vector<std::vector<idNode>> vec;
481 for(unsigned int i = 0; i < vec.size(); ++i)
482 if(vec[i].size() != 0) {
483 ss << i << " : ";
484 for(auto t : vec[i])
485 ss << t << " ";
486 ss << std::endl;
487 }
488
489 if(doPrint)
490 printMsg(ss.str());
491 return ss;
492 }
493
494 // --------------------
495 // Make tree utils
496 // --------------------
498 ftm::idNode treeRoot = 0;
499 for(unsigned int i = 0; i < tree->getNumberOfNodes(); ++i) {
500 if(tree->getNode(i)->getNumberOfDownSuperArcs() != 0
501 and tree->getNode(i)->getNumberOfUpSuperArcs() == 0)
502 treeRoot = i;
503 }
504
505 for(unsigned int i = 0; i < tree->getNumberOfNodes(); ++i)
506 if(tree->getNode(i)->getNumberOfUpSuperArcs() > 1) {
507 ftm::idNode lowestParent = std::numeric_limits<ftm::idNode>::max();
508 for(long unsigned int j = 0;
509 j < tree->getNode(i)->getNumberOfUpSuperArcs(); ++j) {
510 auto tParent
511 = tree->getSuperArc(tree->getNode(i)->getUpSuperArcId(j))
512 ->getUpNodeId();
513 lowestParent = (lowestParent > tParent) ? tParent : lowestParent;
514 }
515
516 for(long unsigned int j = 0;
517 j < tree->getNode(i)->getNumberOfUpSuperArcs(); ++j) {
518 ftm::idSuperArc nodeArcId = tree->getNode(i)->getUpSuperArcId(j);
519 auto tParent = tree->getSuperArc(nodeArcId)->getUpNodeId();
520 if(tParent != lowestParent) {
521
522 if(tParent == treeRoot) {
523 for(long unsigned int k = 0;
524 k < tree->getNode(i)->getNumberOfDownSuperArcs(); ++k) {
525 ftm::idSuperArc nodeArcId2
526 = tree->getNode(i)->getDownSuperArcId(k);
527 auto tChildren
528 = tree->getSuperArc(nodeArcId2)->getDownNodeId();
529 if(tChildren > i) {
530 tree->getNode(i)->removeDownSuperArc(nodeArcId2);
531 tree->getNode(tChildren)->removeUpSuperArc(nodeArcId2);
532 tree->makeSuperArc(tChildren, treeRoot);
533 break;
534 }
535 }
536 }
537
538 // Delete down arc from old parent
539 tree->getNode(tParent)->removeDownSuperArc(nodeArcId);
540 // Delete up arc from node
541 tree->getNode(i)->removeUpSuperArc(nodeArcId);
542 }
543 }
544 }
545 }
546
548 for(unsigned int i = 0; i < tree->getNumberOfNodes(); ++i) {
549 for(unsigned int j = 0; j < tree->getNode(i)->getNumberOfUpSuperArcs();
550 ++j) {
551 ftm::idSuperArc nodeArcId = tree->getNode(i)->getUpSuperArcId(j);
552 auto tParent = tree->getSuperArc(nodeArcId)->getUpNodeId();
553 if(tParent == i) {
554 // Delete down arc
555 tree->getNode(i)->removeDownSuperArc(nodeArcId);
556 // Delete up arc
557 tree->getNode(i)->removeUpSuperArc(nodeArcId);
558 }
559 }
560 }
561 }
562
563 } // namespace ftm
564} // namespace ttk
int printMsg(const std::string &msg, const debug::Priority &priority=debug::Priority::INFO, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cout) const
Definition: Debug.h:118
int printErr(const std::string &msg, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cerr) const
Definition: Debug.h:149
bool notNeedToNormalize(idNode nodeId)
void getLevelToNode(std::vector< std::vector< idNode > > &res)
bool isNodeIdInconsistent(idNode nodeId)
SuperArc * getSuperArc(idSuperArc i)
Definition: FTMTree_MT.h:367
idNode getNumberOfNodes() const
Definition: FTMTree_MT.h:389
void setParent(idNode nodeId, idNode newParentNodeId)
bool isNodeMerged(idNode nodeId)
int getNumberOfChildren(idNode nodeId)
idNode getDownNodeId(const SuperArc *a)
Definition: FTMTree_MT.cpp:371
std::stringstream printMultiPersOriginsVectorFromTree(bool doPrint=true)
void getTreeBranching(std::vector< idNode > &branching, std::vector< int > &branchingID, std::vector< std::vector< idNode > > &nodeBranching)
bool isRoot(idNode nodeId)
void getMultiPersOriginsVectorFromTree(std::vector< std::vector< idNode > > &res)
idNode getParentSafe(idNode nodeId)
void getBranchSubtree(std::vector< idNode > &branching, idNode branchRoot, std::vector< idNode > &res)
bool isNodeOriginDefined(idNode nodeId)
void printNodeSS(idNode node, std::stringstream &ss)
void deleteIthUpArc(idNode nodeId, int arcIth)
int getNodeLevel(idNode nodeId)
void getAllRoots(std::vector< idNode > &res)
void getChildren(idNode nodeId, std::vector< idNode > &res)
void deleteNode(idNode nodeId)
const std::vector< idNode > & getLeaves() const
Definition: FTMTree_MT.h:407
bool isMultiPersPair(idNode nodeId)
idNode makeNode(SimplexId vertexId, SimplexId linked=nullVertex)
Definition: FTMTree_MT.cpp:473
bool isLeaf(idNode nodeId)
void deleteParent(idNode nodeId)
bool isNodeAlone(idNode nodeId)
idSuperArc makeSuperArc(idNode downNodeId, idNode upNodeId)
Definition: FTMTree_MT.cpp:499
bool isBranchOrigin(idNode nodeId)
void copyMergeTreeStructure(FTMTree_MT *tree)
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
void getAllNodeLevel(std::vector< int > &res)
std::stringstream printTree(bool doPrint=true)
void deleteSubtree(idNode nodeId)
bool isThereOnlyOnePersistencePair()
std::stringstream printTreeStats(bool doPrint=true)
idSuperArc getUpSuperArcId(idSuperArc neighborId) const
Definition: FTMNode.h:105
idSuperArc clearUpSuperArcs()
Definition: FTMNode.h:133
idSuperArc getNumberOfDownSuperArcs() const
Definition: FTMNode.h:82
idSuperArc getDownSuperArcId(idSuperArc neighborId) const
Definition: FTMNode.h:94
void removeUpSuperArc(idSuperArc idSa)
Definition: FTMNode.h:158
idSuperArc clearDownSuperArcs()
Definition: FTMNode.h:127
void setOrigin(SimplexId linked)
Definition: FTMNode.h:72
void removeDownSuperArc(idSuperArc idSa)
Definition: FTMNode.h:146
SimplexId getOrigin() const
Definition: FTMNode.h:64
idSuperArc getNumberOfUpSuperArcs() const
Definition: FTMNode.h:86
idNode getUpNodeId() const
Definition: FTMSuperArc.h:68
idNode getDownNodeId() const
Definition: FTMSuperArc.h:72
long unsigned int idSuperArc
SuperArc index in vect_superArcs_.
Definition: FTMDataTypes.h:37
void removeSelfLink(FTMTree_MT *tree)
void printTreesStats(std::vector< ftm::FTMTree_MT * > &trees)
Definition: FTMTreeUtils.cpp:5
unsigned int idNode
Node index in vect_nodes_.
Definition: FTMDataTypes.h:39
void manageInconsistentArcsMultiParent(FTMTree_MT *tree)
The Topology ToolKit.