1 /* This file is part of libDAI - http://www.libdai.org/
2 *
4 *
5 * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
6 */
9 /// \file
10 /// \brief Defines the FactorGraph class, which represents factor graphs (e.g., Bayesian networks or Markov random fields)
13 #ifndef __defined_libdai_factorgraph_h
14 #define __defined_libdai_factorgraph_h
17 #include <iostream>
18 #include <map>
19 #include <dai/bipgraph.h>
20 #include <dai/graph.h>
21 #include <dai/factor.h>
24 namespace dai {
27 /// Represents a factor graph.
28 /** Both Bayesian Networks and Markov random fields can be represented in a
29 * unifying representation, called <em>factor graph</em> [\ref KFL01],
30 * implemented in libDAI by the FactorGraph class.
31 *
32 * Consider a probability distribution over \f$N\f$ discrete random variables
33 * \f$x_0,x_1,\dots,x_{N-1}\f$ that factorizes as a product of \f$M\f$ factors, each of
34 * which depends on some subset of the variables:
35 * \f[
36 * P(x_0,x_1,\dots,x_{N-1}) = \frac{1}{Z} \prod_{I=0}^{M-1} f_I(x_I), \qquad
37 * Z = \sum_{x_0}\dots\sum_{x_{N-1}} \prod_{I=0}^{M-1} f_I(X_I).
38 * \f]
39 * Each factor \f$f_I\f$ is a function from an associated subset
40 * of variables \f$X_I \subset \{x_0,x_1,\dots,x_{N-1}\}\f$ to the nonnegative
41 * real numbers.
42 *
43 * For a Bayesian network, each factor corresponds to a (conditional)
44 * probability table, whereas for a Markov random field, each factor
45 * corresponds to a maximal clique of the undirected graph.
46 *
47 * Factor graphs explicitly express the factorization structure of the
48 * corresponding probability distribution. A factor graph is a bipartite graph,
49 * containing variable nodes and factor nodes, and an edge between a variable
50 * node and a factor node if the corresponding factor depends on that variable.
51 * In libDAI, this structure is represented by a BipartiteGraph.
52 *
53 * So basically, a FactorGraph consists of a BipartiteGraph, a vector of Var 's
54 * and a vector of TFactor 's.
55 *
56 * \idea Alternative implementation of undo factor changes: the only things that have to be
57 * undone currently are setting a factor to 1 and setting a factor to a Kronecker delta. This
58 * could also be implemented in the TFactor itself, which could maintain its state
59 * (ones/delta/full) and act accordingly. Update: it seems that the proposed functionality
60 * would not be enough for CBP, for which it would make more sense to add more levels of
61 * backup/restore.
62 *
63 * \todo Write a method that applies evidence (should we represent evidence as a map<Var,size_t> or as a map<size_t,size_t>?)
64 */
65 class FactorGraph {
66 private:
67 /// Stores the neighborhood structure
68 BipartiteGraph _G;
69 /// Stores the variables
70 std::vector<Var> _vars;
71 /// Stores the factors
72 std::vector<Factor> _factors;
73 /// Stores backups of some factors
74 std::map<size_t,Factor> _backup;
76 public:
77 /// \name Constructors and destructors
78 //@{
79 /// Default constructor
80 FactorGraph() : _G(), _vars(), _factors(), _backup() {}
82 /// Constructs a factor graph from a vector of factors
83 FactorGraph( const std::vector<Factor>& P );
85 /// Constructs a factor graph from given factor and variable iterators
86 /** \tparam FactorInputIterator Iterates over instances of type dai::Factor
87 * \tparam VarInputIterator Iterates over instances of type Var
88 * \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)
89 */
90 template<typename FactorInputIterator, typename VarInputIterator>
91 FactorGraph(FactorInputIterator facBegin, FactorInputIterator facEnd, VarInputIterator varBegin, VarInputIterator varEnd, size_t nrFacHint = 0, size_t nrVarHint = 0 );
93 /// Destructor
94 virtual ~FactorGraph() {}
96 /// Virtual copy constructor
97 virtual FactorGraph* clone() const { return new FactorGraph(*this); }
98 //@}
100 /// \name Accessors and mutators
101 //@{
102 /// Returns constant reference the \a i 'th variable
103 const Var& var( size_t i ) const {
104 DAI_DEBASSERT( i < nrVars() );
105 return _vars[i];
106 }
108 /// Returns constant reference to all variables
109 const std::vector<Var>& vars() const { return _vars; }
111 /// Returns constant reference to \a I 'th factor
112 const Factor& factor( size_t I ) const {
113 DAI_DEBASSERT( I < nrFactors() );
114 return _factors[I];
115 }
116 /// Returns constant reference to all factors
117 const std::vector<Factor>& factors() const { return _factors; }
119 /// Returns constant reference to neighbors of the \a i 'th variable
120 const Neighbors& nbV( size_t i ) const { return _G.nb1(i); }
121 /// Returns constant reference to neighbors of the \a I 'th factor
122 const Neighbors& nbF( size_t I ) const { return _G.nb2(I); }
123 /// Returns constant reference to the \a _I 'th neighbor of the \a i 'th variable
124 const Neighbor& nbV( size_t i, size_t _I ) const { return _G.nb1(i)[_I]; }
125 /// Returns constant reference to the \a _i 'th neighbor of the \a I 'th factor
126 const Neighbor& nbF( size_t I, size_t _i ) const { return _G.nb2(I)[_i]; }
127 //@}
129 /// \name Queries
130 //@{
131 /// Returns neighborhood structure
132 const BipartiteGraph& bipGraph() const { return _G; }
133 /// Returns number of variables
134 size_t nrVars() const { return vars().size(); }
135 /// Returns number of factors
136 size_t nrFactors() const { return factors().size(); }
137 /// Calculates number of edges
138 /** \note Time complexity: O(nrVars())
139 */
140 size_t nrEdges() const { return _G.nrEdges(); }
142 /// Returns the index of a particular variable
143 /** \note Time complexity: O(nrVars())
144 * \throw OBJECT_NOT_FOUND if the variable is not part of this factor graph
145 */
146 size_t findVar( const Var& n ) const {
147 size_t i = find( vars().begin(), vars().end(), n ) - vars().begin();
148 if( i == nrVars() )
149 DAI_THROW(OBJECT_NOT_FOUND);
150 return i;
151 }
153 /// Returns a set of indexes corresponding to a set of variables
154 /** \note Time complexity: O( nrVars() * ns.size() )
155 * \throw OBJECT_NOT_FOUND if one of the variables is not part of this factor graph
156 */
157 SmallSet<size_t> findVars( const VarSet& ns ) const {
158 SmallSet<size_t> result;
159 for( VarSet::const_iterator n = ns.begin(); n != ns.end(); n++ )
160 result.insert( findVar( *n ) );
161 return result;
162 }
164 /// Returns index of the first factor that depends on the variables
165 /** \note Time complexity: O(nrFactors())
166 * \throw OBJECT_NOT_FOUND if no factor in this factor graph depends on those variables
167 */
168 size_t findFactor( const VarSet& ns ) const {
169 size_t I;
170 for( I = 0; I < nrFactors(); I++ )
171 if( factor(I).vars() == ns )
172 break;
173 if( I == nrFactors() )
174 DAI_THROW(OBJECT_NOT_FOUND);
175 return I;
176 }
178 /// Return all variables that occur in a factor involving the \a i 'th variable, itself included
179 VarSet Delta( size_t i ) const;
181 /// Return all variables that occur in a factor involving some variable in \a vs, \a vs itself included
182 VarSet Delta( const VarSet& vs ) const;
184 /// Return all variables that occur in a factor involving the \a i 'th variable, itself excluded
185 VarSet delta( size_t i ) const {
186 return( Delta( i ) / var( i ) );
187 }
189 /// Return all variables that occur in a factor involving some variable in \a vs, \a vs itself excluded
190 VarSet delta( const VarSet& vs ) const {
191 return Delta( vs ) / vs;
192 }
194 /// Returns \c true if the factor graph is connected
195 bool isConnected() const { return _G.isConnected(); }
197 /// Returns \c true if the factor graph is a tree (i.e., has no cycles and is connected)
198 bool isTree() const { return _G.isTree(); }
200 /// Returns \c true if each factor depends on at most two variables
201 bool isPairwise() const;
203 /// Returns \c true if each variable has only two possible values
204 bool isBinary() const;
206 /// Constructs the corresponding Markov graph
207 /** \note The Markov graph has the variables as nodes and an edge
208 * between two variables if and only if the variables share a factor.
209 */
210 GraphAL MarkovGraph() const;
212 /// Returns whether the \a I 'th factor is maximal
213 /** \note A factor (domain) is \a maximal if and only if it is not a
214 * strict subset of another factor domain.
215 */
216 bool isMaximal( size_t I ) const;
218 /// Returns the index of a maximal factor that contains the \a I 'th factor
219 /** \note A factor (domain) is \a maximal if and only if it is not a
220 * strict subset of another factor domain.
221 */
222 size_t maximalFactor( size_t I ) const;
224 /// Returns the maximal factor domains in this factorgraph
225 /** \note A factor domain is \a maximal if and only if it is not a
226 * strict subset of another factor domain.
227 */
228 std::vector<VarSet> maximalFactorDomains() const;
230 /// Evaluates the log score (i.e., minus the energy) of the joint configuration \a statevec
231 Real logScore( const std::vector<size_t>& statevec ) const;
232 //@}
234 /// \name Backup/restore mechanism for factors
235 //@{
236 /// Set the content of the \a I 'th factor and make a backup of its old content if \a backup == \c true
237 virtual void setFactor( size_t I, const Factor& newFactor, bool backup = false ) {
238 DAI_ASSERT( newFactor.vars() == factor(I).vars() );
239 if( backup )
240 backupFactor( I );
241 _factors[I] = newFactor;
242 }
244 /// Set the contents of all factors as specified by \a facs and make a backup of the old contents if \a backup == \c true
245 virtual void setFactors( const std::map<size_t, Factor>& facs, bool backup = false ) {
246 for( std::map<size_t, Factor>::const_iterator fac = facs.begin(); fac != facs.end(); fac++ ) {
247 if( backup )
248 backupFactor( fac->first );
249 setFactor( fac->first, fac->second );
250 }
251 }
253 /// Makes a backup of the \a I 'th factor
254 /** \throw MULTIPLE_UNDO if a backup already exists
255 */
256 void backupFactor( size_t I );
258 /// Restores the \a I 'th factor from the backup (it should be backed up first)
259 /** \throw OBJECT_NOT_FOUND if a backup does not exist
260 */
261 void restoreFactor( size_t I );
263 /// Backup the factors specified by indices in \a facs
264 /** \throw MULTIPLE_UNDO if a backup already exists
265 */
266 virtual void backupFactors( const std::set<size_t>& facs );
268 /// Restore all factors to the backup copies
269 virtual void restoreFactors();
271 /// Makes a backup of all factors connected to a set of variables
272 /** \throw MULTIPLE_UNDO if a backup already exists
273 */
274 void backupFactors( const VarSet& ns );
276 /// Restores all factors connected to a set of variables from their backups
277 void restoreFactors( const VarSet& ns );
278 //@}
280 /// \name Transformations
281 //@{
282 /// Returns a copy of \c *this, where all factors that are subsumed by some larger factor are merged with the larger factors.
283 FactorGraph maximalFactors() const;
285 /// Returns a copy of \c *this, where the \a i 'th variable has been clamped to value \a x
286 /** \note This version changes the factor graph structure and thus returns a newly constructed FactorGraph
287 * and keeps the current one constant, contrary to clamp()
288 */
289 FactorGraph clamped( size_t i, size_t x ) const;
290 //@}
292 /// \name Operations
293 //@{
294 /// Clamp the \a i 'th variable to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{x_i, x}\f$)
295 /** If \a backup == \c true, make a backup of all factors that are changed
296 */
297 virtual void clamp( size_t i, size_t x, bool backup = false );
299 /// Clamp a variable in a factor graph to have one out of a list of values
300 /** If \a backup == \c true, make a backup of all factors that are changed
301 */
302 void clampVar( size_t i, const std::vector<size_t>& xis, bool backup = false );
304 /// Clamp a factor in a factor graph to have one out of a list of values
305 /** If \a backup == \c true, make a backup of all factors that are changed
306 */
307 void clampFactor( size_t I, const std::vector<size_t>& xIs, bool backup = false );
309 /// Set all factors interacting with the \a i 'th variable to 1
310 /** If \a backup == \c true, make a backup of all factors that are changed
311 */
312 virtual void makeCavity( size_t i, bool backup = false );
313 //@}
315 /// \name Input/Output
316 //@{
317 /// Reads a factor graph from a file
318 /** \see \ref fileformats-factorgraph
319 * \throw CANNOT_READ_FILE if the file cannot be opened
320 * \throw INVALID_FACTORGRAPH_FILE if the file is not valid
321 */
322 virtual void ReadFromFile( const char *filename );
324 /// Writes a factor graph to a file
325 /** \see \ref fileformats-factorgraph
326 * \throw CANNOT_WRITE_FILE if the file cannot be written
327 */
328 virtual void WriteToFile( const char *filename, size_t precision=15 ) const;
330 /// Writes a factor graph to an output stream
331 /** \see \ref fileformats-factorgraph
332 */
333 friend std::ostream& operator<< (std::ostream& os, const FactorGraph& fg );
335 /// Reads a factor graph from an input stream
336 /** \see \ref fileformats-factorgraph
337 * \throw INVALID_FACTORGRAPH_FILE if the input stream is not valid
338 */
339 friend std::istream& operator>> (std::istream& is, FactorGraph& fg );
341 /// Writes a factor graph to a GraphViz .dot file
342 virtual void printDot( std::ostream& os ) const;
343 //@}
345 private:
346 /// Part of constructors (creates edges, neighbors and adjacency matrix)
347 void constructGraph( size_t nrEdges );
348 };
351 template<typename FactorInputIterator, typename VarInputIterator>
352 FactorGraph::FactorGraph(FactorInputIterator facBegin, FactorInputIterator facEnd, VarInputIterator varBegin, VarInputIterator varEnd, size_t nrFacHint, size_t nrVarHint ) : _G(), _backup() {
353 // add factors
354 size_t nrEdges = 0;
355 _factors.reserve( nrFacHint );
356 for( FactorInputIterator p2 = facBegin; p2 != facEnd; ++p2 ) {
357 _factors.push_back( *p2 );
358 nrEdges += p2->vars().size();
359 }
361 // add variables
362 _vars.reserve( nrVarHint );
363 for( VarInputIterator p1 = varBegin; p1 != varEnd; ++p1 )
364 _vars.push_back( *p1 );
366 // create graph structure
367 constructGraph( nrEdges );
368 }
371 /** \example example_sprinkler.cpp
372 * This example illustrates how to manually construct a factor graph and
373 * write it to a file.
374 */
377 } // end of namespace dai
380 #endif