Merged SVN head ...
[libdai.git] / include / dai / jtree.h
1 /* Copyright (C) 2006-2008 Joris Mooij [j dot mooij at science dot ru dot nl]
2 Radboud University Nijmegen, The Netherlands
3
4 This file is part of libDAI.
5
6 libDAI is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 libDAI is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with libDAI; if not, write to the Free Software
18 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 */
20
21
22 #ifndef __defined_libdai_jtree_h
23 #define __defined_libdai_jtree_h
24
25
26 #include <vector>
27 #include <string>
28 #include <dai/daialg.h>
29 #include <dai/varset.h>
30 #include <dai/regiongraph.h>
31 #include <dai/factorgraph.h>
32 #include <dai/clustergraph.h>
33 #include <dai/weightedgraph.h>
34 #include <dai/enum.h>
35 #include <dai/properties.h>
36
37
38 namespace dai {
39
40
41 class JTree : public DAIAlgRG {
42 protected:
43 DEdgeVec _RTree; // rooted tree
44 std::vector<Factor> _Qa;
45 std::vector<Factor> _Qb;
46 std::vector<std::vector<Factor> > _mes;
47 double _logZ;
48
49 public:
50 struct Properties {
51 size_t verbose;
52 DAI_ENUM(UpdateType,HUGIN,SHSH)
53 UpdateType updates;
54 } props;
55 /// Name of this inference method
56 static const char *Name;
57
58 public:
59 /// Default constructor
60 JTree() : DAIAlgRG(), _RTree(), _Qa(), _Qb(), _mes(), _logZ(), props() {}
61
62 /// Construct from FactorGraph fg and PropertySet opts
63 JTree( const FactorGraph &fg, const PropertySet &opts, bool automatic=true );
64
65 /// Copy constructor
66 JTree( const JTree &x ) : DAIAlgRG(x), _RTree(x._RTree), _Qa(x._Qa), _Qb(x._Qb), _mes(x._mes), _logZ(x._logZ), props(x.props) {}
67
68 /// Clone *this (virtual copy constructor)
69 virtual JTree* clone() const { return new JTree(*this); }
70
71 /// Create (virtual default constructor)
72 virtual JTree* create() const { return new JTree(); }
73
74 /// Assignment operator
75 JTree& operator=( const JTree &x ) {
76 if( this != &x ) {
77 DAIAlgRG::operator=( x );
78 _RTree = x._RTree;
79 _Qa = x._Qa;
80 _Qb = x._Qb;
81 _mes = x._mes;
82 _logZ = x._logZ;
83 props = x.props;
84 }
85 return *this;
86 }
87
88 /// Identifies itself for logging purposes
89 virtual std::string identify() const;
90
91 /// Get single node belief
92 virtual Factor belief( const Var &n ) const;
93
94 /// Get general belief
95 virtual Factor belief( const VarSet &ns ) const;
96
97 /// Get all beliefs
98 virtual std::vector<Factor> beliefs() const;
99
100 /// Get log partition sum
101 virtual Real logZ() const;
102
103 /// Clear messages and beliefs
104 virtual void init() {}
105
106 /// Clear messages and beliefs corresponding to the nodes in ns
107 virtual void init( const VarSet &/*ns*/ ) {}
108
109 /// The actual approximate inference algorithm
110 virtual double run();
111
112 /// Return maximum difference between single node beliefs in the last pass
113 virtual double maxDiff() const { return 0.0; }
114
115 /// Return number of passes over the factorgraph
116 virtual size_t Iterations() const { return 1UL; }
117
118
119 void GenerateJT( const std::vector<VarSet> &Cliques );
120
121 Factor & message( size_t alpha, size_t _beta ) { return _mes[alpha][_beta]; }
122 const Factor & message( size_t alpha, size_t _beta ) const { return _mes[alpha][_beta]; }
123
124 void runHUGIN();
125 void runShaferShenoy();
126 size_t findEfficientTree( const VarSet& ns, DEdgeVec &Tree, size_t PreviousRoot=(size_t)-1 ) const;
127 Factor calcMarginal( const VarSet& ns );
128
129 void setProperties( const PropertySet &opts );
130 PropertySet getProperties() const;
131 std::string printProperties() const;
132 };
133
134
135 std::pair<size_t,size_t> treewidth( const FactorGraph & fg );
136
137
138 } // end of namespace dai
139
140
141 #endif