Updated copyright headers
[libdai.git] / include / dai / bp_dual.h
index aca369a..c41659b 100644 (file)
-#ifndef ____defined_libdai_bp_dual_h__
-#define ____defined_libdai_bp_dual_h__
+/*  This file is part of libDAI - http://www.libdai.org/
+ *
+ *  libDAI is licensed under the terms of the GNU General Public License version
+ *  2, or (at your option) any later version. libDAI is distributed without any
+ *  warranty. See the file COPYING for more details.
+ *
+ *  Copyright (C) 2009  Frederik Eaton [frederik at ofb dot net]
+ */
 
-#include <dai/daialg.h>
-#include <dai/factorgraph.h>
-#include <dai/enum.h>
-#include <dai/bp.h>
-
-namespace dai {
-
-using namespace std;
-
-struct BP_dual_messages {
-  // messages:
-  // indexed by edge index (using VV2E)
-  vector<Prob> n;
-  vector<Real> Zn;
-  vector<Prob> m;
-  vector<Real> Zm;
-};
 
-struct BP_dual_beliefs {
-  // beliefs:
-  // indexed by node
-  vector<Prob> b1;
-  vector<Real> Zb1;
-  // indexed by factor
-  vector<Prob> b2;
-  vector<Real> Zb2;
-};
-
-void _clamp(FactorGraph &g, const Var & n, const vector<size_t> &is );
+/// \file
+/// \brief Defines class BP_dual
+/// \todo This replicates a large part of the functionality of BP; would it not be shorter to adapt BP instead?
 
-// clamp a factor to have one of a set of values
-void _clampFactor(FactorGraph &g, size_t I, const vector<size_t> &is);
 
-class BP_dual : public DAIAlgFG {
- public:
-        typedef vector<size_t>  _ind_t;
+#ifndef __defined_libdai_bp_dual_h
+#define __defined_libdai_bp_dual_h
 
- protected:
 
-        // indexed by edge index. for each edge i->I, contains a
-        // vector whose entries correspond to those of I, and the
-        // value of each entry is the corresponding entry of i
-        vector<_ind_t>          _indices; 
+#include <dai/daialg.h>
+#include <dai/factorgraph.h>
+#include <dai/enum.h>
 
-        BP_dual_messages _msgs;
-        BP_dual_messages _new_msgs;
- public:
-        BP_dual_beliefs _beliefs;
 
-        size_t _iters;
-        double _maxdiff;
+namespace dai {
 
-        struct Properties {
-          typedef BP::Properties::UpdateType UpdateType;
-          UpdateType updates;
-          double tol;
-          size_t maxiter;
-          size_t verbose;
-        } props;
 
-        /// List of property names
-        static const char *PropertyList[];
-        /// Name of this inference algorithm
-        static const char *Name;
+/// Calculates both types of BP messages and their normalizers from an InfAlg.
+/** BP_dual calculates "dual" versions of BP messages (both messages from factors
+ *  to variables and messages from variables to factors), and normalizers, given an InfAlg.
+ *  These are computed from the variable and factor beliefs of the InfAlg.
+ *  This class is used primarily by BBP.
+ */
+class BP_dual {
+
+    protected:
+        /// Convenience label for storing edge properties
+        template<class T>
+        struct _edges_t : public std::vector<std::vector<T> > {};
+
+        /// Groups together the data structures for storing the two types of messages and their normalizers
+        struct messages {
+            /// Unnormalized variable->factor messages
+            _edges_t<Prob> n;
+            /// Normalizers of variable->factor messages
+            _edges_t<Real> Zn;
+            /// Unnormalized Factor->variable messages
+            _edges_t<Prob> m;
+            /// Normalizers of factor->variable messages
+            _edges_t<Real> Zm;
+        };
+        /// Stores all messages
+        messages _msgs;
+
+        /// Groups together the data structures for storing the two types of beliefs and their normalizers
+        struct beliefs {
+            /// Unnormalized variable beliefs
+            std::vector<Prob> b1;
+            /// Normalizers of variable beliefs
+            std::vector<Real> Zb1;
+            /// Unnormalized factor beliefs
+            std::vector<Prob> b2;
+            /// Normalizers of factor beliefs
+            std::vector<Real> Zb2;
+        };
+        /// Stores all beliefs
+        beliefs _beliefs;
+
+        /// Pointer to the InfAlg object
+        const InfAlg *_ia;
+
+        /// Does all necessary preprocessing
+        void init();
+        /// Allocates space for _msgs
+        void regenerateMessages();
+        /// Allocates space for _beliefs
+        void regenerateBeliefs();
+
+        /// Calculate all messages from InfAlg beliefs
+        void calcMessages();
+        /// Update factor->variable message (i->I)
+        void calcNewM(size_t i, size_t _I);
+        /// Update variable->factor message (I->i)
+        void calcNewN(size_t i, size_t _I);
+
+        /// Calculate all variable and factor beliefs from messages
+        void calcBeliefs();
+        /// Calculate variable belief
+        void calcBeliefV(size_t i);
+        /// Calculate factor belief
+        void calcBeliefF(size_t I);
 
     public:
-        void Regenerate(); // used by constructor
-        void RegenerateIndices();
-        void RegenerateMessages();
-        void RegenerateBeliefs();
-
-        void CalcBelief1(size_t i);
-        void CalcBelief2(size_t I);
-        void CalcBeliefs(); // called after run()
-
-        void calcNewM(size_t iI);
-        void calcNewN(size_t iI);
-        void upMsgM(size_t iI);
-        void upMsgN(size_t iI);
-
-/*             DAI_ENUM(UpdateType,SEQFIX,SEQRND,SEQMAX,PARALL) */
-        typedef BP::Properties::UpdateType UpdateType;
-        UpdateType Updates() const { return props.updates; }
-        size_t Verbose() const { return props.verbose; }
-
-        /// construct BP_dual object from FactorGraph
-        BP_dual(const FactorGraph & fg, const PropertySet &opts) : DAIAlgFG(fg) {
-            setProperties(opts);
-            Regenerate();
-        }
-        
-        DAI_ACCMUT(Prob & msgM(size_t I, size_t i), { return _msgs.m[VV2E(i,I)]; });
-        DAI_ACCMUT(Prob & msgN(size_t i, size_t I), { return _msgs.n[VV2E(i,I)]; });
-        DAI_ACCMUT(Prob & msgM(size_t iI), { return _msgs.m[iI]; });
-        DAI_ACCMUT(Prob & msgN(size_t iI), { return _msgs.n[iI]; });
-        DAI_ACCMUT(Real & zM(size_t I, size_t i), { return _msgs.Zm[VV2E(i,I)]; });
-        DAI_ACCMUT(Real & zN(size_t i, size_t I), { return _msgs.Zn[VV2E(i,I)]; });
-        DAI_ACCMUT(Real & zM(size_t iI), { return _msgs.Zm[iI]; });
-        DAI_ACCMUT(Real & zN(size_t iI), { return _msgs.Zn[iI]; });
-        DAI_ACCMUT(Prob & newMsgM(size_t I, size_t i), { return _new_msgs.m[VV2E(i,I)]; });
-        DAI_ACCMUT(Prob & newMsgN(size_t i, size_t I), { return _new_msgs.n[VV2E(i,I)]; });
-        DAI_ACCMUT(Real & newZM(size_t I, size_t i), { return _new_msgs.Zm[VV2E(i,I)]; });
-        DAI_ACCMUT(Real & newZN(size_t i, size_t I), { return _new_msgs.Zn[VV2E(i,I)]; });
-
-        DAI_ACCMUT(_ind_t & index(size_t i, size_t I), { return( _indices[VV2E(i,I)] ); });
-
-        Real belief1Z(size_t i) const { return _beliefs.Zb1[i]; }
-        Real belief2Z(size_t I) const { return _beliefs.Zb2[I]; }
-
-        size_t doneIters() const { return _iters; }
-
-
-        /// @name General InfAlg interface
-        //@{
-        virtual BP_dual* clone() const { return new BP_dual(*this); }
-/*         virtual BP_dual* create() const { return new BP_dual(); } */
-        virtual BP_dual* create() const { return NULL; }
-        virtual std::string identify() const;
-        virtual Factor belief (const Var &n) const { return( belief1( findVar( n ) ) ); }
-        virtual Factor belief (const VarSet &n) const;
-        virtual std::vector<Factor> beliefs() const;
-        virtual Real logZ() const;
-        virtual void init();
-        virtual void init( const VarSet &ns );
-        virtual double run();
-        virtual double maxDiff() const { return _maxdiff; }
-        virtual size_t Iterations() const { return _iters; }
-        //@}
-
-        void init(const vector<size_t>& state);
-        Factor belief1 (size_t i) const { return Factor(var(i), _beliefs.b1[i]); }
-        Factor belief2 (size_t I) const { return Factor(factor(I).vars(), _beliefs.b2[I]); }
-
-        void updateMaxDiff( double maxdiff ) { if( maxdiff > _maxdiff ) _maxdiff = maxdiff; }
-
-        /// Set Props according to the PropertySet opts, where the values can be stored as std::strings or as the type of the corresponding Props member
-        void setProperties( const PropertySet &opts );
-        PropertySet getProperties() const;
-        std::string printProperties() const;
+        /// Construct BP_dual object from (converged) InfAlg object's beliefs and factors.
+        /*  A pointer to the the InfAlg object is stored,
+         *  so the object must not be destroyed before the BP_dual is destroyed.
+         */
+        BP_dual( const InfAlg *ia ) : _ia(ia) { init(); }
+
+        /// Returns the underlying FactorGraph
+        const FactorGraph& fg() const { return _ia->fg(); }
+
+        /// Returns factor -> var message (I->i)
+        DAI_ACCMUT(Prob & msgM( size_t i, size_t _I ), { return _msgs.m[i][_I]; });
+        /// Returns var -> factor message (i->I)
+        DAI_ACCMUT(Prob & msgN( size_t i, size_t _I ), { return _msgs.n[i][_I]; });
+        /// Returns normalizer for msgM
+        DAI_ACCMUT(Real & zM( size_t i, size_t _I ), { return _msgs.Zm[i][_I]; });
+        /// Returns normalizer for msgN
+        DAI_ACCMUT(Real & zN( size_t i, size_t _I ), { return _msgs.Zn[i][_I]; });
+
+        /// Returns variable belief
+        Factor beliefV( size_t i ) const { return Factor( _ia->fg().var(i), _beliefs.b1[i] ); }
+        /// Returns factor belief
+        Factor beliefF( size_t I ) const { return Factor( _ia->fg().factor(I).vars(), _beliefs.b2[I] ); }
+
+        /// Returns normalizer for variable belief
+        Real beliefVZ( size_t i ) const { return _beliefs.Zb1[i]; }
+        /// Returns normalizer for factor belief
+        Real beliefFZ( size_t I ) const { return _beliefs.Zb2[I]; }
 };
 
-}
+
+} // end of namespace dai
+
 
 #endif