-/* Copyright (C) 2006-2008 Joris Mooij [j dot mooij at science dot ru dot nl]
- Radboud University Nijmegen, The Netherlands
-
+/* Copyright (C) 2006-2008 Joris Mooij [joris dot mooij at tuebingen dot mpg dot de]
+ Radboud University Nijmegen, The Netherlands /
+ Max Planck Institute for Biological Cybernetics, Germany
+
This file is part of libDAI.
libDAI is free software; you can redistribute it and/or modify
*/
+/// \file
+/// \brief Defines class JTree
+/// \todo Improve documentation
+
+
#ifndef __defined_libdai_jtree_h
#define __defined_libdai_jtree_h
namespace dai {
+/// Exact inference algorithm using junction tree
class JTree : public DAIAlgRG {
- protected:
- DEdgeVec _RTree; // rooted tree
- std::vector<Factor> _Qa;
- std::vector<Factor> _Qb;
+ private:
std::vector<std::vector<Factor> > _mes;
double _logZ;
public:
+ /// Rooted tree
+ DEdgeVec RTree;
+
+ /// Outer region beliefs
+ std::vector<Factor> Qa;
+
+ /// Inner region beliefs
+ std::vector<Factor> Qb;
+
+ /// Parameters of this inference algorithm
struct Properties {
- size_t verbose;
+ /// Enumeration of possible JTree updates
DAI_ENUM(UpdateType,HUGIN,SHSH)
+
+ /// Verbosity
+ size_t verbose;
+
+ /// Type of updates
UpdateType updates;
} props;
- /// Name of this inference method
+
+ /// Name of this inference algorithm
static const char *Name;
public:
/// Default constructor
- JTree() : DAIAlgRG(), _RTree(), _Qa(), _Qb(), _mes(), _logZ(), props() {}
+ JTree() : DAIAlgRG(), _mes(), _logZ(), RTree(), Qa(), Qb(), props() {}
- /// Construct JTree object using the specified properties
+ /// Construct from FactorGraph fg and PropertySet opts
JTree( const FactorGraph &fg, const PropertySet &opts, bool automatic=true );
- /// Copy constructor
- JTree( const JTree &x ) : DAIAlgRG(x), _RTree(x._RTree), _Qa(x._Qa), _Qb(x._Qb), _mes(x._mes), _logZ(x._logZ), props(x.props) {}
-
- /// Assignment operator
- JTree & operator=( const JTree &x ) {
- if( this != &x ) {
- DAIAlgRG::operator=( x );
- _RTree = x._RTree;
- _Qa = x._Qa;
- _Qb = x._Qb;
- _mes = x._mes;
- _logZ = x._logZ;
- props = x.props;
- }
- return *this;
- }
-
- /// Clone (virtual copy constructor)
- virtual JTree* clone() const { return new JTree(*this); }
- /// Create (virtual constructor)
+ /// @name General InfAlg interface
+ //@{
+ virtual JTree* clone() const { return new JTree(*this); }
virtual JTree* create() const { return new JTree(); }
-
- /// Return number of passes over the factorgraph
- virtual size_t Iterations() const { return 1UL; }
-
- /// Return maximum difference between single node beliefs for two consecutive iterations
- virtual double maxDiff() const { return 0.0; }
-
- /// Identifies itself for logging purposes
- std::string identify() const;
-
- /// Get single node belief
- Factor belief( const Var &n ) const;
-
- /// Get general belief
- Factor belief( const VarSet &ns ) const;
-
- /// Get all beliefs
- std::vector<Factor> beliefs() const;
-
- /// Get log partition sum
- Real logZ() const;
-
- /// Clear messages and beliefs
- void init() {}
-
- /// Clear messages and beliefs corresponding to the nodes in ns
+ virtual std::string identify() const;
+ virtual Factor belief( const Var &n ) const;
+ virtual Factor belief( const VarSet &ns ) const;
+ virtual std::vector<Factor> beliefs() const;
+ virtual Real logZ() const;
+ virtual void init() {}
virtual void init( const VarSet &/*ns*/ ) {}
-
- /// The actual approximate inference algorithm
- double run();
+ virtual double run();
+ virtual double maxDiff() const { return 0.0; }
+ virtual size_t Iterations() const { return 1UL; }
+ //@}
+ /// @name Additional interface specific for JTree
+ //@{
void GenerateJT( const std::vector<VarSet> &Cliques );
+ /// Returns reference the message from outer region alpha to its _beta'th neighboring inner region
Factor & message( size_t alpha, size_t _beta ) { return _mes[alpha][_beta]; }
+ /// Returns const reference to the message from outer region alpha to its _beta'th neighboring inner region
const Factor & message( size_t alpha, size_t _beta ) const { return _mes[alpha][_beta]; }
+ /// Runs junction-tree with HUGIN updates
void runHUGIN();
+
+ /// Runs junction-tree with Shafer-Shenoy updates
void runShaferShenoy();
+
+ /// Finds an efficient tree for calculating the marginal of some variables
size_t findEfficientTree( const VarSet& ns, DEdgeVec &Tree, size_t PreviousRoot=(size_t)-1 ) const;
+
+ /// Calculates the marginal of a set of variables
Factor calcMarginal( const VarSet& ns );
+ //@}
+ private:
void setProperties( const PropertySet &opts );
PropertySet getProperties() const;
std::string printProperties() const;
};
+/// Calculates upper bound to the treewidth of a FactorGraph
+/** \relates JTree
+ * \return a pair (number of variables in largest clique, number of states in largest clique)
+ */
std::pair<size_t,size_t> treewidth( const FactorGraph & fg );
projects / libdai.git / blobdiff