Cleaned up variable elimination code in ClusterGraph
[libdai.git] / include / dai / regiongraph.h
index b7ab9e7..2c580a5 100644 (file)
@@ -1,22 +1,16 @@
-/*  Copyright (C) 2006-2008  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) 2006-2009  Joris Mooij  [joris dot mooij at libdai dot org]
+ *  Copyright (C) 2006-2007  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  02110-1301  USA
-*/
+/// \file
+/// \brief Defines classes Region, FRegion and RegionGraph, which implement a particular subclass of region graphs.
 
 
 #ifndef __defined_libdai_regiongraph_h
@@ -34,194 +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) {}
 
-        /// Provide read access to counting number
-        const double & c() const { return _c; }
-        /// Provide full access to counting number
-        double & c() { return _c; }
+        /// Returns constant reference to counting number
+        const Real & c() const { 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; }
 };
 
 
-typedef BipartiteGraph<FRegion,Region> BipRegGraph;
+/// 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<FRegion>    ORs;
 
-/// A RegionGraph is a bipartite graph consisting of outer regions (type FRegion) and inner regions (type Region)
-class RegionGraph : public FactorGraph, BipRegGraph {
-    public:
-        typedef BipRegGraph::_nb_t      R_nb_t;
-        typedef R_nb_t::const_iterator  R_nb_cit;
-        typedef BipRegGraph::_edge_t    R_edge_t;
+        /// The inner regions (corresponding to nodes of type 2)
+        std::vector<Region>     IRs;
 
-        
-    protected:
-        /// Give back the OR index that corresponds to a factor index
-        typedef std::map<size_t,size_t>::const_iterator fac2OR_cit;
-        std::map<size_t,size_t>         _fac2OR;
+        /// Stores for each factor index the index of the outer region it belongs to
+        std::vector<size_t>     fac2OR;
 
 
     public:
+    /// \name Constructors and destructors
+    //@{
         /// Default constructor
-        RegionGraph() : FactorGraph(), BipRegGraph(), _fac2OR() {}
-
-        /// Constructs a RegionGraph from a FactorGraph
-        RegionGraph(const FactorGraph & fg) : FactorGraph(fg), BipRegGraph(), _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<Region> & ors, const std::vector<Region> & irs, const std::vector<R_edge_t> & edges);
-        
-        /// Constructs a RegionGraph from a FactorGraph and a vector of outer VarSets (CVM style)
-        RegionGraph(const FactorGraph & fg, const std::vector<VarSet> & cl);
-
-        /// Copy constructor
-        RegionGraph(const RegionGraph & x) : FactorGraph(x), BipRegGraph(x), _fac2OR(x._fac2OR) {}
-
-        /// Assignment operator
-        RegionGraph & operator=(const RegionGraph & x) {
-            if( this != &x ) {
-                FactorGraph::operator=(x);
-                BipRegGraph::operator=(x);
-                _fac2OR = x._fac2OR;
-            }
-            return *this;
+        RegionGraph() : FactorGraph(), G(), ORs(), IRs(), fac2OR() {}
+
+        /// Partially constructs a region graph from a factor graph
+        RegionGraph( const FactorGraph &fg ) : FactorGraph(fg), G(), ORs(), IRs(), fac2OR() {}
+
+        /// 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<VarSet> &ors, const std::vector<Region> &irs, const std::vector<std::pair<size_t,size_t> > &edges ) : FactorGraph(), G(), ORs(), IRs(), fac2OR() {
+            construct( fg, ors, irs, edges );
+
+            // Check counting numbers
+#ifdef DAI_DEBUG
+            checkCountingNumbers();
+#endif
+        }
+
+        /// 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<VarSet> &, const std::vector<Region> &, const std::vector<std::pair<size_t,size_t> > & ) instead.
+         */
+        RegionGraph( const FactorGraph &fg, const std::vector<Region> &ors, const std::vector<Region> &irs, const std::vector<std::pair<size_t,size_t> > &edges );
+
+        /// 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<VarSet> &cl ) : FactorGraph(), G(), ORs(), IRs(), fac2OR() {
+            constructCVM( fg, cl );
+
+            // Check counting numbers
+#ifdef DAI_DEBUG
+            checkCountingNumbers();
+#endif
         }
 
-        /// Provides read access to outer region
-        const FRegion & OR(long alpha) const { return BipRegGraph::V1(alpha); }
-        /// Provides access to outer region
-        FRegion & OR(long alpha) { return BipRegGraph::V1(alpha); }
-        /// Provides read access to all outer regions
-        const std::vector<FRegion> & ORs() const { return BipRegGraph::V1s(); }
-        /// Provides access to all outer regions
-        std::vector<FRegion> &ORs() { return BipRegGraph::V1s(); }
+        /// Clone \c *this (virtual copy constructor)
+        virtual RegionGraph* clone() const { return new RegionGraph(*this); }
+    //@}
+
+    /// \name Queries
+    //@{
         /// Returns number of outer regions
-        size_t nr_ORs() const { return BipRegGraph::V1s().size(); }
-
-        /// Provides read access to inner region
-        const Region & IR(long beta) const { return BipRegGraph::V2(beta); }
-        /// Provides access to inner region
-        Region & IR(long beta) { return BipRegGraph::V2(beta); }
-        /// Provides read access to all inner regions
-        const std::vector<Region> & IRs() const { return BipRegGraph::V2s(); }
-        /// Provides access to all inner regions
-        std::vector<Region> & IRs() { return BipRegGraph::V2s(); }
+        size_t nrORs() const { return ORs.size(); }
         /// Returns number of inner regions
-        size_t nr_IRs() const { return BipRegGraph::V2s().size(); }
-
-        /// Provides read access to edge
-        const R_edge_t & Redge(size_t ind) const { return BipRegGraph::edge(ind); }
-        /// Provides full access to edge
-        R_edge_t & Redge(size_t ind) { return BipRegGraph::edge(ind); }
-        /// Provides read access to all edges
-        const std::vector<R_edge_t> & Redges() const { return BipRegGraph::edges(); }
-        /// Provides full access to all edges
-        std::vector<R_edge_t> & Redges() { return BipRegGraph::edges(); }
-        /// Returns number of edges
-        size_t nr_Redges() const { return BipRegGraph::edges().size(); }
-
-        /// Provides read access to neighbours of outer region
-        const R_nb_t & nbOR( size_t i1 ) const { return BipRegGraph::nb1(i1); }
-        /// Provides full access to neighbours of outer region
-        R_nb_t & nbOR( size_t i1 ) { return BipRegGraph::nb1(i1); }
-
-        /// Provides read access to neighbours of inner region
-        const R_nb_t & nbIR( size_t i2 ) const { return BipRegGraph::nb2(i2); }
-        /// Provides full access to neighbours of inner region
-        R_nb_t & nbIR( size_t i2 ) { return BipRegGraph::nb2(i2); }
-
-        /// Converts the pair of outer/inner region indices (i1,i2) to the corresponding edge index
-        size_t ORIR2E( const size_t i1, const size_t i2 ) const { return BipRegGraph::VV2E(i1, i2); }
-
-        void Regenerate() { BipRegGraph::Regenerate(); }
-        
-        
-        /// 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();
+        size_t nrIRs() const { return IRs.size(); }
 
-        /// Recompute all outer regions
-        void RecomputeORs();
+        /// Returns constant reference to outer region \a alpha
+        const FRegion & OR(size_t alpha) const { return ORs[alpha]; }
+        /// Returns reference to outer region \a alpha
+        FRegion & OR(size_t alpha) { return ORs[alpha]; }
 
-        /// Recompute all outer regions involving the variables in ns
-        void RecomputeORs( const VarSet & ns );
+        /// Returns constant reference to inner region \a beta
+        const Region & IR(size_t beta) const { return IRs[beta]; }
+        /// Returns reference to inner region \a beta
+        Region & IR(size_t beta) { return IRs[beta]; }
 
-        /// Recompute all outer regions involving factor I
-        void RecomputeOR( size_t I );
-
-        /// We have to overload FactorGraph::clamp because the corresponding outer regions have to be recomputed
-        void clamp( const Var &n, size_t i ) { FactorGraph::clamp( n, i ); RecomputeORs( n ); }
+        /// Returns constant reference to the neighbors of outer region \a alpha
+        const Neighbors & nbOR( size_t alpha ) const { return G.nb1(alpha); }
+        /// Returns constant reference to the neighbors of inner region \a beta
+        const Neighbors & nbIR( size_t beta ) const { return G.nb2(beta); }
 
-        /// We have to overload FactorGraph::makeCavity because the corresponding outer regions have to be recomputed
-        void makeCavity( const Var &n ) { FactorGraph::makeCavity( n ); RecomputeORs( n ); }
+        /// Check whether the counting numbers are valid
+        /** 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 );
+        }
 
-        /// We have to overload FactorGraph::makeFactorCavity because the corresponding outer regions have to be recomputed
-        void makeFactorCavity( size_t I ) { FactorGraph::makeFactorCavity( I ); 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<size_t, Factor> & facs, bool backup = false ) {
+            FactorGraph::setFactors( facs, backup );
+            VarSet ns;
+            for( std::map<size_t, Factor>::const_iterator fac = facs.begin(); fac != facs.end(); fac++ )
+                ns |= fac->second.vars();
+            RecomputeORs( ns );
+        }
 
-        /// We have to overload FactorGraph::undoProbs because the corresponding outer regions have to be recomputed
-        void undoProbs( const VarSet &ns ) { FactorGraph::undoProbs( ns ); 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();
 
-        /// We have to overload FactorGraph::undoProb because the corresponding outer regions have to be recomputed
-        void undoProb( size_t I ) { FactorGraph::undoProb( I ); RecomputeOR( I ); }
+        /// 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 );
 
-        /// If updateFactor is called, we know that factor I has been changed and we should recompute the outer regions involving I
-        void updatedFactor( size_t I ) { RecomputeOR( 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<VarSet> &ors, const std::vector<Region> &irs, const std::vector<std::pair<size_t,size_t> > &edges );
+
+        /// Helper function for constructors (CVM style)
+        void constructCVM( const FactorGraph &fg, const std::vector<VarSet> &cl );
 };