Removed all the virtual default constructors *::create(), as they are not used.
[libdai.git] / include / dai / bp.h
index 9bb1b51..1b1e577 100644 (file)
@@ -1,6 +1,7 @@
-/*  Copyright (C) 2006-2008  Joris Mooij  [j dot mooij at science dot ru dot nl]
-    Radboud University Nijmegen, The Netherlands
-    
+/*  Copyright (C) 2006-2008  Joris Mooij  [joris dot mooij at tuebingen dot mpg dot de]
+    Radboud University Nijmegen, The Netherlands /
+    Max Planck Institute for Biological Cybernetics, Germany
+
     This file is part of libDAI.
 
     libDAI is free software; you can redistribute it and/or modify
 */
 
 
+/// \file
+/// \brief Defines class BP
+/// \todo Improve documentation
+
+
 #ifndef __defined_libdai_bp_h
 #define __defined_libdai_bp_h
 
 #include <string>
 #include <dai/daialg.h>
 #include <dai/factorgraph.h>
+#include <dai/properties.h>
 #include <dai/enum.h>
 
 
 namespace dai {
 
 
+/// Approximate inference algorithm "(Loopy) Belief Propagation"
 class BP : public DAIAlgFG {
-    protected:
+    private:
         typedef std::vector<size_t> ind_t;
+           typedef std::multimap<double, std::pair<std::size_t, std::size_t> > LutType;
         struct EdgeProp {
             ind_t  index;
             Prob   message;
             Prob   newMessage;
             double residual;
         };
+        std::vector<std::vector<EdgeProp> > _edges;
+        std::vector<std::vector<LutType::iterator> > _edge2lut;
+        LutType _lut;
+        /// Maximum difference encountered so far
+        double _maxdiff;
+        /// Number of iterations needed
+        size_t _iters;
+    
+    public:
+        /// Parameters of this inference algorithm
+        struct Properties {
+            /// Enumeration of possible update schedules
+            DAI_ENUM(UpdateType,SEQFIX,SEQRND,SEQMAX,PARALL)
+
+            /// Enumeration of inference variants
+            DAI_ENUM(InfType,SUMPROD,MAXPROD)
+        
+            /// Verbosity
+            size_t verbose;
+
+            /// Maximum number of iterations
+            size_t maxiter;
+
+            /// Tolerance
+            double tol;
+
+            /// Do updates in logarithmic domain?
+            bool logdomain;
+
+            /// Damping constant
+            double damping;
 
-        std::vector<std::vector<EdgeProp> > edges;
-        bool logDomain;
+            /// Update schedule
+            UpdateType updates;
+
+            /// Type of inference: sum-product or max-product?
+            InfType inference;
+        } props;
+
+        /// Name of this inference algorithm
+        static const char *Name;
 
     public:
-        ENUM4(UpdateType,SEQFIX,SEQRND,SEQMAX,PARALL)
-        UpdateType Updates() const { return GetPropertyAs<UpdateType>("updates"); }
-
-        // default constructor
-        BP() : DAIAlgFG(), edges(), logDomain(false) {};
-        // copy constructor
-        BP(const BP & x) : DAIAlgFG(x), edges(x.edges), logDomain(x.logDomain) {};
-        BP* clone() const { return new BP(*this); }
-        // construct BP object from FactorGraph
-        BP(const FactorGraph & fg, const Properties &opts) : DAIAlgFG(fg, opts), edges(), logDomain(false) {
-            assert( checkProperties() );
-            create();
+        /// Default constructor
+        BP() : DAIAlgFG(), _edges(), _edge2lut(), _lut(), _maxdiff(0.0), _iters(0U), props() {}
+
+        /// Copy constructor
+        BP( const BP &x ) : DAIAlgFG(x), _edges(x._edges), _edge2lut(x._edge2lut), _lut(x._lut), _maxdiff(x._maxdiff), _iters(x._iters), props(x.props) {
+            for( LutType::iterator l = _lut.begin(); l != _lut.end(); ++l )
+                _edge2lut[l->second.first][l->second.second] = l;
         }
-        // assignment operator
-        BP & operator=(const BP & x) {
-            if(this!=&x) {
-                DAIAlgFG::operator=(x);
-                edges = x.edges;
-                logDomain = x.logDomain;
+
+        /// Assignment operator
+        BP& operator=( const BP &x ) {
+            if( this != &x ) {
+                DAIAlgFG::operator=( x );
+                _edges = x._edges;
+                _lut = x._lut;
+                for( LutType::iterator l = _lut.begin(); l != _lut.end(); ++l )
+                    _edge2lut[l->second.first][l->second.second] = l;
+                _maxdiff = x._maxdiff;
+                _iters = x._iters;
+                props = x.props;
             }
             return *this;
         }
 
-        static const char *Name;
+        /// Construct from FactorGraph fg and PropertySet opts
+        BP( const FactorGraph & fg, const PropertySet &opts ) : DAIAlgFG(fg), _edges(), _maxdiff(0.0), _iters(0U), props() {
+            setProperties( opts );
+            construct();
+        }
 
-        Prob & message(size_t i, size_t _I) { return edges[i][_I].message; }
-        const Prob & message(size_t i, size_t _I) const { return edges[i][_I].message; }
-        Prob & newMessage(size_t i, size_t _I) { return edges[i][_I].newMessage; }
-        const Prob & newMessage(size_t i, size_t _I) const { return edges[i][_I].newMessage; }
-        ind_t & index(size_t i, size_t _I) { return edges[i][_I].index; }
-        const ind_t & index(size_t i, size_t _I) const { return edges[i][_I].index; }
-        double & residual(size_t i, size_t _I) { return edges[i][_I].residual; }
-        const double & residual(size_t i, size_t _I) const { return edges[i][_I].residual; }
-        void findMaxResidual( size_t &i, size_t &_I );
 
-        std::string identify() const;
-        void create();
-        void init();
+        /// @name General InfAlg interface
+        //@{
+        virtual BP* clone() const { return new BP(*this); }
+        virtual std::string identify() const;
+        virtual Factor belief( const Var &n ) const;
+        virtual Factor belief( const VarSet &ns ) 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; }
+        //@}
+
+
+        /// @name Additional interface specific for BP
+        //@{
+        Factor beliefV( size_t i ) const;
+        Factor beliefF( size_t I ) const;
+        //@}
+
+        /// Calculates the joint state of all variables that has maximum probability
+        /** Assumes that run() has been called and that props.inference == MAXPROD
+         */
+        std::vector<std::size_t> findMaximum() const;
+
+    private:
+        const Prob & message(size_t i, size_t _I) const { return _edges[i][_I].message; }
+        Prob & message(size_t i, size_t _I) { return _edges[i][_I].message; }
+        Prob & newMessage(size_t i, size_t _I) { return _edges[i][_I].newMessage; }
+        const Prob & newMessage(size_t i, size_t _I) const { return _edges[i][_I].newMessage; }
+        ind_t & index(size_t i, size_t _I) { return _edges[i][_I].index; }
+        const ind_t & index(size_t i, size_t _I) const { return _edges[i][_I].index; }
+        double & residual(size_t i, size_t _I) { return _edges[i][_I].residual; }
+        const double & residual(size_t i, size_t _I) const { return _edges[i][_I].residual; }
+
         void calcNewMessage( size_t i, size_t _I );
-        double run();
-        Factor beliefV (size_t i) const;
-        Factor beliefF (size_t I) const;
-        Factor belief (const Var &n) const;
-        Factor belief (const VarSet &n) const;
-        std::vector<Factor> beliefs() const;
-        Complex logZ() const;
-
-        void init( const VarSet &ns );
-        void undoProbs( const VarSet &ns ) { FactorGraph::undoProbs(ns); init(ns); }
-        bool checkProperties();
+        void updateMessage( size_t i, size_t _I );
+        void updateResidual( size_t i, size_t _I, double r );
+        void findMaxResidual( size_t &i, size_t &_I );
+        /// Calculates unnormalized belief of variable
+        void calcBeliefV( size_t i, Prob &p ) const;
+        /// Calculates unnormalized belief of factor
+        void calcBeliefF( size_t I, Prob &p ) const;
+
+        void construct();
+        /// 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;
 };