clustergraph.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_clustergraph_h
#define __defined_libdai_clustergraph_h


#include <set>
#include <vector>
#include <dai/varset.h>
#include <dai/bipgraph.h>
#include <dai/factorgraph.h>


namespace dai {



    class ClusterGraph {
        private:
            BipartiteGraph       _G;

            std::vector<Var>     _vars;

            std::vector<VarSet>  _clusters;

        public:

            ClusterGraph() : _G(), _vars(), _clusters() {}

            ClusterGraph( const std::vector<VarSet>& cls );


            ClusterGraph( const FactorGraph& fg, bool onlyMaximal );


            const BipartiteGraph& bipGraph() const { return _G; }

            size_t nrVars() const { return _vars.size(); }

            const std::vector<Var>& vars() const { return _vars; }

            const Var& var( size_t i ) const {
                DAI_DEBASSERT( i < nrVars() );
                return _vars[i]; 
            }

            size_t nrClusters() const { return _clusters.size(); }

            const std::vector<VarSet>& clusters() const { return _clusters; }

            const VarSet& cluster( size_t I ) const {
                DAI_DEBASSERT( I < nrClusters() );
                return _clusters[I]; 
            }

            size_t findVar( const Var& n ) const {
                return find( _vars.begin(), _vars.end(), n ) - _vars.begin();
            }

            size_t findCluster( const VarSet& cl ) const {
                return find( _clusters.begin(), _clusters.end(), cl ) - _clusters.begin();
            }

            VarSet Delta( size_t i ) const {
                VarSet result;
                bforeach( const Neighbor& I, _G.nb1(i) )
                    result |= _clusters[I];
                return result;
            }

            VarSet delta( size_t i ) const {
                return Delta( i ) / _vars[i];
            }

            bool adj( size_t i1, size_t i2 ) const {
                if( i1 == i2 )
                    return false;
                bool result = false;
                bforeach( const Neighbor& I, _G.nb1(i1) )
                    if( find( _G.nb2(I).begin(), _G.nb2(I).end(), i2 ) != _G.nb2(I).end() ) {
                        result = true;
                        break;
                    }
                return result;
            }

            bool isMaximal( size_t I ) const {
                DAI_DEBASSERT( I < _G.nrNodes2() );
                const VarSet & clI = _clusters[I];
                bool maximal = true;
                // The following may not be optimal, since it may repeatedly test the same cluster *J
                bforeach( const Neighbor& i, _G.nb2(I) ) {
                    bforeach( const Neighbor& J, _G.nb1(i) )
                        if( (J != I) && (clI << _clusters[J]) ) {
                            maximal = false;
                            break;
                        }
                    if( !maximal )
                        break;
                }
                return maximal;
            }



            size_t insert( const VarSet& cl ) {
                size_t index = findCluster( cl );  // OPTIMIZE ME
                if( index == _clusters.size() ) {
                    _clusters.push_back( cl );
                    // add variables (if necessary) and calculate neighborhood of new cluster
                    std::vector<size_t> nbs;
                    for( VarSet::const_iterator n = cl.begin(); n != cl.end(); n++ ) {
                        size_t iter = findVar( *n );  // OPTIMIZE ME
                        nbs.push_back( iter );
                        if( iter == _vars.size() ) {
                            _G.addNode1();
                            _vars.push_back( *n );
                        }
                    }
                    _G.addNode2( nbs.begin(), nbs.end(), nbs.size() );
                }
                return index;
            }

            ClusterGraph& eraseNonMaximal() {
                for( size_t I = 0; I < _G.nrNodes2(); ) {
                    if( !isMaximal(I) ) {
                        _clusters.erase( _clusters.begin() + I );
                        _G.eraseNode2(I);
                    } else
                        I++;
                }
                return *this;
            }

            ClusterGraph& eraseSubsuming( size_t i ) {
                DAI_ASSERT( i < nrVars() );
                while( _G.nb1(i).size() ) {
                    _clusters.erase( _clusters.begin() + _G.nb1(i)[0] );
                    _G.eraseNode2( _G.nb1(i)[0] );
                }
                return *this;
            }


            VarSet elimVar( size_t i ) {
                DAI_ASSERT( i < nrVars() );
                VarSet Di = Delta( i );
                insert( Di / var(i) );
                eraseSubsuming( i );
                eraseNonMaximal();
                return Di;
            }


            friend std::ostream& operator << ( std::ostream& os, const ClusterGraph& cl ) {
                os << cl.clusters();
                return os;
            }

            std::string toString() const {
                std::stringstream ss;
                ss << *this;
                return ss.str();
            }



            template<class EliminationChoice>
            ClusterGraph VarElim( EliminationChoice f, size_t maxStates=0 ) const {
                // Make a copy
                ClusterGraph cl(*this);
                cl.eraseNonMaximal();

                ClusterGraph result;

                // Construct set of variable indices
                std::set<size_t> varindices;
                for( size_t i = 0; i < _vars.size(); ++i )
                    varindices.insert( i );

                // Do variable elimination
                BigInt totalStates = 0;
                while( !varindices.empty() ) {
                    size_t i = f( cl, varindices );
                    VarSet Di = cl.elimVar( i );
                    result.insert( Di );
                    if( maxStates ) {
                        totalStates += Di.nrStates();
                        if( totalStates > (BigInt)maxStates )
                            DAI_THROW(OUT_OF_MEMORY);
                    }
                    varindices.erase( i );
                }

                return result;
            }
    };



    class sequentialVariableElimination {
        private:
            std::vector<Var> seq;
            size_t i;

        public:
            sequentialVariableElimination( const std::vector<Var> s ) : seq(s), i(0) {}

           size_t operator()( const ClusterGraph &cl, const std::set<size_t> &/*remainingVars*/ );
    };



    class greedyVariableElimination {
        public:
            typedef size_t (*eliminationCostFunction)(const ClusterGraph &, size_t);

        private:
            eliminationCostFunction heuristic;

        public:

            greedyVariableElimination( eliminationCostFunction h ) : heuristic(h) {}


            size_t operator()( const ClusterGraph &cl, const std::set<size_t>& remainingVars );
    };



    size_t eliminationCost_MinNeighbors( const ClusterGraph& cl, size_t i );



    size_t eliminationCost_MinWeight( const ClusterGraph& cl, size_t i );



    size_t eliminationCost_MinFill( const ClusterGraph& cl, size_t i );



    size_t eliminationCost_WeightedMinFill( const ClusterGraph& cl, size_t i );


} // end of namespace dai


#endif