1 /* This file is part of libDAI - http://www.libdai.org/
2 *
4 *
5 * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
6 */
9 /// \file
10 /// \brief Defines classes Region, FRegion and RegionGraph, which implement a particular subclass of region graphs.
13 #ifndef __defined_libdai_regiongraph_h
14 #define __defined_libdai_regiongraph_h
17 #include <iostream>
18 #include <dai/bipgraph.h>
19 #include <dai/factorgraph.h>
20 #include <dai/weightedgraph.h>
23 namespace dai {
26 /// A Region is a set of variables with a counting number
27 class Region : public VarSet {
28 private:
29 /// Counting number
30 Real _c;
32 public:
33 /// Default constructor
34 Region() : VarSet(), _c(1.0) {}
36 /// Construct from a set of variables and a counting number
37 Region( const VarSet& x, Real c ) : VarSet(x), _c(c) {}
39 /// Returns constant reference to counting number
40 const Real& c() const { return _c; }
42 /// Returns reference to counting number
43 Real& c() { return _c; }
44 };
47 /// An FRegion is a factor with a counting number
48 class FRegion : public Factor {
49 private:
50 /// Counting number
51 Real _c;
53 public:
54 /// Default constructor
55 FRegion() : Factor(), _c(1.0) {}
57 /// Constructs from a factor and a counting number
58 FRegion( const Factor& x, Real c ) : Factor(x), _c(c) {}
60 /// Returns constant reference to counting number
61 const Real& c() const { return _c; }
63 /// Returns reference to counting number
64 Real& c() { return _c; }
65 };
68 /// A RegionGraph combines a bipartite graph consisting of outer regions (type FRegion) and inner regions (type Region) with a FactorGraph
69 /** A RegionGraph inherits from a FactorGraph and adds additional structure in the form of a "region graph". Our definition of region graph
70 * is inspired by [\ref HAK03], which is less general than the definition given in [\ref YFW05].
71 *
72 * The extra structure described by a RegionGraph compared with that described by a FactorGraph is:
73 * - a set of outer regions (indexed by \f$\alpha\f$), where each outer region consists of
74 * - a factor defined on a subset of variables
75 * - a counting number
76 * - a set of inner regions (indexed by \f$\beta\f$), where each inner region consists of
77 * - a subset of variables
78 * - a counting number
79 * - edges between inner and outer regions
80 *
81 * Each factor in the factor graph belongs to an outer region; normally, the factor contents
82 * of an outer region would be the product of all the factors that belong to that region.
83 * \idea Generalize the definition of region graphs to the one given in [\ref YFW05], i.e., replace
84 * the current implementation which uses a BipartiteGraph with one that uses a DAG.
85 * \idea The outer regions are products of factors; right now, this product is constantly cached:
86 * changing one factor results in an update of all relevant outer regions. This may not be the most
87 * efficient approach; an alternative would be to only precompute the factor products at the start
88 * of an inference algorithm - e.g., in init(). This has the additional advantage that FactorGraph
90 */
91 class RegionGraph : public FactorGraph {
92 protected:
93 /// Stores the neighborhood structure
94 BipartiteGraph _G;
96 /// The outer regions (corresponding to nodes of type 1)
97 std::vector<FRegion> _ORs;
99 /// The inner regions (corresponding to nodes of type 2)
100 std::vector<Region> _IRs;
102 /// Stores for each factor index the index of the outer region it belongs to
103 std::vector<size_t> _fac2OR;
106 public:
107 /// \name Constructors and destructors
108 //@{
109 /// Default constructor
110 RegionGraph() : FactorGraph(), _G(), _ORs(), _IRs(), _fac2OR() {}
112 /// Constructs a region graph from a factor graph, a vector of outer regions, a vector of inner regions and a vector of edges
113 /** The counting numbers for the outer regions are set to 1.
114 */
115 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() {
116 construct( fg, ors, irs, edges );
118 // Check counting numbers
119 #ifdef DAI_DEBUG
120 checkCountingNumbers();
121 #endif
122 }
124 /// Constructs a region graph from a factor graph and a vector of outer clusters (CVM style)
125 /** The region graph is constructed as in the Cluster Variation Method.
126 *
127 * The outer regions have as variable subsets the clusters specified in \a cl.
128 * Each factor in the factor graph \a fg is assigned to one of the outer regions.
129 * Each outer region gets counting number 1.
130 *
131 * The inner regions are (repeated) intersections of outer regions.
132 * An inner and an outer region are connected if the variables in the inner region form a
133 * subset of the variables in the outer region. The counting numbers for the inner
134 * regions are calculated by calcCountingNumbers() and satisfy the Moebius formula.
135 */
136 RegionGraph( const FactorGraph& fg, const std::vector<VarSet>& cl ) : FactorGraph(), _G(), _ORs(), _IRs(), _fac2OR() {
137 constructCVM( fg, cl );
139 // Check counting numbers
140 #ifdef DAI_DEBUG
141 checkCountingNumbers();
142 #endif
143 }
145 /// Clone \c *this (virtual copy constructor)
146 virtual RegionGraph* clone() const { return new RegionGraph(*this); }
147 //@}
149 /// \name Accessors and mutators
150 //@{
151 /// Returns number of outer regions
152 size_t nrORs() const { return _ORs.size(); }
153 /// Returns number of inner regions
154 size_t nrIRs() const { return _IRs.size(); }
156 /// Returns constant reference to outer region \a alpha
157 const FRegion& OR( size_t alpha ) const {
158 DAI_DEBASSERT( alpha < nrORs() );
159 return _ORs[alpha];
160 }
161 /// Returns reference to outer region \a alpha
162 FRegion& OR( size_t alpha ) {
163 DAI_DEBASSERT( alpha < nrORs() );
164 return _ORs[alpha];
165 }
167 /// Returns constant reference to inner region \a beta
168 const Region& IR( size_t beta ) const {
169 DAI_DEBASSERT( beta < nrIRs() );
170 return _IRs[beta];
171 }
172 /// Returns reference to inner region \a beta
173 Region& IR( size_t beta ) {
174 DAI_DEBASSERT( beta < nrIRs() );
175 return _IRs[beta];
176 }
178 /// Returns the index of the outer region to which the \a I 'th factor corresponds
179 size_t fac2OR( size_t I ) const {
180 DAI_DEBASSERT( I < nrFactors() );
181 DAI_DEBASSERT( I < _fac2OR.size() );
182 return _fac2OR[I];
183 }
185 /// Returns constant reference to the neighbors of outer region \a alpha
186 const Neighbors& nbOR( size_t alpha ) const { return _G.nb1(alpha); }
188 /// Returns constant reference to the neighbors of inner region \a beta
189 const Neighbors& nbIR( size_t beta ) const { return _G.nb2(beta); }
191 /// Returns DAG structure of the region graph
192 /** \note Currently, the DAG is implemented as a BipartiteGraph; the nodes of
193 * type 1 are the outer regions, the nodes of type 2 the inner regions, and
194 * edges correspond with arrows from nodes of type 1 to type 2.
195 */
196 const BipartiteGraph& DAG() const { return _G; }
197 //@}
199 /// \name Queries
200 //@{
201 /// Check whether the counting numbers are valid
202 /** Counting numbers are said to be (variable) valid if for each variable \f$x\f$,
203 * \f[\sum_{\alpha \ni x} c_\alpha + \sum_{\beta \ni x} c_\beta = 1\f]
204 * or in words, if the sum of the counting numbers of the regions
205 * that contain the variable equals one.
206 */
207 bool checkCountingNumbers() const;
208 //@}
210 /// \name Operations
211 //@{
212 /// Set the content of the \a I 'th factor and make a backup of its old content if \a backup == \c true
213 virtual void setFactor( size_t I, const Factor& newFactor, bool backup = false ) {
214 FactorGraph::setFactor( I, newFactor, backup );
215 recomputeOR( I );
216 }
218 /// Set the contents of all factors as specified by \a facs and make a backup of the old contents if \a backup == \c true
219 virtual void setFactors( const std::map<size_t, Factor>& facs, bool backup = false ) {
220 FactorGraph::setFactors( facs, backup );
221 VarSet ns;
222 for( std::map<size_t, Factor>::const_iterator fac = facs.begin(); fac != facs.end(); fac++ )
223 ns |= fac->second.vars();
224 recomputeORs( ns );
225 }
226 //@}
228 /// \name Input/output
229 //@{
230 /// Reads a region graph from a file
231 /** \note Not implemented yet
232 */
233 virtual void ReadFromFile( const char* /*filename*/ ) {
234 DAI_THROW(NOT_IMPLEMENTED);
235 }
237 /// Writes a region graph to a file
238 /** \note Not implemented yet
239 */
240 virtual void WriteToFile( const char* /*filename*/, size_t /*precision*/=15 ) const {
241 DAI_THROW(NOT_IMPLEMENTED);
242 }
244 /// Writes a region graph to an output stream
245 friend std::ostream& operator<< ( std::ostream& os, const RegionGraph& rg );
247 /// Formats a region graph as a string
248 std::string toString() const {
249 std::stringstream ss;
250 ss << *this;
251 return ss.str();
252 }
254 /// Writes a region graph to a GraphViz .dot file
255 /** \note Not implemented yet
256 */
257 virtual void printDot( std::ostream& /*os*/ ) const {
258 DAI_THROW(NOT_IMPLEMENTED);
259 }
260 //@}
262 protected:
263 /// Helper function for constructors
264 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 );
266 /// Helper function for constructors (CVM style)
267 void constructCVM( const FactorGraph& fg, const std::vector<VarSet>& cl, size_t verbose=0 );
269 /// Recompute all outer regions
270 /** The factor contents of each outer region is set to the product of the factors belonging to that region.
271 */
272 void recomputeORs();
274 /// Recompute all outer regions involving the variables in \a vs
275 /** 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.
276 */
277 void recomputeORs( const VarSet& vs );
279 /// Recompute all outer regions involving factor \a I
280 /** 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.
281 */
282 void recomputeOR( size_t I );
284 /// Calculates counting numbers of inner regions based upon counting numbers of outer regions
285 /** The counting numbers of the inner regions are set using the Moebius inversion formula:
286 * \f[ c_\beta := 1 - \sum_{\gamma \in \mathrm{an}(\beta)} c_\gamma \f]
287 * where \f$\mathrm{an}(\beta)\f$ are the ancestors of inner region \f$\beta\f$ according to
288 * the partial ordering induced by the subset relation (i.e., a region is a child of another
289 * region if its variables are a subset of the variables of its parent region).
290 */
291 void calcCVMCountingNumbers();
293 };
296 } // end of namespace dai
299 #endif