75 template <
class triangulationType = AbstractTriangulation>
77 const triangulationType *triangulation);
79 template <
class triangulationType = AbstractTriangulation>
81 const triangulationType *triangulation);
83 template <
class triangulationType = AbstractTriangulation>
85 const triangulationType *triangulation);
87 template <
class triangulationType>
90 template <
class triangulationType = AbstractTriangulation>
94 const triangulationType *triangulation,
95 bool &isLowerOnBoundary,
96 bool &isUpperOnBoundary,
97 std::vector<std::vector<ttk::SimplexId>> *upperComponents,
98 std::vector<std::vector<ttk::SimplexId>> *lowerComponents)
const;
100 template <
class triangulationType = AbstractTriangulation>
104 const triangulationType *triangulation,
105 std::vector<std::vector<ttk::SimplexId>> *upperComponents
107 std::vector<std::vector<ttk::SimplexId>> *lowerComponents
112 const std::vector<std::pair<SimplexId, SimplexId>>
113 &vertexLinkEdgeList)
const;
120 setOutput(std::vector<std::pair<SimplexId, char>> *criticalPoints) {
138 const std::vector<std::vector<std::pair<SimplexId, SimplexId>>>
160 const std::vector<std::vector<std::pair<SimplexId, SimplexId>>>
177template <
class triangulationType>
179 const SimplexId *
const offsets,
const triangulationType *triangulation) {
201template <
class triangulationType>
203 const SimplexId *
const offsets,
const triangulationType *triangulation) {
205 progT_.setDebugLevel(debugLevel_);
206 progT_.setThreadNumber(threadNumber_);
209 progT_.setStartingResolutionLevel(StartingResolutionLevel);
210 progT_.setStoppingResolutionLevel(StoppingResolutionLevel);
211 progT_.setTimeLimit(TimeLimit);
212 progT_.setIsResumable(IsResumable);
213 progT_.setPreallocateMemory(
true);
215 progT_.computeProgressiveCP(criticalPoints_, offsets);
221template <
class triangulationType>
223 const SimplexId *
const offsets,
const triangulationType *triangulation) {
226#ifndef TTK_ENABLE_KAMIKAZE
227 if((!dimension_) && ((!triangulation) || (triangulation->isEmpty())))
229 if((!vertexNumber_) && ((!triangulation) || (triangulation->isEmpty())))
231 if((!vertexLinkEdgeLists_) && (!triangulation))
238 vertexNumber_ = triangulation->getNumberOfVertices();
239 dimension_ = triangulation->getCellVertexNumber(0) - 1;
242 printMsg(
"Extracting critical points...");
248#ifdef TTK_ENABLE_OPENMP
249 int chunkSize = std::max(1000, (
int)vertexNumber_ / (threadNumber_ * 100));
254#ifdef TTK_ENABLE_OPENMP
255#pragma omp parallel for schedule(dynamic, chunkSize) num_threads(threadNumber_)
259 if(!isRunningWithMPI()
260 || (isRunningWithMPI()
264 vertexTypes[i] = getCriticalType(i, offsets, triangulation);
267 }
else if(vertexLinkEdgeLists_) {
269#ifdef TTK_ENABLE_OPENMP
270#pragma omp parallel for schedule(dynamic, chunkSize) num_threads(threadNumber_)
274 vertexTypes[i] = getCriticalType(i, offsets, (*vertexLinkEdgeLists_)[i]);
278 SimplexId minimumNumber = 0, maximumNumber = 0, saddleNumber = 0,
279 oneSaddleNumber = 0, twoSaddleNumber = 0, monkeySaddleNumber = 0;
283 if(dimension_ == 3) {
284 for(
SimplexId i = 0; i < vertexNumber_; i++) {
285 switch(vertexTypes[i]) {
304 monkeySaddleNumber++;
308 }
else if(dimension_ == 2) {
309 for(
SimplexId i = 0; i < vertexNumber_; i++) {
310 switch(vertexTypes[i]) {
325 monkeySaddleNumber++;
332 std::vector<std::vector<std::string>> stats;
333 stats.push_back({
" #Minima", std::to_string(minimumNumber)});
334 if(dimension_ == 3) {
335 stats.push_back({
" #1-saddles", std::to_string(oneSaddleNumber)});
336 stats.push_back({
" #2-saddles", std::to_string(twoSaddleNumber)});
338 if(dimension_ == 2) {
339 stats.push_back({
" #Saddles", std::to_string(saddleNumber)});
341 stats.push_back({
" #Multi-saddles", std::to_string(monkeySaddleNumber)});
342 stats.push_back({
" #Maxima", std::to_string(maximumNumber)});
349 criticalPoints_->clear();
350 criticalPoints_->reserve(vertexNumber_);
351 for(
SimplexId i = 0; i < vertexNumber_; i++) {
353 criticalPoints_->emplace_back(i, vertexTypes[i]);
357 printMsg(
"Processed " + std::to_string(vertexNumber_) +
" vertices", 1,
363template <
class triangulationType>
367 const triangulationType *triangulation,
368 bool &isLowerOnBoundary,
369 bool &isUpperOnBoundary,
370 std::vector<std::vector<ttk::SimplexId>> *upperComponents,
371 std::vector<std::vector<ttk::SimplexId>> *lowerComponents)
const {
373 SimplexId neighborNumber = triangulation->getVertexNeighborNumber(vertexId);
374 std::vector<SimplexId> lowerNeighbors, upperNeighbors;
376 for(
SimplexId i = 0; i < neighborNumber; i++) {
378 triangulation->getVertexNeighbor(vertexId, i, neighborId);
380 if(offsets[neighborId] < offsets[vertexId]) {
381 lowerNeighbors.push_back(neighborId);
382 if(dimension_ == 3) {
383 if(triangulation->isVertexOnBoundary(neighborId))
384 isLowerOnBoundary =
true;
389 if(offsets[neighborId] > offsets[vertexId]) {
390 upperNeighbors.push_back(neighborId);
391 if(dimension_ == 3) {
392 if(triangulation->isVertexOnBoundary(neighborId))
393 isUpperOnBoundary =
true;
399 std::vector<UnionFind> lowerSeeds(lowerNeighbors.size());
400 std::vector<UnionFind *> lowerList(lowerNeighbors.size());
401 std::vector<UnionFind> upperSeeds(upperNeighbors.size());
402 std::vector<UnionFind *> upperList(upperNeighbors.size());
405 lowerList[i] = &(lowerSeeds[i]);
408 upperList[i] = &(upperSeeds[i]);
411 SimplexId vertexStarSize = triangulation->getVertexStarNumber(vertexId);
413 for(
SimplexId i = 0; i < vertexStarSize; i++) {
415 triangulation->getVertexStar(vertexId, i, cellId);
417 SimplexId cellSize = triangulation->getCellVertexNumber(cellId);
418 for(
SimplexId j = 0; j < cellSize; j++) {
420 triangulation->getCellVertex(cellId, j, neighborId0);
422 if(neighborId0 != vertexId) {
425 bool lower0 = offsets[neighborId0] < offsets[vertexId];
428 for(
SimplexId k = j + 1; k < cellSize; k++) {
431 triangulation->getCellVertex(cellId, k, neighborId1);
433 if((neighborId1 != neighborId0) && (neighborId1 != vertexId)) {
435 bool lower1 = offsets[neighborId1] < offsets[vertexId];
437 std::vector<SimplexId> *neighbors = &lowerNeighbors;
438 std::vector<UnionFind *> *seeds = &lowerList;
441 neighbors = &upperNeighbors;
445 if(lower0 == lower1) {
449 if((*neighbors)[l] == neighborId0) {
452 if((*neighbors)[l] == neighborId1) {
456 if((lowerId0 != -1) && (lowerId1 != -1)) {
458 (*seeds)[lowerId0], (*seeds)[lowerId1]);
459 (*seeds)[lowerId1] = (*seeds)[lowerId0];
472 lowerList[i] = lowerList[i]->find();
474 upperList[i] = upperList[i]->find();
476 std::unordered_map<UnionFind *, std::vector<ttk::SimplexId>>::iterator it;
477 std::unordered_map<UnionFind *, std::vector<ttk::SimplexId>>
479 std::unordered_map<UnionFind *, std::vector<ttk::SimplexId>>
484 it = upperComponentId.find(upperList[i]);
485 if(it != upperComponentId.end()) {
486 upperComponentId[upperList[i]].push_back(upperNeighbors[i]);
488 upperComponentId[upperList[i]]
489 = std::vector<ttk::SimplexId>(1, upperNeighbors[i]);
492 for(
auto elt : upperComponentId) {
493 upperComponents->push_back(std::vector<ttk::SimplexId>());
495 upperComponents->back().push_back(elt.second.at(i));
500 it = lowerComponentId.find(lowerList[i]);
501 if(it != lowerComponentId.end()) {
502 lowerComponentId[lowerList[i]].push_back(lowerNeighbors[i]);
504 lowerComponentId[lowerList[i]]
505 = std::vector<ttk::SimplexId>(1, lowerNeighbors[i]);
508 for(
auto elt : lowerComponentId) {
509 lowerComponents->push_back(std::vector<ttk::SimplexId>());
511 lowerComponents->back().push_back(elt.second.at(i));
516 printMsg(
"Vertex #" + std::to_string(vertexId)
517 +
": lowerLink-#CC=" + std::to_string(lowerComponentId.size())
518 +
" upperLink-#CC=" + std::to_string(upperComponentId.size()),
525template <
class triangulationType>
529 const triangulationType *triangulation,
530 std::vector<std::vector<ttk::SimplexId>> *upperComponents,
531 std::vector<std::vector<ttk::SimplexId>> *lowerComponents)
const {
533 bool isLowerOnBoundary =
false, isUpperOnBoundary =
false;
534 std::vector<std::vector<ttk::SimplexId>> localUpperComponents;
535 std::vector<std::vector<ttk::SimplexId>> localLowerComponents;
536 if(upperComponents ==
nullptr) {
537 upperComponents = &localUpperComponents;
539 if(lowerComponents ==
nullptr) {
540 lowerComponents = &localLowerComponents;
542 getLowerUpperComponents(vertexId, offsets, triangulation, isLowerOnBoundary,
543 isUpperOnBoundary, upperComponents, lowerComponents);
547 if(dimension_ == 1) {
548 if(lowerComponentNumber == 0 && upperComponentNumber != 0) {
550 }
else if(lowerComponentNumber != 0 && upperComponentNumber == 0) {
552 }
else if(lowerComponentNumber == 1 && upperComponentNumber == 1) {
558 if(lowerComponentNumber == 0 && upperComponentNumber == 1) {
560 }
else if(lowerComponentNumber == 1 && upperComponentNumber == 0) {
562 }
else if(lowerComponentNumber == 1 && upperComponentNumber == 1) {
564 if((dimension_ == 3) && (triangulation->isVertexOnBoundary(vertexId))) {
566 if((isUpperOnBoundary) && (!isLowerOnBoundary))
568 if((!isUpperOnBoundary) && (isLowerOnBoundary))
576 if(dimension_ == 2 || dimension_ == 1) {
577 if((lowerComponentNumber == 2 && upperComponentNumber == 1)
578 || (lowerComponentNumber == 1 && upperComponentNumber == 2)
579 || (lowerComponentNumber == 2 && upperComponentNumber == 2)) {
590 }
else if(dimension_ == 3) {
591 if(lowerComponentNumber == 2 && upperComponentNumber == 1) {
593 }
else if(lowerComponentNumber == 1 && upperComponentNumber == 2) {
607template <
class triangulationType>
609 const triangulationType *
ttkNotUsed(triangulation)) {
610 if(BackEnd == BACKEND::PROGRESSIVE_TOPOLOGY
611 && !std::is_same<ttk::ImplicitWithPreconditions, triangulationType>::value
612 && !std::is_same<ttk::ImplicitNoPreconditions, triangulationType>::value) {
614 printWrn(
"Explicit, Compact or Periodic triangulation detected.");
615 printWrn(
"Defaulting to the generic backend.");
617 BackEnd = BACKEND::GENERIC;
#define ttkNotUsed(x)
Mark function/method parameters that are not used in the function body at all.
AbstractTriangulation is an interface class that defines an interface for efficient traversal methods...
virtual int preconditionVertexStars()
virtual int preconditionBoundaryVertices()
virtual int preconditionVertexNeighbors()
virtual SimplexId getNumberOfVertices() const
virtual int getDimensionality() const
Minimalist debugging class.
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
int printErr(const std::string &msg, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cerr) const
ImplicitTriangulation is a class that provides time and memory efficient traversal methods on triangu...
TTK processing package for progressive Topological Data Analysis.
TTK processing package for the computation of critical points in PL scalar fields defined on PL manif...
void checkProgressivityRequirement(const triangulationType *triangulation)
int executeProgressive(const SimplexId *const offsets, const triangulationType *triangulation)
void preconditionTriangulation(AbstractTriangulation *triangulation)
void setVertexLinkEdgeLists(const std::vector< std::vector< std::pair< SimplexId, SimplexId > > > *edgeList)
int StartingResolutionLevel
void setNonManifold(const bool b)
int setVertexNumber(const SimplexId &vertexNumber)
const std::vector< std::vector< std::pair< SimplexId, SimplexId > > > * vertexLinkEdgeLists_
ProgressiveTopology progT_
int StoppingResolutionLevel
void setOutput(std::vector< std::pair< SimplexId, char > > *criticalPoints)
int execute(const SimplexId *const offsets, const triangulationType *triangulation)
int executeLegacy(const SimplexId *const offsets, const triangulationType *triangulation)
char getCriticalType(const SimplexId &vertexId, const SimplexId *const offsets, const triangulationType *triangulation, std::vector< std::vector< ttk::SimplexId > > *upperComponents=nullptr, std::vector< std::vector< ttk::SimplexId > > *lowerComponents=nullptr) const
ScalarFieldCriticalPoints()
void setDomainDimension(const int &dimension)
bool forceNonManifoldCheck
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
std::vector< std::pair< SimplexId, char > > * criticalPoints_
static UnionFind * makeUnion(UnionFind *uf0, UnionFind *uf1)
COMMON_EXPORTS int MPIrank_
int SimplexId
Identifier type for simplices of any dimension.
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)