Updated copyright headers
[libdai.git] / include / dai / bp_dual.h
index fab7959..c41659b 100644 (file)
-/*  Copyright (C) 2009  Frederik Eaton [frederik at ofb dot net]
-
-    This file is part of libDAI.
-
-    libDAI is free software; you can redistribute it and/or modify
-    it under the terms of the GNU General Public License as published by
-    the Free Software Foundation; either version 2 of the License, or
-    (at your option) any later version.
-
-    libDAI is distributed in the hope that it will be useful,
-    but WITHOUT ANY WARRANTY; without even the implied warranty of
-    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-    GNU General Public License for more details.
-
-    You should have received a copy of the GNU General Public License
-    along with libDAI; if not, write to the Free Software
-    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
-*/
+/*  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]
+ */
 
 
 /// \file
 /// \brief Defines class BP_dual
-/// \todo Improve documentation
-/// \todo Clean up
+/// \todo This replicates a large part of the functionality of BP; would it not be shorter to adapt BP instead?
 
 
-#ifndef ____defined_libdai_bp_dual_h__
-#define ____defined_libdai_bp_dual_h__
+#ifndef __defined_libdai_bp_dual_h
+#define __defined_libdai_bp_dual_h
 
 
 #include <dai/daialg.h>
 #include <dai/factorgraph.h>
 #include <dai/enum.h>
-#include <dai/bp.h>
 
 
 namespace dai {
 
-    
-struct BP_dual_messages {
-    // messages:
-    // indexed by edge index (using VV2E)
-    std::vector<Prob> n;
-    std::vector<Real> Zn;
-    std::vector<Prob> m;
-    std::vector<Real> Zm;
-};
-
-
-struct BP_dual_beliefs {
-    // beliefs:
-    // indexed by node
-    std::vector<Prob> b1;
-    std::vector<Real> Zb1;
-    // indexed by factor
-    std::vector<Prob> b2;
-    std::vector<Real> Zb2;
-};
-
-
-void _clamp( FactorGraph &g, const Var &n, const std::vector<size_t> &is );
 
-
-/// Clamp a factor to have one of a set of values
-void _clampFactor( FactorGraph &g, size_t I, const std::vector<size_t> &is );
-
-
-class BP_dual : public DAIAlgFG {
-    public:
-        typedef std::vector<size_t>  _ind_t;
+/// 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:
-        // 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
-        std::vector<_ind_t>          _indices; 
-
-        BP_dual_messages _msgs;
-        BP_dual_messages _new_msgs;
-    public:
-        BP_dual_beliefs _beliefs;
-
-        size_t _iters;
-        double _maxdiff;
-
-        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;
+        /// 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; }
-
-        /// Default constructor
-        BP_dual() {}
-
-        /// 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 std::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]; }
 };