1 /* This file is part of libDAI - http://www.libdai.org/
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.
7 * Copyright (C) 2006-2009 Joris Mooij [joris dot mooij at libdai dot org]
8 * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
13 /// \brief Defines class JTree
14 /// \todo Improve documentation
17 #ifndef __defined_libdai_jtree_h
18 #define __defined_libdai_jtree_h
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>
30 #include <dai/properties.h>
36 /// Exact inference algorithm using junction tree
37 class JTree
: public DAIAlgRG
{
39 std::vector
<std::vector
<Factor
> > _mes
;
46 /// Outer region beliefs
47 std::vector
<Factor
> Qa
;
49 /// Inner region beliefs
50 std::vector
<Factor
> Qb
;
52 /// Parameters of this inference algorithm
54 /// Enumeration of possible JTree updates
55 DAI_ENUM(UpdateType
,HUGIN
,SHSH
);
57 /// Enumeration of inference variants
58 DAI_ENUM(InfType
,SUMPROD
,MAXPROD
);
66 /// Type of inference: sum-product or max-product?
70 /// Name of this inference algorithm
71 static const char *Name
;
74 /// Default constructor
75 JTree() : DAIAlgRG(), _mes(), _logZ(), RTree(), Qa(), Qb(), props() {}
77 /// Construct from FactorGraph fg and PropertySet opts
78 JTree( const FactorGraph
&fg
, const PropertySet
&opts
, bool automatic
=true );
81 /// \name General InfAlg interface
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*/ ) {}
92 virtual Real
maxDiff() const { return 0.0; }
93 virtual size_t Iterations() const { return 1UL; }
97 /// \name Additional interface specific for JTree
99 void GenerateJT( const std::vector
<VarSet
> &Cliques
);
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
]; }
106 /// Runs junction-tree with HUGIN updates
109 /// Runs junction-tree with Shafer-Shenoy updates
110 void runShaferShenoy();
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;
115 /// Calculates the marginal of a set of variables
116 Factor
calcMarginal( const VarSet
& ns
);
118 /// Calculates the joint state of all variables that has maximum probability
119 /** Assumes that run() has been called and that props.inference == MAXPROD
121 std::vector
<std::size_t> findMaximum() const;
124 /// \name Managing parameters (which are stored in JTree::props)
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.
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;
139 /// Calculates upper bound to the treewidth of a FactorGraph
141 * \return a pair (number of variables in largest clique, number of states in largest clique)
143 std::pair
<size_t,size_t> treewidth( const FactorGraph
& fg
);
146 } // end of namespace dai