bp.h

Go to the documentation of this file.

/*  This file is part of libDAI - http://www.libdai.org/
 *
 *  Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
 *
 *  Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
 */




#ifndef __defined_libdai_bp_h
#define __defined_libdai_bp_h


#include <dai/dai_config.h>
#ifdef DAI_WITH_BP


#include <string>
#include <dai/daialg.h>
#include <dai/factorgraph.h>
#include <dai/properties.h>
#include <dai/enum.h>


namespace dai {



class BP : public DAIAlgFG {
    protected:
        typedef std::vector<size_t> ind_t;
        struct EdgeProp {
            ind_t  index;
            Prob   message;
            Prob   newMessage;
            Real   residual;
        };
        std::vector<std::vector<EdgeProp> > _edges;
        typedef std::multimap<Real, std::pair<size_t, size_t> > LutType;
        std::vector<std::vector<LutType::iterator> > _edge2lut;
        LutType _lut;
        Real _maxdiff;
        size_t _iters;
        std::vector<std::pair<size_t, size_t> > _sentMessages;
        std::vector<Factor> _oldBeliefsV;
        std::vector<Factor> _oldBeliefsF;
        std::vector<Edge> _updateSeq;

    public:
        struct Properties {

            DAI_ENUM(UpdateType,SEQFIX,SEQRND,SEQMAX,PARALL);


            DAI_ENUM(InfType,SUMPROD,MAXPROD);

            size_t verbose;

            size_t maxiter;

            double maxtime;

            Real tol;

            bool logdomain;

            Real damping;

            UpdateType updates;

            InfType inference;
        } props;

        bool recordSentMessages;

    public:

        BP() : DAIAlgFG(), _edges(), _edge2lut(), _lut(), _maxdiff(0.0), _iters(0U), _sentMessages(), _oldBeliefsV(), _oldBeliefsF(), _updateSeq(), props(), recordSentMessages(false) {}


        BP( const FactorGraph & fg, const PropertySet &opts ) : DAIAlgFG(fg), _edges(), _maxdiff(0.0), _iters(0U), _sentMessages(), _oldBeliefsV(), _oldBeliefsF(), _updateSeq(), props(), recordSentMessages(false) {
            setProperties( opts );
            construct();
        }

        BP( const BP &x ) : DAIAlgFG(x), _edges(x._edges), _edge2lut(x._edge2lut), _lut(x._lut), _maxdiff(x._maxdiff), _iters(x._iters), _sentMessages(x._sentMessages), _oldBeliefsV(x._oldBeliefsV), _oldBeliefsF(x._oldBeliefsF), _updateSeq(x._updateSeq), props(x.props), recordSentMessages(x.recordSentMessages) {
            for( LutType::iterator l = _lut.begin(); l != _lut.end(); ++l )
                _edge2lut[l->second.first][l->second.second] = l;
        }

        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;
                _sentMessages = x._sentMessages;
                _oldBeliefsV = x._oldBeliefsV;
                _oldBeliefsF = x._oldBeliefsF;
                _updateSeq = x._updateSeq;
                props = x.props;
                recordSentMessages = x.recordSentMessages;
            }
            return *this;
        }


        virtual BP* clone() const { return new BP(*this); }
        virtual BP* construct( const FactorGraph &fg, const PropertySet &opts ) const { return new BP( fg, opts ); }
        virtual std::string name() const { return "BP"; }
        virtual Factor belief( const Var &v ) const { return beliefV( findVar( v ) ); }
        virtual Factor belief( const VarSet &vs ) const;
        virtual Factor beliefV( size_t i ) const;
        virtual Factor beliefF( size_t I ) const;
        virtual std::vector<Factor> beliefs() const;
        virtual Real logZ() const;
        std::vector<size_t> findMaximum() const { return dai::findMaximum( *this ); }
        virtual void init();
        virtual void init( const VarSet &ns );
        virtual Real run();
        virtual Real maxDiff() const { return _maxdiff; }
        virtual size_t Iterations() const { return _iters; }
        virtual void setMaxIter( size_t maxiter ) { props.maxiter = maxiter; }
        virtual void setProperties( const PropertySet &opts );
        virtual PropertySet getProperties() const;
        virtual std::string printProperties() const;


        const std::vector<std::pair<size_t, size_t> >& getSentMessages() const {
            return _sentMessages;
        }

        void clearSentMessages() { _sentMessages.clear(); }

    protected:
        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; }
        const Prob & newMessage(size_t i, size_t _I) const { return _edges[i][_I].newMessage; }
        Prob & newMessage(size_t i, size_t _I) { return _edges[i][_I].newMessage; }
        const ind_t & index(size_t i, size_t _I) const { return _edges[i][_I].index; }
        ind_t & index(size_t i, size_t _I) { return _edges[i][_I].index; }
        const Real & residual(size_t i, size_t _I) const { return _edges[i][_I].residual; }
        Real & residual(size_t i, size_t _I) { return _edges[i][_I].residual; }


        virtual Prob calcIncomingMessageProduct( size_t I, bool without_i, size_t i ) const;
        virtual void calcNewMessage( size_t i, size_t _I );
        void updateMessage( size_t i, size_t _I );
        void updateResidual( size_t i, size_t _I, Real r );
        void findMaxResidual( size_t &i, size_t &_I );
        virtual void calcBeliefV( size_t i, Prob &p ) const;
        virtual void calcBeliefF( size_t I, Prob &p ) const {
            p = calcIncomingMessageProduct( I, false, 0 );
        }

        virtual void construct();
};


} // end of namespace dai


#endif


#endif