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         /// Construct from FactorGraph fg and PropertySet opts
  83         JTree( const FactorGraph &fg, const PropertySet &opts, bool automatic=true );
  84
  85
  86         /// @name General InfAlg interface
  87         //@{
  88         virtual JTree* clone() const { return new JTree(*this); }
  89         virtual std::string identify() const;
  90         virtual Factor belief( const Var &n ) const;
  91         virtual Factor belief( const VarSet &ns ) const;
  92         virtual std::vector<Factor> beliefs() const;
  93         virtual Real logZ() const;
  94         virtual void init() {}
  95         virtual void init( const VarSet &/*ns*/ ) {}
  96         virtual double run();
  97         virtual double maxDiff() const { return 0.0; }
  98         virtual size_t Iterations() const { return 1UL; }
  99         //@}
 100
 101
 102         /// @name Additional interface specific for JTree
 103         //@{
 104         void GenerateJT( const std::vector<VarSet> &Cliques );
 105
 106         /// Returns reference the message from outer region alpha to its _beta'th neighboring inner region
 107         Factor & message( size_t alpha, size_t _beta ) { return _mes[alpha][_beta]; }
 108         /// Returns const reference to the message from outer region alpha to its _beta'th neighboring inner region
 109         const Factor & message( size_t alpha, size_t _beta ) const { return _mes[alpha][_beta]; }
 110
 111         /// Runs junction-tree with HUGIN updates
 112         void runHUGIN();
 113
 114         /// Runs junction-tree with Shafer-Shenoy updates
 115         void runShaferShenoy();
 116
 117         /// Finds an efficient tree for calculating the marginal of some variables
 118         size_t findEfficientTree( const VarSet& ns, DEdgeVec &Tree, size_t PreviousRoot=(size_t)-1 ) const;
 119
 120         /// Calculates the marginal of a set of variables
 121         Factor calcMarginal( const VarSet& ns );
 122         //@}
 123
 124     private:
 125         void setProperties( const PropertySet &opts );
 126         PropertySet getProperties() const;
 127         std::string printProperties() const;
 128 };
 129
 130
 131 /// Calculates upper bound to the treewidth of a FactorGraph
 132 /** \relates JTree
 133  *  \return a pair (number of variables in largest clique, number of states in largest clique)
 134  */
 135 std::pair<size_t,size_t> treewidth( const FactorGraph & fg );
 136
 137
 138 } // end of namespace dai
 139
 140
 141 #endif