DynamicTree.h

Go to the documentation of this file.

 
 
#pragma once
 
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
 
namespace ttk {
 
  struct DynTreeNode {
    DynTreeNode *parent_{nullptr};
 
    // Accessor functions
    // ------------------
 
    inline bool hasParent() const {
      return parent_ != nullptr;
    }
 
    // Graph functions
    // ---------------
 
    // Various way to do that, test perfs ?
    void evert();
 
    DynTreeNode *findRoot() const;
 
    bool insertEdge(DynTreeNode *const n);
 
    inline void removeEdge() {
#ifndef TTK_ENABLE_KAMIKAZE
      if(!parent_) {
        std::cerr << "[DynamicTree]: DynTree remove edge in root node"
                  << std::endl;
        return;
      }
#endif
      parent_ = nullptr;
    }
  };
 
  // WARNING : this class allows to maintain the number of components
  // as it evolves, IT IS NOT PARALLEL SAFE
  class DynamicTree {
    std::vector<DynTreeNode> nodes_{};
 
  public:
    // Initialize functions
    // --------------------
 
    inline void alloc(const std::size_t nbNodes) {
      nodes_.resize(nbNodes);
    }
 
    inline DynTreeNode *getNode(const std::size_t nid) {
      return &nodes_[nid];
    }
 
    inline const DynTreeNode *getNode(const std::size_t nid) const {
      return &nodes_[nid];
    }
 
    inline std::size_t getNodeId(DynTreeNode *node) {
      return node - &nodes_[0];
    }
 
    bool insertEdge(DynTreeNode *const n1, DynTreeNode *const n2) {
      return n1->insertEdge(n2);
    }
 
    inline bool insertEdge(const std::size_t n1, const std::size_t n2) {
      return getNode(n1)->insertEdge(getNode(n2));
    }
 
    inline void removeEdge(DynTreeNode *const n) {
      n->removeEdge();
    }
 
    inline void removeEdge(const std::size_t nid) {
      getNode(nid)->removeEdge();
    }
 
    int removeEdge(DynTreeNode *const n1, DynTreeNode *const n2) {
      if(n1->parent_ == n2) {
        n1->removeEdge();
        return 1;
      }
      if(n2->parent_ == n1) {
        n2->removeEdge();
        return 2;
      }
      return 0;
    }
 
    inline int removeEdge(const std::size_t nid1, const std::size_t nid2) {
      return removeEdge(getNode(nid1), getNode(nid2));
    }
 
    inline std::size_t getCCFromNode(const std::size_t n0) const {
      return getNode(n0)->findRoot() - &nodes_[0];
    }
    void retrieveNbCC(std::vector<size_t> &nbccIds) const {
      for(size_t nId = 0; nId < nodes_.size(); nId++) {
        if(nodes_[nId].parent_ == nullptr)
          nbccIds.emplace_back(nId);
      }
    }
    inline size_t getNbCC() const {
      return std::count_if(
        nodes_.begin(), nodes_.end(),
        [](const DynTreeNode &dtn) { return dtn.parent_ == nullptr; });
    }
 
    // Debug
 
    std::string print() const;
    std::string printNbCC() const;
  };
 
} // namespace ttk