TTK
Loading...
Searching...
No Matches
FTMTree_CT.cpp
Go to the documentation of this file.
1
13
14#include <iterator>
15#include <string>
16
17#include "FTMTree_CT.h"
18
19using namespace std;
20using namespace ttk;
21
22using namespace ftm;
23
24FTMTree_CT::FTMTree_CT(const std::shared_ptr<Params> &params,
25 const std::shared_ptr<Scalars> &scalars)
26 : FTMTree_MT(params, scalars, TreeType::Contour),
27 jt_(params, scalars, TreeType::Join),
28 st_(params, scalars, TreeType::Split) {
29 this->setDebugMsgPrefix("FTMTree_CT");
30}
31
33 Timer stepTime;
34 queue<pair<bool, idNode>> growingNodes, remainingNodes;
35
36 const bool DEBUG = false;
37
38 // Reserve
42
43 // Add JT & ST Leaves to growingNodes
44
45 // Add leves to growing nodes
46 const auto &nbSTLeaves = st_.getNumberOfLeaves();
47 if(nbSTLeaves > 1) {
48 for(idNode n = 0; n < nbSTLeaves; ++n) {
49 const auto &nId = st_.getLeave(n);
50 growingNodes.emplace(false, nId);
51 }
52 } else {
53 move(jt_);
54 return 0;
55 }
56
57 // count how many leaves can be added, if more than one : ok!
58 const auto &nbJTLeaves = jt_.getNumberOfLeaves();
59 if(nbJTLeaves > 1) {
60 for(idNode n = 0; n < nbJTLeaves; ++n) {
61 const auto &nId = jt_.getLeave(n);
62 growingNodes.emplace(true, nId);
63 }
64 } // else can't clone, not same up and down
65
66 if(DEBUG) {
67 cout << "growingNodes : " << growingNodes.size()
68 << " in : " << stepTime.getElapsedTime() << endl;
69 }
70
71 // Warning, have a reserve here, can't make it at the begnining, need build
72 // output
73 mt_data_.leaves.reserve(jt_.getLeaves().size() + st_.getLeaves().size());
76
77 if(growingNodes.empty()) {
78 cout << "[FTMTree_CT::combine ] Nothing to combine" << endl;
79 }
80
81#ifdef TTK_ENABLE_FTM_TREE_DUAL_QUEUE_COMBINE
82 do {
83 while(!remainingNodes.empty()) {
84 bool isJT;
85 idNode currentNodeId;
86 FTMTree_MT *xt;
87
88 tie(isJT, currentNodeId) = remainingNodes.front();
89 remainingNodes.pop();
90 if(isJT) {
91 // node come from jt
92 xt = &jt_;
93 } else {
94 // node come from st
95 xt = &st_;
96 }
97 if(xt->getNode(currentNodeId)->getNumberOfUpSuperArcs() == 1) {
98 growingNodes.emplace(isJT, currentNodeId);
99 if(DEBUG) {
100 cout << "repush in growing:" << isJT
101 << "::" << xt->printNode(currentNodeId) << endl;
102 }
103 }
104 }
105#endif
106
107 while(!growingNodes.empty()) {
108 idNode currentNodeId;
109 bool isJT;
110
111 // INFO QUEUE
112
113 tie(isJT, currentNodeId) = growingNodes.front();
114 growingNodes.pop();
115
116 FTMTree_MT *xt = (isJT) ? &jt_ : &st_;
117 FTMTree_MT *yt = (isJT) ? &st_ : &jt_;
118
119 // INFO JT / ST
120
121 // i <- Get(Q)
122 const Node *currentNode = xt->getNode(currentNodeId);
123
124 if(DEBUG) {
125 if(xt == &jt_)
126 cout << endl << "JT ";
127 else
128 cout << endl << "ST ";
129 cout << "node : " << currentNode->getVertexId() << endl;
130 }
131
132 // "choose a non-root leaf that is not a split in ST" so we ignore such
133 // nodes
134 if(currentNode->getNumberOfUpSuperArcs() == 0) {
135 if(DEBUG) {
136 cout << " ignore already processed" << endl;
137 }
138 continue;
139 }
140
141 idNode correspondingNodeId
142 = yt->getCorrespondingNodeId(currentNode->getVertexId());
143
144 if(yt->getNode(correspondingNodeId)->getNumberOfDownSuperArcs() > 1) {
145 if(DEBUG) {
146 cout << "put remain:" << isJT << "::" << xt->printNode(currentNodeId)
147 << endl;
148 cout << " which is in yt : " << yt->printNode(correspondingNodeId)
149 << endl;
150 }
151#ifdef TTK_ENABLE_FTM_TREE_DUAL_QUEUE_COMBINE
152 remainingNodes.emplace(isJT, currentNodeId);
153#else
154 growingNodes.emplace(isJT, currentNodeId);
155#endif
156 continue;
157 }
158
159 // NODES IN CT
160
161 idNode node1, node2;
162 SimplexId curVert = currentNode->getVertexId();
163 // NODE1
164 if(isCorrespondingNode(curVert)) {
165 // already a node in the tree
166 node1 = getCorrespondingNodeId(curVert);
167 } else {
168 // create a new node
169 node1 = makeNode(currentNode);
170
171 // check if leaf
172 if(!currentNode->getNumberOfDownSuperArcs()
173 || !currentNode->getNumberOfUpSuperArcs())
174 mt_data_.leaves.emplace_back(node1);
175 }
176
177 // j <- GetAdj(XT, i)
178 idSuperArc curUpArc = currentNode->getUpSuperArcId(0);
179 idNode parentId = xt->getSuperArc(curUpArc)->getUpNodeId();
180 const Node *parentNode = xt->getNode(parentId);
181
182 if(DEBUG) {
183 cout << " parent node :" << parentNode->getVertexId() << endl;
184 }
185
186 SimplexId parVert = parentNode->getVertexId();
187 // NODE2
188 if(isCorrespondingNode(parVert)) {
189 // already a node in the tree
190 node2 = getCorrespondingNodeId(parVert);
191 } else {
192 // create a new node
193 node2 = makeNode(parentNode);
194 if(!parentNode->getNumberOfUpSuperArcs())
195 mt_data_.leaves.emplace_back(node2);
196 }
197
198 // CREATE ARC
199
200 idSuperArc processArc = currentNode->getUpSuperArcId(0);
201
202 // create the arc in in the good direction
203 // and add it to crossing if needed
204 idSuperArc createdArc;
205 if(scalars_->isLower(
206 currentNode->getVertexId(),
207 parentNode->getVertexId())) { // take care of the order
208 createdArc = makeSuperArc(node1, node2);
209 } else {
210 createdArc = makeSuperArc(node2, node1);
211 }
212
213 // Segmentation
214 if(params_->segm) {
215 createCTArcSegmentation(createdArc, isJT, processArc);
216 }
217
218 if(DEBUG) {
219 cout << "create arc : " << printArc(createdArc) << endl;
220 }
221
222 // DEL NODES
223
224 // DelNode(XT, i)
225 {
226 if(DEBUG) {
227 cout << " delete xt (" << (xt == &jt_) << ") ";
228 cout << "node :" << xt->printNode(currentNodeId) << endl;
229 }
230
231 xt->delNode(currentNodeId);
232 }
233
234 // DelNode(YT, i)
235 {
236 if(DEBUG) {
237 cout << " delete yt (" << isJT << ") node :";
238 cout << yt->printNode(correspondingNodeId) << endl;
239 }
240
241 yt->delNode(correspondingNodeId);
242 }
243
244 // PROCESS QUEUE
245
246 if(parentNode->getNumberOfDownSuperArcs() == 0
247 && parentNode->getNumberOfUpSuperArcs()) {
248 growingNodes.emplace(isJT, parentId);
249
250 if(DEBUG) {
251 cout << "will see : " << parentNode->getVertexId() << endl;
252 }
253 }
254 }
255#ifdef TTK_ENABLE_FTM_TREE_DUAL_QUEUE_COMBINE
256 } while(!remainingNodes.empty());
257#endif
258
259 if(DEBUG) {
260 printTree2();
261 }
262
263 return 0;
264}
265
267 const bool isJT,
268 idSuperArc xtArc) {
269 const FTMTree_MT *xt = (isJT) ? &jt_ : &st_;
270
271 /*Here we prefer to create lots of small region, each arc having its own
272 * segmentation with no overlap instead of having a same vertice in several
273 * arc and using vert2tree to decide because we do not want to maintain
274 * vert2tree information during the whole computation*/
275 const list<Region> &xtRegions = xt->getSuperArc(xtArc)->getRegions();
276 for(const Region &reg : xtRegions) {
277 segm_it cur = reg.segmentBegin;
278 segm_it end = reg.segmentEnd;
279 segm_it tmpBeg = reg.segmentBegin;
280 // each element inside this region
281 for(; cur != end; ++cur) {
282 if(isCorrespondingNull(*cur)) {
283 updateCorrespondingArc(*cur, ctArc);
284 } else {
285 // already set, we finish a region
286 if(cur != tmpBeg) {
287 getSuperArc(ctArc)->concat(tmpBeg, cur);
288 }
289 // if several contiguous vertices are discarded
290 // cur will be equals to tmpBeg and we will not create empty regions
291 tmpBeg = cur + 1;
292 }
293 }
294 // close last region
295 if(cur != tmpBeg) {
296 getSuperArc(ctArc)->concat(tmpBeg, cur);
297 }
298 }
299}
300
302 Timer finSegmTime;
303 const auto &nbArc = getNumberOfSuperArcs();
304
305#ifdef TTK_ENABLE_OPENMP
306#pragma omp parallel for schedule(dynamic)
307#endif
308 for(idSuperArc i = 0; i < nbArc; i++) {
310 }
311
312 printTime(finSegmTime, "post-process segm", 4);
313}
314
316 vector<idNode> sortedJTNodes = jt_.sortedNodes(true);
317 vector<idNode> sortedSTNodes = st_.sortedNodes(true);
318
319 for(const idNode &t : sortedSTNodes) {
320
321 SimplexId vertId = st_.getNode(t)->getVertexId();
322 if(jt_.isCorrespondingNode(vertId)) {
323 continue;
324 }
326 }
327
328 for(const idNode &t : sortedJTNodes) {
329
330 SimplexId vertId = jt_.getNode(t)->getVertexId();
331 if(st_.isCorrespondingNode(vertId)) {
332 continue;
333 }
335 }
336}
#define DEBUG(msg)
Definition: Graph_Template.h:7
void setDebugMsgPrefix(const std::string &prefix)
Definition: Debug.h:364
double getElapsedTime()
Definition: Timer.h:15
void createCTArcSegmentation(idSuperArc ctArc, const bool isJT, idSuperArc xtArc)
Definition: FTMTree_CT.cpp:266
FTMTree_CT(const std::shared_ptr< Params > &params, const std::shared_ptr< Scalars > &scalars)
Definition: FTMTree_CT.cpp:24
bool isCorrespondingNode(const SimplexId val) const
Definition: FTMTree_MT.h:449
std::shared_ptr< Params > params_
Definition: FTMTree_MT.h:86
idNode getLeave(const idNode id) const
Definition: FTMTree_MT.h:412
std::string printNode(idNode n)
Definition: FTMTree_MT.cpp:681
SuperArc * getSuperArc(idSuperArc i)
Definition: FTMTree_MT.h:367
idNode getNumberOfNodes() const
Definition: FTMTree_MT.h:389
bool isCorrespondingNull(const SimplexId val) const
Definition: FTMTree_MT.h:453
void delNode(idNode node)
Definition: FTMTree_MT.cpp:289
std::string printArc(idSuperArc a)
Definition: FTMTree_MT.cpp:642
void move(FTMTree_MT &mt)
Definition: FTMTree_MT.cpp:512
idSuperArc insertNode(Node *node, const bool segm=true)
Definition: FTMTree_MT.cpp:422
idNode getCorrespondingNodeId(const SimplexId val) const
Definition: FTMTree_MT.h:459
idSuperArc getNumberOfSuperArcs() const
Definition: FTMTree_MT.h:363
idNode getNumberOfLeaves() const
Definition: FTMTree_MT.h:403
int printTime(Timer &t, const std::string &s, const int debugLevel=2) const
Definition: FTMTree_MT.cpp:727
const std::vector< idNode > & getLeaves() const
Definition: FTMTree_MT.h:407
idNode makeNode(SimplexId vertexId, SimplexId linked=nullVertex)
Definition: FTMTree_MT.cpp:473
idSuperArc makeSuperArc(idNode downNodeId, idNode upNodeId)
Definition: FTMTree_MT.cpp:499
bool isJT() const
Definition: FTMTree_MT.h:289
Node * getNode(idNode nodeId)
Definition: FTMTree_MT.h:393
std::shared_ptr< Scalars > scalars_
Definition: FTMTree_MT.h:87
void updateCorrespondingArc(const SimplexId vert, const idSuperArc arc)
Definition: FTMTree_MT.h:493
std::vector< idNode > sortedNodes(const bool parallel=false)
Definition: FTMTree_MT.cpp:909
idSuperArc getUpSuperArcId(idSuperArc neighborId) const
Definition: FTMNode.h:105
idSuperArc getNumberOfDownSuperArcs() const
Definition: FTMNode.h:82
SimplexId getVertexId() const
Definition: FTMNode.h:54
idSuperArc getNumberOfUpSuperArcs() const
Definition: FTMNode.h:86
idNode getUpNodeId() const
Definition: FTMSuperArc.h:68
void concat(const segm_it &begin, const segm_it &end)
Definition: FTMSuperArc.h:138
const std::list< Region > & getRegions() const
Definition: FTMSuperArc.h:160
void createSegmentation(const Scalars *s)
Definition: FTMSuperArc.h:155
long unsigned int idSuperArc
SuperArc index in vect_superArcs_.
Definition: FTMDataTypes.h:37
std::vector< SimplexId >::iterator segm_it
unsigned int idNode
Node index in vect_nodes_.
Definition: FTMDataTypes.h:39
The Topology ToolKit.
int SimplexId
Identifier type for simplices of any dimension.
Definition: DataTypes.h:22
std::shared_ptr< FTMAtomicVector< SuperArc > > superArcs
Definition: FTMTree_MT.h:46
std::shared_ptr< FTMAtomicVector< Node > > nodes
Definition: FTMTree_MT.h:47
std::vector< idNode > leaves
Definition: FTMTree_MT.h:49