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 /// \file
  24 /// \brief Defines the FactorGraph class
  25 /// \todo Improve documentation
  26
  27
  28 #ifndef __defined_libdai_factorgraph_h
  29 #define __defined_libdai_factorgraph_h
  30
  31
  32 #include <iostream>
  33 #include <map>
  34 #include <dai/bipgraph.h>
  35 #include <dai/factor.h>
  36
  37
  38 namespace dai {
  39
  40
  41 /// Represents a factor graph.
  42 /** Both Bayesian Networks and Markov random fields can be represented in a
  43  *  unifying representation, called <em>factor graph</em> [\ref KFL01],
  44  *  implemented in libDAI by the FactorGraph class.
  45  *
  46  *  Consider a probability distribution over \f$N\f$ discrete random variables
  47  *  \f$x_0,x_1,\dots,x_N\f$ that factorizes as a product of factors, each of
  48  *  which depends on some subset of the variables:
  49  *  \f[
  50  *    P(x_0,x_1,\dots,x_N) = \frac{1}{Z} \prod_{I=0}^M f_I(x_I), \qquad
  51  *    Z = \sum_{x_0}\dots\sum_{x_N} \prod_{I=0}^M f_I(X_I).
  52  *  \f]
  53  *  Each factor \f$f_I\f$ is a function from an associated subset
  54  *  of variables \f$X_I \subset \{x_0,x_1,\dots,x_N\}\f$ to the nonnegative
  55  *  real numbers.
  56  *
  57  *  For a Bayesian network, each factor corresponds to a (conditional)
  58  *  probability table, whereas for a Markov random field, each factor
  59  *  corresponds to a maximal clique of the undirected graph.
  60  *
  61  *  Factor graphs explicitly express the factorization structure of the
  62  *  corresponding probability distribution.
  63  *
  64  *  \todo Alternative implementation of undo factor changes: the only things that have to be
  65  *  undone currently are setting a factor to 1 and setting a factor to a Kronecker delta. This
  66  *  could also be implemented in the TFactor itself, which could maintain its state
  67  *  (ones/delta/full) and act accordingly.
  68  */
  69 class FactorGraph {
  70     public:
  71         /// Stores the neighborhood structure
  72         BipartiteGraph                    G;
  73
  74         /// Shorthand for BipartiteGraph::Neighbor
  75         typedef BipartiteGraph::Neighbor  Neighbor;
  76
  77         /// Shorthand for BipartiteGraph::Neighbors
  78         typedef BipartiteGraph::Neighbors Neighbors;
  79
  80         /// Shorthand for BipartiteGraph::Edge
  81         typedef BipartiteGraph::Edge      Edge;
  82
  83         /// Iterator over factors
  84         typedef std::vector<Factor>::iterator iterator;
  85
  86         /// Const iterator over factors
  87         typedef std::vector<Factor>::const_iterator const_iterator;
  88
  89
  90     private:
  91         std::vector<Var>         _vars;
  92         std::vector<Factor>      _factors;
  93         std::map<size_t,Factor>  _backup;
  94
  95     public:
  96         /// Default constructor
  97         FactorGraph() : G(), _vars(), _factors(), _backup() {}
  98
  99         /// Constructs a FactorGraph from a vector of factors
 100         FactorGraph(const std::vector<Factor> &P);
 101
 102         /// Constructs a FactorGraph from given factor and variable iterators
 103         /** \tparam FactorInputIterator Iterator with value_type Factor
 104          *  \tparam VarInputIterator Iterator with value_type Var
 105          *  \pre 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)
 106          */
 107         template<typename FactorInputIterator, typename VarInputIterator>
 108         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 );
 109
 110         /// Destructor
 111         virtual ~FactorGraph() {}
 112
 113         /// Clone *this (virtual copy constructor)
 114         virtual FactorGraph* clone() const { return new FactorGraph(); }
 115
 116         /// Returns const reference to i'th variable
 117         const Var & var(size_t i) const { return _vars[i]; }
 118         /// Returns const reference to all factors
 119         const std::vector<Var> & vars() const { return _vars; }
 120         /// Returns reference to I'th factor
 121         Factor & factor(size_t I) { return _factors[I]; }
 122         /// Returns const reference to I'th factor
 123         const Factor & factor(size_t I) const { return _factors[I]; }
 124         /// Returns const reference to all factors
 125         const std::vector<Factor> & factors() const { return _factors; }
 126         /// Returns iterator pointing to first factor
 127         iterator begin() { return _factors.begin(); }
 128         /// Returns const iterator pointing to first factor
 129         const_iterator begin() const { return _factors.begin(); }
 130         /// Returns iterator pointing beyond last factor
 131         iterator end() { return _factors.end(); }
 132         /// Returns const iterator pointing beyond last factor
 133         const_iterator end() const { return _factors.end(); }
 134
 135         /// Returns number of variables
 136         size_t nrVars() const { return vars().size(); }
 137         /// Returns number of factors
 138         size_t nrFactors() const { return factors().size(); }
 139         /// Calculates number of edges
 140         size_t nrEdges() const { return G.nrEdges(); }
 141
 142         /// Provides read access to neighbors of variable
 143         const Neighbors & nbV( size_t i ) const { return G.nb1(i); }
 144         /// Provides full access to neighbors of variable
 145         Neighbors & nbV( size_t i ) { return G.nb1(i); }
 146         /// Provides read access to neighbors of factor
 147         const Neighbors & nbF( size_t I ) const { return G.nb2(I); }
 148         /// Provides full access to neighbors of factor
 149         Neighbors & nbF( size_t I ) { return G.nb2(I); }
 150         /// Provides read access to neighbor of variable
 151         const Neighbor & nbV( size_t i, size_t _I ) const { return G.nb1(i)[_I]; }
 152         /// Provides full access to neighbor of variable
 153         Neighbor & nbV( size_t i, size_t _I ) { return G.nb1(i)[_I]; }
 154         /// Provides read access to neighbor of factor
 155         const Neighbor & nbF( size_t I, size_t _i ) const { return G.nb2(I)[_i]; }
 156         /// Provides full access to neighbor of factor
 157         Neighbor & nbF( size_t I, size_t _i ) { return G.nb2(I)[_i]; }
 158
 159         /// Returns the index of a particular variable
 160         size_t findVar( const Var & n ) const {
 161             size_t i = find( vars().begin(), vars().end(), n ) - vars().begin();
 162             assert( i != nrVars() );
 163             return i;
 164         }
 165
 166         /// Returns a set of indexes corresponding to a set of variables
 167         std::set<size_t> findVars( VarSet &ns ) const {
 168             std::set<size_t> indexes;
 169             for( VarSet::const_iterator n = ns.begin(); n != ns.end(); n++ )
 170                 indexes.insert( findVar( *n ) );
 171             return indexes;
 172         }
 173
 174         /// Returns index of the first factor that depends on the variables
 175         size_t findFactor(const VarSet &ns) const {
 176             size_t I;
 177             for( I = 0; I < nrFactors(); I++ )
 178                 if( factor(I).vars() == ns )
 179                     break;
 180             assert( I != nrFactors() );
 181             return I;
 182         }
 183
 184         /// Return all variables that occur in a factor involving the i'th variable, itself included
 185         VarSet Delta( unsigned i ) const;
 186
 187         /// Return all variables that occur in a factor involving some variable in ns, ns itself included
 188         VarSet Delta( const VarSet &ns ) const;
 189
 190         /// Return all variables that occur in a factor involving the i'th variable, n itself excluded
 191         VarSet delta( unsigned i ) const;
 192
 193         /// Return all variables that occur in a factor involving some variable in ns, ns itself excluded
 194         VarSet delta( const VarSet & ns ) const {
 195             return Delta( ns ) / ns;
 196         }
 197
 198         /// Set the content of the I'th factor and make a backup of its old content if backup == true
 199         virtual void setFactor( size_t I, const Factor &newFactor, bool backup = false ) {
 200             assert( newFactor.vars() == factor(I).vars() );
 201             if( backup )
 202                 backupFactor( I );
 203             _factors[I] = newFactor;
 204         }
 205
 206         /// Set the contents of all factors as specified by facs and make a backup of the old contents if backup == true
 207         virtual void setFactors( const std::map<size_t, Factor> & facs, bool backup = false ) {
 208             for( std::map<size_t, Factor>::const_iterator fac = facs.begin(); fac != facs.end(); fac++ ) {
 209                 if( backup )
 210                     backupFactor( fac->first );
 211                 setFactor( fac->first, fac->second );
 212             }
 213         }
 214
 215         /// Clamp variable n to value i (i.e. multiply with a Kronecker delta \f$\delta_{x_n, i}\f$)
 216         /** If backup == true, make a backup of all factors that are changed
 217          */
 218         virtual void clamp( const Var & n, size_t i, bool backup = false );
 219
 220         /// Clamp a variable in a factor graph to have one out of a list of values
 221         /** If backup == true, make a backup of all factors that are changed
 222          */
 223         void clampVar( size_t i, const std::vector<size_t> &xis, bool backup = false );
 224
 225         /// Clamp a factor in a factor graph to have one out of a list of values
 226         /** If backup == true, make a backup of all factors that are changed
 227          */
 228         void clampFactor( size_t I, const std::vector<size_t> &xIs, bool backup = false );
 229
 230         /// Set all factors interacting with the i'th variable 1
 231         virtual void makeCavity( unsigned i, bool backup = false );
 232
 233         /// Backup the factors specified by indices in facs
 234         virtual void backupFactors( const std::set<size_t> & facs );
 235
 236         /// Restore all factors to the backup copies
 237         virtual void restoreFactors();
 238
 239         /// Returns true if the FactorGraph is connected
 240         bool isConnected() const { return G.isConnected(); }
 241
 242         /// Returns true if the FactorGraph is a tree
 243         bool isTree() const { return G.isTree(); }
 244
 245         /// Returns true if each factor depends on at most two variables
 246         bool isPairwise() const;
 247
 248         /// Returns true if each variable has only two possible values
 249         bool isBinary() const;
 250
 251         /// Reads a FactorGraph from a file
 252         void ReadFromFile(const char *filename);
 253
 254         /// Writes a FactorGraph to a file
 255         void WriteToFile(const char *filename, size_t precision=15) const;
 256
 257         /// Writes a FactorGraph to a GraphViz .dot file
 258         void printDot( std::ostream& os ) const;
 259
 260         /// Returns the cliques in this FactorGraph
 261         std::vector<VarSet> Cliques() const;
 262
 263         /// Clamp variable v_i to value state (i.e. multiply with a Kronecker delta \f$\delta_{x_{v_i},x}\f$);
 264         /** This version changes the factor graph structure and thus returns a newly constructed FactorGraph
 265          *  and keeps the current one constant, contrary to clamp()
 266          */
 267         FactorGraph clamped( const Var & v_i, size_t x ) const;
 268
 269         /// Returns a copy of *this, where all factors that are subsumed by some larger factor are merged with the larger factors.
 270         FactorGraph maximalFactors() const;
 271
 272         /// Makes a backup of the I'th Factor
 273         void restoreFactor( size_t I );
 274
 275         /// Restores the I'th Factor from the backup (it should be backed up first)
 276         void backupFactor( size_t I );
 277
 278         /// Makes a backup of all factors connected to a set of variables
 279         void backupFactors( const VarSet &ns );
 280         /// Restores all factors connected to a set of variables from their backups
 281         void restoreFactors( const VarSet &ns );
 282
 283         // Friends
 284         friend std::ostream& operator << (std::ostream& os, const FactorGraph& fg);
 285         friend std::istream& operator >> (std::istream& is, FactorGraph& fg);
 286
 287         /// @name Backwards compatibility layer (to be removed soon)
 288         //@{
 289         size_t VV2E(size_t n1, size_t n2) const { return G.VV2E(n1,n2); }
 290         const Edge& edge(size_t e) const { return G.edge(e); }
 291         void indexEdges() { G.indexEdges(); }
 292         size_t nr_edges() const { return G.nr_edges(); }
 293         const std::vector<Edge>& edges() const { return G.edges(); }
 294         //}@
 295
 296     private:
 297         /// Part of constructors (creates edges, neighbors and adjacency matrix)
 298         void constructGraph( size_t nrEdges );
 299 };
 300
 301
 302 template<typename FactorInputIterator, typename VarInputIterator>
 303 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() {
 304     // add factors
 305     size_t nrEdges = 0;
 306     _factors.reserve( nr_fact_hint );
 307     for( FactorInputIterator p2 = fact_begin; p2 != fact_end; ++p2 ) {
 308         _factors.push_back( *p2 );
 309         nrEdges += p2->vars().size();
 310     }
 311
 312     // add variables
 313     _vars.reserve( nr_var_hint );
 314     for( VarInputIterator p1 = var_begin; p1 != var_end; ++p1 )
 315         _vars.push_back( *p1 );
 316
 317     // create graph structure
 318     constructGraph( nrEdges );
 319 }
 320
 321
 322 } // end of namespace dai
 323
 324
 325 #endif