include/dai/jtree.h

   1 /*  Copyright (C) 2006-2008  Joris Mooij  [joris dot mooij at tuebingen dot mpg dot de]
   2     Radboud University Nijmegen, The Netherlands /
   3     Max Planck Institute for Biological Cybernetics, Germany
   4
   5     This file is part of libDAI.
   6
   7     libDAI is free software; you can redistribute it and/or modify
   8     it under the terms of the GNU General Public License as published by
   9     the Free Software Foundation; either version 2 of the License, or
  10     (at your option) any later version.
  11
  12     libDAI is distributed in the hope that it will be useful,
  13     but WITHOUT ANY WARRANTY; without even the implied warranty of
  14     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15     GNU General Public License for more details.
  16
  17     You should have received a copy of the GNU General Public License
  18     along with libDAI; if not, write to the Free Software
  19     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20 */
  21
  22
  23 /// \file
  24 /// \brief Defines class JTree
  25 /// \todo Improve documentation
  26
  27
  28 #ifndef __defined_libdai_jtree_h
  29 #define __defined_libdai_jtree_h
  30
  31
  32 #include <vector>
  33 #include <string>
  34 #include <dai/daialg.h>
  35 #include <dai/varset.h>
  36 #include <dai/regiongraph.h>
  37 #include <dai/factorgraph.h>
  38 #include <dai/clustergraph.h>
  39 #include <dai/weightedgraph.h>
  40 #include <dai/enum.h>
  41 #include <dai/properties.h>
  42
  43
  44 namespace dai {
  45
  46
  47 /// Exact inference algorithm using junction tree
  48 class JTree : public DAIAlgRG {
  49     private:
  50         std::vector<std::vector<Factor> >  _mes;
  51         double               _logZ;
  52
  53     public:
  54         /// Rooted tree
  55         DEdgeVec             RTree;
  56
  57         /// Outer region beliefs
  58         std::vector<Factor>  Qa;
  59
  60         /// Inner region beliefs
  61         std::vector<Factor>  Qb;
  62
  63         /// Parameters of this inference algorithm
  64         struct Properties {
  65             /// Enumeration of possible JTree updates
  66             DAI_ENUM(UpdateType,HUGIN,SHSH)
  67
  68             /// Verbosity
  69             size_t verbose;
  70
  71             /// Type of updates
  72             UpdateType updates;
  73         } props;
  74
  75         /// Name of this inference algorithm
  76         static const char *Name;
  77
  78     public:
  79         /// Default constructor
  80         JTree() : DAIAlgRG(), _mes(), _logZ(), RTree(), Qa(), Qb(), props() {}
  81
  82         /// Copy constructor
  83         JTree( const JTree &x ) : DAIAlgRG(x), _mes(x._mes), _logZ(x._logZ), RTree(x.RTree), Qa(x.Qa), Qb(x.Qb), props(x.props) {}
  84
  85         /// Assignment operator
  86         JTree& operator=( const JTree &x ) {
  87             if( this != &x ) {
  88                 DAIAlgRG::operator=( x );
  89                 _mes    = x._mes;
  90                 _logZ   = x._logZ;
  91                 RTree   = x.RTree;
  92                 Qa      = x.Qa;
  93                 Qb      = x.Qb;
  94                 props   = x.props;
  95             }
  96             return *this;
  97         }
  98
  99         /// Construct from FactorGraph fg and PropertySet opts
 100         JTree( const FactorGraph &fg, const PropertySet &opts, bool automatic=true );
 101
 102
 103         /// @name General InfAlg interface
 104         //@{
 105         virtual JTree* clone() const { return new JTree(*this); }
 106         virtual JTree* create() const { return new JTree(); }
 107         virtual std::string identify() const;
 108         virtual Factor belief( const Var &n ) const;
 109         virtual Factor belief( const VarSet &ns ) const;
 110         virtual std::vector<Factor> beliefs() const;
 111         virtual Real logZ() const;
 112         virtual void init() {}
 113         virtual void init( const VarSet &/*ns*/ ) {}
 114         virtual double run();
 115         virtual double maxDiff() const { return 0.0; }
 116         virtual size_t Iterations() const { return 1UL; }
 117         //@}
 118
 119
 120         /// @name Additional interface specific for JTree
 121         //@{
 122         void GenerateJT( const std::vector<VarSet> &Cliques );
 123
 124         /// Returns reference the message from outer region alpha to its _beta'th neighboring inner region
 125         Factor & message( size_t alpha, size_t _beta ) { return _mes[alpha][_beta]; }
 126         /// Returns const reference to the message from outer region alpha to its _beta'th neighboring inner region
 127         const Factor & message( size_t alpha, size_t _beta ) const { return _mes[alpha][_beta]; }
 128
 129         /// Runs junction-tree with HUGIN updates
 130         void runHUGIN();
 131
 132         /// Runs junction-tree with Shafer-Shenoy updates
 133         void runShaferShenoy();
 134
 135         /// Finds an efficient tree for calculating the marginal of some variables
 136         size_t findEfficientTree( const VarSet& ns, DEdgeVec &Tree, size_t PreviousRoot=(size_t)-1 ) const;
 137
 138         /// Calculates the marginal of a set of variables
 139         Factor calcMarginal( const VarSet& ns );
 140         //@}
 141
 142     private:
 143         void setProperties( const PropertySet &opts );
 144         PropertySet getProperties() const;
 145         std::string printProperties() const;
 146 };
 147
 148
 149 /// Calculates upper bound to the treewidth of a FactorGraph
 150 /** \relates JTree
 151  *  \return a pair (number of variables in largest clique, number of states in largest clique)
 152  */
 153 std::pair<size_t,size_t> treewidth( const FactorGraph & fg );
 154
 155
 156 } // end of namespace dai
 157
 158
 159 #endif