1 /* This file is part of libDAI - http://www.libdai.org/
3 * Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
5 * Use of this source code is governed by a BSD-style license that can be found in the LICENSE 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
18 #include <dai/bipgraph.h>
19 #include <dai/factorgraph.h>
20 #include <dai/weightedgraph.h>
26 /// A Region is a set of variables with a counting number
27 class Region
: public VarSet
{
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
; }
47 /// An FRegion is a factor with a counting number
48 class FRegion
: public Factor
{
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
; }
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].
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
76 * - a set of inner regions (indexed by \f$\beta\f$), where each inner region consists of
77 * - a subset of variables
79 * - edges between inner and outer regions
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
89 e can offer write access to its factors.
91 class RegionGraph
: public FactorGraph
{
93 /// Stores the neighborhood structure
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
;
107 /// \name Constructors and destructors
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.
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
120 checkCountingNumbers();
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.
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.
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.
136 RegionGraph( const FactorGraph
& fg
, const std::vector
<VarSet
>& cl
) : FactorGraph(), _G(), _ORs(), _IRs(), _fac2OR() {
137 constructCVM( fg
, cl
);
139 // Check counting numbers
141 checkCountingNumbers();
145 /// Clone \c *this (virtual copy constructor)
146 virtual RegionGraph
* clone() const { return new RegionGraph(*this); }
149 /// \name Accessors and mutators
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() );
161 /// Returns reference to outer region \a alpha
162 FRegion
& OR( size_t alpha
) {
163 DAI_DEBASSERT( alpha
< nrORs() );
167 /// Returns constant reference to inner region \a beta
168 const Region
& IR( size_t beta
) const {
169 DAI_DEBASSERT( beta
< nrIRs() );
172 /// Returns reference to inner region \a beta
173 Region
& IR( size_t beta
) {
174 DAI_DEBASSERT( beta
< nrIRs() );
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() );
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.
196 const BipartiteGraph
& DAG() const { return _G
; }
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.
207 bool checkCountingNumbers() const;
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
);
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
);
222 for( std::map
<size_t, Factor
>::const_iterator fac
= facs
.begin(); fac
!= facs
.end(); fac
++ )
223 ns
|= fac
->second
.vars();
228 /// \name Input/output
230 /// Reads a region graph from a file
231 /** \note Not implemented yet
233 virtual void ReadFromFile( const char* /*filename*/ ) {
234 DAI_THROW(NOT_IMPLEMENTED
);
237 /// Writes a region graph to a file
238 /** \note Not implemented yet
240 virtual void WriteToFile( const char* /*filename*/, size_t /*precision*/=15 ) const {
241 DAI_THROW(NOT_IMPLEMENTED
);
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
;
254 /// Writes a region graph to a GraphViz .dot file
255 /** \note Not implemented yet
257 virtual void printDot( std::ostream
& /*os*/ ) const {
258 DAI_THROW(NOT_IMPLEMENTED
);
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.
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.
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.
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).
291 void calcCVMCountingNumbers();
296 } // end of namespace dai