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 #ifndef __defined_libdai_jtree_h
  24 #define __defined_libdai_jtree_h
  25
  26
  27 #include <vector>
  28 #include <string>
  29 #include <dai/daialg.h>
  30 #include <dai/varset.h>
  31 #include <dai/regiongraph.h>
  32 #include <dai/factorgraph.h>
  33 #include <dai/clustergraph.h>
  34 #include <dai/weightedgraph.h>
  35 #include <dai/enum.h>
  36 #include <dai/properties.h>
  37
  38
  39 namespace dai {
  40
  41
  42 class JTree : public DAIAlgRG {
  43     private:
  44         std::vector<std::vector<Factor> >  _mes;
  45         double               _logZ;
  46
  47     public:
  48         DEdgeVec             RTree;     // rooted tree
  49         std::vector<Factor>  Qa;
  50         std::vector<Factor>  Qb;
  51         struct Properties {
  52             size_t verbose;
  53             DAI_ENUM(UpdateType,HUGIN,SHSH)
  54             UpdateType updates;
  55         } props;
  56         /// Name of this inference method
  57         static const char *Name;
  58
  59     public:
  60         /// Default constructor
  61         JTree() : DAIAlgRG(), _mes(), _logZ(), RTree(), Qa(), Qb(), props() {}
  62
  63         /// Construct from FactorGraph fg and PropertySet opts
  64         JTree( const FactorGraph &fg, const PropertySet &opts, bool automatic=true );
  65
  66         /// Copy constructor
  67         JTree( const JTree &x ) : DAIAlgRG(x), _mes(x._mes), _logZ(x._logZ), RTree(x.RTree), Qa(x.Qa), Qb(x.Qb), props(x.props) {}
  68
  69         /// Clone *this (virtual copy constructor)
  70         virtual JTree* clone() const { return new JTree(*this); }
  71
  72         /// Create (virtual default constructor)
  73         virtual JTree* create() const { return new JTree(); }
  74
  75         /// Assignment operator
  76         JTree& operator=( const JTree &x ) {
  77             if( this != &x ) {
  78                 DAIAlgRG::operator=( x );
  79                 _mes    = x._mes;
  80                 _logZ   = x._logZ;
  81                 RTree   = x.RTree;
  82                 Qa      = x.Qa;
  83                 Qb      = x.Qb;
  84                 props   = x.props;
  85             }
  86             return *this;
  87         }
  88
  89         /// Identifies itself for logging purposes
  90         virtual std::string identify() const;
  91
  92         /// Get single node belief
  93         virtual Factor belief( const Var &n ) const;
  94
  95         /// Get general belief
  96         virtual Factor belief( const VarSet &ns ) const;
  97
  98         /// Get all beliefs
  99         virtual std::vector<Factor> beliefs() const;
 100
 101         /// Get log partition sum
 102         virtual Real logZ() const;
 103
 104         /// Clear messages and beliefs
 105         virtual void init() {}
 106
 107         /// Clear messages and beliefs corresponding to the nodes in ns
 108         virtual void init( const VarSet &/*ns*/ ) {}
 109
 110         /// The actual approximate inference algorithm
 111         virtual double run();
 112
 113         /// Return maximum difference between single node beliefs in the last pass
 114         virtual double maxDiff() const { return 0.0; }
 115
 116         /// Return number of passes over the factorgraph
 117         virtual size_t Iterations() const { return 1UL; }
 118
 119
 120         void GenerateJT( const std::vector<VarSet> &Cliques );
 121
 122         Factor & message( size_t alpha, size_t _beta ) { return _mes[alpha][_beta]; }
 123         const Factor & message( size_t alpha, size_t _beta ) const { return _mes[alpha][_beta]; }
 124
 125         void runHUGIN();
 126         void runShaferShenoy();
 127         size_t findEfficientTree( const VarSet& ns, DEdgeVec &Tree, size_t PreviousRoot=(size_t)-1 ) const;
 128         Factor calcMarginal( const VarSet& ns );
 129
 130         void setProperties( const PropertySet &opts );
 131         PropertySet getProperties() const;
 132         std::string printProperties() const;
 133 };
 134
 135
 136 std::pair<size_t,size_t> treewidth( const FactorGraph & fg );
 137
 138
 139 } // end of namespace dai
 140
 141
 142 #endif