TTK
Loading...
Searching...
No Matches
FTMTreeUtils_Template.h
Go to the documentation of this file.
1
7
8#pragma once
9
10#include <FTMTree_MT.h>
11
12namespace ttk {
13 namespace ftm {
14
15 // --------------------
16 // Is
17 // --------------------
18 template <class dataType>
20 auto root = this->getRoot();
21 std::vector<idNode> rootChildren;
22 this->getChildren(root, rootChildren);
23 idNode child = rootChildren[0];
24 if(this->isFullMerge()) {
25 dataType min = std::numeric_limits<dataType>::max();
26 for(unsigned int i = 0; i < this->getNumberOfNodes(); ++i) {
27 dataType value = this->getValue<dataType>(i);
28 if(not this->isNodeAlone(i) and value < min) {
29 min = value;
30 child = i;
31 }
32 }
33 }
34 return this->getValue<dataType>(root) > this->getValue<dataType>(child);
35 }
36
37 template <class dataType>
39 double threshold,
40 std::vector<double> &excludeLower,
41 std::vector<double> &excludeHigher) {
42 dataType rootPers = this->getNodePersistence<dataType>(this->getRoot());
43 if(threshold > 1)
44 threshold /= 100.0;
45 threshold = rootPers * threshold;
46 auto pers = this->getNodePersistence<dataType>(nodeId);
47
48 // Excluded pairs
49 bool isExcluded = false;
50 if(excludeLower.size() == excludeHigher.size())
51 for(unsigned i = 0; i < excludeLower.size(); ++i) {
52 isExcluded |= (pers > rootPers * excludeLower[i] / 100.0
53 and pers < rootPers * excludeHigher[i] / 100.0);
54 }
55
56 return pers > threshold and not isExcluded;
57 }
58
59 template <class dataType>
60 bool FTMTree_MT::isImportantPair(idNode nodeId, double threshold) {
61 std::vector<double> excludeLower, excludeHigher;
62 return this->isImportantPair<dataType>(
63 nodeId, threshold, excludeLower, excludeHigher);
64 }
65
66 template <class dataType>
68 auto parentBirthDeath
69 = this->getBirthDeath<dataType>(this->getParentSafe(nodeId));
70 dataType parentBirth = std::get<0>(parentBirthDeath);
71 dataType parentDeath = std::get<1>(parentBirthDeath);
72 auto birthDeath = this->getBirthDeath<dataType>(nodeId);
73 dataType birth = std::get<0>(birthDeath);
74 dataType death = std::get<1>(birthDeath);
75 bool parentInconsistent = parentDeath < death or parentBirth > birth;
76 return parentInconsistent;
77 }
78
79 template <class dataType>
81 bool inconsistency = false;
82 std::queue<idNode> queue;
83 queue.emplace(this->getRoot());
84 while(!queue.empty()) {
85 idNode node = queue.front();
86 queue.pop();
87 if(!this->isRoot(node) and this->isParentInconsistent<dataType>(node)) {
88 printErr("inconsistency");
89 this->printNode2<dataType>(node);
90 this->printNode2<dataType>(this->getParentSafe(node));
91 inconsistency = true;
92 }
93 std::vector<idNode> children;
94 this->getChildren(node, children);
95 for(idNode child : children)
96 queue.emplace(child);
97 }
98 return inconsistency;
99 }
100
101 // --------------------
102 // Get
103 // --------------------
104 template <class dataType>
106 dataType maxPers = std::numeric_limits<dataType>::lowest();
107 int maxIndex = -1;
108 auto root = this->getRoot();
109 for(unsigned int j = 0; j < this->getNumberOfNodes(); ++j) {
110 if(j != root and this->isNodeOriginDefined(j)
111 and this->getNode(j)->getOrigin() == (int)root) {
112 dataType nodePers = this->getNodePersistence<dataType>(j);
113 if(nodePers > maxPers) {
114 maxPers = nodePers;
115 maxIndex = j;
116 }
117 }
118 }
119 return maxIndex;
120 }
121
122 template <class dataType>
124 idNode lowestNode = nodeStart;
125 bool isJT = this->isJoinTree<dataType>();
126 dataType bestVal = isJT ? std::numeric_limits<dataType>::max()
127 : std::numeric_limits<dataType>::lowest();
128 std::queue<idNode> queue;
129 queue.emplace(nodeStart);
130 while(!queue.empty()) {
131 idNode node = queue.front();
132 queue.pop();
133 dataType val = this->getValue<dataType>(node);
134 if((val < bestVal and isJT) or (val > bestVal and not isJT)) {
135 lowestNode = node;
136 bestVal = val;
137 }
138 std::vector<idNode> children;
139 this->getChildren(node, children);
140 for(idNode child : children)
141 queue.emplace(child);
142 }
143 return lowestNode;
144 }
145
146 // --------------------
147 // Persistence
148 // --------------------
149 template <class dataType>
150 std::tuple<dataType, dataType>
152 dataType scalar1 = this->getValue<dataType>(nodeId1);
153 dataType scalar2 = this->getValue<dataType>(nodeId2);
154 dataType birth = std::min(scalar1, scalar2);
155 dataType death = std::max(scalar1, scalar2);
156 return std::make_tuple(birth, death);
157 }
158
159 template <class dataType>
160 std::tuple<dataType, dataType>
162 auto nodeValue = this->getValue<dataType>(nodeId1);
163 auto node2Value = this->getValue<dataType>(nodeId2);
164 auto nodeBirth = (nodeValue < node2Value ? nodeId1 : nodeId2);
165 auto nodeDeath = (nodeValue < node2Value ? nodeId2 : nodeId1);
166 return std::make_tuple(nodeBirth, nodeDeath);
167 }
168
169 template <class dataType>
170 std::tuple<dataType, dataType> FTMTree_MT::getBirthDeath(idNode nodeId) {
171 // Avoid error if origin is not defined
172 if(this->isNodeOriginDefined(nodeId)) {
173 return this->getBirthDeathFromIds<dataType>(
174 nodeId, this->getNode(nodeId)->getOrigin());
175 }
176 return std::make_tuple(0.0, 0.0);
177 }
178
179 template <class dataType>
180 std::tuple<ftm::idNode, ftm::idNode>
182 if(this->isNodeOriginDefined(nodeId)) {
183 return this->getBirthDeathNodeFromIds<dataType>(
184 nodeId, this->getNode(nodeId)->getOrigin());
185 }
186 return std::make_tuple(0.0, 0.0);
187 }
188
189 template <class dataType>
190 std::tuple<dataType, dataType> FTMTree_MT::getMergedRootBirthDeath() {
191 if(!this->isFullMerge())
192 return this->getBirthDeath<dataType>(this->getRoot());
193 return this->getBirthDeathFromIds<dataType>(
194 this->getRoot(), this->getMergedRootOrigin<dataType>());
195 }
196
197 template <class dataType>
198 std::tuple<ftm::idNode, ftm::idNode>
200 if(!this->isFullMerge())
201 return this->getBirthDeathNode<dataType>(this->getRoot());
202 return this->getBirthDeathNodeFromIds<dataType>(
203 this->getRoot(), this->getMergedRootOrigin<dataType>());
204 }
205
206 template <class dataType>
207 dataType FTMTree_MT::getBirth(idNode nodeId) {
208 return std::get<0>(this->getBirthDeath<dataType>(nodeId));
209 }
210
211 template <class dataType>
213 std::tuple<dataType, dataType> birthDeath
214 = this->getBirthDeath<dataType>(nodeId);
215 return std::get<1>(birthDeath) - std::get<0>(birthDeath);
216 }
217
218 template <class dataType>
220 idNode root = this->getRoot();
221 bool fullMerge = this->isFullMerge();
222
223 // Classic case
224 if(not fullMerge)
225 return this->getNodePersistence<dataType>(this->getRoot());
226
227 // Full merge case
228 dataType maxPers = std::numeric_limits<dataType>::lowest();
229 for(unsigned int i = 0; i < this->getNumberOfNodes(); ++i)
230 if(/*not this->isNodeAlone(i) and*/ this->isNodeOriginDefined(i)
231 and this->getNode(i)->getOrigin() == (int)root)
232 maxPers = std::max(maxPers, this->getNodePersistence<dataType>(i));
233
234 return maxPers;
235 }
236
237 template <class dataType>
239 idNode root = this->getRoot();
240 dataType pers = std::numeric_limits<dataType>::lowest();
241 ftm::idNode nodeSecMax = -1;
242 for(unsigned int i = 0; i < this->getNumberOfNodes(); ++i) {
243 if(not this->isRoot(i) and not this->isNodeAlone(i)
244 and this->isNodeOriginDefined(i)) {
245 idNode nodeOrigin = this->getNode(i)->getOrigin();
246 if(not(nodeOrigin == root
247 and this->getNode(nodeOrigin)->getOrigin() == (int)i)) {
248 auto nodePers = this->getNodePersistence<dataType>(i);
249 if(pers < nodePers) {
250 pers = nodePers;
251 nodeSecMax = i;
252 }
253 }
254 }
255 }
256 return nodeSecMax;
257 }
258
259 template <class dataType>
261 return this->getNodePersistence<dataType>(
262 this->getSecondMaximumPersistenceNode<dataType>());
263 }
264
265 template <class dataType>
267 std::vector<std::tuple<idNode, idNode, dataType>> &pairs, bool useBD) {
268 std::vector<idNode> nodes;
269 if(useBD) {
270 for(unsigned int i = 0; i < this->getNumberOfNodes(); ++i)
271 if(!this->isNodeAlone(i) and this->getNode(i)->getOrigin() != (int)i)
272 nodes.push_back(i);
273 } else
274 this->getLeavesFromTree(nodes);
275 for(auto node : nodes) {
276 auto pers = this->getNodePersistence<dataType>(node);
277 pairs.push_back(
278 std::make_tuple(node, this->getNode(node)->getOrigin(), pers));
279 }
280 auto comp = [&](const std::tuple<idNode, idNode, dataType> a,
281 const std::tuple<idNode, idNode, dataType> b) {
282 return std::get<2>(a) < std::get<2>(b);
283 };
284 sort(pairs.begin(), pairs.end(), comp);
285 }
286
287 template <class dataType>
288 std::vector<idNode> FTMTree_MT::getMultiPersOrigins(bool useBD) {
289 std::vector<idNode> multiPersOrigins;
290
291 std::vector<std::tuple<idNode, idNode, dataType>> pairs;
292 this->getPersistencePairsFromTree(pairs, useBD);
293 // std::vector<idNode> origins(this->getNumberOfNodes(), -1);
294 std::vector<std::vector<idNode>> origins(this->getNumberOfNodes());
295 std::vector<bool> birthFound(this->getNumberOfNodes(), false);
296 for(auto pair : pairs) {
297 idNode nodeBirth = std::get<0>(pair);
298 idNode nodeDeath = std::get<1>(pair);
299
300 origins[nodeDeath].push_back(nodeBirth);
301 birthFound[nodeBirth] = true;
302 }
303
304 for(unsigned int i = 0; i < origins.size(); ++i)
305 if(birthFound[i])
306 for(auto node : origins[i])
307 multiPersOrigins.push_back(node);
308
309 return multiPersOrigins;
310 }
311
312 // --------------------
313 // Utils
314 // --------------------
315 template <class dataType>
316 std::stringstream FTMTree_MT::printNode2(idNode nodeId, bool doPrint) {
317 auto origin = this->getNode(nodeId)->getOrigin();
318 std::stringstream ss;
319 ss << "nodeId = " << nodeId << " (" << this->getValue<dataType>(nodeId)
320 << ") _ originId = " << this->getNode(nodeId)->getOrigin();
321 if(not this->isNodeIdInconsistent(origin))
322 ss << " (" << this->getValue<dataType>(origin) << ")";
323 if(doPrint)
324 printMsg(ss.str());
325 return ss;
326 }
327
328 template <class dataType>
329 std::stringstream FTMTree_MT::printMergedRoot(bool doPrint) {
330 std::stringstream ss;
331 ss << this->getRoot() << " (" << this->getValue<dataType>(this->getRoot())
332 << ") _ ";
333 auto mergedRootOrigin = this->getMergedRootOrigin<dataType>();
334 ss << mergedRootOrigin;
335 if(not this->isNodeIdInconsistent(mergedRootOrigin))
336 ss << " (" << this->getValue<dataType>(mergedRootOrigin) << ")";
337 ss << " _ " << this->getNodePersistence<dataType>(this->getRoot());
338 if(not this->isNodeIdInconsistent(mergedRootOrigin))
339 ss << " _ " << this->getNodePersistence<dataType>(mergedRootOrigin);
340 ss << std::endl;
341 if(doPrint)
342 printMsg(ss.str());
343 return ss;
344 }
345
346 template <class dataType>
347 std::stringstream FTMTree_MT::printTreeScalars(bool printNodeAlone,
348 bool doPrint) {
349 std::stringstream wholeSS;
350 std::streamsize sSize = std::cout.precision();
351 for(unsigned int i = 0; i < this->getNumberOfNodes(); ++i) {
352 idNode iOrigin
353 = this->isNodeOriginDefined(i) ? this->getNode(i)->getOrigin() : i;
354 if(printNodeAlone
355 or (not printNodeAlone
356 and (not this->isNodeAlone(i)
357 or not this->isNodeAlone(iOrigin)))) {
358 std::stringstream ss;
359 ss << i << " _ " << std::setprecision(12)
360 << this->getValue<dataType>(i);
361 if(doPrint)
362 printMsg(ss.str());
363 wholeSS << ss.str() << std::endl;
364 }
365 }
366 if(doPrint)
368 std::cout.precision(sSize);
369 return wholeSS;
370 }
371
372 template <class dataType>
373 std::stringstream FTMTree_MT::printPairsFromTree(bool useBD,
374 bool printPairs,
375 bool doPrint) {
376 std::stringstream ss;
377 std::vector<std::tuple<idNode, idNode, dataType>> pairs;
378 this->getPersistencePairsFromTree(pairs, useBD);
379 ss << "size=" << pairs.size() << std::endl;
380 if(printPairs)
381 for(auto pair : pairs) {
382 ss << std::get<0>(pair) << " ("
383 << this->getValue<dataType>(std::get<0>(pair)) << ") _ ";
384 ss << std::get<1>(pair) << " ("
385 << this->getValue<dataType>(std::get<1>(pair)) << ") _ ";
386 ss << std::get<2>(pair) << std::endl;
387 }
388
389 if(doPrint) {
390 printMsg(ss.str());
392 }
393 return ss;
394 }
395
396 template <class dataType>
397 std::stringstream FTMTree_MT::printMultiPersPairsFromTree(bool useBD,
398 bool printPairs,
399 bool doPrint) {
400 std::vector<std::tuple<idNode, idNode, dataType>> pairs;
401 this->getPersistencePairsFromTree(pairs, useBD);
402 std::vector<int> noOrigin(this->getNumberOfNodes(), 0);
403 int noMultiPers = 0;
404 for(auto pair : pairs) {
405 noOrigin[std::get<0>(pair)]++;
406 noMultiPers += (noOrigin[std::get<0>(pair)] > 1) ? 1 : 0;
407 noOrigin[std::get<1>(pair)]++;
408 noMultiPers += (noOrigin[std::get<1>(pair)] > 1) ? 1 : 0;
409 }
410 std::stringstream ss;
411 ss << "Number of multi pers pairs : " << noMultiPers << std::endl;
412 if(printPairs) {
413 auto multiPers = this->getMultiPersOrigins<dataType>(useBD);
414 for(auto node : multiPers)
415 ss << node << std::endl;
416 }
417 if(doPrint) {
418 printMsg(ss.str());
420 }
421 return ss;
422 }
423
424 } // namespace ftm
425} // 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
std::vector< ftm::idNode > getMultiPersOrigins(bool useBD)
std::stringstream printMultiPersPairsFromTree(bool useBD=false, bool printPairs=true, bool doPrint=true)
bool isNodeIdInconsistent(idNode nodeId)
dataType getNodePersistence(idNode nodeId)
idNode getNumberOfNodes() const
Definition: FTMTree_MT.h:389
std::stringstream printTreeScalars(bool printNodeAlone=true, bool doPrint=true)
std::tuple< dataType, dataType > getBirthDeath(idNode nodeId)
bool isRoot(idNode nodeId)
std::tuple< ftm::idNode, ftm::idNode > getBirthDeathNode(idNode nodeId)
bool isParentInconsistent(ftm::idNode nodeId)
idNode getParentSafe(idNode nodeId)
bool isNodeOriginDefined(idNode nodeId)
std::tuple< ftm::idNode, ftm::idNode > getMergedRootBirthDeathNode()
ftm::idNode getSecondMaximumPersistenceNode()
bool isImportantPair(idNode nodeId, double threshold, std::vector< double > &excludeLower, std::vector< double > &excludeHigher)
std::stringstream printNode2(idNode nodeId, bool doPrint=true)
void getPersistencePairsFromTree(std::vector< std::tuple< ftm::idNode, ftm::idNode, dataType > > &pairs, bool useBD)
void getChildren(idNode nodeId, std::vector< idNode > &res)
std::tuple< dataType, dataType > getMergedRootBirthDeath()
std::stringstream printPairsFromTree(bool useBD=false, bool printPairs=true, bool doPrint=true)
std::tuple< dataType, dataType > getBirthDeathFromIds(idNode nodeId1, idNode nodeId2)
bool isNodeAlone(idNode nodeId)
bool isJT() const
Definition: FTMTree_MT.h:289
void getLeavesFromTree(std::vector< idNode > &res)
idNode getLowestNode(idNode nodeStart)
Node * getNode(idNode nodeId)
Definition: FTMTree_MT.h:393
std::stringstream printMergedRoot(bool doPrint=true)
dataType getBirth(idNode nodeId)
std::tuple< dataType, dataType > getBirthDeathNodeFromIds(idNode nodeId1, idNode nodeId2)
SimplexId getOrigin() const
Definition: FTMNode.h:64
unsigned int idNode
Node index in vect_nodes_.
Definition: FTMDataTypes.h:39
The Topology ToolKit.