include/dai/regiongraph.h

   1 /*  This file is part of libDAI - http://www.libdai.org/
   2  *
   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.
   6  *
   7  *  Copyright (C) 2006-2009  Joris Mooij  [joris dot mooij at libdai dot org]
   8  *  Copyright (C) 2006-2007  Radboud University Nijmegen, The Netherlands
   9  */
  10
  11
  12 /// \file
  13 /// \brief Defines classes Region, FRegion and RegionGraph, which implement a particular subclass of region graphs.
  14
  15
  16 #ifndef __defined_libdai_regiongraph_h
  17 #define __defined_libdai_regiongraph_h
  18
  19
  20 #include <iostream>
  21 #include <dai/bipgraph.h>
  22 #include <dai/factorgraph.h>
  23 #include <dai/weightedgraph.h>
  24
  25
  26 namespace dai {
  27
  28
  29 /// A Region is a set of variables with a counting number
  30 class Region : public VarSet {
  31     private:
  32         /// Counting number
  33         Real          _c;
  34
  35     public:
  36         /// Default constructor
  37         Region() : VarSet(), _c(1.0) {}
  38
  39         /// Construct from a set of variables and a counting number
  40         Region( const VarSet &x, Real c ) : VarSet(x), _c(c) {}
  41
  42         /// Returns constant reference to counting number
  43         const Real & c() const { return _c; }
  44
  45         /// Returns reference to counting number
  46         Real & c() { return _c; }
  47 };
  48
  49
  50 /// An FRegion is a factor with a counting number
  51 class FRegion : public Factor {
  52     private:
  53         /// Counting number
  54         Real _c;
  55
  56     public:
  57         /// Default constructor
  58         FRegion() : Factor(), _c(1.0) {}
  59
  60         /// Constructs from a factor and a counting number
  61         FRegion( const Factor & x, Real c ) : Factor(x), _c(c) {}
  62
  63         /// Returns constant reference to counting number
  64         const Real & c() const { return _c; }
  65
  66         /// Returns reference to counting number
  67         Real & c() { return _c; }
  68 };
  69
  70
  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].
  74  *
  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
  78  *    - a counting number
  79  *  - a set of inner regions (indexed by \f$\beta\f$), where each inner region consists of
  80  *    - a subset of variables
  81  *    - a counting number
  82  *  - edges between inner and outer regions
  83  *
  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.
  86  */
  87 class RegionGraph : public FactorGraph {
  88     public:
  89         /// Stores the neighborhood structure
  90         BipartiteGraph          G;
  91
  92         /// The outer regions (corresponding to nodes of type 1)
  93         std::vector<FRegion>    ORs;
  94
  95         /// The inner regions (corresponding to nodes of type 2)
  96         std::vector<Region>     IRs;
  97
  98         /// Stores for each factor index the index of the outer region it belongs to
  99         std::vector<size_t>     fac2OR;
 100
 101
 102     public:
 103     /// \name Constructors and destructors
 104     //@{
 105         /// Default constructor
 106         RegionGraph() : FactorGraph(), G(), ORs(), IRs(), fac2OR() {}
 107
 108         /// Partially constructs a region graph from a factor graph
 109         RegionGraph( const FactorGraph &fg ) : FactorGraph(fg), G(), ORs(), IRs(), fac2OR() {}
 110
 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.
 113          */
 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 );
 116
 117             // Check counting numbers
 118 #ifdef DAI_DEBUG
 119             checkCountingNumbers();
 120 #endif
 121         }
 122
 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.
 126          */
 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 );
 128
 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.
 131          *
 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.
 135          *
 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.
 140          */
 141         RegionGraph( const FactorGraph &fg, const std::vector<VarSet> &cl ) : FactorGraph(), G(), ORs(), IRs(), fac2OR() {
 142             constructCVM( fg, cl );
 143
 144             // Check counting numbers
 145 #ifdef DAI_DEBUG
 146             checkCountingNumbers();
 147 #endif
 148         }
 149
 150         /// Clone \c *this (virtual copy constructor)
 151         virtual RegionGraph* clone() const { return new RegionGraph(*this); }
 152     //@}
 153
 154     /// \name Queries
 155     //@{
 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(); }
 160
 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]; }
 165
 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]; }
 170
 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); }
 175
 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.
 181          */
 182         bool checkCountingNumbers() const;
 183     //@}
 184
 185     /// \name Operations
 186     //@{
 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 );
 190             RecomputeOR( I );
 191         }
 192
 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 );
 196             VarSet ns;
 197             for( std::map<size_t, Factor>::const_iterator fac = facs.begin(); fac != facs.end(); fac++ )
 198                 ns |= fac->second.vars();
 199             RecomputeORs( ns );
 200         }
 201
 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.
 204          */
 205         void RecomputeORs();
 206
 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.
 209          */
 210         void RecomputeORs( const VarSet &vs );
 211
 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.
 214          */
 215         void RecomputeOR( size_t I );
 216
 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).
 223          */
 224         void calcCountingNumbers();
 225     //@}
 226
 227     /// \name Input/output
 228     //@{
 229         /// Writes a RegionGraph to an output stream
 230         friend std::ostream & operator << ( std::ostream & os, const RegionGraph & rg );
 231     //@}
 232
 233     protected:
 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 );
 236
 237         /// Helper function for constructors (CVM style)
 238         void constructCVM( const FactorGraph &fg, const std::vector<VarSet> &cl );
 239 };
 240
 241
 242 } // end of namespace dai
 243
 244
 245 #endif