glc.h

Go to the documentation of this file.

/*  This file is part of libDAI - http://www.libdai.org/
 *
 *  Copyright (c) 2006-2012, 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_glc_h
#define __defined_libdai_glc_h


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


#include <algorithm>
#include <set>
#include <string>
#include <dai/util.h>
#include <dai/daialg.h>
#include <dai/enum.h>
#include <dai/cobwebgraph.h>
#include <dai/properties.h>
#include <dai/exceptions.h>


namespace dai {



class Cobweb {
    public:
        DAIAlgFG *cav;


        std::map<int, size_t> _g2l;

        Cobweb(){}

        Cobweb( const std::map<int, size_t>& g2l ): cav(0), _g2l(g2l) {}

        virtual ~Cobweb(){ delete cav; }

        void setInfAlg( DAIAlgFG* alg ) {
            cav = alg;
        }

        Factor factor( size_t I ) {
            return cav->factor( _g2l[I] );
        }

        void initialize() {
            cav->init();
        }

        Factor marginal( const VarSet& ns, const std::vector<size_t>& rmgind ) {
            // Set the factors in rmgind to one
            VarSet vs;
            std::vector<size_t> rmlinds; // local index
            rmlinds.reserve( rmgind.size() );
            for( std::vector<size_t>::const_iterator it = rmgind.begin(); it != rmgind.end(); it++ ) {
                vs |= cav->factor( _g2l[*it] ).vars();
                rmlinds.push_back( _g2l[*it] );
            }
            cav->makeRegionCavity( rmlinds, true );
            // Initialize if necessary
            cav->init( vs );
            cav->run();
            Factor result;
            result = cav->belief( ns );
            cav->restoreFactors();
            return result;
        }


        Factor marginal( const int& outmsgind, const std::vector<size_t>& rmgind ) {
            // set the factors in rmgind to one
            VarSet vs;
            std::vector<size_t> rmlinds; // local index
            rmlinds.reserve( rmgind.size() );
            for( std::vector<size_t>::const_iterator it = rmgind.begin(); it != rmgind.end(); it++ ) {
                vs |= cav->factor( _g2l[*it] ).vars();
                rmlinds.push_back( _g2l[*it] );
            }
            cav->makeRegionCavity( rmlinds, true );
            // Initialize if necessary
            cav->init( vs );
            cav->run();
            Factor result;
            result = cav->beliefF( _g2l[outmsgind] );
            cav->restoreFactors();
            return result;
        }

        void updateFactor( int gind, const Factor& msg, bool multiply=false ) {
            if( !multiply )
                cav->setFactor( _g2l[gind], msg, false );
            else
                cav->setFactor( _g2l[gind], (msg*(cav->factor( _g2l[gind] ))).normalized(), false );
        }

        Factor belief( const Var v ) {
            cav->run();
            return cav->belief( v );
        }

        Factor belief( const VarSet& vs ) {
            cav->run();
            return cav->belief( vs );
        }
};



class GLC : public DAIAlgCG {
    private:
        std::vector<Cobweb> _CWs;

        std::vector<int> _outOffset; 


        std::vector<std::vector<Factor> > _cavitydists;

        std::vector<Factor> _beliefs;

        std::map<VarSet, Factor> _factorBeliefs;

        Real _maxdiff;

        size_t _iters;

    public:
        struct Properties {

            DAI_ENUM(CavityType,FULL,PAIR,PAIR2,UNIFORM);


            DAI_ENUM(RegionType,SINGLE,FACTOR,OVFACTOR,LOOP,OVLOOP,DELTA,OVDELTA)

            

            DAI_ENUM(UpdateType,SEQFIX,SEQRND);

            size_t verbose;

            // Maximum length of the loops to use in construction of loopy regions
            size_t loopdepth;

            size_t maxiter;

            Real maxtime;

            Real tol;

            bool reinit;


            bool auxfactors;

            CavityType cavity;

            // Type of region
            RegionType rgntype;

            UpdateType updates;

            CobwebGraph::NeighborType neighbors;

            std::string cavainame;

            PropertySet cavaiopts;

            // Name of the algorithm used for marginalization over a region (EXACT is fine)
            std::string inainame;

            // Parameters for algorithm used for marginalization over a region
            PropertySet inaiopts;
        } props;


    public:
        GLC() : DAIAlgCG(), _CWs(),_outOffset(), _cavitydists(), _beliefs(), _factorBeliefs(), _maxdiff(), _iters(), props() {}


        GLC( const FactorGraph &fg, const PropertySet &opts );


        virtual GLC* clone() const { return new GLC(*this); }
        virtual GLC* construct( const FactorGraph &fg, const PropertySet &opts ) const { return new GLC( fg, opts ); }
        virtual std::string name() const { return "GLC"; }
        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 { return _beliefs[i]; }
        virtual std::vector<Factor> beliefs() const;
        virtual Real logZ() const { DAI_THROW(NOT_IMPLEMENTED); return 0.0; }
        virtual void init(){ initCWs(); }
        virtual void init( const VarSet &/*ns*/ ) { init(); }
        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 Cobweb& CW( size_t alpha ) const {
            DAI_DEBASSERT( alpha < nrCWs() );
            return _CWs[alpha];
        }

        Cobweb& CW( size_t alpha ) {
            DAI_DEBASSERT( alpha < nrCWs() );
            return _CWs[alpha];
        }

        Real CalcCavityDist( size_t i, const std::string &name, const PropertySet &opts );

        Real InitCavityDists( const std::string &name, const PropertySet &opts );

        void NewPancake( size_t R, size_t _R2 );


        void OVNewPancake( size_t R );

        void CalcBelief( size_t i, bool isFinal = false );

        void CalcFactorBelief( size_t I );

        std::vector<SmallSet<size_t> > calcRegions();

        void initCWs();


        void setCWs( const std::string &name, const PropertySet &opts );


        void findLoopClusters( SmallSet<size_t>& remaining, std::set<SmallSet<size_t> > &allcl, SmallSet<size_t> newcl, const size_t& root, size_t length, SmallSet<size_t> vars );


        void findOVLoopClusters( SmallSet<size_t>& remaining, std::set<SmallSet<size_t> > &allcl, SmallSet<size_t> newcl, const size_t& root, size_t length, SmallSet<size_t> vars );
};


} // end of namespace dai


#endif


#endif