DynamicGraph.h

Go to the documentation of this file.

 
 
#pragma once
 
#include "FTRCommon.h"
 
#include <set>
#include <vector>
 
namespace ttk {
  namespace ftr {
 
    template <typename Type>
    struct DynGraphNode;
 
    using idRoot = int;
 
    template <typename Type>
    class DynamicGraph : public Allocable {
    protected:
      std::vector<DynGraphNode<Type>> nodes_;
 
    public:
      DynamicGraph();
      ~DynamicGraph() override;
 
      // Initialize functions
      // --------------------
 
      void setNumberOfNodes(const std::size_t nbNodes) {
        setNumberOfElmt(nbNodes);
      }
 
      void alloc() override;
 
      void init() override;
 
      // Dyn Graph functions
      // -------------------
 
      DynGraphNode<Type> *getNode(const std::size_t nid) {
        return &nodes_[nid];
      }
 
      const DynGraphNode<Type> *getNode(const std::size_t nid) const {
        return &nodes_[nid];
      }
 
      std::size_t getNodeId(DynGraphNode<Type> *node) {
        return std::distance(&(nodes_[0]), node);
      }
 
      void setSubtreeArc(const std::size_t nid, const idSuperArc arc) {
        getNode(nid)->findRoot()->setRootArc(arc);
      }
 
      void setCorArc(const std::size_t nid, idSuperArc arc) {
        getNode(nid)->setRootArc(arc);
      }
 
      idSuperArc getSubtreeArc(const std::size_t nid) const {
        const auto node{getNode(nid)};
        return node != nullptr ? node->findRootArc() : nullSuperArc;
      }
 
      idSuperArc getCorArc(const std::size_t nid) const {
        return getNode(nid)->getCorArc();
      }
 
      // check whether or not this node is connected to others
      bool isDisconnected(const DynGraphNode<Type> *const node) const {
        return !node->hasParent();
      }
 
      // check whether or not this node is connected to others
      bool isDisconnected(const std::size_t nid) {
        return !getNode(nid)->hasParent();
      }
 
      DynGraphNode<Type> *findRoot(const DynGraphNode<Type> *const node) {
        return node->findRoot();
      }
 
      DynGraphNode<Type> *findRoot(const std::size_t nid) {
        return findRoot(getNode(nid));
      }
 
      std::vector<DynGraphNode<Type> *>
        findRoot(std::initializer_list<DynGraphNode<Type> *> nodes) {
        std::vector<DynGraphNode<Type> *> roots;
        roots.reserve(nodes.size());
        for(auto *n : nodes) {
          roots.emplace_back(findRoot(n));
        }
        std::sort(roots.begin(), roots.end());
        const auto it = std::unique(roots.begin(), roots.end());
        roots.erase(it, roots.end());
        return roots;
      }
 
      std::vector<DynGraphNode<Type> *>
        findRoot(std::initializer_list<std::size_t> nodesIds) {
        std::vector<DynGraphNode<Type> *> roots;
        roots.reserve(nodesIds.size());
        for(auto n : nodesIds) {
          roots.emplace_back(findRoot(n));
        }
        std::sort(roots.begin(), roots.end());
        const auto it = std::unique(roots.begin(), roots.end());
        roots.erase(it, roots.end());
        return roots;
      }
 
      template <typename type>
      std::set<DynGraphNode<Type> *>
        findRoot(const std::vector<type> &nodesIds) {
 
        std::set<DynGraphNode<Type> *> roots;
        for(auto n : nodesIds) {
          roots.emplace(findRoot(n));
        }
        return roots;
      }
 
      bool insertEdge(DynGraphNode<Type> *const n1,
                      DynGraphNode<Type> *const n2,
                      const Type w,
                      const idSuperArc corArc) {
        return n1->insertEdge(n2, w, corArc);
      }
 
      bool insertEdge(const std::size_t n1,
                      const std::size_t n2,
                      const Type w,
                      const idSuperArc corArc) {
        return insertEdge(getNode(n1), getNode(n2), w, corArc);
      }
 
      void removeEdge(DynGraphNode<Type> *const n) {
        n->removeEdge();
      }
 
      void removeEdge(const std::size_t nid) {
        removeEdge(getNode(nid));
      }
 
      int removeEdge(DynGraphNode<Type> *const n1,
                     DynGraphNode<Type> *const n2);
 
      int removeEdge(const std::size_t nid1, const std::size_t nid2) {
        return removeEdge(getNode(nid1), getNode(nid2));
      }
 
      // Debug
 
      std::string print();
 
      std::string print(const std::function<std::string(std::size_t)> &);
 
      std::string printNbCC();
 
      void test();
    };
 
    // Same as dynamic graph but keep the number of subtrees at any time
    // CAREFUL: this number is not protected for parallel modification, and
    // this class is not made for parallel access.
    template <typename Type>
    class LocalForest : public DynamicGraph<Type> {
      std::size_t nbCC_;
      using super = DynamicGraph<Type>;
 
    public:
      LocalForest() : super(), nbCC_{0} {
      }
 
      void setNumberOfNodes(const std::size_t nbNodes) {
        super::setNumberOfNodes(nbNodes);
        nbCC_ = nbNodes;
      }
 
      void setNbCC(const std::size_t nb) {
        // usefull if the forest is willingly larger than the real number of
        // nodes
        nbCC_ = nb;
      }
 
      void reset() {
        for(auto &node : this->nodes_) {
          node.parent_ = nullptr;
          node.weight_ = 0;
          std::ignore = node;
        }
        nbCC_ = this->nodes_.size();
      }
 
      bool insertEdge(DynGraphNode<Type> *const n1,
                      DynGraphNode<Type> *const n2,
                      const Type w,
                      const idSuperArc corArc) {
        bool connect = super::insertEdge(n1, n2, w, corArc);
        if(connect)
          --nbCC_;
        return connect;
      }
 
      bool insertEdge(const std::size_t n1,
                      const std::size_t n2,
                      const Type w,
                      const idSuperArc corArc) {
        bool connect = super::insertEdge(n1, n2, w, corArc);
        if(connect)
          --nbCC_;
        return connect;
      }
 
      void removeEdge(DynGraphNode<Type> *const n) {
        super::removeEdge(n);
        ++nbCC_;
      }
 
      void removeEdge(const std::size_t nid) {
        super::removeEdge(nid);
        ++nbCC_;
      }
 
      int removeEdge(DynGraphNode<Type> *const n1,
                     DynGraphNode<Type> *const n2) {
        int ret = super::removeEdge(n1, n2);
        if(ret)
          ++nbCC_;
        return ret;
      }
 
      int removeEdge(const std::size_t nid1, const std::size_t nid2) {
        int ret = super::removeEdge(nid1, nid2);
        if(ret)
          ++nbCC_;
        return ret;
      }
 
      std::size_t getNbCC() const {
        return nbCC_;
      }
    };
 
    template <typename Type>
    struct DynGraphNode {
      DynGraphNode *parent_;
      Type weight_;
 
      idSuperArc corArc_;
 
      explicit DynGraphNode()
        : parent_(nullptr), weight_(0), corArc_(nullSuperArc) {
      }
 
      DynGraphNode(const DynGraphNode &other) {
        operator=(other);
      }
 
      DynGraphNode &operator=(const DynGraphNode &other) {
        if(this != &other) {
          parent_ = other.parent_;
          weight_ = other.weight_;
        }
        return *this;
      }
 
      // Accessor functions
      // ------------------
 
      Type getWeight() const {
        return weight_;
      }
 
      bool hasParent() const {
        return parent_;
      }
 
      // Graph functions
      // ---------------
 
      // Various way to do that, test perfs ?
      void evert();
 
      DynGraphNode *findRoot() const;
 
      idSuperArc findRootArc() const;
 
      idSuperArc getCorArc() const {
        idSuperArc corArc;
#ifdef TTK_ENABLE_OPENMP
#pragma omp atomic read
#endif
        corArc = corArc_;
        return corArc;
      }
 
      void setRootArc(const idSuperArc arcId);
 
      std::tuple<DynGraphNode<Type> *, DynGraphNode<Type> *>
        findMinWeightRoot() const;
 
      bool insertEdge(DynGraphNode *const n,
                      const Type weight,
                      const idSuperArc corArc);
 
      void removeEdge();
    };
  } // namespace ftr
} // namespace ttk
 
#include "DynamicGraph_Template.h"