TTK
Loading...
Searching...
No Matches
FTMTreeUtils.h
Go to the documentation of this file.
1
6
7#pragma once
8
9#include <FTMTree_MT.h>
10#include <stack>
11
12namespace ttk {
13 namespace ftm {
14
15 // --------------------
16 // Utils
17 // --------------------
18 void printTreesStats(std::vector<ftm::FTMTree_MT *> &trees);
19
20 template <class dataType>
21 void printTree(MergeTree<dataType> &tree, bool doPrint = true) {
22 tree.tree.printTree(doPrint);
23 }
24
25 template <class dataType>
29
30 template <class dataType>
32 bool printNodeAlone = true) {
33 printTreeScalars<dataType>(&(tree.tree), printNodeAlone);
34 }
35
36 template <class dataType>
37 void mergeTreeToFTMTree(std::vector<MergeTree<dataType>> &trees,
38 std::vector<ftm::FTMTree_MT *> &treesT) {
39 treesT.clear();
40 for(MergeTree<dataType> &t : trees)
41 treesT.push_back(&(t.tree));
42 }
43
44 template <class dataType>
46 MergeTree<double> &newMt) {
47 auto newScalarsValues = std::make_shared<std::vector<double>>();
48 for(auto val : *mt.scalarsValues)
49 newScalarsValues->push_back(static_cast<double>(val));
50 auto newScalars = std::make_shared<ftm::Scalars>(*mt.scalars);
51 newMt = MergeTree<double>(newScalars, newScalarsValues, mt.params);
52 newMt.tree.copyMergeTreeStructure(&(mt.tree));
53 }
54
55 template <class dataType>
57 std::vector<MergeTree<double>> &newMts) {
58 newMts.clear();
59 for(auto &mt : mts) {
61 mergeTreeTemplateToDouble<dataType>(mt, newMt);
62 newMts.push_back(newMt);
63 }
64 }
65
66 template <class dataType>
68 std::vector<std::vector<MergeTree<dataType>>> &mts,
69 std::vector<std::vector<MergeTree<double>>> &newMts) {
70 newMts.clear();
71 newMts.reserve(mts.size());
72 for(auto &mt : mts) {
73 std::vector<MergeTree<double>> newMt;
74 mergeTreesTemplateToDouble<dataType>(mt, newMt);
75 newMts.emplace_back(newMt);
76 }
77 }
78
79 template <class dataType>
81 MergeTree<dataType> &newMt) {
82 auto newScalarsValues = std::make_shared<std::vector<dataType>>();
83 for(auto val : *mt.scalarsValues)
84 newScalarsValues->push_back(static_cast<dataType>(val));
85 auto newScalars = std::make_shared<ftm::Scalars>(*mt.scalars);
86 newMt = MergeTree<dataType>(newScalars, newScalarsValues, mt.params);
87 newMt.tree.copyMergeTreeStructure(&(mt.tree));
88 }
89
90 template <class dataType>
92 std::vector<MergeTree<dataType>> &newMts) {
93 newMts.clear();
94 for(auto &mt : mts) {
96 mergeTreeDoubleToTemplate<dataType>(mt, newMt);
97 newMts.push_back(newMt);
98 }
99 }
100
101 template <class dataType>
103 std::vector<std::vector<MergeTree<double>>> &mts,
104 std::vector<std::vector<MergeTree<dataType>>> &newMts) {
105 newMts.clear();
106 newMts.reserve(mts.size());
107 for(auto &mt : mts) {
108 std::vector<MergeTree<dataType>> newMt;
109 mergeTreesDoubleToTemplate<dataType>(mt, newMt);
110 newMts.emplace_back(newMt);
111 }
112 }
113
114 // --------------------
115 // Make tree utils
116 // --------------------
118
119 void removeSelfLink(FTMTree_MT *tree);
120
121 // --------------------
122 // MergeTree
123 // --------------------
124 template <class dataType>
126 // Init Scalars
127 auto scalars = std::make_shared<ftm::Scalars>();
128 scalars->size = scalarSize;
129 scalars->values = (void *)nullptr;
130
131 // Init Params
132 auto params = std::make_shared<ftm::Params>();
133 params->treeType = ftm::Join_Split;
134
135 // Init tree
136 MergeTree<dataType> const mergeTree(scalars, params);
137
138 return mergeTree;
139 }
140
141 template <class dataType>
143 std::vector<dataType> &scalarsVector) {
144 mergeTree.scalarsValues
145 = std::make_shared<std::vector<dataType>>(scalarsVector);
146 mergeTree.scalars->values = (void *)(mergeTree.scalarsValues->data());
147 mergeTree.scalars->size = mergeTree.scalarsValues->size();
148 }
149
150 template <class dataType>
152 std::vector<dataType> &scalarsVector) {
153 scalarsVector.clear();
154 for(unsigned int i = 0; i < tree->getNumberOfNodes(); ++i)
155 scalarsVector.push_back(tree->getValue<dataType>(i));
156 }
157
158 template <class dataType>
160 std::vector<dataType> &scalarsVector) {
161 getTreeScalars<dataType>(&(mergeTree.tree), scalarsVector);
162 }
163
164 template <class dataType>
166 bool doSplitMultiPersPairs = false) {
167 std::vector<dataType> scalarsVector;
168 getTreeScalars<dataType>(tree, scalarsVector);
169
170 // Get multi persistence pairs
171 std::vector<ftm::idNode> multiPersOrigins;
172 if(doSplitMultiPersPairs) {
173 multiPersOrigins = tree->getMultiPersOrigins<dataType>(true);
174 for(ftm::idNode const nodeOrigin : multiPersOrigins) {
175 scalarsVector[nodeOrigin]
176 = tree->getValue<dataType>(tree->getNode(nodeOrigin)->getOrigin());
177 scalarsVector.push_back(tree->getValue<dataType>(nodeOrigin));
178 }
179 }
180
181 // Create new tree
182 MergeTree<dataType> mergeTree
183 = createEmptyMergeTree<dataType>(scalarsVector.size());
184 ftm::FTMTree_MT *treeNew = &(mergeTree.tree);
185 setTreeScalars<dataType>(mergeTree, scalarsVector);
186
187 // Copy tree structure
188 treeNew->copyMergeTreeStructure(tree);
189
190 // Add multi persistence nodes origins
191 if(doSplitMultiPersPairs) {
192 for(ftm::idNode const nodeOrigin : multiPersOrigins) {
193 int const nodeCpt = treeNew->getNumberOfNodes();
194 treeNew->makeNode(nodeCpt);
195 treeNew->getNode(nodeCpt)->setOrigin(nodeOrigin);
196 treeNew->getNode(nodeOrigin)->setOrigin(nodeCpt);
197 }
198 }
199
200 return mergeTree;
201 }
202
203 template <class dataType>
205 bool doSplitMultiPersPairs = false) {
206 return copyMergeTree<dataType>(&(mergeTree.tree), doSplitMultiPersPairs);
207 }
208
209 // Remove unused nodes
210 template <class dataType>
212 std::vector<int> &nodeCorr,
213 bool useBD = true) {
214 // Create new tree
215 int const newNoNodes = tree->getRealNumberOfNodes() * 2;
216 MergeTree<dataType> mTreeNew = createEmptyMergeTree<dataType>(newNoNodes);
217 ftm::FTMTree_MT *treeNew = &(mTreeNew.tree);
218 std::vector<dataType> newScalarsVector(newNoNodes, 0);
219
220 // Copy the old tree structure
221 std::vector<int> nodeDone(tree->getNumberOfNodes(), 0);
222 nodeCorr = std::vector<int>(tree->getNumberOfNodes(), -1);
223 std::vector<std::vector<ftm::idNode>> treeMultiPers;
224 if(not useBD)
225 tree->getMultiPersOriginsVectorFromTree(treeMultiPers);
226 std::queue<ftm::idNode> queue;
227 std::vector<idNode> leaves;
228 tree->getLeavesFromTree(leaves);
229 for(auto leaf : leaves)
230 queue.push(leaf);
231 while(!queue.empty()) {
232 ftm::idNode const node = queue.front();
233 queue.pop();
234 ftm::idNode nodeOrigin = tree->getNode(node)->getOrigin();
235 if(tree->isRoot(node) and tree->isFullMerge())
236 nodeOrigin = tree->getMergedRootOrigin<dataType>();
237
238 if(useBD) {
239 int nodeOriginIndex = treeNew->getNumberOfNodes();
240 if(nodeCorr[nodeOrigin] == -1)
241 treeNew->makeNode(nodeOriginIndex);
242 else
243 nodeOriginIndex = nodeCorr[nodeOrigin];
244 int nodeIndex = treeNew->getNumberOfNodes();
245 if(nodeCorr[node] == -1)
246 treeNew->makeNode(nodeIndex);
247 else
248 nodeIndex = nodeCorr[node];
249
250 if(nodeCorr[nodeOrigin] == -1)
251 treeNew->getNode(nodeOriginIndex)->setOrigin(nodeIndex);
252 treeNew->getNode(nodeIndex)->setOrigin(nodeOriginIndex);
253
254 newScalarsVector[nodeOriginIndex]
255 = tree->getValue<dataType>(nodeOrigin);
256 newScalarsVector[nodeIndex] = tree->getValue<dataType>(node);
257 nodeCorr[nodeOrigin] = nodeOriginIndex;
258 nodeCorr[node] = nodeIndex;
259 } else {
260 int const nodeCpt = treeNew->getNumberOfNodes();
261 treeNew->makeNode(nodeCpt);
262 if(!tree->isLeaf(node)) {
263 treeNew->getNode(nodeCpt)->setOrigin(nodeCorr[nodeOrigin]);
264 if(not(tree->isRoot(node) and node == nodeOrigin))
265 treeNew->getNode(nodeCorr[nodeOrigin])->setOrigin(nodeCpt);
266 for(auto nodeMultiPers : treeMultiPers[node])
267 treeNew->getNode(nodeCorr[nodeMultiPers])->setOrigin(nodeCpt);
268 } else if(tree->isNodeAlone(nodeOrigin)) { // saddle merged
269 treeNew->makeNode(nodeCpt + 1);
270 newScalarsVector[nodeCpt + 1]
271 = tree->getValue<dataType>(nodeOrigin);
272 nodeCorr[nodeOrigin] = nodeCpt + 1;
273 treeNew->getNode(nodeCpt)->setOrigin(nodeCorr[nodeOrigin]);
274 treeNew->getNode(nodeCorr[nodeOrigin])->setOrigin(nodeCpt);
275 }
276 newScalarsVector[nodeCpt] = tree->getValue<dataType>(node);
277 nodeCorr[node] = nodeCpt;
278 }
279
280 std::vector<idNode> children;
281 tree->getChildren(node, children);
282 for(idNode const child : children)
283 treeNew->makeSuperArc(nodeCorr[child], nodeCorr[node]);
284
285 if(!tree->isRoot(node)) {
286 ftm::idNode const parent = tree->getParentSafe(node);
287 nodeDone[parent] += 1;
288 if(nodeDone[parent] == tree->getNumberOfChildren(parent))
289 queue.push(parent);
290 }
291 }
292
293 // Manage full merge
294 auto treeRoot = tree->getRoot();
295 if(tree->getNode(treeRoot)->getOrigin() == (int)treeRoot) {
296 auto treeNewRoot = treeNew->getRoot();
297 auto treeNewRootOrigin = treeNew->getNode(treeNewRoot)->getOrigin();
298 newScalarsVector[treeNewRootOrigin]
299 = tree->getValue<dataType>(tree->getMergedRootOrigin<dataType>());
300 treeNew->getNode(treeNewRoot)->setOrigin(treeNewRoot);
301 }
302
303 // Set new scalars
304 setTreeScalars<dataType>(mTreeNew, newScalarsVector);
305
306 // Return new tree
307 return mTreeNew;
308 }
309
310 template <class dataType>
312 std::vector<int> &nodeCorr,
313 bool useBD = true) {
314 mTree = cleanMergeTree<dataType>(&(mTree.tree), nodeCorr, useBD);
315 }
316
317 template <class dataType>
318 void cleanMergeTree(MergeTree<dataType> &mTree, bool useBD = true) {
319 std::vector<int> nodeCorr;
320 cleanMergeTree<dataType>(mTree, nodeCorr, useBD);
321 }
322
323 } // namespace ftm
324} // namespace ttk
TTK container representing a node of the FTMTree_MT.
std::vector< ftm::idNode > getMultiPersOrigins(bool useBD)
const scalarType & getValue(SimplexId nodeId) const
Definition FTMTree_MT.h:339
idNode getNumberOfNodes() const
Definition FTMTree_MT.h:389
int getNumberOfChildren(idNode nodeId)
bool isRoot(idNode nodeId)
void getMultiPersOriginsVectorFromTree(std::vector< std::vector< idNode > > &res)
idNode getParentSafe(idNode nodeId)
void getChildren(idNode nodeId, std::vector< idNode > &res)
idNode makeNode(SimplexId vertexId, SimplexId linked=nullVertex)
bool isLeaf(idNode nodeId)
bool isNodeAlone(idNode nodeId)
idSuperArc makeSuperArc(idNode downNodeId, idNode upNodeId)
void copyMergeTreeStructure(FTMTree_MT *tree)
void getLeavesFromTree(std::vector< idNode > &res)
Node * getNode(idNode nodeId)
Definition FTMTree_MT.h:393
std::stringstream printTree(bool doPrint=true)
std::stringstream printTreeStats(bool doPrint=true)
void setOrigin(SimplexId linked)
Definition FTMNode.h:72
SimplexId getOrigin() const
Definition FTMNode.h:64
void setTreeScalars(MergeTree< dataType > &mergeTree, std::vector< dataType > &scalarsVector)
MergeTree< dataType > cleanMergeTree(ftm::FTMTree_MT *tree, std::vector< int > &nodeCorr, bool useBD=true)
void mergeTreeTemplateToDouble(MergeTree< dataType > &mt, MergeTree< double > &newMt)
void printTree(MergeTree< dataType > &tree, bool doPrint=true)
void removeSelfLink(FTMTree_MT *tree)
void mergeTreeToFTMTree(std::vector< MergeTree< dataType > > &trees, std::vector< ftm::FTMTree_MT * > &treesT)
MergeTree< dataType > createEmptyMergeTree(int scalarSize)
void printTreeScalars(MergeTree< dataType > &tree, bool printNodeAlone=true)
void printTreesStats(std::vector< ftm::FTMTree_MT * > &trees)
MergeTree< dataType > copyMergeTree(ftm::FTMTree_MT *tree, bool doSplitMultiPersPairs=false)
void mergeTreesDoubleToTemplate(std::vector< MergeTree< double > > &mts, std::vector< MergeTree< dataType > > &newMts)
void printTreeStats(MergeTree< dataType > &tree)
void mergeTreeDoubleToTemplate(MergeTree< double > &mt, MergeTree< dataType > &newMt)
void mergeTreesTemplateToDouble(std::vector< MergeTree< dataType > > &mts, std::vector< MergeTree< double > > &newMts)
unsigned int idNode
Node index in vect_nodes_.
void manageInconsistentArcsMultiParent(FTMTree_MT *tree)
void getTreeScalars(ftm::FTMTree_MT *tree, std::vector< dataType > &scalarsVector)
The Topology ToolKit.
std::shared_ptr< ftm::Params > params
Definition FTMTree_MT.h:902
std::shared_ptr< std::vector< dataType > > scalarsValues
Definition FTMTree_MT.h:901
ftm::FTMTree_MT tree
Definition FTMTree_MT.h:903
std::shared_ptr< ftm::Scalars > scalars
Definition FTMTree_MT.h:900