include/dai/regiongraph.h

   1 /*  Copyright (C) 2006-2008  Joris Mooij  [joris dot mooij at tuebingen dot mpg dot de]
   2     Radboud University Nijmegen, The Netherlands /
   3     Max Planck Institute for Biological Cybernetics, Germany
   4
   5     This file is part of libDAI.
   6
   7     libDAI is free software; you can redistribute it and/or modify
   8     it under the terms of the GNU General Public License as published by
   9     the Free Software Foundation; either version 2 of the License, or
  10     (at your option) any later version.
  11
  12     libDAI is distributed in the hope that it will be useful,
  13     but WITHOUT ANY WARRANTY; without even the implied warranty of
  14     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15     GNU General Public License for more details.
  16
  17     You should have received a copy of the GNU General Public License
  18     along with libDAI; if not, write to the Free Software
  19     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20 */
  21
  22
  23 /// \file
  24 /// \brief Defines classes Region, FRegion and RegionGraph
  25 /// \todo Improve documentation
  26
  27
  28 #ifndef __defined_libdai_regiongraph_h
  29 #define __defined_libdai_regiongraph_h
  30
  31
  32 #include <iostream>
  33 #include <dai/bipgraph.h>
  34 #include <dai/factorgraph.h>
  35 #include <dai/weightedgraph.h>
  36
  37
  38 namespace dai {
  39
  40
  41 /// A Region is a set of variables with a counting number
  42 class Region : public VarSet {
  43     private:
  44         /// Counting number
  45         double          _c;
  46
  47     public:
  48         /// Default constructor
  49         Region() : VarSet(), _c(1.0) {}
  50
  51         /// Construct Region from a VarSet and a counting number
  52         Region(const VarSet & x, double c) : VarSet(x), _c(c) {}
  53
  54         /// Copy constructor
  55         Region(const Region & x) : VarSet(x), _c(x._c) {}
  56
  57         /// Assignment operator
  58         Region & operator=(const Region & x) {
  59             if( this != &x ) {
  60                 VarSet::operator=(x);
  61                 _c          = x._c;
  62             }
  63             return *this;
  64         }
  65
  66         /// Provide read access to counting number
  67         const double & c() const { return _c; }
  68         /// Provide full access to counting number
  69         double & c() { return _c; }
  70 };
  71
  72
  73 /// A FRegion is a factor with a counting number
  74 class FRegion : public Factor {
  75     private:
  76         /// Counting number
  77         double _c;
  78
  79     public:
  80         /// Default constructor
  81         FRegion() : Factor(), _c(1.0) {}
  82
  83         /// Constructs FRegion from a Factor and a counting number
  84         FRegion( const Factor & x, double c ) : Factor(x), _c(c) {}
  85
  86         /// Copy constructor
  87         FRegion( const FRegion & x ) : Factor(x), _c(x._c) {}
  88
  89         /// Assignment operator
  90         FRegion & operator=(const FRegion & x) {
  91             if( this != &x ) {
  92                 Factor::operator=(x);
  93                 _c = x._c;
  94             }
  95             return *this;
  96         }
  97
  98         /// Provide read access to counting number
  99         const double & c() const { return _c; }
 100         /// Provide full access to counting number
 101         double & c() { return _c; }
 102 };
 103
 104
 105 /// A RegionGraph is a bipartite graph consisting of outer regions (type FRegion) and inner regions (type Region)
 106 class RegionGraph : public FactorGraph {
 107     public:
 108         /// Stores the neighborhood structure
 109         BipartiteGraph          G;
 110
 111         /// The outer regions (corresponding to nodes of type 1)
 112         std::vector<FRegion>    ORs;
 113
 114         /// The inner regions (corresponding to nodes of type 2)
 115         std::vector<Region>     IRs;
 116
 117         /// Stores for each factor index the index of the outer region it belongs to
 118         std::vector<size_t>     fac2OR;
 119
 120
 121     public:
 122         /// Default constructor
 123         RegionGraph() : FactorGraph(), G(), ORs(), IRs(), fac2OR() {}
 124
 125         /// Constructs a RegionGraph from a FactorGraph
 126         RegionGraph( const FactorGraph &fg ) : FactorGraph(fg), G(), ORs(), IRs(), fac2OR() {}
 127
 128         /// Constructs a RegionGraph from a FactorGraph, a vector of outer regions, a vector of inner regions and a vector of edges
 129         RegionGraph( const FactorGraph &fg, const std::vector<Region> &ors, const std::vector<Region> &irs, const std::vector<std::pair<size_t,size_t> > &edges );
 130
 131         /// Constructs a RegionGraph from a FactorGraph and a vector of outer VarSets (CVM style)
 132         RegionGraph( const FactorGraph &fg, const std::vector<VarSet> &cl );
 133
 134         /// Copy constructor
 135         RegionGraph( const RegionGraph &x ) : FactorGraph(x), G(x.G), ORs(x.ORs), IRs(x.IRs), fac2OR(x.fac2OR) {}
 136
 137         /// Assignment operator
 138         RegionGraph & operator=( const RegionGraph &x ) {
 139             if( this != &x ) {
 140                 FactorGraph::operator=( x );
 141                 G = x.G;
 142                 ORs = x.ORs;
 143                 IRs = x.IRs;
 144                 fac2OR = x.fac2OR;
 145             }
 146             return *this;
 147         }
 148
 149         /// Clone *this (virtual copy constructor)
 150         virtual RegionGraph* clone() const { return new RegionGraph(*this); }
 151
 152         /// Create (virtual default constructor)
 153         virtual RegionGraph* create() const { return new RegionGraph(); }
 154
 155         /// Set the content of the I'th factor and make a backup of its old content if backup == true
 156         virtual void setFactor( size_t I, const Factor &newFactor, bool backup = false ) {
 157             FactorGraph::setFactor( I, newFactor, backup );
 158             RecomputeOR( I );
 159         }
 160
 161         /// Set the contents of all factors as specified by facs and make a backup of the old contents if backup == true
 162         virtual void setFactors( const std::map<size_t, Factor> & facs, bool backup = false ) {
 163             FactorGraph::setFactors( facs, backup );
 164             VarSet ns;
 165             for( std::map<size_t, Factor>::const_iterator fac = facs.begin(); fac != facs.end(); fac++ )
 166                 ns |= fac->second.vars();
 167             RecomputeORs( ns );
 168         }
 169
 170
 171         /// Provides read access to outer region
 172         const FRegion & OR(size_t alpha) const { return ORs[alpha]; }
 173         /// Provides access to outer region
 174         FRegion & OR(size_t alpha) { return ORs[alpha]; }
 175
 176         /// Provides read access to inner region
 177         const Region & IR(size_t beta) const { return IRs[beta]; }
 178         /// Provides access to inner region
 179         Region & IR(size_t beta) { return IRs[beta]; }
 180
 181         /// Returns number of outer regions
 182         size_t nrORs() const { return ORs.size(); }
 183         /// Returns number of inner regions
 184         size_t nrIRs() const { return IRs.size(); }
 185
 186
 187         /// Provides read access to neighbors of outer region
 188         const Neighbors & nbOR( size_t alpha ) const { return G.nb1(alpha); }
 189         /// Provides full access to neighbors of outer region
 190         Neighbors & nbOR( size_t alpha ) { return G.nb1(alpha); }
 191
 192         /// Provides read access to neighbors of inner region
 193         const Neighbors & nbIR( size_t beta ) const { return G.nb2(beta); }
 194         /// Provides full access to neighbors of inner region
 195         Neighbors & nbIR( size_t beta ) { return G.nb2(beta); }
 196
 197
 198         /// Calculates counting numbers of inner regions based upon counting numbers of outer regions
 199         void Calc_Counting_Numbers();
 200         /// Check whether the counting numbers are valid
 201         bool Check_Counting_Numbers();
 202
 203         /// Recompute all outer regions
 204         void RecomputeORs();
 205
 206         /// Recompute all outer regions involving the variables in ns
 207         void RecomputeORs( const VarSet & ns );
 208
 209         /// Recompute all outer regions involving factor I
 210         void RecomputeOR( size_t I );
 211
 212         // Friends
 213         friend std::ostream & operator << ( std::ostream & os, const RegionGraph & rg );
 214 };
 215
 216
 217 } // end of namespace dai
 218
 219
 220 #endif