include/dai/factorgraph.h

   1 /*  Copyright (C) 2006-2008  Joris Mooij  [joris dot mooij at tuebingen dot mpg dot de]
   2     Radboud University Nijmegen, The Netherlands /
   3     Max Planck Institute for Biological Cybernetics, Germany
   4
   5     This file is part of libDAI.
   6
   7     libDAI is free software; you can redistribute it and/or modify
   8     it under the terms of the GNU General Public License as published by
   9     the Free Software Foundation; either version 2 of the License, or
  10     (at your option) any later version.
  11
  12     libDAI is distributed in the hope that it will be useful,
  13     but WITHOUT ANY WARRANTY; without even the implied warranty of
  14     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15     GNU General Public License for more details.
  16
  17     You should have received a copy of the GNU General Public License
  18     along with libDAI; if not, write to the Free Software
  19     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20 */
  21
  22
  23 #ifndef __defined_libdai_factorgraph_h
  24 #define __defined_libdai_factorgraph_h
  25
  26
  27 #include <iostream>
  28 #include <map>
  29 #include <dai/bipgraph.h>
  30 #include <dai/factor.h>
  31
  32
  33 namespace dai {
  34
  35
  36 class FactorGraph {
  37     public:
  38         BipartiteGraph         G;
  39         std::vector<Var>       vars;
  40         typedef BipartiteGraph::Neighbor  Neighbor;
  41         typedef BipartiteGraph::Neighbors Neighbors;
  42         typedef BipartiteGraph::Edge      Edge;
  43
  44     private:
  45         std::vector<Factor>      _factors;
  46         std::map<size_t,Factor>  _backup;
  47
  48     public:
  49         /// Default constructor
  50         FactorGraph() : G(), vars(), _factors(), _backup() {}
  51         /// Copy constructor
  52         FactorGraph(const FactorGraph & x) : G(x.G), vars(x.vars), _factors(x._factors), _backup(x._backup) {}
  53         /// Construct FactorGraph from vector of Factors
  54         FactorGraph(const std::vector<Factor> &P);
  55         // Construct a FactorGraph from given factor and variable iterators
  56         template<typename FactorInputIterator, typename VarInputIterator>
  57         FactorGraph(FactorInputIterator fact_begin, FactorInputIterator fact_end, VarInputIterator var_begin, VarInputIterator var_end, size_t nr_fact_hint = 0, size_t nr_var_hint = 0 );
  58
  59         /// Assignment operator
  60         FactorGraph & operator=(const FactorGraph & x) {
  61             if( this != &x ) {
  62                 G          = x.G;
  63                 vars       = x.vars;
  64                 _factors   = x._factors;
  65                 _backup    = x._backup;
  66             }
  67             return *this;
  68         }
  69         virtual ~FactorGraph() {}
  70
  71         /// Clone *this (virtual copy constructor)
  72         virtual FactorGraph* clone() const { return new FactorGraph(); }
  73
  74         /// Create (virtual default constructor)
  75         virtual FactorGraph* create() const { return new FactorGraph(*this); }
  76
  77         // aliases
  78         Var & var(size_t i) { return vars[i]; }
  79         /// Get const reference to i'th variable
  80         const Var & var(size_t i) const { return vars[i]; }
  81         /// Get const reference to I'th factor
  82         Factor & factor(size_t I) { return _factors[I]; }
  83         /// Get const reference to I'th factor
  84         const Factor & factor(size_t I) const { return _factors[I]; }
  85         /// Get const reference to all factors
  86         const std::vector<Factor> & factors() const { return _factors; }
  87
  88         /// Get number of variables
  89         size_t nrVars() const { return vars.size(); }
  90         /// Get number of factors
  91         size_t nrFactors() const { return _factors.size(); }
  92         size_t nrEdges() const { return G.nrEdges(); }
  93
  94         /// Provides read access to neighbors of variable
  95         const Neighbors & nbV( size_t i ) const { return G.nb1(i); }
  96         /// Provides full access to neighbors of variable
  97         Neighbors & nbV( size_t i ) { return G.nb1(i); }
  98         /// Provides read access to neighbors of factor
  99         const Neighbors & nbF( size_t I ) const { return G.nb2(I); }
 100         /// Provides full access to neighbors of factor
 101         Neighbors & nbF( size_t I ) { return G.nb2(I); }
 102         /// Provides read access to neighbor of variable
 103         const Neighbor & nbV( size_t i, size_t _I ) const { return G.nb1(i)[_I]; }
 104         /// Provides full access to neighbor of variable
 105         Neighbor & nbV( size_t i, size_t _I ) { return G.nb1(i)[_I]; }
 106         /// Provides read access to neighbor of factor
 107         const Neighbor & nbF( size_t I, size_t _i ) const { return G.nb2(I)[_i]; }
 108         /// Provides full access to neighbor of factor
 109         Neighbor & nbF( size_t I, size_t _i ) { return G.nb2(I)[_i]; }
 110
 111         /// Get index of variable n
 112         size_t findVar( const Var & n ) const {
 113             size_t i = find( vars.begin(), vars.end(), n ) - vars.begin();
 114             assert( i != nrVars() );
 115             return i;
 116         }
 117
 118         /// Get set of indexes for set of variables
 119         std::set<size_t> findVars( VarSet &ns ) const {
 120             std::set<size_t> indexes;
 121             for( VarSet::const_iterator n = ns.begin(); n != ns.end(); n++ )
 122                 indexes.insert( findVar( *n ) );
 123             return indexes;
 124         }
 125
 126         /// Get index of first factor involving ns
 127         size_t findFactor(const VarSet &ns) const {
 128             size_t I;
 129             for( I = 0; I < nrFactors(); I++ )
 130                 if( factor(I).vars() == ns )
 131                     break;
 132             assert( I != nrFactors() );
 133             return I;
 134         }
 135
 136         /// Return all variables that occur in a factor involving the i'th variable, itself included
 137         VarSet Delta( unsigned i ) const;
 138
 139         /// Return all variables that occur in a factor involving some variable in ns, ns itself included
 140         VarSet Delta( const VarSet &ns ) const;
 141
 142         /// Return all variables that occur in a factor involving the i'th variable, n itself excluded
 143         VarSet delta( unsigned i ) const;
 144
 145         /// Return all variables that occur in a factor involving some variable in ns, ns itself excluded
 146         VarSet delta( const VarSet & ns ) const {
 147             return Delta( ns ) / ns;
 148         }
 149
 150         /// Set the content of the I'th factor and make a backup of its old content if backup == true
 151         virtual void setFactor( size_t I, const Factor &newFactor, bool backup = false ) {
 152             assert( newFactor.vars() == factor(I).vars() );
 153             if( backup )
 154                 backupFactor( I );
 155             _factors[I] = newFactor;
 156         }
 157
 158         /// Set the contents of all factors as specified by facs and make a backup of the old contents if backup == true
 159         virtual void setFactors( const std::map<size_t, Factor> & facs, bool backup = false ) {
 160             for( std::map<size_t, Factor>::const_iterator fac = facs.begin(); fac != facs.end(); fac++ ) {
 161                 if( backup )
 162                     backupFactor( fac->first );
 163                 setFactor( fac->first, fac->second );
 164             }
 165         }
 166
 167         /// Clamp variable n to value i (i.e. multiply with a Kronecker delta \f$\delta_{x_n, i}\f$);
 168         /// If backup == true, make a backup of all factors that are changed
 169         virtual void clamp( const Var & n, size_t i, bool backup = false );
 170
 171         /// Set all factors interacting with the i'th variable 1
 172         virtual void makeCavity( unsigned i, bool backup = false );
 173
 174         /// Backup the factors specified by indices in facs
 175         virtual void backupFactors( const std::set<size_t> & facs );
 176
 177         /// Restore all factors to the backup copies
 178         virtual void restoreFactors();
 179
 180         bool isConnected() const { return G.isConnected(); }
 181         bool isTree() const { return G.isTree(); }
 182
 183         friend std::ostream& operator << (std::ostream& os, const FactorGraph& fg);
 184         friend std::istream& operator >> (std::istream& is, FactorGraph& fg);
 185
 186         void ReadFromFile(const char *filename);
 187         void WriteToFile(const char *filename) const;
 188         void printDot( std::ostream& os ) const;
 189
 190         std::vector<VarSet> Cliques() const;
 191
 192         // Clamp variable v_i to value state (i.e. multiply with a Kronecker delta \f$\delta_{x_{v_i},x}\f$);
 193         // This version changes the factor graph structure and thus returns a newly constructed FactorGraph
 194         // and keeps the current one constant, contrary to clamp()
 195         FactorGraph clamped( const Var & v_i, size_t x ) const;
 196
 197         FactorGraph maximalFactors() const;
 198
 199         bool isPairwise() const;
 200         bool isBinary() const;
 201
 202         void restoreFactor( size_t I );
 203         void backupFactor( size_t I );
 204         void restoreFactors( const VarSet &ns );
 205         void backupFactors( const VarSet &ns );
 206         /// Part of constructors (creates edges, neighbors and adjacency matrix)
 207         void constructGraph( size_t nrEdges );
 208 };
 209
 210
 211 // assumes that the set of variables in [var_begin,var_end) is the union of the variables in the factors in [fact_begin, fact_end)
 212 template<typename FactorInputIterator, typename VarInputIterator>
 213 FactorGraph::FactorGraph(FactorInputIterator fact_begin, FactorInputIterator fact_end, VarInputIterator var_begin, VarInputIterator var_end, size_t nr_fact_hint, size_t nr_var_hint ) : G(), _backup() {
 214     // add factors
 215     size_t nrEdges = 0;
 216     _factors.reserve( nr_fact_hint );
 217     for( FactorInputIterator p2 = fact_begin; p2 != fact_end; ++p2 ) {
 218         _factors.push_back( *p2 );
 219         nrEdges += p2->vars().size();
 220     }
 221
 222     // add variables
 223     vars.reserve( nr_var_hint );
 224     for( VarInputIterator p1 = var_begin; p1 != var_end; ++p1 )
 225         vars.push_back( *p1 );
 226
 227     // create graph structure
 228     constructGraph( nrEdges );
 229 }
 230
 231
 232 } // end of namespace dai
 233
 234
 235 #endif