8107757bc565113767b52ad7546fad7b9a7e72ee
[libdai.git] / 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 double _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 double run();
92 virtual double 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 private:
125 void setProperties( const PropertySet &opts );
126 PropertySet getProperties() const;
127 std::string printProperties() const;
128 };
129
130
131 /// Calculates upper bound to the treewidth of a FactorGraph
132 /** \relates JTree
133 * \return a pair (number of variables in largest clique, number of states in largest clique)
134 */
135 std::pair<size_t,size_t> treewidth( const FactorGraph & fg );
136
137
138 } // end of namespace dai
139
140
141 #endif