BayesTree.h

Go to the documentation of this file.

/* ----------------------------------------------------------------------------
 
 * GTSAM Copyright 2010, Georgia Tech Research Corporation,
 * Atlanta, Georgia 30332-0415
 * All Rights Reserved
 * Authors: Frank Dellaert, et al. (see THANKS for the full author list)
 
 * See LICENSE for the license information
 
 * -------------------------------------------------------------------------- */
 
// \callgraph
 
#pragma once
 
#include <boost/shared_ptr.hpp>
 
#include <gtsam/inference/Key.h>
#include <gtsam/base/FastList.h>
#include <gtsam/base/ConcurrentMap.h>
#include <gtsam/base/FastVector.h>
 
#include <string>
 
namespace gtsam {
 
  // Forward declarations
  template<class FACTOR> class FactorGraph;
  template<class BAYESTREE, class GRAPH> class EliminatableClusterTree;
 
  /* ************************************************************************* */
  struct GTSAM_EXPORT BayesTreeCliqueStats {
    double avgConditionalSize;
    std::size_t maxConditionalSize;
    double avgSeparatorSize;
    std::size_t maxSeparatorSize;
    void print(const std::string& s = "") const ;
  };
 
  struct GTSAM_EXPORT BayesTreeCliqueData {
    FastVector<std::size_t> conditionalSizes;
    FastVector<std::size_t> separatorSizes;
    BayesTreeCliqueStats getStats() const;
  };
 
  /* ************************************************************************* */
  template<class CLIQUE>
  class BayesTree
  {
  protected:
    typedef BayesTree<CLIQUE> This;
    typedef boost::shared_ptr<This> shared_ptr;
 
  public:
    typedef CLIQUE Clique; 
    typedef boost::shared_ptr<Clique> sharedClique; 
    typedef Clique Node; 
    typedef sharedClique sharedNode; 
    typedef typename CLIQUE::ConditionalType ConditionalType;
    typedef boost::shared_ptr<ConditionalType> sharedConditional;
    typedef typename CLIQUE::BayesNetType BayesNetType;
    typedef boost::shared_ptr<BayesNetType> sharedBayesNet;
    typedef typename CLIQUE::FactorType FactorType;
    typedef boost::shared_ptr<FactorType> sharedFactor;
    typedef typename CLIQUE::FactorGraphType FactorGraphType;
    typedef boost::shared_ptr<FactorGraphType> sharedFactorGraph;
    typedef typename FactorGraphType::Eliminate Eliminate;
    typedef typename CLIQUE::EliminationTraitsType EliminationTraitsType;
 
    typedef FastList<sharedClique> Cliques;
 
    typedef ConcurrentMap<Key, sharedClique> Nodes;
 
    typedef FastVector<sharedClique> Roots;
 
  protected:
 
    Nodes nodes_;
 
    Roots roots_;
 
 
    BayesTree() {}
 
    BayesTree(const This& other);
 
 
    This& operator=(const This& other);
 
 
    bool equals(const This& other, double tol = 1e-9) const;
 
  public:
    void print(const std::string& s = "",
        const KeyFormatter& keyFormatter = DefaultKeyFormatter) const;
 
 
    size_t size() const;
 
    inline bool empty() const {
      return nodes_.empty();
    }
 
    const Nodes& nodes() const { return nodes_; }
 
    const sharedNode operator[](Key j) const { return nodes_.at(j); }
 
    const Roots& roots() const { return roots_;  }
 
    const sharedClique& clique(Key j) const {
      typename Nodes::const_iterator c = nodes_.find(j);
      if(c == nodes_.end())
        throw std::out_of_range("Requested the BayesTree clique for a key that is not in the BayesTree");
      else
        return c->second;
    }
 
    BayesTreeCliqueData getCliqueData() const;
 
    size_t numCachedSeparatorMarginals() const;
 
    sharedConditional marginalFactor(Key j, const Eliminate& function = EliminationTraitsType::DefaultEliminate) const;
 
    sharedFactorGraph joint(Key j1, Key j2, const Eliminate& function = EliminationTraitsType::DefaultEliminate) const;
 
    sharedBayesNet jointBayesNet(Key j1, Key j2, const Eliminate& function = EliminationTraitsType::DefaultEliminate) const;
 
    void saveGraph(const std::string& s, const KeyFormatter& keyFormatter = DefaultKeyFormatter) const;
 
 
    template<class CONTAINER>
    Key findParentClique(const CONTAINER& parents) const;
 
    void clear();
 
    void deleteCachedShortcuts();
 
    void removePath(sharedClique clique, BayesNetType* bn, Cliques* orphans);
 
    void removeTop(const KeyVector& keys, BayesNetType* bn, Cliques* orphans);
 
    Cliques removeSubtree(const sharedClique& subtree);
 
    void insertRoot(const sharedClique& subtree);
 
    void addClique(const sharedClique& clique, const sharedClique& parent_clique = sharedClique());
 
    void addFactorsToGraph(FactorGraph<FactorType>* graph) const;
 
  protected:
 
    void saveGraph(std::ostream &s, sharedClique clique, const KeyFormatter& keyFormatter,
        int parentnum = 0) const;
 
    void getCliqueData(sharedClique clique, BayesTreeCliqueData* stats) const;
 
    void removeClique(sharedClique clique);
 
    void fillNodesIndex(const sharedClique& subtree);
 
    // Friend JunctionTree because it directly fills roots and nodes index.
    template<class BAYESRTEE, class GRAPH> friend class EliminatableClusterTree;
 
   private:
    friend class boost::serialization::access;
    template<class ARCHIVE>
    void serialize(ARCHIVE & ar, const unsigned int /*version*/) {
      ar & BOOST_SERIALIZATION_NVP(nodes_);
      ar & BOOST_SERIALIZATION_NVP(roots_);
    }
 
 
  }; // BayesTree
 
  /* ************************************************************************* */
  template<class CLIQUE>
  class BayesTreeOrphanWrapper : public CLIQUE::ConditionalType
  {
  public:
    typedef CLIQUE CliqueType;
    typedef typename CLIQUE::ConditionalType Base;
 
    boost::shared_ptr<CliqueType> clique;
 
    BayesTreeOrphanWrapper(const boost::shared_ptr<CliqueType>& clique) :
      clique(clique)
    {
      // Store parent keys in our base type factor so that eliminating those parent keys will pull
      // this subtree into the elimination.
      this->keys_.assign(clique->conditional()->beginParents(), clique->conditional()->endParents());
    }
 
    void print(const std::string& s="", const KeyFormatter& formatter = DefaultKeyFormatter) const override {
      clique->print(s + "stored clique", formatter);
    }
  };
 
}