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