48a2c29d184149f2238d96c0b8594d835095234b
[libdai.git] / 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