Fixed three minor issues
[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 compared with 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 * \idea Generalize the definition of region graphs to the one given in [\ref YFW05], i.e., replace
87 * the current implementation which uses a BipartiteGraph with one that uses a DAG.
88 * \idea The outer regions are products of factors; right now, this product is constantly cached:
89 * changing one factor results in an update of all relevant outer regions. This may not be the most
90 * efficient approach; an alternative would be to only precompute the factor products at the start
91 * of an inference algorithm - e.g., in init(). This has the additional advantage that FactorGraph
92 e can offer write access to its factors.
93 */
94 class RegionGraph : public FactorGraph {
95 protected:
96 /// Stores the neighborhood structure
97 BipartiteGraph _G;
98
99 /// The outer regions (corresponding to nodes of type 1)
100 std::vector<FRegion> _ORs;
101
102 /// The inner regions (corresponding to nodes of type 2)
103 std::vector<Region> _IRs;
104
105 /// Stores for each factor index the index of the outer region it belongs to
106 std::vector<size_t> _fac2OR;
107
108
109 public:
110 /// \name Constructors and destructors
111 //@{
112 /// Default constructor
113 RegionGraph() : FactorGraph(), _G(), _ORs(), _IRs(), _fac2OR() {}
114
115 /// Constructs a region graph from a factor graph, a vector of outer regions, a vector of inner regions and a vector of edges
116 /** The counting numbers for the outer regions are set to 1.
117 */
118 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() {
119 construct( fg, ors, irs, edges );
120
121 // Check counting numbers
122 #ifdef DAI_DEBUG
123 checkCountingNumbers();
124 #endif
125 }
126
127 /// Constructs a region graph from a factor graph and a vector of outer clusters (CVM style)
128 /** The region graph is constructed as in the Cluster Variation Method.
129 *
130 * The outer regions have as variable subsets the clusters specified in \a cl.
131 * Each factor in the factor graph \a fg is assigned to one of the outer regions.
132 * Each outer region gets counting number 1.
133 *
134 * The inner regions are (repeated) intersections of outer regions.
135 * An inner and an outer region are connected if the variables in the inner region form a
136 * subset of the variables in the outer region. The counting numbers for the inner
137 * regions are calculated by calcCountingNumbers() and satisfy the Moebius formula.
138 */
139 RegionGraph( const FactorGraph& fg, const std::vector<VarSet>& cl ) : FactorGraph(), _G(), _ORs(), _IRs(), _fac2OR() {
140 constructCVM( fg, cl );
141
142 // Check counting numbers
143 #ifdef DAI_DEBUG
144 checkCountingNumbers();
145 #endif
146 }
147
148 /// Clone \c *this (virtual copy constructor)
149 virtual RegionGraph* clone() const { return new RegionGraph(*this); }
150 //@}
151
152 /// \name Accessors and mutators
153 //@{
154 /// Returns number of outer regions
155 size_t nrORs() const { return _ORs.size(); }
156 /// Returns number of inner regions
157 size_t nrIRs() const { return _IRs.size(); }
158
159 /// Returns constant reference to outer region \a alpha
160 const FRegion& OR( size_t alpha ) const {
161 DAI_DEBASSERT( alpha < nrORs() );
162 return _ORs[alpha];
163 }
164 /// Returns reference to outer region \a alpha
165 FRegion& OR( size_t alpha ) {
166 DAI_DEBASSERT( alpha < nrORs() );
167 return _ORs[alpha];
168 }
169
170 /// Returns constant reference to inner region \a beta
171 const Region& IR( size_t beta ) const {
172 DAI_DEBASSERT( beta < nrIRs() );
173 return _IRs[beta];
174 }
175 /// Returns reference to inner region \a beta
176 Region& IR( size_t beta ) {
177 DAI_DEBASSERT( beta < nrIRs() );
178 return _IRs[beta];
179 }
180
181 /// Returns the index of the outer region to which the \a I 'th factor corresponds
182 size_t fac2OR( size_t I ) const {
183 DAI_DEBASSERT( I < nrFactors() );
184 DAI_DEBASSERT( I < _fac2OR.size() );
185 return _fac2OR[I];
186 }
187
188 /// Returns constant reference to the neighbors of outer region \a alpha
189 const Neighbors& nbOR( size_t alpha ) const { return _G.nb1(alpha); }
190
191 /// Returns constant reference to the neighbors of inner region \a beta
192 const Neighbors& nbIR( size_t beta ) const { return _G.nb2(beta); }
193
194 /// Returns DAG structure of the region graph
195 /** \note Currently, the DAG is implemented as a BipartiteGraph; the nodes of
196 * type 1 are the outer regions, the nodes of type 2 the inner regions, and
197 * edges correspond with arrows from nodes of type 1 to type 2.
198 */
199 const BipartiteGraph& DAG() const { return _G; }
200 //@}
201
202 /// \name Queries
203 //@{
204 /// Check whether the counting numbers are valid
205 /** Counting numbers are said to be (variable) valid if for each variable \f$x\f$,
206 * \f[\sum_{\alpha \ni x} c_\alpha + \sum_{\beta \ni x} c_\beta = 1\f]
207 * or in words, if the sum of the counting numbers of the regions
208 * that contain the variable equals one.
209 */
210 bool checkCountingNumbers() const;
211 //@}
212
213 /// \name Operations
214 //@{
215 /// Set the content of the \a I 'th factor and make a backup of its old content if \a backup == \c true
216 virtual void setFactor( size_t I, const Factor& newFactor, bool backup = false ) {
217 FactorGraph::setFactor( I, newFactor, backup );
218 recomputeOR( I );
219 }
220
221 /// Set the contents of all factors as specified by \a facs and make a backup of the old contents if \a backup == \c true
222 virtual void setFactors( const std::map<size_t, Factor>& facs, bool backup = false ) {
223 FactorGraph::setFactors( facs, backup );
224 VarSet ns;
225 for( std::map<size_t, Factor>::const_iterator fac = facs.begin(); fac != facs.end(); fac++ )
226 ns |= fac->second.vars();
227 recomputeORs( ns );
228 }
229
230 /// Calculates counting numbers of inner regions based upon counting numbers of outer regions
231 /** The counting numbers of the inner regions are set using the Moebius inversion formula:
232 * \f[ c_\beta := 1 - \sum_{\gamma \in \mathrm{an}(\beta)} c_\gamma \f]
233 * where \f$\mathrm{an}(\beta)\f$ are the ancestors of inner region \f$\beta\f$ according to
234 * the partial ordering induced by the subset relation (i.e., a region is a child of another
235 * region if its variables are a subset of the variables of its parent region).
236 * \deprecated This functionality has been protected.
237 */
238 void calcCountingNumbers() { calcCVMCountingNumbers(); }
239
240 /// Recompute all outer regions
241 /** The factor contents of each outer region is set to the product of the factors belonging to that region.
242 * \deprecated This functionality has been protected.
243 */
244 void RecomputeORs() { recomputeORs(); }
245
246 /// Recompute all outer regions involving the variables in \a vs
247 /** 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.
248 * \deprecated This functionality has been protected.
249 */
250 void RecomputeORs( const VarSet& vs ) { recomputeORs( vs ); }
251
252 /// Recompute all outer regions involving factor \a I
253 /** 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.
254 * \deprecated This functionality has been protected.
255 */
256 void RecomputeOR( size_t I ) { recomputeOR( I ); }
257 //@}
258
259 /// \name Input/output
260 //@{
261 /// Reads a region graph from a file
262 /** \note Not implemented yet
263 */
264 virtual void ReadFromFile( const char* /*filename*/ ) {
265 DAI_THROW(NOT_IMPLEMENTED);
266 }
267
268 /// Writes a factor graph to a file
269 /** \note Not implemented yet
270 */
271 virtual void WriteToFile( const char* /*filename*/, size_t /*precision*/=15 ) const {
272 DAI_THROW(NOT_IMPLEMENTED);
273 }
274
275 /// Writes a RegionGraph to an output stream
276 friend std::ostream& operator<< ( std::ostream& os, const RegionGraph& rg );
277
278 /// Writes a region graph to a GraphViz .dot file
279 /** \note Not implemented yet
280 */
281 virtual void printDot( std::ostream& /*os*/ ) const {
282 DAI_THROW(NOT_IMPLEMENTED);
283 }
284 //@}
285
286 protected:
287 /// Helper function for constructors
288 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 );
289
290 /// Helper function for constructors (CVM style)
291 void constructCVM( const FactorGraph& fg, const std::vector<VarSet>& cl );
292
293 /// Recompute all outer regions
294 /** The factor contents of each outer region is set to the product of the factors belonging to that region.
295 */
296 void recomputeORs();
297
298 /// Recompute all outer regions involving the variables in \a vs
299 /** 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.
300 */
301 void recomputeORs( const VarSet& vs );
302
303 /// Recompute all outer regions involving factor \a I
304 /** 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.
305 */
306 void recomputeOR( size_t I );
307
308 /// Calculates counting numbers of inner regions based upon counting numbers of outer regions
309 /** The counting numbers of the inner regions are set using the Moebius inversion formula:
310 * \f[ c_\beta := 1 - \sum_{\gamma \in \mathrm{an}(\beta)} c_\gamma \f]
311 * where \f$\mathrm{an}(\beta)\f$ are the ancestors of inner region \f$\beta\f$ according to
312 * the partial ordering induced by the subset relation (i.e., a region is a child of another
313 * region if its variables are a subset of the variables of its parent region).
314 */
315 void calcCVMCountingNumbers();
316
317 };
318
319
320 } // end of namespace dai
321
322
323 #endif