TTK
Loading...
Searching...
No Matches
FTRGraph_Template.h
Go to the documentation of this file.
1#pragma once
2
3#include "FTRGraph.h"
4#include "FTRPropagation.h"
5#include "FTRTasks.h"
6
7#ifdef TTK_ENABLE_FTR_TASK_STATS
8#include <iterator>
9#endif
10#ifdef TTK_ENABLE_FTR_VERT_STATS
11#include <iterator>
12#endif
13
14#ifdef TTK_ENABLE_OMP_PRIORITY
15#define OPTIONAL_PRIORITY(value) priority(value)
16#else
17#define OPTIONAL_PRIORITY(value)
18#endif
19
20#ifdef GPROFILE
21#include <gperftools/profiler.h>
22#endif
23
24namespace ttk {
25 namespace ftr {
26 template <typename ScalarType, typename triangulationType>
28 this->setDebugMsgPrefix("FTRGraph");
29 }
30
31 template <typename ScalarType, typename triangulationType>
33 this->setDebugMsgPrefix("FTRGraph");
34 preconditionTriangulation(mesh);
35 }
36
37 template <typename ScalarType, typename triangulationType>
39 Timer t;
40
41 // init some values
42
43#ifdef TTK_ENABLE_OPENMP
44 ParallelGuard pg{params_.threadNumber};
45 omp_set_nested(1);
46#ifdef TTK_ENABLE_OMP_PRIORITY
47 if(omp_get_max_task_priority() < PriorityLevel::Max) {
48 this->printWrn("OpenMP max priority is lower than 5");
49 }
50#endif
51#endif
52
53 params_.printSelf();
54
55 // Precompute
56 Timer timeAlloc;
57 alloc();
58 this->printMsg(
59 "alloc time: ", 1.0, timeAlloc.getElapsedTime(), this->threadNumber_);
60
61 Timer timeInit;
62 init();
63 this->printMsg(
64 "init time: ", 1.0, timeInit.getElapsedTime(), this->threadNumber_);
65
66 // std::cout << printMesh() << std::endl;
67 // std::cout << mesh_.printEdges() << std::endl;
68
69 Timer finTime;
70#ifdef GPROFILE
71 std::cout << "Profiling enabled ..." << std::endl;
72 ProfilerStart("ftr.log");
73#endif
74
75 Timer timeSort;
76 this->printMsg(
77 "sort time: ", 1.0, timeSort.getElapsedTime(), this->threadNumber_);
78
79 Timer timePreSortSimplices;
80 mesh_.preSortEdges([&](const idVertex a, const idVertex b) {
81 return scalars_.isLower(a, b);
82 });
83 mesh_.preSortTriangles([&](const idVertex a, const idVertex b) {
84 return scalars_.isLower(a, b);
85 });
86 this->printMsg("simplices sort time: ", 1.0,
87 timePreSortSimplices.getElapsedTime(),
88 this->threadNumber_);
89
90 // Build the graph
91
92 Timer timeBuild;
93
94#ifdef TTK_ENABLE_OPENMP
95#pragma omp parallel num_threads(params_.threadNumber)
96#endif
97 {
98#ifdef TTK_ENABLE_OPENMP
99#pragma omp single nowait
100#endif
101 {
102 Timer timeCritSearch;
103 criticalSearch();
104 this->printMsg("leaf search time ", 1.0,
105 timeCritSearch.getElapsedTime(), this->threadNumber_);
106
107 Timer timeSwipe;
108 sweepFrowSeeds();
109 // sweepSequential();
110 this->printMsg("sweepFrowSeeds time: ", 1.0,
111 timeSwipe.getElapsedTime(), this->threadNumber_);
112 }
113 }
114 this->printMsg(
115 "build time: ", 1.0, timeBuild.getElapsedTime(), this->threadNumber_);
116
117 // Debug print
118#ifndef NDEBUG
119 // std::cout << graph_.printVisit() << std::endl;
120 // printGraph(4);
121 // std::cout << "up" << std::endl;
122 // std::cout << dynGraphs_.up.print() << std::endl;
123 // std::cout << "down" << std::endl;
124 // std::cout << dynGraphs_.down.print() << std::endl;
125#endif
126
127 // post-process
128 Timer postProcTime;
129 graph_.mergeArcs<ScalarType>(&scalars_);
130 graph_.arcs2nodes<ScalarType>(&scalars_);
131 this->printMsg("postProcess: ", 1.0, postProcTime.getElapsedTime(),
132 this->threadNumber_);
133
134 // std::cout << "nb verts: " << mesh_.getNumberOfVertices() << std::endl;
135 // std::cout << "nb triangle: " << mesh_.getNumberOfVertices() <<
136 // std::endl; std::cout << "nb nodes: " << graph_.getNumberOfNodes() <<
137 // std::endl; std::cout << "nb leaves: " << graph_.getNumberOfLeaves() <<
138 // std::endl; std::cout << "nb arcs: " << graph_.getNumberOfVisibleArcs()
139 // << std::endl;
140
141 this->printMsg(
142 "*TOTAL* time: ", 1.0, finTime.getElapsedTime(), this->threadNumber_);
143
144#ifdef GPROFILE
145 ProfilerStop();
146#endif
147
148 // list of regular vertices on each arc
149 // explicit build: for sampling
150 if(params_.samplingLvl) {
151 graph_.buildArcSegmentation<ScalarType>(&scalars_);
152 }
153
154 // Debug print
155#ifndef NDEBUG
156 // std::cout << graph_.printVisit() << std::endl;
157 // printGraph(4);
158 // std::cout << dynGraphs_.up.printNbCC() << std::endl;
159#endif
160 this->printMsg(
161 std::vector<std::vector<std::string>>{
162 {"#Visible arcs", std::to_string(graph_.getNumberOfVisibleArcs())},
163 {"#Arcs", std::to_string(graph_.getNumberOfArcs())},
164 },
166
167#ifdef TTK_ENABLE_FTR_TASK_STATS
168 std::cout << "propTimes_ :" << std::endl;
169 copy(propTimes_.crbegin(), propTimes_.crend(),
170 std::ostream_iterator<float>(std::cout, " "));
171 std::cout << std::endl;
172#endif
173
174#ifdef TTK_ENABLE_FTR_VERT_STATS
175 idVertex nbRevisit = graph_.getNbMultiTouch();
176 std::cout << "revisit: " << nbRevisit << " / "
177 << mesh_.getNumberOfVertices();
178 std::cout << " = "
179 << ((float)nbRevisit / mesh_.getNumberOfVertices()) * 100
180 << std::endl;
181 std::cout << "avoided: " << graph_.getNbAvoided() << std::endl;
182#endif
183 }
184
185 // protected
186
187 template <typename ScalarType, typename triangulationType>
189 const bool addMin = true;
190 const bool addMax = !params_.singleSweep;
191
192 ScalarFieldCriticalPoints critPoints;
193
194 TaskChunk leafChunkParams(scalars_.getSize());
195 leafChunkParams.grainSize = 10000;
196 auto leafChunk = Tasks::getChunk(leafChunkParams);
197
198 for(idPropagation leafChunkId = 0; leafChunkId < std::get<1>(leafChunk);
199 ++leafChunkId) {
200#ifdef TTK_ENABLE_OPENMP
201#pragma omp task firstprivate(leafChunkId)
202#endif
203 {
204 const idVertex lowerBound
205 = Tasks::getBegin(leafChunkId, std::get<0>(leafChunk));
206 const idVertex upperBound = Tasks::getEnd(
207 leafChunkId, std::get<0>(leafChunk), scalars_.getSize());
208
209 // each task uses its local forests
210 for(idVertex v = lowerBound; v < upperBound; ++v) {
211 bool lBoundary = false, uBoundary = false;
212 std::vector<std::vector<ttk::SimplexId>> upperComponents;
213 std::vector<std::vector<ttk::SimplexId>> lowerComponents;
214 critPoints.getLowerUpperComponents(
215 v, scalars_.getOffsets(), mesh_.getTriangulation(), lBoundary,
216 uBoundary, &upperComponents, &lowerComponents);
217 valences_.lower[v] = lowerComponents.size();
218 valences_.upper[v] = upperComponents.size();
219 // leaf cases
220 if(addMin && valences_.lower[v] == 0) {
221 graph_.addLeaf(v, true);
222 }
223 if(addMax && valences_.upper[v] == 0) {
224 graph_.addLeaf(v, false);
225 }
226 }
227 } // end task
228 }
229#ifdef TTK_ENABLE_OPENMP
230#pragma omp taskwait
231#endif
232#ifdef TTK_ENABLE_FTR_TASK_STATS
233 // Stats
234 nbProp_ = graph_.getNumberOfLeaves();
235 propTimes_.resize(nbProp_);
236#endif
237 this->printMsg(std::vector<std::vector<std::string>>{
238 {"#Leaves", std::to_string(graph_.getNumberOfLeaves())}});
239 }
240
241 template <typename ScalarType, typename triangulationType>
243 const idNode nbSeed = graph_.getNumberOfLeaves();
244 // used to interleave min and max
245 // Note: useless if only start for min or max
246
247 graph_.sortLeaves<ScalarType>(&scalars_);
248
249#ifdef TTK_ENABLE_FTR_TASK_STATS
250 sweepStart_.reStart();
251#endif
252#ifdef TTK_ENABLE_OPENMP
253#pragma omp taskgroup
254#endif
255 {
256 for(idNode i = 0; i < nbSeed; i++) {
257 // alterneate min/max, string at the deepest
258 idVertex l = (i % 2) ? i / 2 : nbSeed - 1 - i / 2;
259 // increasing order, min first
260 // idVertex l = i;
261 // initialize structure
262 const idVertex corLeaf = graph_.getLeaf(l);
263 const bool fromMin = graph_.isLeafFromMin(l);
264 Propagation *localPropagation = newPropagation(corLeaf, fromMin);
265 const idSuperArc newArc
266 = graph_.openArc(graph_.makeNode(corLeaf), localPropagation);
267 // graph_.visit(corLeaf, newArc);
268 // process
269#ifdef TTK_ENABLE_OPENMP
270#pragma omp task OPTIONAL_PRIORITY(PriorityLevel::Higher)
271#endif
272 growthFromSeed(corLeaf, localPropagation, newArc);
273 }
274 }
275 }
276
277 template <typename ScalarType, typename triangulationType>
279 growthSequential(0, mesh_.getNumberOfVertices());
280 }
281
282 template <typename ScalarType, typename triangulationType>
284 mesh_.alloc();
285
286 scalars_.setSize(mesh_.getNumberOfVertices());
287 scalars_.alloc();
288
289 graph_.setNumberOfElmt(mesh_.getNumberOfVertices());
290 graph_.alloc();
291
292 propagations_.setNumberOfElmt(mesh_.getNumberOfVertices());
293 propagations_.alloc();
294
295 dynGraphs_.up.setNumberOfElmt(mesh_.getNumberOfEdges());
296 dynGraphs_.up.alloc();
297
298 dynGraphs_.down.setNumberOfElmt(mesh_.getNumberOfEdges());
299 dynGraphs_.down.alloc();
300
301#ifndef TTK_DISABLE_FTR_LAZY
302 lazy_.setNumberOfElmt(mesh_.getNumberOfVertices() * 2);
303 lazy_.alloc();
304#endif
305
306 valences_.lower.resize(mesh_.getNumberOfVertices());
307 valences_.upper.resize(mesh_.getNumberOfVertices());
308 }
309
310 template <typename ScalarType, typename triangulationType>
312 scalars_.removeNaN();
313 scalars_.init();
314 graph_.init();
315 propagations_.init();
316 dynGraphs_.up.init();
317 dynGraphs_.down.init();
318
319#ifndef TTK_DISABLE_FTR_LAZY
320 lazy_.init();
321#endif
322
323 // Stats
324#ifdef TTK_ENABLE_FTR_TASK_STATS
325 fillVector<float>(propTimes_, 0);
326#endif
327 }
328
329 } // namespace ftr
330} // namespace ttk
TTK processing package for the computation of critical points in PL scalar fields defined on PL manif...
int getLowerUpperComponents(const SimplexId vertexId, const SimplexId *const offsets, const triangulationType *triangulation, bool &isLowerOnBoundary, bool &isUpperOnBoundary, std::vector< std::vector< ttk::SimplexId > > *upperComponents, std::vector< std::vector< ttk::SimplexId > > *lowerComponents) const
double getElapsedTime()
Definition: Timer.h:15
void alloc() override
void init() override
TTK fTRGraph propagation management with Fibonacci heaps.
static std::tuple< idVertex, idPropagation > getChunk(const TaskChunk &params)
Definition: FTRTasks.h:45
static idVertex getBegin(const idPropagation chunkId, const idVertex grainSize, const idVertex offset=0)
Definition: FTRTasks.h:68
static idVertex getEnd(const idPropagation chunkId, const idVertex grainSize, const idVertex maxEnd=nullVertex)
Definition: FTRTasks.h:74
idNode idPropagation
for task identifiers
Definition: FTRDataTypes.h:35
long unsigned int idSuperArc
SuperArc index in vect_superArcs_.
Definition: FTRDataTypes.h:25
SimplexId idVertex
Vertex index in scalars_.
Definition: FTRDataTypes.h:29
unsigned int idNode
Node index in vect_nodes_.
Definition: FTRDataTypes.h:27
The Topology ToolKit.
idVertex grainSize
Definition: FTRTasks.h:30
printMsg(debug::output::GREEN+"                           "+debug::output::ENDCOLOR+debug::output::GREEN+"▒"+debug::output::ENDCOLOR+debug::output::GREEN+"▒▒▒▒▒▒▒▒▒▒▒▒▒░"+debug::output::ENDCOLOR, debug::Priority::PERFORMANCE, debug::LineMode::NEW, stream)