ClusterTree.h

Go to the documentation of this file.

 
#pragma once
 
#include <gtsam/base/Testable.h>
#include <gtsam/base/FastMap.h>
#include <gtsam/base/FastSet.h>
#include <gtsam/base/FastVector.h>
#include <gtsam/inference/Ordering.h>
 
namespace gtsam {

template <class GRAPH>
class ClusterTree {
 public:
  typedef GRAPH FactorGraphType;               
  typedef ClusterTree<GRAPH> This;             
  typedef std::shared_ptr<This> shared_ptr;  
 
  typedef typename GRAPH::FactorType FactorType;       
  typedef std::shared_ptr<FactorType> sharedFactor;  

  // TODO(frank): re-factor JunctionTree so we can make members private
  struct Cluster {
    typedef FastVector<std::shared_ptr<Cluster> > Children;
    Children children;  
 
    typedef Ordering Keys;
    Keys orderedFrontalKeys;  
 
    FactorGraphType factors;  
 
    int problemSize_;
 
    Cluster() : problemSize_(0) {}
 
    virtual ~Cluster() {}
 
    const Cluster& operator[](size_t i) const {
      return *(children.at(i));
    }

    template <class CONTAINER>
    Cluster(Key key, const CONTAINER& factorsToAdd)
        : problemSize_(0) {
      addFactors(key, factorsToAdd);
    }

    template <class CONTAINER>
    void addFactors(Key key, const CONTAINER& factorsToAdd) {
      orderedFrontalKeys.push_back(key);
      factors.push_back(factorsToAdd);
      problemSize_ += factors.size();
    }

    void addChild(const std::shared_ptr<Cluster>& cluster) {
      children.push_back(cluster);
      problemSize_ = std::max(problemSize_, cluster->problemSize_);
    }
 
    size_t nrChildren() const {
      return children.size();
    }
 
    size_t nrFactors() const {
      return factors.size();
    }
 
    size_t nrFrontals() const {
      return orderedFrontalKeys.size();
    }
 
    int problemSize() const {
      return problemSize_;
    }

    virtual void print(const std::string& s = "",
                       const KeyFormatter& keyFormatter = DefaultKeyFormatter) const;

    std::vector<size_t> nrFrontalsOfChildren() const;
 
    using KeySetMap = FastMap<const Cluster*, KeySet>;

    KeySet separatorKeys(KeySetMap* cache = nullptr) const;

    void merge(const std::shared_ptr<Cluster>& cluster);

    void mergeChildren(const std::vector<bool>& merge);

    void mergeChildrenSiblings(const std::vector<bool>& merge);

    void mergeChildren(const Children& selected);

    void mergeChildrenSiblings(const Children& selected);

    Children childrenFromMask(const std::vector<bool>& merge) const;
  };
 
  typedef std::shared_ptr<Cluster> sharedCluster;  
 
  // Define Node=Cluster for compatibility with tree traversal functions
  typedef Cluster Node;
  typedef sharedCluster sharedNode;

  GTSAM_CONCEPT_TESTABLE_TYPE(FactorType)
 
 protected:
  FastVector<sharedNode> roots_;


  ClusterTree(const This& other) {
    *this = other;
  }

 
 public:

  ClusterTree() {}


  void print(const std::string& s = "",
             const KeyFormatter& keyFormatter = DefaultKeyFormatter) const;

 
  void addRoot(const std::shared_ptr<Cluster>& cluster) {
    roots_.push_back(cluster);
  }
 
  void addChildrenAsRoots(const std::shared_ptr<Cluster>& cluster) {
    for (auto child : cluster->children)
      this->addRoot(child);
  }
 
  size_t nrRoots() const {
    return roots_.size();
  }

  const FastVector<sharedNode>& roots() const {
    return roots_;
  }
 
  const Cluster& operator[](size_t i) const {
    return *(roots_.at(i));
  }

 
 protected:
  ~ClusterTree();


  This& operator=(const This& other);

};

template <class BAYESTREE, class GRAPH>
class EliminatableClusterTree : public ClusterTree<GRAPH> {
 public:
  typedef BAYESTREE BayesTreeType;  
  typedef GRAPH FactorGraphType;    
  typedef EliminatableClusterTree<BAYESTREE, GRAPH> This;  
  typedef std::shared_ptr<This> shared_ptr;              
 
  typedef typename BAYESTREE::ConditionalType ConditionalType;  
  typedef std::shared_ptr<ConditionalType>
      sharedConditional;  
 
  typedef typename GRAPH::Eliminate Eliminate;         
  typedef typename GRAPH::FactorType FactorType;       
  typedef std::shared_ptr<FactorType> sharedFactor;  
 
 protected:
  FastVector<sharedFactor> remainingFactors_;


  EliminatableClusterTree(const This& other) : ClusterTree<GRAPH>(other) {
    *this = other;
  }

 
 public:

  std::pair<std::shared_ptr<BayesTreeType>, std::shared_ptr<FactorGraphType> > eliminate(
      const Eliminate& function) const;



  const FastVector<sharedFactor>& remainingFactors() const {
    return remainingFactors_;
  }

 
 protected:

  This& operator=(const This& other);

  EliminatableClusterTree() {}

};
}
 
#include <gtsam/inference/ClusterTree-inst.h>