XGitUrl: http://git.tuebingen.mpg.de/?p=libdai.git;a=blobdiff_plain;f=include%2Fdai%2Fregiongraph.h;h=2c580a5bdb2913a7d513b38a0653841e09f412e9;hp=9d0d9248dd7bc98b286451605d65aeea6654be87;hb=b04b00f5eb8997766bef6f9d1b5dd105ff832645;hpb=7f2ae0d584185669fd276f75bf41e46690e0ab51
diff git a/include/dai/regiongraph.h b/include/dai/regiongraph.h
index 9d0d924..2c580a5 100644
 a/include/dai/regiongraph.h
+++ b/include/dai/regiongraph.h
@@ 1,22 +1,16 @@
/* Copyright (C) 20062008 Joris Mooij [j dot mooij at science dot ru dot nl]
 Radboud University Nijmegen, The Netherlands

 This file is part of libDAI.
+/* This file is part of libDAI  http://www.libdai.org/
+ *
+ * libDAI is licensed under the terms of the GNU General Public License version
+ * 2, or (at your option) any later version. libDAI is distributed without any
+ * warranty. See the file COPYING for more details.
+ *
+ * Copyright (C) 20062009 Joris Mooij [joris dot mooij at libdai dot org]
+ * Copyright (C) 20062007 Radboud University Nijmegen, The Netherlands
+ */
 libDAI is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or
 (at your option) any later version.
 libDAI is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with libDAI; if not, write to the Free Software
 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 021101301 USA
*/
+/// \file
+/// \brief Defines classes Region, FRegion and RegionGraph, which implement a particular subclass of region graphs.
#ifndef __defined_libdai_regiongraph_h
@@ 34,173 +28,214 @@ namespace dai {
/// A Region is a set of variables with a counting number
class Region : public VarSet {
 protected:
+ private:
/// Counting number
 double _c;
+ Real _c;
public:
/// Default constructor
Region() : VarSet(), _c(1.0) {}
 /// Construct Region from a VarSet and a counting number
 Region(const VarSet & x, double c) : VarSet(x), _c(c) {}

 /// Copy constructor
 Region(const Region & x) : VarSet(x), _c(x._c) {}

 /// Assignment operator
 Region & operator=(const Region & x) {
 if( this != &x ) {
 VarSet::operator=(x);
 _c = x._c;
 }
 return *this;
 }
+ /// Construct from a set of variables and a counting number
+ Region( const VarSet &x, Real c ) : VarSet(x), _c(c) {}
+
+ /// Returns constant reference to counting number
+ const Real & c() const { return _c; }
 /// Provide read access to counting number
 const double & c() const { return _c; }
 /// Provide full access to counting number
 double & c() { return _c; }
+ /// Returns reference to counting number
+ Real & c() { return _c; }
};
/// A FRegion is a factor with a counting number
+/// An FRegion is a factor with a counting number
class FRegion : public Factor {
 protected:
+ private:
/// Counting number
 double _c;
+ Real _c;
public:
/// Default constructor
FRegion() : Factor(), _c(1.0) {}
 /// Constructs FRegion from a Factor and a counting number
 FRegion( const Factor & x, double c ) : Factor(x), _c(c) {}

 /// Copy constructor
 FRegion( const FRegion & x ) : Factor(x), _c(x._c) {}

 /// Assignment operator
 FRegion & operator=(const FRegion & x) {
 if( this != &x ) {
 Factor::operator=(x);
 _c = x._c;
 }
 return *this;
 }
+ /// Constructs from a factor and a counting number
+ FRegion( const Factor & x, Real c ) : Factor(x), _c(c) {}
+
+ /// Returns constant reference to counting number
+ const Real & c() const { return _c; }
 /// Provide read access to counting number
 const double & c() const { return _c; }
 /// Provide full access to counting number
 double & c() { return _c; }
+ /// Returns reference to counting number
+ Real & c() { return _c; }
};
/// A RegionGraph is a bipartite graph consisting of outer regions (type FRegion) and inner regions (type Region)
+/// A RegionGraph combines a bipartite graph consisting of outer regions (type FRegion) and inner regions (type Region) with a FactorGraph
+/** A RegionGraph inherits from a FactorGraph and adds additional structure in the form of a "region graph". Our definition of region graph
+ * is inspired by [\ref HAK03], which is less general than the definition given in [\ref YFW05].
+ *
+ * The extra structure described by a RegionGraph over that described by a FactorGraph is:
+ *  a set of outer regions (indexed by \f$\alpha\f$), where each outer region consists of
+ *  a factor defined on a subset of variables
+ *  a counting number
+ *  a set of inner regions (indexed by \f$\beta\f$), where each inner region consists of
+ *  a subset of variables
+ *  a counting number
+ *  edges between inner and outer regions
+ *
+ * Each factor in the factor graph belongs to an outer region; normally, the factor contents
+ * of an outer region would be the product of all the factors that belong to that region.
+ */
class RegionGraph : public FactorGraph {
public:
+ /// Stores the neighborhood structure
BipartiteGraph G;
+
+ /// The outer regions (corresponding to nodes of type 1)
std::vector ORs;
+
+ /// The inner regions (corresponding to nodes of type 2)
std::vector IRs;
 protected:
 /// Give back the OR index that corresponds to a factor index
+ /// Stores for each factor index the index of the outer region it belongs to
std::vector fac2OR;
public:
+ /// \name Constructors and destructors
+ //@{
/// Default constructor
RegionGraph() : FactorGraph(), G(), ORs(), IRs(), fac2OR() {}
 /// Constructs a RegionGraph from a FactorGraph
+ /// Partially constructs a region graph from a factor graph
RegionGraph( const FactorGraph &fg ) : FactorGraph(fg), G(), ORs(), IRs(), fac2OR() {}
 /// Constructs a RegionGraph from a FactorGraph, a vector of outer regions, a vector of inner regions and a vector of edges
 RegionGraph( const FactorGraph &fg, const std::vector &ors, const std::vector &irs, const std::vector > &edges );

 /// Constructs a RegionGraph from a FactorGraph and a vector of outer VarSets (CVM style)
 RegionGraph( const FactorGraph &fg, const std::vector &cl );

 /// Copy constructor
 RegionGraph( const RegionGraph &x ) : FactorGraph(x), G(x.G), ORs(x.ORs), IRs(x.IRs), fac2OR(x.fac2OR) {}

 /// Assignment operator
 RegionGraph & operator=( const RegionGraph &x ) {
 if( this != &x ) {
 FactorGraph::operator=( x );
 G = x.G;
 ORs = x.ORs;
 IRs = x.IRs;
 fac2OR = x.fac2OR;
 }
 return *this;
 }
+ /// Constructs a region graph from a factor graph, a vector of outer regions, a vector of inner regions and a vector of edges
+ /** The counting numbers for the outer regions are set to 1.
+ */
+ RegionGraph( const FactorGraph &fg, const std::vector &ors, const std::vector &irs, const std::vector > &edges ) : FactorGraph(), G(), ORs(), IRs(), fac2OR() {
+ construct( fg, ors, irs, edges );
 /// Clone *this (virtual copy constructor)
 virtual RegionGraph* clone() const { return new RegionGraph(*this); }
+ // Check counting numbers
+#ifdef DAI_DEBUG
+ checkCountingNumbers();
+#endif
+ }
 /// Create (virtual default constructor)
 virtual RegionGraph* create() const { return new RegionGraph(); }
+ /// Constructs a region graph from a factor graph, a vector of outer regions, a vector of inner regions and a vector of edges
+ /** \note The counting numbers for the outer regions need to be 1.
+ * \deprecated Please use dai::RegionGraph::RegionGraph( const FactorGraph &, const std::vector &, const std::vector &, const std::vector > & ) instead.
+ */
+ RegionGraph( const FactorGraph &fg, const std::vector &ors, const std::vector &irs, const std::vector > &edges );
 /// Set the content of the I'th factor and make a backup of its old content if backup == true
 virtual void setFactor( size_t I, const Factor &newFactor, bool backup = false ) {
 FactorGraph::setFactor( I, newFactor, backup );
 RecomputeOR( I );
+ /// Constructs a region graph from a factor graph and a vector of outer clusters (CVM style)
+ /** The region graph is constructed as in the Cluster Variation Method.
+ *
+ * The outer regions have as variable subsets the clusters specified in \a cl.
+ * Each factor in the factor graph \a fg is assigned to one of the outer regions.
+ * Each outer region gets counting number 1.
+ *
+ * The inner regions are (repeated) intersections of outer regions.
+ * An inner and an outer region are connected if the variables in the inner region form a
+ * subset of the variables in the outer region. The counting numbers for the inner
+ * regions are calculated by calcCountingNumbers() and satisfy the Moebius formula.
+ */
+ RegionGraph( const FactorGraph &fg, const std::vector &cl ) : FactorGraph(), G(), ORs(), IRs(), fac2OR() {
+ constructCVM( fg, cl );
+
+ // Check counting numbers
+#ifdef DAI_DEBUG
+ checkCountingNumbers();
+#endif
}
 /// Set the contents of all factors as specified by facs and make a backup of the old contents if backup == true
 virtual void setFactors( const std::map & facs, bool backup = false ) {
 FactorGraph::setFactors( facs, backup );
 VarSet ns;
 for( std::map::const_iterator fac = facs.begin(); fac != facs.end(); fac++ )
 ns = fac>second.vars();
 RecomputeORs( ns );
 }
+ /// Clone \c *this (virtual copy constructor)
+ virtual RegionGraph* clone() const { return new RegionGraph(*this); }
+ //@}
+ /// \name Queries
+ //@{
+ /// Returns number of outer regions
+ size_t nrORs() const { return ORs.size(); }
+ /// Returns number of inner regions
+ size_t nrIRs() const { return IRs.size(); }
 /// Provides read access to outer region
+ /// Returns constant reference to outer region \a alpha
const FRegion & OR(size_t alpha) const { return ORs[alpha]; }
 /// Provides access to outer region
+ /// Returns reference to outer region \a alpha
FRegion & OR(size_t alpha) { return ORs[alpha]; }
 /// Provides read access to inner region
+ /// Returns constant reference to inner region \a beta
const Region & IR(size_t beta) const { return IRs[beta]; }
 /// Provides access to inner region
+ /// Returns reference to inner region \a beta
Region & IR(size_t beta) { return IRs[beta]; }
 /// Returns number of outer regions
 size_t nrORs() const { return ORs.size(); }
 /// Returns number of inner regions
 size_t nrIRs() const { return IRs.size(); }


 /// Provides read access to neighbors of outer region
+ /// Returns constant reference to the neighbors of outer region \a alpha
const Neighbors & nbOR( size_t alpha ) const { return G.nb1(alpha); }
 /// Provides full access to neighbors of outer region
 Neighbors & nbOR( size_t alpha ) { return G.nb1(alpha); }

 /// Provides read access to neighbors of inner region
+ /// Returns constant reference to the neighbors of inner region \a beta
const Neighbors & nbIR( size_t beta ) const { return G.nb2(beta); }
 /// Provides full access to neighbors of inner region
 Neighbors & nbIR( size_t beta ) { return G.nb2(beta); }

 /// Calculates counting numbers of inner regions based upon counting numbers of outer regions
 void Calc_Counting_Numbers();
/// Check whether the counting numbers are valid
 bool Check_Counting_Numbers();
+ /** Counting numbers are said to be (variable) valid if for each variable \f$x\f$,
+ * \f[\sum_{\alpha \ni x} c_\alpha + \sum_{\beta \ni x} c_\beta = 1\f]
+ * or in words, if the sum of the counting numbers of the regions
+ * that contain the variable equals one.
+ */
+ bool checkCountingNumbers() const;
+ //@}
+
+ /// \name Operations
+ //@{
+ /// Set the content of the \a I 'th factor and make a backup of its old content if \a backup == \c true
+ virtual void setFactor( size_t I, const Factor &newFactor, bool backup = false ) {
+ FactorGraph::setFactor( I, newFactor, backup );
+ RecomputeOR( I );
+ }
+
+ /// Set the contents of all factors as specified by \a facs and make a backup of the old contents if \a backup == \c true
+ virtual void setFactors( const std::map & facs, bool backup = false ) {
+ FactorGraph::setFactors( facs, backup );
+ VarSet ns;
+ for( std::map::const_iterator fac = facs.begin(); fac != facs.end(); fac++ )
+ ns = fac>second.vars();
+ RecomputeORs( ns );
+ }
/// Recompute all outer regions
+ /** The factor contents of each outer region is set to the product of the factors belonging to that region.
+ */
void RecomputeORs();
 /// Recompute all outer regions involving the variables in ns
 void RecomputeORs( const VarSet & ns );
+ /// Recompute all outer regions involving the variables in \a vs
+ /** 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.
+ */
+ void RecomputeORs( const VarSet &vs );
 /// Recompute all outer regions involving factor I
+ /// Recompute all outer regions involving factor \a I
+ /** 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.
+ */
void RecomputeOR( size_t I );
 /// Send RegionGraph to output stream
+ /// Calculates counting numbers of inner regions based upon counting numbers of outer regions
+ /** The counting numbers of the inner regions are set using the Moebius inversion formula:
+ * \f[ c_\beta := 1  \sum_{\gamma \in \mathrm{an}(\beta)} c_\gamma \f]
+ * where \f$\mathrm{an}(\beta)\f$ are the ancestors of inner region \f$\beta\f$ according to
+ * the partial ordering induced by the subset relation (i.e., a region is a child of another
+ * region if its variables are a subset of the variables of its parent region).
+ */
+ void calcCountingNumbers();
+ //@}
+
+ /// \name Input/output
+ //@{
+ /// Writes a RegionGraph to an output stream
friend std::ostream & operator << ( std::ostream & os, const RegionGraph & rg );
+ //@}
+
+ protected:
+ /// Helper function for constructors
+ void construct( const FactorGraph &fg, const std::vector &ors, const std::vector &irs, const std::vector > &edges );
+
+ /// Helper function for constructors (CVM style)
+ void constructCVM( const FactorGraph &fg, const std::vector &cl );
};