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
5 This file is part of libDAI.
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.
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.
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
24 /// \brief Defines class JTree
25 /// \todo Improve documentation
28 #ifndef __defined_libdai_jtree_h
29 #define __defined_libdai_jtree_h
34 #include <dai/daialg.h>
35 #include <dai/varset.h>
36 #include <dai/regiongraph.h>
37 #include <dai/factorgraph.h>
38 #include <dai/clustergraph.h>
39 #include <dai/weightedgraph.h>
41 #include <dai/properties.h>
47 /// Exact inference algorithm using junction tree
48 class JTree
: public DAIAlgRG
{
50 std::vector
<std::vector
<Factor
> > _mes
;
57 /// Outer region beliefs
58 std::vector
<Factor
> Qa
;
60 /// Inner region beliefs
61 std::vector
<Factor
> Qb
;
63 /// Parameters of this inference algorithm
65 /// Enumeration of possible JTree updates
66 DAI_ENUM(UpdateType
,HUGIN
,SHSH
)
75 /// Name of this inference algorithm
76 static const char *Name
;
79 /// Default constructor
80 JTree() : DAIAlgRG(), _mes(), _logZ(), RTree(), Qa(), Qb(), props() {}
82 /// Construct from FactorGraph fg and PropertySet opts
83 JTree( const FactorGraph
&fg
, const PropertySet
&opts
, bool automatic
=true );
86 /// @name General InfAlg interface
88 virtual JTree
* clone() const { return new JTree(*this); }
89 virtual std::string
identify() const;
90 virtual Factor
belief( const Var
&n
) const;
91 virtual Factor
belief( const VarSet
&ns
) const;
92 virtual std::vector
<Factor
> beliefs() const;
93 virtual Real
logZ() const;
94 virtual void init() {}
95 virtual void init( const VarSet
&/*ns*/ ) {}
97 virtual double maxDiff() const { return 0.0; }
98 virtual size_t Iterations() const { return 1UL; }
102 /// @name Additional interface specific for JTree
104 void GenerateJT( const std::vector
<VarSet
> &Cliques
);
106 /// Returns reference the message from outer region alpha to its _beta'th neighboring inner region
107 Factor
& message( size_t alpha
, size_t _beta
) { return _mes
[alpha
][_beta
]; }
108 /// Returns const reference to the message from outer region alpha to its _beta'th neighboring inner region
109 const Factor
& message( size_t alpha
, size_t _beta
) const { return _mes
[alpha
][_beta
]; }
111 /// Runs junction-tree with HUGIN updates
114 /// Runs junction-tree with Shafer-Shenoy updates
115 void runShaferShenoy();
117 /// Finds an efficient tree for calculating the marginal of some variables
118 size_t findEfficientTree( const VarSet
& ns
, DEdgeVec
&Tree
, size_t PreviousRoot
=(size_t)-1 ) const;
120 /// Calculates the marginal of a set of variables
121 Factor
calcMarginal( const VarSet
& ns
);
125 void setProperties( const PropertySet
&opts
);
126 PropertySet
getProperties() const;
127 std::string
printProperties() const;
131 /// Calculates upper bound to the treewidth of a FactorGraph
133 * \return a pair (number of variables in largest clique, number of states in largest clique)
135 std::pair
<size_t,size_t> treewidth( const FactorGraph
& fg
);
138 } // end of namespace dai