include/dai/jtree.h

   1 /*  This file is part of libDAI - http://www.libdai.org/
   2  *
   3  *  libDAI is licensed under the terms of the GNU General Public License version
   4  *  2, or (at your option) any later version. libDAI is distributed without any
   5  *  warranty. See the file COPYING for more details.
   6  *
   7  *  Copyright (C) 2006-2009  Joris Mooij  [joris dot mooij at libdai dot org]
   8  *  Copyright (C) 2006-2007  Radboud University Nijmegen, The Netherlands
   9  */
  10
  11
  12 /// \file
  13 /// \brief Defines class JTree
  14 /// \todo Improve documentation
  15
  16
  17 #ifndef __defined_libdai_jtree_h
  18 #define __defined_libdai_jtree_h
  19
  20
  21 #include <vector>
  22 #include <string>
  23 #include <dai/daialg.h>
  24 #include <dai/varset.h>
  25 #include <dai/regiongraph.h>
  26 #include <dai/factorgraph.h>
  27 #include <dai/clustergraph.h>
  28 #include <dai/weightedgraph.h>
  29 #include <dai/enum.h>
  30 #include <dai/properties.h>
  31
  32
  33 namespace dai {
  34
  35
  36 /// Exact inference algorithm using junction tree
  37 class JTree : public DAIAlgRG {
  38     private:
  39         std::vector<std::vector<Factor> >  _mes;
  40         Real _logZ;
  41
  42     public:
  43         /// Rooted tree
  44         DEdgeVec             RTree;
  45
  46         /// Outer region beliefs
  47         std::vector<Factor>  Qa;
  48
  49         /// Inner region beliefs
  50         std::vector<Factor>  Qb;
  51
  52         /// Parameters of this inference algorithm
  53         struct Properties {
  54             /// Enumeration of possible JTree updates
  55             DAI_ENUM(UpdateType,HUGIN,SHSH);
  56
  57             /// Enumeration of inference variants
  58             DAI_ENUM(InfType,SUMPROD,MAXPROD);
  59
  60             /// Verbosity
  61             size_t verbose;
  62
  63             /// Type of updates
  64             UpdateType updates;
  65
  66             /// Type of inference: sum-product or max-product?
  67             InfType inference;
  68         } props;
  69
  70         /// Name of this inference algorithm
  71         static const char *Name;
  72
  73     public:
  74         /// Default constructor
  75         JTree() : DAIAlgRG(), _mes(), _logZ(), RTree(), Qa(), Qb(), props() {}
  76
  77         /// Construct from FactorGraph fg and PropertySet opts
  78         JTree( const FactorGraph &fg, const PropertySet &opts, bool automatic=true );
  79
  80
  81     /// \name General InfAlg interface
  82     //@{
  83         virtual JTree* clone() const { return new JTree(*this); }
  84         virtual std::string identify() const;
  85         virtual Factor belief( const Var &n ) const;
  86         virtual Factor belief( const VarSet &ns ) const;
  87         virtual std::vector<Factor> beliefs() const;
  88         virtual Real logZ() const;
  89         virtual void init() {}
  90         virtual void init( const VarSet &/*ns*/ ) {}
  91         virtual Real run();
  92         virtual Real maxDiff() const { return 0.0; }
  93         virtual size_t Iterations() const { return 1UL; }
  94     //@}
  95
  96
  97     /// \name Additional interface specific for JTree
  98     //@{
  99         void GenerateJT( const std::vector<VarSet> &Cliques );
 100
 101         /// Returns reference the message from outer region alpha to its _beta'th neighboring inner region
 102         Factor & message( size_t alpha, size_t _beta ) { return _mes[alpha][_beta]; }
 103         /// Returns const reference to the message from outer region alpha to its _beta'th neighboring inner region
 104         const Factor & message( size_t alpha, size_t _beta ) const { return _mes[alpha][_beta]; }
 105
 106         /// Runs junction-tree with HUGIN updates
 107         void runHUGIN();
 108
 109         /// Runs junction-tree with Shafer-Shenoy updates
 110         void runShaferShenoy();
 111
 112         /// Finds an efficient tree for calculating the marginal of some variables
 113         size_t findEfficientTree( const VarSet& ns, DEdgeVec &Tree, size_t PreviousRoot=(size_t)-1 ) const;
 114
 115         /// Calculates the marginal of a set of variables
 116         Factor calcMarginal( const VarSet& ns );
 117
 118         /// Calculates the joint state of all variables that has maximum probability
 119         /** Assumes that run() has been called and that props.inference == MAXPROD
 120          */
 121         std::vector<std::size_t> findMaximum() const;
 122     //@}
 123
 124     /// \name Managing parameters (which are stored in JTree::props)
 125     //@{
 126         /// Set parameters of this inference algorithm.
 127         /** The parameters are set according to \a opts.
 128          *  The values can be stored either as std::string or as the type of the corresponding JTree::props member.
 129          */
 130         void setProperties( const PropertySet &opts );
 131         /// Returns parameters of this inference algorithm converted into a PropertySet.
 132         PropertySet getProperties() const;
 133         /// Returns parameters of this inference algorithm formatted as a string in the format "[key1=val1,key2=val2,...,keyn=valn]".
 134         std::string printProperties() const;
 135     //@}
 136 };
 137
 138
 139 /// Calculates upper bound to the treewidth of a FactorGraph
 140 /** \relates JTree
 141  *  \return a pair (number of variables in largest clique, number of states in largest clique)
 142  */
 143 std::pair<size_t,size_t> treewidth( const FactorGraph & fg );
 144
 145
 146 } // end of namespace dai
 147
 148
 149 #endif