aaff0e21adacb144366e8f2fb302b195a3018917
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 JTree
* create() const { return new JTree(); }
90 virtual std::string
identify() const;
91 virtual Factor
belief( const Var
&n
) const;
92 virtual Factor
belief( const VarSet
&ns
) const;
93 virtual std::vector
<Factor
> beliefs() const;
94 virtual Real
logZ() const;
95 virtual void init() {}
96 virtual void init( const VarSet
&/*ns*/ ) {}
98 virtual double maxDiff() const { return 0.0; }
99 virtual size_t Iterations() const { return 1UL; }
103 /// @name Additional interface specific for JTree
105 void GenerateJT( const std::vector
<VarSet
> &Cliques
);
107 /// Returns reference the message from outer region alpha to its _beta'th neighboring inner region
108 Factor
& message( size_t alpha
, size_t _beta
) { return _mes
[alpha
][_beta
]; }
109 /// Returns const reference to the message from outer region alpha to its _beta'th neighboring inner region
110 const Factor
& message( size_t alpha
, size_t _beta
) const { return _mes
[alpha
][_beta
]; }
112 /// Runs junction-tree with HUGIN updates
115 /// Runs junction-tree with Shafer-Shenoy updates
116 void runShaferShenoy();
118 /// Finds an efficient tree for calculating the marginal of some variables
119 size_t findEfficientTree( const VarSet
& ns
, DEdgeVec
&Tree
, size_t PreviousRoot
=(size_t)-1 ) const;
121 /// Calculates the marginal of a set of variables
122 Factor
calcMarginal( const VarSet
& ns
);
126 void setProperties( const PropertySet
&opts
);
127 PropertySet
getProperties() const;
128 std::string
printProperties() const;
132 /// Calculates upper bound to the treewidth of a FactorGraph
134 * \return a pair (number of variables in largest clique, number of states in largest clique)
136 std::pair
<size_t,size_t> treewidth( const FactorGraph
& fg
);
139 } // end of namespace dai