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
  26
  27 #ifndef __defined_libdai_jtree_h
  28 #define __defined_libdai_jtree_h
  29
  30
  31 #include <vector>
  32 #include <string>
  33 #include <dai/daialg.h>
  34 #include <dai/varset.h>
  35 #include <dai/regiongraph.h>
  36 #include <dai/factorgraph.h>
  37 #include <dai/clustergraph.h>
  38 #include <dai/weightedgraph.h>
  39 #include <dai/enum.h>
  40 #include <dai/properties.h>
  41
  42
  43 namespace dai {
  44
  45
  46 /// Exact inference algorithm using junction tree
  47 class JTree : public DAIAlgRG {
  48     private:
  49         std::vector<std::vector<Factor> >  _mes;
  50         double               _logZ;
  51
  52     public:
  53         /// Rooted tree
  54         DEdgeVec             RTree;
  55
  56         /// Outer region beliefs
  57         std::vector<Factor>  Qa;
  58
  59         /// Inner region beliefs
  60         std::vector<Factor>  Qb;
  61
  62         /// Parameters of this inference algorithm
  63         struct Properties {
  64             /// Enumeration of possible JTree updates
  65             DAI_ENUM(UpdateType,HUGIN,SHSH)
  66
  67             /// Verbosity
  68             size_t verbose;
  69
  70             /// Type of updates
  71             UpdateType updates;
  72         } props;
  73
  74         /// Name of this inference algorithm
  75         static const char *Name;
  76
  77     public:
  78         /// Default constructor
  79         JTree() : DAIAlgRG(), _mes(), _logZ(), RTree(), Qa(), Qb(), props() {}
  80
  81         /// Copy constructor
  82         JTree( const JTree &x ) : DAIAlgRG(x), _mes(x._mes), _logZ(x._logZ), RTree(x.RTree), Qa(x.Qa), Qb(x.Qb), props(x.props) {}
  83
  84         /// Assignment operator
  85         JTree& operator=( const JTree &x ) {
  86             if( this != &x ) {
  87                 DAIAlgRG::operator=( x );
  88                 _mes    = x._mes;
  89                 _logZ   = x._logZ;
  90                 RTree   = x.RTree;
  91                 Qa      = x.Qa;
  92                 Qb      = x.Qb;
  93                 props   = x.props;
  94             }
  95             return *this;
  96         }
  97
  98         /// Construct from FactorGraph fg and PropertySet opts
  99         JTree( const FactorGraph &fg, const PropertySet &opts, bool automatic=true );
 100
 101
 102         /// @name General InfAlg interface
 103         //@{
 104         virtual JTree* clone() const { return new JTree(*this); }
 105         virtual JTree* create() const { return new JTree(); }
 106         virtual std::string identify() const;
 107         virtual Factor belief( const Var &n ) const;
 108         virtual Factor belief( const VarSet &ns ) const;
 109         virtual std::vector<Factor> beliefs() const;
 110         virtual Real logZ() const;
 111         virtual void init() {}
 112         virtual void init( const VarSet &/*ns*/ ) {}
 113         virtual double run();
 114         virtual double maxDiff() const { return 0.0; }
 115         virtual size_t Iterations() const { return 1UL; }
 116         //@}
 117
 118
 119         /// @name Additional interface specific for JTree
 120         //@{
 121         void GenerateJT( const std::vector<VarSet> &Cliques );
 122
 123         /// Returns reference the message from outer region alpha to its _beta'th neighboring inner region
 124         Factor & message( size_t alpha, size_t _beta ) { return _mes[alpha][_beta]; }
 125         /// Returns const reference to the message from outer region alpha to its _beta'th neighboring inner region
 126         const Factor & message( size_t alpha, size_t _beta ) const { return _mes[alpha][_beta]; }
 127
 128         /// Runs junction-tree with HUGIN updates
 129         void runHUGIN();
 130
 131         /// Runs junction-tree with Shafer-Shenoy updates
 132         void runShaferShenoy();
 133
 134         /// Finds an efficient tree for calculating the marginal of some variables
 135         size_t findEfficientTree( const VarSet& ns, DEdgeVec &Tree, size_t PreviousRoot=(size_t)-1 ) const;
 136
 137         /// Calculates the marginal of a set of variables
 138         Factor calcMarginal( const VarSet& ns );
 139         //@}
 140
 141     private:
 142         void setProperties( const PropertySet &opts );
 143         PropertySet getProperties() const;
 144         std::string printProperties() const;
 145 };
 146
 147
 148 /// Calculates upper bound to the treewidth of a FactorGraph
 149 /** \relates JTree
 150  *  \return a pair (number of variables in largest clique, number of states in largest clique)
 151  */
 152 std::pair<size_t,size_t> treewidth( const FactorGraph & fg );
 153
 154
 155 } // end of namespace dai
 156
 157
 158 #endif