1 /* This file is part of libDAI - http://www.libdai.org/
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.
7 * Copyright (C) 2006-2009 Joris Mooij [joris dot mooij at libdai dot org]
8 * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
13 /// \brief Defines classes Region, FRegion and RegionGraph, which implement a particular subclass of region graphs.
16 #ifndef __defined_libdai_regiongraph_h
17 #define __defined_libdai_regiongraph_h
21 #include <dai/bipgraph.h>
22 #include <dai/factorgraph.h>
23 #include <dai/weightedgraph.h>
29 /// A Region is a set of variables with a counting number
30 class Region
: public VarSet
{
36 /// Default constructor
37 Region() : VarSet(), _c(1.0) {}
39 /// Construct from a set of variables and a counting number
40 Region( const VarSet
&x
, Real c
) : VarSet(x
), _c(c
) {}
42 /// Returns constant reference to counting number
43 const Real
& c() const { return _c
; }
45 /// Returns reference to counting number
46 Real
& c() { return _c
; }
50 /// An FRegion is a factor with a counting number
51 class FRegion
: public Factor
{
57 /// Default constructor
58 FRegion() : Factor(), _c(1.0) {}
60 /// Constructs from a factor and a counting number
61 FRegion( const Factor
& x
, Real c
) : Factor(x
), _c(c
) {}
63 /// Returns constant reference to counting number
64 const Real
& c() const { return _c
; }
66 /// Returns reference to counting number
67 Real
& c() { return _c
; }
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].
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
79 * - a set of inner regions (indexed by \f$\beta\f$), where each inner region consists of
80 * - a subset of variables
82 * - edges between inner and outer regions
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.
87 class RegionGraph
: public FactorGraph
{
89 /// Stores the neighborhood structure
92 /// The outer regions (corresponding to nodes of type 1)
93 std::vector
<FRegion
> ORs
;
95 /// The inner regions (corresponding to nodes of type 2)
96 std::vector
<Region
> IRs
;
98 /// Stores for each factor index the index of the outer region it belongs to
99 std::vector
<size_t> fac2OR
;
103 /// \name Constructors and destructors
105 /// Default constructor
106 RegionGraph() : FactorGraph(), G(), ORs(), IRs(), fac2OR() {}
108 /// Partially constructs a region graph from a factor graph
109 RegionGraph( const FactorGraph
&fg
) : FactorGraph(fg
), G(), ORs(), IRs(), fac2OR() {}
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.
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
);
117 // Check counting numbers
119 checkCountingNumbers();
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.
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
);
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.
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.
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.
141 RegionGraph( const FactorGraph
&fg
, const std::vector
<VarSet
> &cl
) : FactorGraph(), G(), ORs(), IRs(), fac2OR() {
142 constructCVM( fg
, cl
);
144 // Check counting numbers
146 checkCountingNumbers();
150 /// Clone \c *this (virtual copy constructor)
151 virtual RegionGraph
* clone() const { return new RegionGraph(*this); }
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(); }
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
]; }
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
]; }
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
); }
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.
182 bool checkCountingNumbers() const;
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
);
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
);
197 for( std::map
<size_t, Factor
>::const_iterator fac
= facs
.begin(); fac
!= facs
.end(); fac
++ )
198 ns
|= fac
->second
.vars();
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.
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.
210 void RecomputeORs( const VarSet
&vs
);
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.
215 void RecomputeOR( size_t I
);
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).
224 void calcCountingNumbers();
227 /// \name Input/output
229 /// Writes a RegionGraph to an output stream
230 friend std::ostream
& operator << ( std::ostream
& os
, const RegionGraph
& rg
);
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
);
237 /// Helper function for constructors (CVM style)
238 void constructCVM( const FactorGraph
&fg
, const std::vector
<VarSet
> &cl
);
242 } // end of namespace dai