include/dai/regiongraph.h

   1 /*  This file is part of libDAI - http://www.libdai.org/
   2  *
   3  *  Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
   4  *
   5  *  Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
   6  */
   7
   8
   9 /// \file
  10 /// \brief Defines classes Region, FRegion and RegionGraph, which implement a particular subclass of region graphs.
  11
  12
  13 #ifndef __defined_libdai_regiongraph_h
  14 #define __defined_libdai_regiongraph_h
  15
  16
  17 #include <iostream>
  18 #include <dai/bipgraph.h>
  19 #include <dai/factorgraph.h>
  20 #include <dai/weightedgraph.h>
  21
  22
  23 namespace dai {
  24
  25
  26 /// A Region is a set of variables with a counting number
  27 class Region : public VarSet {
  28     private:
  29         /// Counting number
  30         Real _c;
  31
  32     public:
  33         /// Default constructor
  34         Region() : VarSet(), _c(1.0) {}
  35
  36         /// Construct from a set of variables and a counting number
  37         Region( const VarSet& x, Real c ) : VarSet(x), _c(c) {}
  38
  39         /// Returns constant reference to counting number
  40         const Real& c() const { return _c; }
  41
  42         /// Returns reference to counting number
  43         Real& c() { return _c; }
  44 };
  45
  46
  47 /// An FRegion is a factor with a counting number
  48 class FRegion : public Factor {
  49     private:
  50         /// Counting number
  51         Real _c;
  52
  53     public:
  54         /// Default constructor
  55         FRegion() : Factor(), _c(1.0) {}
  56
  57         /// Constructs from a factor and a counting number
  58         FRegion( const Factor& x, Real c ) : Factor(x), _c(c) {}
  59
  60         /// Returns constant reference to counting number
  61         const Real& c() const { return _c; }
  62
  63         /// Returns reference to counting number
  64         Real& c() { return _c; }
  65 };
  66
  67
  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].
  71  *
  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
  75  *    - a counting number
  76  *  - a set of inner regions (indexed by \f$\beta\f$), where each inner region consists of
  77  *    - a subset of variables
  78  *    - a counting number
  79  *  - edges between inner and outer regions
  80  *
  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.
  90  */
  91 class RegionGraph : public FactorGraph {
  92     protected:
  93         /// Stores the neighborhood structure
  94         BipartiteGraph          _G;
  95
  96         /// The outer regions (corresponding to nodes of type 1)
  97         std::vector<FRegion>    _ORs;
  98
  99         /// The inner regions (corresponding to nodes of type 2)
 100         std::vector<Region>     _IRs;
 101
 102         /// Stores for each factor index the index of the outer region it belongs to
 103         std::vector<size_t>     _fac2OR;
 104
 105
 106     public:
 107     /// \name Constructors and destructors
 108     //@{
 109         /// Default constructor
 110         RegionGraph() : FactorGraph(), _G(), _ORs(), _IRs(), _fac2OR() {}
 111
 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.
 114          */
 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 );
 117
 118             // Check counting numbers
 119 #ifdef DAI_DEBUG
 120             checkCountingNumbers();
 121 #endif
 122         }
 123
 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.
 126          *
 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.
 130          *
 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.
 135          */
 136         RegionGraph( const FactorGraph& fg, const std::vector<VarSet>& cl ) : FactorGraph(), _G(), _ORs(), _IRs(), _fac2OR() {
 137             constructCVM( fg, cl );
 138
 139             // Check counting numbers
 140 #ifdef DAI_DEBUG
 141             checkCountingNumbers();
 142 #endif
 143         }
 144
 145         /// Clone \c *this (virtual copy constructor)
 146         virtual RegionGraph* clone() const { return new RegionGraph(*this); }
 147     //@}
 148
 149     /// \name Accessors and mutators
 150     //@{
 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(); }
 155
 156         /// Returns constant reference to outer region \a alpha
 157         const FRegion& OR( size_t alpha ) const {
 158             DAI_DEBASSERT( alpha < nrORs() );
 159             return _ORs[alpha];
 160         }
 161         /// Returns reference to outer region \a alpha
 162         FRegion& OR( size_t alpha ) {
 163             DAI_DEBASSERT( alpha < nrORs() );
 164             return _ORs[alpha];
 165         }
 166
 167         /// Returns constant reference to inner region \a beta
 168         const Region& IR( size_t beta ) const {
 169             DAI_DEBASSERT( beta < nrIRs() );
 170             return _IRs[beta];
 171         }
 172         /// Returns reference to inner region \a beta
 173         Region& IR( size_t beta ) {
 174             DAI_DEBASSERT( beta < nrIRs() );
 175             return _IRs[beta];
 176         }
 177
 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() );
 182             return _fac2OR[I];
 183         }
 184
 185         /// Returns constant reference to the neighbors of outer region \a alpha
 186         const Neighbors& nbOR( size_t alpha ) const { return _G.nb1(alpha); }
 187
 188         /// Returns constant reference to the neighbors of inner region \a beta
 189         const Neighbors& nbIR( size_t beta ) const { return _G.nb2(beta); }
 190
 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.
 195          */
 196         const BipartiteGraph& DAG() const { return _G; }
 197     //@}
 198
 199     /// \name Queries
 200     //@{
 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.
 206          */
 207         bool checkCountingNumbers() const;
 208     //@}
 209
 210     /// \name Operations
 211     //@{
 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 );
 215             recomputeOR( I );
 216         }
 217
 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 );
 221             VarSet ns;
 222             for( std::map<size_t, Factor>::const_iterator fac = facs.begin(); fac != facs.end(); fac++ )
 223                 ns |= fac->second.vars();
 224             recomputeORs( ns );
 225         }
 226     //@}
 227
 228     /// \name Input/output
 229     //@{
 230         /// Reads a region graph from a file
 231         /** \note Not implemented yet
 232          */
 233         virtual void ReadFromFile( const char* /*filename*/ ) {
 234             DAI_THROW(NOT_IMPLEMENTED);
 235         }
 236
 237         /// Writes a region graph to a file
 238         /** \note Not implemented yet
 239          */
 240         virtual void WriteToFile( const char* /*filename*/, size_t /*precision*/=15 ) const {
 241             DAI_THROW(NOT_IMPLEMENTED);
 242         }
 243
 244         /// Writes a region graph to an output stream
 245         friend std::ostream& operator<< ( std::ostream& os, const RegionGraph& rg );
 246
 247         /// Formats a region graph as a string
 248         std::string toString() const {
 249             std::stringstream ss;
 250             ss << *this;
 251             return ss.str();
 252         }
 253
 254         /// Writes a region graph to a GraphViz .dot file
 255         /** \note Not implemented yet
 256          */
 257         virtual void printDot( std::ostream& /*os*/ ) const {
 258             DAI_THROW(NOT_IMPLEMENTED);
 259         }
 260     //@}
 261
 262     protected:
 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 );
 265
 266         /// Helper function for constructors (CVM style)
 267         void constructCVM( const FactorGraph& fg, const std::vector<VarSet>& cl, size_t verbose=0 );
 268
 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.
 271          */
 272         void recomputeORs();
 273
 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.
 276          */
 277         void recomputeORs( const VarSet& vs );
 278
 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.
 281          */
 282         void recomputeOR( size_t I );
 283
 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).
 290          */
 291         void calcCVMCountingNumbers();
 292
 293 };
 294
 295
 296 } // end of namespace dai
 297
 298
 299 #endif