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 /// Returns the VarSet corresponding to a vector of variable indices
179 VarSet inds2vars( const std::vector<size_t>& inds ) const {
180 VarSet vs;
181 for( std::vector<size_t>::const_iterator it = inds.begin(); it != inds.end(); it++ )
182 vs.insert( var(*it) );
183 return vs;
184 }
186 /// Return all variables that occur in a factor involving the \a i 'th variable, itself included
187 VarSet Delta( size_t i ) const;
189 /// Return all variables that occur in a factor involving some variable in \a vs, \a vs itself included
190 VarSet Delta( const VarSet& vs ) const;
192 /// Return all variables that occur in a factor involving the \a i 'th variable, itself excluded
193 VarSet delta( size_t i ) const {
194 return( Delta( i ) / var( i ) );
195 }
197 /// Return all variables that occur in a factor involving some variable in \a vs, \a vs itself excluded
198 VarSet delta( const VarSet& vs ) const {
199 return Delta( vs ) / vs;
200 }
202 /// Return all the indices of variables that occur in a factor involving the \a i 'th variable, itself included
203 SmallSet<size_t> Deltai( size_t i ) const;
205 /// Return all the indices of variables that occur in a factor involving the \a i 'th variable, itself excluded
206 SmallSet<size_t> deltai( size_t i ) const {
207 return( Deltai( i ) / i );
208 }
210 /// Returns \c true if the factor graph is connected
211 bool isConnected() const { return _G.isConnected(); }
213 /// Returns \c true if the factor graph is a tree (i.e., has no cycles and is connected)
214 bool isTree() const { return _G.isTree(); }
216 /// Returns \c true if each factor depends on at most two variables
217 bool isPairwise() const;
219 /// Returns \c true if each variable has only two possible values
220 bool isBinary() const;
222 /// Constructs the corresponding Markov graph
223 /** \note The Markov graph has the variables as nodes and an edge
224 * between two variables if and only if the variables share a factor.
225 */
226 GraphAL MarkovGraph() const;
228 /// Returns whether the \a I 'th factor is maximal
229 /** \note A factor (domain) is \a maximal if and only if it is not a
230 * strict subset of another factor domain.
231 */
232 bool isMaximal( size_t I ) const;
234 /// Returns the index of a maximal factor that contains the \a I 'th factor
235 /** \note A factor (domain) is \a maximal if and only if it is not a
236 * strict subset of another factor domain.
237 */
238 size_t maximalFactor( size_t I ) const;
240 /// Returns the maximal factor domains in this factorgraph
241 /** \note A factor domain is \a maximal if and only if it is not a
242 * strict subset of another factor domain.
243 */
244 std::vector<VarSet> maximalFactorDomains() const;
246 /// Evaluates the log score (i.e., minus the energy) of the joint configuration \a statevec
247 Real logScore( const std::vector<size_t>& statevec ) const;
248 //@}
250 /// \name Backup/restore mechanism for factors
251 //@{
252 /// Set the content of the \a I 'th factor and make a backup of its old content if \a backup == \c true
253 virtual void setFactor( size_t I, const Factor& newFactor, bool backup = false ) {
254 DAI_ASSERT( newFactor.vars() == factor(I).vars() );
255 if( backup )
256 backupFactor( I );
257 _factors[I] = newFactor;
258 }
260 /// Set the contents of all factors as specified by \a facs and make a backup of the old contents if \a backup == \c true
261 virtual void setFactors( const std::map<size_t, Factor>& facs, bool backup = false ) {
262 for( std::map<size_t, Factor>::const_iterator fac = facs.begin(); fac != facs.end(); fac++ ) {
263 if( backup )
264 backupFactor( fac->first );
265 setFactor( fac->first, fac->second );
266 }
267 }
269 /// Makes a backup of the \a I 'th factor
270 /** \throw MULTIPLE_UNDO if a backup already exists
271 */
272 void backupFactor( size_t I );
274 /// Restores the \a I 'th factor from the backup (it should be backed up first)
275 /** \throw OBJECT_NOT_FOUND if a backup does not exist
276 */
277 void restoreFactor( size_t I );
279 /// Backup the factors specified by indices in \a facs
280 /** \throw MULTIPLE_UNDO if a backup already exists
281 */
282 virtual void backupFactors( const std::set<size_t>& facs );
284 /// Restore all factors to the backup copies
285 virtual void restoreFactors();
287 /// Makes a backup of all factors connected to a set of variables
288 /** \throw MULTIPLE_UNDO if a backup already exists
289 */
290 void backupFactors( const VarSet& ns );
292 /// Restores all factors connected to a set of variables from their backups
293 void restoreFactors( const VarSet& ns );
294 //@}
296 /// \name Transformations
297 //@{
298 /// Returns a copy of \c *this, where all factors that are subsumed by some larger factor are merged with the larger factors.
299 FactorGraph maximalFactors() const;
301 /// Returns a copy of \c *this, where the \a i 'th variable has been clamped to value \a x
302 /** \note This version changes the factor graph structure and thus returns a newly constructed FactorGraph
303 * and keeps the current one constant, contrary to clamp()
304 */
305 FactorGraph clamped( size_t i, size_t x ) const;
306 //@}
308 /// \name Operations
309 //@{
310 /// Clamp the \a i 'th variable to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{x_i, x}\f$)
311 /** If \a backup == \c true, make a backup of all factors that are changed
312 */
313 virtual void clamp( size_t i, size_t x, bool backup = false );
315 /// Clamp a variable in a factor graph to have one out of a list of values
316 /** If \a backup == \c true, make a backup of all factors that are changed
317 */
318 void clampVar( size_t i, const std::vector<size_t>& xis, bool backup = false );
320 /// Clamp a factor in a factor graph to have one out of a list of values
321 /** If \a backup == \c true, make a backup of all factors that are changed
322 */
323 void clampFactor( size_t I, const std::vector<size_t>& xIs, bool backup = false );
325 /// Set all factors interacting with the \a i 'th variable to 1
326 /** If \a backup == \c true, make a backup of all factors that are changed
327 */
328 virtual void makeCavity( size_t i, bool backup = false );
330 /// Set all factors indexed by \a facInds to 1
331 /** If \a backup == \c true, make a backup of all factors that are changed
332 */
333 virtual void makeRegionCavity( std::vector<size_t> facInds, bool backup );
334 //@}
336 /// \name Input/Output
337 //@{
338 /// Reads a factor graph from a file
339 /** \see \ref fileformats-factorgraph
340 * \throw CANNOT_READ_FILE if the file cannot be opened
341 * \throw INVALID_FACTORGRAPH_FILE if the file is not valid
342 */
343 virtual void ReadFromFile( const char *filename );
345 /// Writes a factor graph to a file
346 /** \see \ref fileformats-factorgraph
347 * \throw CANNOT_WRITE_FILE if the file cannot be written
348 */
349 virtual void WriteToFile( const char *filename, size_t precision=15 ) const;
351 /// Writes a factor graph to an output stream
352 /** \see \ref fileformats-factorgraph
353 */
354 friend std::ostream& operator<< (std::ostream& os, const FactorGraph& fg );
356 /// Reads a factor graph from an input stream
357 /** \see \ref fileformats-factorgraph
358 * \throw INVALID_FACTORGRAPH_FILE if the input stream is not valid
359 */
360 friend std::istream& operator>> (std::istream& is, FactorGraph& fg );
362 /// Writes a factor graph to a GraphViz .dot file
363 virtual void printDot( std::ostream& os ) const;
364 //@}
366 private:
367 /// Part of constructors (creates edges, neighbors and adjacency matrix)
368 void constructGraph( size_t nrEdges );
369 };
372 template<typename FactorInputIterator, typename VarInputIterator>
373 FactorGraph::FactorGraph(FactorInputIterator facBegin, FactorInputIterator facEnd, VarInputIterator varBegin, VarInputIterator varEnd, size_t nrFacHint, size_t nrVarHint ) : _G(), _backup() {
375 size_t nrEdges = 0;
376 _factors.reserve( nrFacHint );
377 for( FactorInputIterator p2 = facBegin; p2 != facEnd; ++p2 ) {
378 _factors.push_back( *p2 );
379 nrEdges += p2->vars().size();
380 }