Cleaned up variable elimination code in ClusterGraph
[libdai.git] / include / dai / regiongraph.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 classes Region, FRegion and RegionGraph, which implement a particular subclass of region graphs.
14
15
16 #ifndef __defined_libdai_regiongraph_h
17 #define __defined_libdai_regiongraph_h
18
19
20 #include <iostream>
21 #include <dai/bipgraph.h>
22 #include <dai/factorgraph.h>
23 #include <dai/weightedgraph.h>
24
25
26 namespace dai {
27
28
29 /// A Region is a set of variables with a counting number
30 class Region : public VarSet {
31 private:
32 /// Counting number
33 Real _c;
34
35 public:
36 /// Default constructor
37 Region() : VarSet(), _c(1.0) {}
38
39 /// Construct from a set of variables and a counting number
40 Region( const VarSet &x, Real c ) : VarSet(x), _c(c) {}
41
42 /// Returns constant reference to counting number
43 const Real & c() const { return _c; }
44
45 /// Returns reference to counting number
46 Real & c() { return _c; }
47 };
48
49
50 /// An FRegion is a factor with a counting number
51 class FRegion : public Factor {
52 private:
53 /// Counting number
54 Real _c;
55
56 public:
57 /// Default constructor
58 FRegion() : Factor(), _c(1.0) {}
59
60 /// Constructs from a factor and a counting number
61 FRegion( const Factor & x, Real c ) : Factor(x), _c(c) {}
62
63 /// Returns constant reference to counting number
64 const Real & c() const { return _c; }
65
66 /// Returns reference to counting number
67 Real & c() { return _c; }
68 };
69
70
71 /// A RegionGraph combines a bipartite graph consisting of outer regions (type FRegion) and inner regions (type Region) with a FactorGraph
72 /** A RegionGraph inherits from a FactorGraph and adds additional structure in the form of a "region graph". Our definition of region graph
73 * is inspired by [\ref HAK03], which is less general than the definition given in [\ref YFW05].
74 *
75 * The extra structure described by a RegionGraph over that described by a FactorGraph is:
76 * - a set of outer regions (indexed by \f$\alpha\f$), where each outer region consists of
77 * - a factor defined on a subset of variables
78 * - a counting number
79 * - a set of inner regions (indexed by \f$\beta\f$), where each inner region consists of
80 * - a subset of variables
81 * - a counting number
82 * - edges between inner and outer regions
83 *
84 * Each factor in the factor graph belongs to an outer region; normally, the factor contents
85 * of an outer region would be the product of all the factors that belong to that region.
86 */
87 class RegionGraph : public FactorGraph {
88 public:
89 /// Stores the neighborhood structure
90 BipartiteGraph G;
91
92 /// The outer regions (corresponding to nodes of type 1)
93 std::vector<FRegion> ORs;
94
95 /// The inner regions (corresponding to nodes of type 2)
96 std::vector<Region> IRs;
97
98 /// Stores for each factor index the index of the outer region it belongs to
99 std::vector<size_t> fac2OR;
100
101
102 public:
103 /// \name Constructors and destructors
104 //@{
105 /// Default constructor
106 RegionGraph() : FactorGraph(), G(), ORs(), IRs(), fac2OR() {}
107
108 /// Partially constructs a region graph from a factor graph
109 RegionGraph( const FactorGraph &fg ) : FactorGraph(fg), G(), ORs(), IRs(), fac2OR() {}
110
111 /// Constructs a region graph from a factor graph, a vector of outer regions, a vector of inner regions and a vector of edges
112 /** The counting numbers for the outer regions are set to 1.
113 */
114 RegionGraph( const FactorGraph &fg, const std::vector<VarSet> &ors, const std::vector<Region> &irs, const std::vector<std::pair<size_t,size_t> > &edges ) : FactorGraph(), G(), ORs(), IRs(), fac2OR() {
115 construct( fg, ors, irs, edges );
116
117 // Check counting numbers
118 #ifdef DAI_DEBUG
119 checkCountingNumbers();
120 #endif
121 }
122
123 /// Constructs a region graph from a factor graph, a vector of outer regions, a vector of inner regions and a vector of edges
124 /** \note The counting numbers for the outer regions need to be 1.
125 * \deprecated Please use dai::RegionGraph::RegionGraph( const FactorGraph &, const std::vector<VarSet> &, const std::vector<Region> &, const std::vector<std::pair<size_t,size_t> > & ) instead.
126 */
127 RegionGraph( const FactorGraph &fg, const std::vector<Region> &ors, const std::vector<Region> &irs, const std::vector<std::pair<size_t,size_t> > &edges );
128
129 /// Constructs a region graph from a factor graph and a vector of outer clusters (CVM style)
130 /** The region graph is constructed as in the Cluster Variation Method.
131 *
132 * The outer regions have as variable subsets the clusters specified in \a cl.
133 * Each factor in the factor graph \a fg is assigned to one of the outer regions.
134 * Each outer region gets counting number 1.
135 *
136 * The inner regions are (repeated) intersections of outer regions.
137 * An inner and an outer region are connected if the variables in the inner region form a
138 * subset of the variables in the outer region. The counting numbers for the inner
139 * regions are calculated by calcCountingNumbers() and satisfy the Moebius formula.
140 */
141 RegionGraph( const FactorGraph &fg, const std::vector<VarSet> &cl ) : FactorGraph(), G(), ORs(), IRs(), fac2OR() {
142 constructCVM( fg, cl );
143
144 // Check counting numbers
145 #ifdef DAI_DEBUG
146 checkCountingNumbers();
147 #endif
148 }
149
150 /// Clone \c *this (virtual copy constructor)
151 virtual RegionGraph* clone() const { return new RegionGraph(*this); }
152 //@}
153
154 /// \name Queries
155 //@{
156 /// Returns number of outer regions
157 size_t nrORs() const { return ORs.size(); }
158 /// Returns number of inner regions
159 size_t nrIRs() const { return IRs.size(); }
160
161 /// Returns constant reference to outer region \a alpha
162 const FRegion & OR(size_t alpha) const { return ORs[alpha]; }
163 /// Returns reference to outer region \a alpha
164 FRegion & OR(size_t alpha) { return ORs[alpha]; }
165
166 /// Returns constant reference to inner region \a beta
167 const Region & IR(size_t beta) const { return IRs[beta]; }
168 /// Returns reference to inner region \a beta
169 Region & IR(size_t beta) { return IRs[beta]; }
170
171 /// Returns constant reference to the neighbors of outer region \a alpha
172 const Neighbors & nbOR( size_t alpha ) const { return G.nb1(alpha); }
173 /// Returns constant reference to the neighbors of inner region \a beta
174 const Neighbors & nbIR( size_t beta ) const { return G.nb2(beta); }
175
176 /// Check whether the counting numbers are valid
177 /** Counting numbers are said to be (variable) valid if for each variable \f$x\f$,
178 * \f[\sum_{\alpha \ni x} c_\alpha + \sum_{\beta \ni x} c_\beta = 1\f]
179 * or in words, if the sum of the counting numbers of the regions
180 * that contain the variable equals one.
181 */
182 bool checkCountingNumbers() const;
183 //@}
184
185 /// \name Operations
186 //@{
187 /// Set the content of the \a I 'th factor and make a backup of its old content if \a backup == \c true
188 virtual void setFactor( size_t I, const Factor &newFactor, bool backup = false ) {
189 FactorGraph::setFactor( I, newFactor, backup );
190 RecomputeOR( I );
191 }
192
193 /// Set the contents of all factors as specified by \a facs and make a backup of the old contents if \a backup == \c true
194 virtual void setFactors( const std::map<size_t, Factor> & facs, bool backup = false ) {
195 FactorGraph::setFactors( facs, backup );
196 VarSet ns;
197 for( std::map<size_t, Factor>::const_iterator fac = facs.begin(); fac != facs.end(); fac++ )
198 ns |= fac->second.vars();
199 RecomputeORs( ns );
200 }
201
202 /// Recompute all outer regions
203 /** The factor contents of each outer region is set to the product of the factors belonging to that region.
204 */
205 void RecomputeORs();
206
207 /// Recompute all outer regions involving the variables in \a vs
208 /** The factor contents of each outer region involving at least one of the variables in \a vs is set to the product of the factors belonging to that region.
209 */
210 void RecomputeORs( const VarSet &vs );
211
212 /// Recompute all outer regions involving factor \a I
213 /** The factor contents of each outer region involving the \a I 'th factor is set to the product of the factors belonging to that region.
214 */
215 void RecomputeOR( size_t I );
216
217 /// Calculates counting numbers of inner regions based upon counting numbers of outer regions
218 /** The counting numbers of the inner regions are set using the Moebius inversion formula:
219 * \f[ c_\beta := 1 - \sum_{\gamma \in \mathrm{an}(\beta)} c_\gamma \f]
220 * where \f$\mathrm{an}(\beta)\f$ are the ancestors of inner region \f$\beta\f$ according to
221 * the partial ordering induced by the subset relation (i.e., a region is a child of another
222 * region if its variables are a subset of the variables of its parent region).
223 */
224 void calcCountingNumbers();
225 //@}
226
227 /// \name Input/output
228 //@{
229 /// Writes a RegionGraph to an output stream
230 friend std::ostream & operator << ( std::ostream & os, const RegionGraph & rg );
231 //@}
232
233 protected:
234 /// Helper function for constructors
235 void construct( const FactorGraph &fg, const std::vector<VarSet> &ors, const std::vector<Region> &irs, const std::vector<std::pair<size_t,size_t> > &edges );
236
237 /// Helper function for constructors (CVM style)
238 void constructCVM( const FactorGraph &fg, const std::vector<VarSet> &cl );
239 };
240
241
242 } // end of namespace dai
243
244
245 #endif