1 /* This file is part of libDAI - http://www.libdai.org/
2 *
4 * 2, or (at your option) any later version. libDAI is distributed without any
5 * warranty. See the file COPYING for more details.
6 *
7 * Copyright (C) 2006-2010 Joris Mooij [joris dot mooij at libdai dot org]
9 */
12 /// \file
13 /// \brief Defines the FactorGraph class, which represents factor graphs (e.g., Bayesian networks or Markov random fields)
16 #ifndef __defined_libdai_factorgraph_h
17 #define __defined_libdai_factorgraph_h
20 #include <iostream>
21 #include <map>
22 #include <dai/bipgraph.h>
23 #include <dai/graph.h>
24 #include <dai/factor.h>
27 namespace dai {
30 /// Represents a factor graph.
31 /** Both Bayesian Networks and Markov random fields can be represented in a
32 * unifying representation, called <em>factor graph</em> [\ref KFL01],
33 * implemented in libDAI by the FactorGraph class.
34 *
35 * Consider a probability distribution over \f$N\f$ discrete random variables
36 * \f$x_0,x_1,\dots,x_{N-1}\f$ that factorizes as a product of \f$M\f$ factors, each of
37 * which depends on some subset of the variables:
38 * \f[
39 * P(x_0,x_1,\dots,x_{N-1}) = \frac{1}{Z} \prod_{I=0}^{M-1} f_I(x_I), \qquad
40 * Z = \sum_{x_0}\dots\sum_{x_{N-1}} \prod_{I=0}^{M-1} f_I(X_I).
41 * \f]
42 * Each factor \f$f_I\f$ is a function from an associated subset
43 * of variables \f$X_I \subset \{x_0,x_1,\dots,x_{N-1}\}\f$ to the nonnegative
44 * real numbers.
45 *
46 * For a Bayesian network, each factor corresponds to a (conditional)
47 * probability table, whereas for a Markov random field, each factor
48 * corresponds to a maximal clique of the undirected graph.
49 *
50 * Factor graphs explicitly express the factorization structure of the
51 * corresponding probability distribution. A factor graph is a bipartite graph,
52 * containing variable nodes and factor nodes, and an edge between a variable
53 * node and a factor node if the corresponding factor depends on that variable.
54 * In libDAI, this structure is represented by a BipartiteGraph.
55 *
56 * So basically, a FactorGraph consists of a BipartiteGraph, a vector of Var 's
57 * and a vector of TFactor 's.
58 *
59 * \idea Alternative implementation of undo factor changes: the only things that have to be
60 * undone currently are setting a factor to 1 and setting a factor to a Kronecker delta. This
61 * could also be implemented in the TFactor itself, which could maintain its state
62 * (ones/delta/full) and act accordingly. Update: it seems that the proposed functionality
63 * would not be enough for CBP, for which it would make more sense to add more levels of
64 * backup/restore.
65 */
66 class FactorGraph {
67 public:
68 /// Shorthand for BipartiteGraph::Neighbor
69 typedef BipartiteGraph::Neighbor Neighbor;
71 /// Shorthand for BipartiteGraph::Neighbors
72 typedef BipartiteGraph::Neighbors Neighbors;
74 /// Shorthand for BipartiteGraph::Edge
75 typedef BipartiteGraph::Edge Edge;
77 /// Iterator over factors
78 /** \deprecated The FactorGraph iterator interface will be removed in future versions of libDAI
79 */
80 typedef std::vector<Factor>::iterator iterator;
82 /// Constant iterator over factors
83 /** \deprecated The FactorGraph iterator interface will be removed in future versions of libDAI
84 */
85 typedef std::vector<Factor>::const_iterator const_iterator;
87 private:
88 /// Stores the neighborhood structure
89 BipartiteGraph _G;
90 /// Stores the variables
91 std::vector<Var> _vars;
92 /// Stores the factors
93 std::vector<Factor> _factors;
94 /// Stores backups of some factors
95 std::map<size_t,Factor> _backup;
97 public:
98 /// \name Constructors and destructors
99 //@{
100 /// Default constructor
101 FactorGraph() : _G(), _vars(), _factors(), _backup() {}
103 /// Constructs a factor graph from a vector of factors
104 FactorGraph( const std::vector<Factor>& P );
106 /// Constructs a factor graph from given factor and variable iterators
107 /** \tparam FactorInputIterator Iterates over instances of type dai::Factor
108 * \tparam VarInputIterator Iterates over instances of type Var
109 * \pre Assumes that the set of variables in [\a varBegin, \a varEnd) is the union of the variables in the factors in [\a facBegin, \a facEnd)
110 */
111 template<typename FactorInputIterator, typename VarInputIterator>
112 FactorGraph(FactorInputIterator facBegin, FactorInputIterator facEnd, VarInputIterator varBegin, VarInputIterator varEnd, size_t nrFacHint = 0, size_t nrVarHint = 0 );
114 /// Destructor
115 virtual ~FactorGraph() {}
117 /// Virtual copy constructor
118 virtual FactorGraph* clone() const { return new FactorGraph(*this); }
119 //@}
121 /// \name Accessors and mutators
122 //@{
123 /// Returns constant reference the \a i 'th variable
124 const Var& var( size_t i ) const {
125 DAI_DEBASSERT( i < nrVars() );
126 return _vars[i];
127 }
129 /// Returns constant reference to all variables
130 const std::vector<Var>& vars() const { return _vars; }
132 /// Returns reference to \a I 'th factor
133 /** \deprecated Please use the const member dai::FactorGraph::factor( size_t ) instead,
134 * or dai::FactorGraph::setFactor() for changing a factor.
135 */
136 Factor& factor( size_t I ) {
137 DAI_DEBASSERT( I < nrFactors() );
138 return _factors[I];
139 }
141 /// Returns constant reference to \a I 'th factor
142 const Factor& factor( size_t I ) const {
143 DAI_DEBASSERT( I < nrFactors() );
144 return _factors[I];
145 }
146 /// Returns constant reference to all factors
147 const std::vector<Factor>& factors() const { return _factors; }
149 /// Returns constant reference to neighbors of the \a i 'th variable
150 const Neighbors& nbV( size_t i ) const { return _G.nb1(i); }
151 /// Returns constant reference to neighbors of the \a I 'th factor
152 const Neighbors& nbF( size_t I ) const { return _G.nb2(I); }
153 /// Returns constant reference to the \a _I 'th neighbor of the \a i 'th variable
154 const Neighbor& nbV( size_t i, size_t _I ) const { return _G.nb1(i)[_I]; }
155 /// Returns constant reference to the \a _i 'th neighbor of the \a I 'th factor
156 const Neighbor& nbF( size_t I, size_t _i ) const { return _G.nb2(I)[_i]; }
157 //@}
159 /// \name Iterator interface
160 //@{
161 /// Returns iterator pointing to first factor
162 /** \deprecated The FactorGraph iterator interface will be removed in future versions of libDAI
163 */
164 iterator begin() { return _factors.begin(); }
165 /// Returns constant iterator pointing to first factor
166 /** \deprecated The FactorGraph iterator interface will be removed in future versions of libDAI
167 */
168 const_iterator begin() const { return _factors.begin(); }
169 /// Returns iterator pointing beyond last factor
170 /** \deprecated The FactorGraph iterator interface will be removed in future versions of libDAI
171 */
172 iterator end() { return _factors.end(); }
173 /// Returns constant iterator pointing beyond last factor
174 /** \deprecated The FactorGraph iterator interface will be removed in future versions of libDAI
175 */
176 const_iterator end() const { return _factors.end(); }
177 //@}
179 /// \name Queries
180 //@{
181 /// Returns neighborhood structure
182 const BipartiteGraph& bipGraph() const { return _G; }
183 /// Returns number of variables
184 size_t nrVars() const { return vars().size(); }
185 /// Returns number of factors
186 size_t nrFactors() const { return factors().size(); }
187 /// Calculates number of edges
188 /** \note Time complexity: O(nrVars())
189 */
190 size_t nrEdges() const { return _G.nrEdges(); }
192 /// Returns the index of a particular variable
193 /** \note Time complexity: O(nrVars())
194 * \throw OBJECT_NOT_FOUND if the variable is not part of this factor graph
195 */
196 size_t findVar( const Var& n ) const {
197 size_t i = find( vars().begin(), vars().end(), n ) - vars().begin();
198 if( i == nrVars() )
199 DAI_THROW(OBJECT_NOT_FOUND);
200 return i;
201 }
203 /// Returns a set of indexes corresponding to a set of variables
204 /** \note Time complexity: O( nrVars() * ns.size() )
205 * \throw OBJECT_NOT_FOUND if one of the variables is not part of this factor graph
206 */
207 SmallSet<size_t> findVars( const VarSet& ns ) const {
208 SmallSet<size_t> result;
209 for( VarSet::const_iterator n = ns.begin(); n != ns.end(); n++ )
210 result.insert( findVar( *n ) );
211 return result;
212 }
214 /// Returns index of the first factor that depends on the variables
215 /** \note Time complexity: O(nrFactors())
216 * \throw OBJECT_NOT_FOUND if no factor in this factor graph depends on those variables
217 */
218 size_t findFactor( const VarSet& ns ) const {
219 size_t I;
220 for( I = 0; I < nrFactors(); I++ )
221 if( factor(I).vars() == ns )
222 break;
223 if( I == nrFactors() )
224 DAI_THROW(OBJECT_NOT_FOUND);
225 return I;
226 }
228 /// Return all variables that occur in a factor involving the \a i 'th variable, itself included
229 VarSet Delta( size_t i ) const;
231 /// Return all variables that occur in a factor involving some variable in \a vs, \a vs itself included
232 VarSet Delta( const VarSet& vs ) const;
234 /// Return all variables that occur in a factor involving the \a i 'th variable, itself excluded
235 VarSet delta( size_t i ) const {
236 return( Delta( i ) / var( i ) );
237 }
239 /// Return all variables that occur in a factor involving some variable in \a vs, \a vs itself excluded
240 VarSet delta( const VarSet& vs ) const {
241 return Delta( vs ) / vs;
242 }
244 /// Returns \c true if the factor graph is connected
245 bool isConnected() const { return _G.isConnected(); }
247 /// Returns \c true if the factor graph is a tree (i.e., has no cycles and is connected)
248 bool isTree() const { return _G.isTree(); }
250 /// Returns \c true if each factor depends on at most two variables
251 bool isPairwise() const;
253 /// Returns \c true if each variable has only two possible values
254 bool isBinary() const;
256 /// Constructs the corresponding Markov graph
257 /** \note The Markov graph has the variables as nodes and an edge
258 * between two variables if and only if the variables share a factor.
259 */
260 GraphAL MarkovGraph() const;
262 /// Returns the maximal factor domains in this factorgraph
263 /** \note A factor domain is \a maximal if and only if it is not a
264 * strict subset of another factor domain.
265 */
266 std::vector<VarSet> maximalFactorDomains() const;
268 /// Returns the maximal factors domains in this factorgraph
270 */
271 std::vector<VarSet> cliques() const {
272 return maximalFactorDomains();
273 }
274 //@}
276 /// \name Backup/restore mechanism for factors
277 //@{
278 /// Set the content of the \a I 'th factor and make a backup of its old content if \a backup == \c true
279 virtual void setFactor( size_t I, const Factor& newFactor, bool backup = false ) {
280 DAI_ASSERT( newFactor.vars() == factor(I).vars() );
281 if( backup )
282 backupFactor( I );
283 _factors[I] = newFactor;
284 }
286 /// Set the contents of all factors as specified by \a facs and make a backup of the old contents if \a backup == \c true
287 virtual void setFactors( const std::map<size_t, Factor>& facs, bool backup = false ) {
288 for( std::map<size_t, Factor>::const_iterator fac = facs.begin(); fac != facs.end(); fac++ ) {
289 if( backup )
290 backupFactor( fac->first );
291 setFactor( fac->first, fac->second );
292 }
293 }
295 /// Makes a backup of the \a I 'th factor
296 /** \throw MULTIPLE_UNDO if a backup already exists
297 */
298 void backupFactor( size_t I );
300 /// Restores the \a I 'th factor from the backup (it should be backed up first)
301 /** \throw OBJECT_NOT_FOUND if a backup does not exist
302 */
303 void restoreFactor( size_t I );
305 /// Backup the factors specified by indices in \a facs
306 /** \throw MULTIPLE_UNDO if a backup already exists
307 */
308 virtual void backupFactors( const std::set<size_t>& facs );
310 /// Restore all factors to the backup copies
311 virtual void restoreFactors();
313 /// Makes a backup of all factors connected to a set of variables
314 /** \throw MULTIPLE_UNDO if a backup already exists
315 */
316 void backupFactors( const VarSet& ns );
318 /// Restores all factors connected to a set of variables from their backups
319 void restoreFactors( const VarSet& ns );
320 //@}
322 /// \name Transformations
323 //@{
324 /// Returns a copy of \c *this, where all factors that are subsumed by some larger factor are merged with the larger factors.
325 FactorGraph maximalFactors() const;
327 /// Returns a copy of \c *this, where the \a i 'th variable has been clamped to value \a x
328 /** \note This version changes the factor graph structure and thus returns a newly constructed FactorGraph
329 * and keeps the current one constant, contrary to clamp()
330 */
331 FactorGraph clamped( size_t i, size_t x ) const;
332 //@}
334 /// \name Operations
335 //@{
336 /// Clamp the \a i 'th variable to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{x_i, x}\f$)
337 /** If \a backup == \c true, make a backup of all factors that are changed
338 */
339 virtual void clamp( size_t i, size_t x, bool backup = false );
341 /// Clamp a variable in a factor graph to have one out of a list of values
342 /** If \a backup == \c true, make a backup of all factors that are changed
343 */
344 void clampVar( size_t i, const std::vector<size_t>& xis, bool backup = false );
346 /// Clamp a factor in a factor graph to have one out of a list of values
347 /** If \a backup == \c true, make a backup of all factors that are changed
348 */
349 void clampFactor( size_t I, const std::vector<size_t>& xIs, bool backup = false );
351 /// Set all factors interacting with the \a i 'th variable to 1
352 /** If \a backup == \c true, make a backup of all factors that are changed
353 */
354 virtual void makeCavity( size_t i, bool backup = false );
355 //@}
357 /// \name Input/Output
358 //@{
359 /// Reads a factor graph from a file
360 /** \see \ref fileformats-factorgraph
361 * \throw CANNOT_READ_FILE if the file cannot be opened
362 * \throw INVALID_FACTORGRAPH_FILE if the file is not valid
363 */
364 virtual void ReadFromFile( const char *filename );
366 /// Writes a factor graph to a file
367 /** \see \ref fileformats-factorgraph
368 * \throw CANNOT_WRITE_FILE if the file cannot be written
369 */
370 virtual void WriteToFile( const char *filename, size_t precision=15 ) const;
372 /// Writes a factor graph to an output stream
373 /** \see \ref fileformats-factorgraph
374 */
375 friend std::ostream& operator<< (std::ostream& os, const FactorGraph& fg );
377 /// Reads a factor graph from an input stream
378 /** \see \ref fileformats-factorgraph
379 * \throw INVALID_FACTORGRAPH_FILE if the input stream is not valid
380 */
381 friend std::istream& operator>> (std::istream& is, FactorGraph& fg );
383 /// Writes a factor graph to a GraphViz .dot file
384 virtual void printDot( std::ostream& os ) const;
385 //@}
387 private:
388 /// Part of constructors (creates edges, neighbors and adjacency matrix)
389 void constructGraph( size_t nrEdges );
390 };
393 template<typename FactorInputIterator, typename VarInputIterator>
394 FactorGraph::FactorGraph(FactorInputIterator facBegin, FactorInputIterator facEnd, VarInputIterator varBegin, VarInputIterator varEnd, size_t nrFacHint, size_t nrVarHint ) : _G(), _backup() {
396 size_t nrEdges = 0;
397 _factors.reserve( nrFacHint );
398 for( FactorInputIterator p2 = facBegin; p2 != facEnd; ++p2 ) {
399 _factors.push_back( *p2 );
400 nrEdges += p2->vars().size();
401 }