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