Fixed regression in TFactor::partSum
[libdai.git] / 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 class FactorGraph {
65 public:
66 /// Stores the neighborhood structure
67 BipartiteGraph G;
68
69 /// Shorthand for BipartiteGraph::Neighbor
70 typedef BipartiteGraph::Neighbor Neighbor;
71
72 /// Shorthand for BipartiteGraph::Neighbors
73 typedef BipartiteGraph::Neighbors Neighbors;
74
75 /// Shorthand for BipartiteGraph::Edge
76 typedef BipartiteGraph::Edge Edge;
77
78 private:
79 std::vector<Var> _vars;
80 std::vector<Factor> _factors;
81 std::map<size_t,Factor> _backup;
82
83 public:
84 /// Default constructor
85 FactorGraph() : G(), _vars(), _factors(), _backup() {}
86
87 /// Copy constructor
88 FactorGraph(const FactorGraph & x) : G(x.G), _vars(x._vars), _factors(x._factors), _backup(x._backup) {}
89
90 /// Assignment operator
91 FactorGraph & operator=(const FactorGraph & x) {
92 if( this != &x ) {
93 G = x.G;
94 _vars = x._vars;
95 _factors = x._factors;
96 _backup = x._backup;
97 }
98 return *this;
99 }
100
101 /// Constructs a FactorGraph from a vector of factors
102 FactorGraph(const std::vector<Factor> &P);
103
104 /// Constructs a FactorGraph from given factor and variable iterators
105 /** \tparam FactorInputIterator Iterator with value_type Factor
106 * \tparam VarInputIterator Iterator with value_type Var
107 * \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)
108 */
109 template<typename FactorInputIterator, typename VarInputIterator>
110 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 );
111
112 /// Destructor
113 virtual ~FactorGraph() {}
114
115 /// Clone *this (virtual copy constructor)
116 virtual FactorGraph* clone() const { return new FactorGraph(); }
117
118 /// Create (virtual default constructor)
119 virtual FactorGraph* create() const { return new FactorGraph(*this); }
120
121 /// Returns const reference to i'th variable
122 const Var & var(size_t i) const { return _vars[i]; }
123 /// Returns const reference to all factors
124 const std::vector<Var> & vars() const { return _vars; }
125 /// Returns reference to I'th factor
126 Factor & factor(size_t I) { return _factors[I]; }
127 /// Returns const reference to I'th factor
128 const Factor & factor(size_t I) const { return _factors[I]; }
129 /// Returns const reference to all factors
130 const std::vector<Factor> & factors() const { return _factors; }
131
132 /// Returns number of variables
133 size_t nrVars() const { return vars().size(); }
134 /// Returns number of factors
135 size_t nrFactors() const { return factors().size(); }
136 /// Calculates number of edges
137 size_t nrEdges() const { return G.nrEdges(); }
138
139 /// Provides read access to neighbors of variable
140 const Neighbors & nbV( size_t i ) const { return G.nb1(i); }
141 /// Provides full access to neighbors of variable
142 Neighbors & nbV( size_t i ) { return G.nb1(i); }
143 /// Provides read access to neighbors of factor
144 const Neighbors & nbF( size_t I ) const { return G.nb2(I); }
145 /// Provides full access to neighbors of factor
146 Neighbors & nbF( size_t I ) { return G.nb2(I); }
147 /// Provides read access to neighbor of variable
148 const Neighbor & nbV( size_t i, size_t _I ) const { return G.nb1(i)[_I]; }
149 /// Provides full access to neighbor of variable
150 Neighbor & nbV( size_t i, size_t _I ) { return G.nb1(i)[_I]; }
151 /// Provides read access to neighbor of factor
152 const Neighbor & nbF( size_t I, size_t _i ) const { return G.nb2(I)[_i]; }
153 /// Provides full access to neighbor of factor
154 Neighbor & nbF( size_t I, size_t _i ) { return G.nb2(I)[_i]; }
155
156 /// Returns the index of a particular variable
157 size_t findVar( const Var & n ) const {
158 size_t i = find( vars().begin(), vars().end(), n ) - vars().begin();
159 assert( i != nrVars() );
160 return i;
161 }
162
163 /// Returns a set of indexes corresponding to a set of variables
164 std::set<size_t> findVars( VarSet &ns ) const {
165 std::set<size_t> indexes;
166 for( VarSet::const_iterator n = ns.begin(); n != ns.end(); n++ )
167 indexes.insert( findVar( *n ) );
168 return indexes;
169 }
170
171 /// Returns index of the first factor that depends on the variables
172 size_t findFactor(const VarSet &ns) const {
173 size_t I;
174 for( I = 0; I < nrFactors(); I++ )
175 if( factor(I).vars() == ns )
176 break;
177 assert( I != nrFactors() );
178 return I;
179 }
180
181 /// Return all variables that occur in a factor involving the i'th variable, itself included
182 VarSet Delta( unsigned i ) const;
183
184 /// Return all variables that occur in a factor involving some variable in ns, ns itself included
185 VarSet Delta( const VarSet &ns ) const;
186
187 /// Return all variables that occur in a factor involving the i'th variable, n itself excluded
188 VarSet delta( unsigned i ) const;
189
190 /// Return all variables that occur in a factor involving some variable in ns, ns itself excluded
191 VarSet delta( const VarSet & ns ) const {
192 return Delta( ns ) / ns;
193 }
194
195 /// Set the content of the I'th factor and make a backup of its old content if backup == true
196 virtual void setFactor( size_t I, const Factor &newFactor, bool backup = false ) {
197 assert( newFactor.vars() == factor(I).vars() );
198 if( backup )
199 backupFactor( I );
200 _factors[I] = newFactor;
201 }
202
203 /// Set the contents of all factors as specified by facs and make a backup of the old contents if backup == true
204 virtual void setFactors( const std::map<size_t, Factor> & facs, bool backup = false ) {
205 for( std::map<size_t, Factor>::const_iterator fac = facs.begin(); fac != facs.end(); fac++ ) {
206 if( backup )
207 backupFactor( fac->first );
208 setFactor( fac->first, fac->second );
209 }
210 }
211
212 /// Clamp variable n to value i (i.e. multiply with a Kronecker delta \f$\delta_{x_n, i}\f$);
213 /// If backup == true, make a backup of all factors that are changed
214 virtual void clamp( const Var & n, size_t i, bool backup = false );
215
216 /// Set all factors interacting with the i'th variable 1
217 virtual void makeCavity( unsigned i, bool backup = false );
218
219 /// Backup the factors specified by indices in facs
220 virtual void backupFactors( const std::set<size_t> & facs );
221
222 /// Restore all factors to the backup copies
223 virtual void restoreFactors();
224
225 /// Returns true if the FactorGraph is connected
226 bool isConnected() const { return G.isConnected(); }
227
228 /// Returns true if the FactorGraph is a tree
229 bool isTree() const { return G.isTree(); }
230
231 /// Returns true if each factor depends on at most two variables
232 bool isPairwise() const;
233
234 /// Returns true if each variable has only two possible values
235 bool isBinary() const;
236
237 /// Reads a FactorGraph from a file
238 void ReadFromFile(const char *filename);
239
240 /// Writes a FactorGraph to a file
241 void WriteToFile(const char *filename) const;
242
243 /// Writes a FactorGraph to a GraphViz .dot file
244 void printDot( std::ostream& os ) const;
245
246 /// Returns the cliques in this FactorGraph
247 std::vector<VarSet> Cliques() const;
248
249 /// Clamp variable v_i to value state (i.e. multiply with a Kronecker delta \f$\delta_{x_{v_i},x}\f$);
250 /** This version changes the factor graph structure and thus returns a newly constructed FactorGraph
251 * and keeps the current one constant, contrary to clamp()
252 */
253 FactorGraph clamped( const Var & v_i, size_t x ) const;
254
255 /// Returns a copy of *this, where all factors that are subsumed by some larger factor are merged with the larger factors.
256 FactorGraph maximalFactors() const;
257
258 /// Makes a backup of the I'th Factor
259 void restoreFactor( size_t I );
260
261 /// Restores the I'th Factor from the backup (it should be backed up first)
262 void backupFactor( size_t I );
263
264 /// Makes a backup of all factors connected to a set of variables
265 void backupFactors( const VarSet &ns );
266 /// Restores all factors connected to a set of variables from their backups
267 void restoreFactors( const VarSet &ns );
268
269 // Friends
270 friend std::ostream& operator << (std::ostream& os, const FactorGraph& fg);
271 friend std::istream& operator >> (std::istream& is, FactorGraph& fg);
272
273 private:
274 /// Part of constructors (creates edges, neighbors and adjacency matrix)
275 void constructGraph( size_t nrEdges );
276 };
277
278
279 template<typename FactorInputIterator, typename VarInputIterator>
280 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() {
281 // add factors
282 size_t nrEdges = 0;
283 _factors.reserve( nr_fact_hint );
284 for( FactorInputIterator p2 = fact_begin; p2 != fact_end; ++p2 ) {
285 _factors.push_back( *p2 );
286 nrEdges += p2->vars().size();
287 }
288
289 // add variables
290 _vars.reserve( nr_var_hint );
291 for( VarInputIterator p1 = var_begin; p1 != var_end; ++p1 )
292 _vars.push_back( *p1 );
293
294 // create graph structure
295 constructGraph( nrEdges );
296 }
297
298
299 } // end of namespace dai
300
301
302 #endif