include/dai/bp_dual.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) 2009  Frederik Eaton [frederik at ofb dot net]
   8  */
   9
  10
  11 /// \file
  12 /// \brief Defines class BP_dual
  13 /// \todo This replicates a large part of the functionality of BP; would it not be shorter to adapt BP instead?
  14
  15
  16 #ifndef __defined_libdai_bp_dual_h
  17 #define __defined_libdai_bp_dual_h
  18
  19
  20 #include <dai/daialg.h>
  21 #include <dai/factorgraph.h>
  22 #include <dai/enum.h>
  23
  24
  25 namespace dai {
  26
  27
  28 /// Calculates both types of BP messages and their normalizers from an InfAlg.
  29 /** BP_dual calculates "dual" versions of BP messages (both messages from factors
  30  *  to variables and messages from variables to factors), and normalizers, given an InfAlg.
  31  *  These are computed from the variable and factor beliefs of the InfAlg.
  32  *  This class is used primarily by BBP.
  33  */
  34 class BP_dual {
  35
  36     protected:
  37         /// Convenience label for storing edge properties
  38         template<class T>
  39         struct _edges_t : public std::vector<std::vector<T> > {};
  40
  41         /// Groups together the data structures for storing the two types of messages and their normalizers
  42         struct messages {
  43             /// Unnormalized variable->factor messages
  44             _edges_t<Prob> n;
  45             /// Normalizers of variable->factor messages
  46             _edges_t<Real> Zn;
  47             /// Unnormalized Factor->variable messages
  48             _edges_t<Prob> m;
  49             /// Normalizers of factor->variable messages
  50             _edges_t<Real> Zm;
  51         };
  52         /// Stores all messages
  53         messages _msgs;
  54
  55         /// Groups together the data structures for storing the two types of beliefs and their normalizers
  56         struct beliefs {
  57             /// Unnormalized variable beliefs
  58             std::vector<Prob> b1;
  59             /// Normalizers of variable beliefs
  60             std::vector<Real> Zb1;
  61             /// Unnormalized factor beliefs
  62             std::vector<Prob> b2;
  63             /// Normalizers of factor beliefs
  64             std::vector<Real> Zb2;
  65         };
  66         /// Stores all beliefs
  67         beliefs _beliefs;
  68
  69         /// Pointer to the InfAlg object
  70         const InfAlg *_ia;
  71
  72         /// Does all necessary preprocessing
  73         void init();
  74         /// Allocates space for _msgs
  75         void regenerateMessages();
  76         /// Allocates space for _beliefs
  77         void regenerateBeliefs();
  78
  79         /// Calculate all messages from InfAlg beliefs
  80         void calcMessages();
  81         /// Update factor->variable message (i->I)
  82         void calcNewM(size_t i, size_t _I);
  83         /// Update variable->factor message (I->i)
  84         void calcNewN(size_t i, size_t _I);
  85
  86         /// Calculate all variable and factor beliefs from messages
  87         void calcBeliefs();
  88         /// Calculate variable belief
  89         void calcBeliefV(size_t i);
  90         /// Calculate factor belief
  91         void calcBeliefF(size_t I);
  92
  93     public:
  94         /// Construct BP_dual object from (converged) InfAlg object's beliefs and factors.
  95         /*  A pointer to the the InfAlg object is stored,
  96          *  so the object must not be destroyed before the BP_dual is destroyed.
  97          */
  98         BP_dual( const InfAlg *ia ) : _ia(ia) { init(); }
  99
 100         /// Returns the underlying FactorGraph
 101         const FactorGraph& fg() const { return _ia->fg(); }
 102
 103         /// Returns factor -> var message (I->i)
 104         DAI_ACCMUT(Prob & msgM( size_t i, size_t _I ), { return _msgs.m[i][_I]; });
 105         /// Returns var -> factor message (i->I)
 106         DAI_ACCMUT(Prob & msgN( size_t i, size_t _I ), { return _msgs.n[i][_I]; });
 107         /// Returns normalizer for msgM
 108         DAI_ACCMUT(Real & zM( size_t i, size_t _I ), { return _msgs.Zm[i][_I]; });
 109         /// Returns normalizer for msgN
 110         DAI_ACCMUT(Real & zN( size_t i, size_t _I ), { return _msgs.Zn[i][_I]; });
 111
 112         /// Returns variable belief
 113         Factor beliefV( size_t i ) const { return Factor( _ia->fg().var(i), _beliefs.b1[i] ); }
 114         /// Returns factor belief
 115         Factor beliefF( size_t I ) const { return Factor( _ia->fg().factor(I).vars(), _beliefs.b2[I] ); }
 116
 117         /// Returns normalizer for variable belief
 118         Real beliefVZ( size_t i ) const { return _beliefs.Zb1[i]; }
 119         /// Returns normalizer for factor belief
 120         Real beliefFZ( size_t I ) const { return _beliefs.Zb2[I]; }
 121 };
 122
 123
 124 } // end of namespace dai
 125
 126
 127 #endif