FTRGraph.h

Go to the documentation of this file.

 
 
#pragma once
 
// base code includes
#include <Triangulation.h>
 
// local includes
#include "DynamicGraph.h"
#include "FTRAtomicVector.h"
#include "FTRCommon.h"
#include "FTRDataTypes.h"
#include "FTRPropagation.h"
#include "FTRPropagations.h"
#include "FTRScalars.h"
#include "Graph.h"
#include "Mesh.h"
 
// other baseCode
#include "ScalarFieldCriticalPoints.h"
 
#ifndef TTK_DISABLE_FTR_LAZY
#include "FTRLazy.h"
#endif
 
// c++ includes
#include <set>
#include <tuple>
 
namespace ttk {
  namespace ftr {
 
    struct DynGraphs {
      // one going up, one going down
      DynamicGraph<idVertex> up{}, down{};
    };
 
    struct Valences {
      std::vector<valence> lower{}, upper{};
    };
 
    struct LocalForests {
      // one for upper link, one for lower link
      LocalForest<idVertex> up{}, down{};
    };
 
    struct Star {
      std::vector<idEdge> lower{}, upper{};
    };
 
    struct Comp {
      std::set<DynGraphNode<idVertex> *> lower{}, upper{};
    };
 
    template <typename ScalarType, typename triangulationType>
    class FTRGraph : public Allocable {
      // External fields
      Params params_{};
      Scalars<ScalarType> scalars_{};
 
      // Internal fields
      Graph graph_{};
      Mesh<triangulationType> mesh_{};
      Propagations propagations_{};
      DynGraphs dynGraphs_{};
      Valences valences_{};
 
#ifndef TTK_DISABLE_FTR_LAZY
      Lazy lazy_{};
#endif
 
#ifdef TTK_ENABLE_FTR_TASK_STATS
      // Stats
      Timer sweepStart_{};
      std::vector<float> propTimes_{};
      idVertex nbProp_{};
#endif
 
    public:
      explicit FTRGraph(triangulationType *mesh);
      FTRGraph();
 
      void build();
 
      // General documentation info:
      //
      //
      //
      // Developer info:
      // ttk::Triangulation is a generic triangulation representation that
      // enables fast mesh traversal, either on explicit triangulations (i.e.
      // tet-meshes) or implicit triangulations (i.e. low-memory footprint
      // implicit triangulations obtained from regular grids).
      //
      // Not all TTK packages need such mesh traversal features. If your
      // TTK package needs any mesh traversal procedure, we recommend to use
      // ttk::Triangulation as described here.
      //
      // Each call to a traversal procedure of ttk::Triangulation
      // must satisfy some pre-condition (see ttk::Triangulation for more
      // details). Such pre-condition functions are typically called from this
      // function.
      inline int preconditionTriangulation(triangulationType *triangulation) {
        mesh_.setTriangulation(triangulation);
        if(triangulation) {
          mesh_.preprocess();
        }
 
        return 0;
      }
 
      // Accessor on the graph
      // ---------------------
 
      Graph &&extractOutputGraph() {
        return std::move(graph_);
      }
 
      // Parameters
      // ----------
 
      int setThreadNumber(const int nb) override {
        params_.threadNumber = nb;
        // Security, but do not rely on this one
        threadNumber_ = nb;
        return 0;
      }
 
      int setDebugLevel(const int &lvl) override {
        params_.debugLevel = lvl;
        return Debug::setDebugLevel(lvl);
      }
 
      void setParams(const Params &p) {
        params_ = p;
        threadNumber_ = params_.threadNumber;
      }
 
      void setScalars(const void *scalars) {
        scalars_.setScalars(
          const_cast<ScalarType *>((const ScalarType *)scalars));
      }
 
      void setVertexSoSoffsets(SimplexId *sos) {
        scalars_.setOffsets(sos);
      }
 
      DynamicGraph<idVertex> &dynGraph(const Propagation *const lp) {
        if(lp->goUp()) {
          return dynGraphs_.up;
        } else {
          return dynGraphs_.down;
        }
      }
 
      DynamicGraph<idVertex> &dynGraph(const bool goUp) {
        if(goUp) {
          return dynGraphs_.up;
        } else {
          return dynGraphs_.down;
        }
      }
 
      DynamicGraph<idVertex> &dynGraphOpposite(const Propagation *const lp) {
        if(lp->goUp()) {
          return dynGraphs_.down;
        } else {
          return dynGraphs_.up;
        }
      }
 
    protected:
      // Build functions
 
      // classify critical points, marks saddle in join/split vectors
      // and add min/max or both as leaves.
      void criticalSearch();
 
      void sweepFrowSeeds();
 
      // launch a sequential sweep on the whole mesh.
      void sweepSequential();
 
      // Print function (FTRGraphPrint)
 
      std::string printMesh() const;
 
      std::string printEdge(const idEdge edgeId,
                            const Propagation *const localProp) const;
 
      std::string printTriangle(const idCell cellId,
                                const Propagation *const localProp) const;
 
      void printGraph(const int verbosity) const;
 
      void printTime(Timer &timer, const std::string &msg) const;
 
      // Initialize functions (virtual inherit from Allocable)
      // called automatically by the build
 
      void alloc() override;
 
      void init() override;
 
    private:
      void growthFromSeed(const idVertex seed,
                          Propagation *localProp,
                          idSuperArc currentArc = nullSuperArc);
 
      // growth like in the original algorithm by maintaining one dynamic graph.
      // the direction of the growth: increasing scalar value.
      void growthSequential(const idVertex begin, const idVertex stop);
 
      void visitStar(const Propagation *const localProp, Star &star) const;
 
      std::set<DynGraphNode<idVertex> *>
        lowerComps(const std::vector<idEdge> &finishingEdges,
                   const Propagation *const localProp);
 
      std::set<DynGraphNode<idVertex> *>
        upperComps(const std::vector<idEdge> &startingEdges,
                   const Propagation *const localProp);
 
      bool checkStop(const std::vector<DynGraphNode<idVertex> *> &lowerComp);
 
      // visit these edges neighborhood to understand the local connectivity
      // return the number of component in lower/upper link
      std::pair<valence, valence> getLinkNbCC(const idVertex curVert,
                                              LocalForests &localForests,
                                              const VertCompFN &comp);
 
      // this update is made using the arc: curArc
      void updatePreimage(const Propagation *const localProp,
                          const idSuperArc curArc);
 
      void updatePreimageStartCell(const orderedTriangle &oTriangle,
                                   const Propagation *const localProp,
                                   const idSuperArc curArc);
 
      void updatePreimageMiddleCell(const orderedTriangle &oTriangle,
                                    const Propagation *const localProp,
                                    const idSuperArc curArc);
 
      void updatePreimageEndCell(const orderedTriangle &oTriangle,
                                 const Propagation *const localProp,
                                 const idSuperArc curArc);
 
#ifndef TTK_DISABLE_FTR_LAZY
 
      // like updatePreimage but only impacte the lazy list in propagation
      // and not the global DG
      void lazyUpdatePreimage(Propagation *const localProp,
                              const idSuperArc curArc);
 
      // updatePreimageStart but in lazy, impact lazy lists and not the DG
      void updateLazyStart(const orderedTriangle &oTriangle,
                           Propagation *const localProp,
                           const idSuperArc curArc);
 
      // updatePreimageMiddle but in lazy, impact lazy lists and not the DG
      void updateLazyMiddle(const orderedTriangle &oTriangle,
                            Propagation *const localProp,
                            const idSuperArc curArc);
 
      // updatePreimageEnd but in lazy, impact lazy lists and not the DG
      void updateLazyEnd(const orderedTriangle &oTriangle,
                         Propagation *const localProp,
                         const idSuperArc curArc);
 
      // impacte the global DG
      void updateLazyAdd(const Propagation *const localProp,
                         const linkEdge edge,
                         const idSuperArc arc);
 
      void updateLazyDel(const Propagation *const localProp,
                         const linkEdge edge,
                         const idSuperArc arc);
 
      // aply modifications from lazy lists to the global DG (for arc a)
      void lazyApply(Propagation *const locapProp, const idSuperArc a);
 
#endif
 
      void updateDynGraphCurArc(const idVertex seed,
                                const idEdge neigEdge,
                                const idSuperArc curArc,
                                const Propagation *const localProp);
 
      void updateDynGraphCurArc(const idVertex seed,
                                const idSuperArc curArc,
                                const Propagation *const localProp);
 
      idNode updateReebGraph(const idSuperArc currentArc,
                             const Propagation *const localProp);
 
      void localGrowth(Propagation *const localProp,
                       const std::vector<idEdge> &upperEdges);
 
      // Check if the current vertex which is on a Join saddle come from the
      // last growth touching this saddle
      bool checkLast(Propagation *const localProp,
                     const std::vector<idEdge> &lowerStarEdges);
 
      // At a join saddle, merge local propagations coming here
      // and close remiang opened arcs.
      // Remove duplicate on the saddleVertex (only)
      // return the number of visible arcs merging
      idSuperArc
        mergeAtSaddle(const idNode saddleId,
                      Propagation *localProp,
                      const std::set<DynGraphNode<idVertex> *> &lowerComp);
 
      // At a join saddle, close onped arcs only
      // do not touch local propagations
      // return the number of visible arcs merging
      idSuperArc
        mergeAtSaddle(const idNode saddleId,
                      const std::set<DynGraphNode<idVertex> *> &lowerComp);
 
      // At a split saddle, assign new arcs at each CC in the DynGraph,
      // and launch a new propagation taking care of these arcs simultaneously
      // if hidden is true, new arcs are created hidden
      void splitAtSaddle(Propagation *const localProp,
                         const std::set<DynGraphNode<idVertex> *> &upperComp,
                         const bool hidden = false);
 
      // Return one triangle by upper CC of the vertex v
      std::set<idCell> upCCtriangleSeeds(const idVertex v,
                                         const Propagation *const localProp);
 
      // bfs on triangles/edges in the neighborhood of the saddle to mark
      // each cc with a distinct identifier.
      void bfsSeed(const std::size_t idt,
                   const valence idcc,
                   std::vector<idCell> &triangles,
                   std::vector<valence> &cc,
                   const Propagation *const localProp);
 
      // bfs on triangles/edges crossing the level set at saddle, starting
      // at seed. upper vertices encountered are added to newLocalProp
      // : saddle is the starting saddle,
      // : seed is at first call the first triangle of this bfs (will change
      // during recursive call)
      // : propagation is the propagation to fill with upper vertcices of
      // visited edges i
      // : arc is the arc id used to marks the segmentation of lower
      // vertices of visited edges (it has newLocalProp associated
      void bfsPropagation(const idVertex saddle,
                          const idCell seed,
                          Propagation *const newLocalProp,
                          const idSuperArc arc);
 
      // visit a vertex in terms of segmentation and history,
      // also check if the current arc is merging through an opposite one.
      idSuperArc visit(Propagation *const localProp, const idSuperArc curArc);
 
      // Tools
 
      // Create a new propagation starting at leaf
      Propagation *newPropagation(const idVertex leaf, const bool fromMax);
 
      // Compute the weight of the edge in the dyngraph between e1 and e2.
      // This weight is the min value of the two endpoints, we use the mirror
      // array (int)
      idVertex getWeight(const orderedEdge &e1,
                         const orderedEdge &e2,
                         const Propagation *const localProp);
 
      // DEPRECATED
      // TODO move in Mesh if not already done
 
      vertPosInTriangle
        getVertPosInTriangle(const orderedTriangle &oTriangle,
                             const Propagation *const localProp) const;
 
      // get the higher vertex: get<1>(get<1>(oTriangle)
      idVertex getEndVertexInTriangle(const orderedTriangle &oTriangle,
                                      const Propagation *const localProp) const;
 
      // get edge in orderer triangle between v0 and v1
      idEdge getEdgeFromOTri(const orderedTriangle oTri,
                             const idVertex v0,
                             const idVertex v1);
    };
  } // namespace ftr
} // namespace ttk
 
// Implementation
#include "FTRGraphPrint_Template.h"
#include "FTRGraphPrivate_Template.h"
#include "FTRGraph_Template.h"