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-2009 Joris Mooij [joris dot mooij at libdai dot org]
8 * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
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/factor.h>
26 namespace dai {
29 /// Represents a factor graph.
30 /** Both Bayesian Networks and Markov random fields can be represented in a
31 * unifying representation, called <em>factor graph</em> [\ref KFL01],
32 * implemented in libDAI by the FactorGraph class.
33 *
34 * Consider a probability distribution over \f$N\f$ discrete random variables
35 * \f$x_0,x_1,\dots,x_{N-1}\f$ that factorizes as a product of \f$M\f$ factors, each of
36 * which depends on some subset of the variables:
37 * \f[
38 * P(x_0,x_1,\dots,x_{N-1}) = \frac{1}{Z} \prod_{I=0}^{M-1} f_I(x_I), \qquad
39 * Z = \sum_{x_0}\dots\sum_{x_{N-1}} \prod_{I=0}^{M-1} f_I(X_I).
40 * \f]
41 * Each factor \f$f_I\f$ is a function from an associated subset
42 * of variables \f$X_I \subset \{x_0,x_1,\dots,x_{N-1}\}\f$ to the nonnegative
43 * real numbers.
44 *
45 * For a Bayesian network, each factor corresponds to a (conditional)
46 * probability table, whereas for a Markov random field, each factor
47 * corresponds to a maximal clique of the undirected graph.
48 *
49 * Factor graphs explicitly express the factorization structure of the
50 * corresponding probability distribution. A factor graph is a bipartite graph,
51 * containing variable nodes and factor nodes, and an edge between a variable
52 * node and a factor node if the corresponding factor depends on that variable.
53 * In libDAI, this structure is represented by a BipartiteGraph.
54 *
55 * So basically, a FactorGraph consists of a BipartiteGraph, a vector of Var 's
56 * and a vector of TFactor 's.
57 *
58 * \todo Alternative implementation of undo factor changes: the only things that have to be
59 * undone currently are setting a factor to 1 and setting a factor to a Kronecker delta. This
60 * could also be implemented in the TFactor itself, which could maintain its state
61 * (ones/delta/full) and act accordingly.
62 */
63 class FactorGraph {
64 public:
65 /// Stores the neighborhood structure
66 BipartiteGraph G;
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 typedef std::vector<Factor>::iterator iterator;
80 /// Constant iterator over factors
81 typedef std::vector<Factor>::const_iterator const_iterator;
84 private:
85 /// Stores the variables
86 std::vector<Var> _vars;
87 /// Stores the factors
88 std::vector<Factor> _factors;
89 /// Stores backups of some factors
90 std::map<size_t,Factor> _backup;
92 public:
93 /// \name Constructors and destructors
94 //@{
95 /// Default constructor
96 FactorGraph() : G(), _vars(), _factors(), _backup() {}
98 /// Constructs a factor graph from a vector of factors
99 FactorGraph( const std::vector<Factor> &P );
101 /// Constructs a factor graph from given factor and variable iterators
102 /** \tparam FactorInputIterator Iterates over instances of type dai::Factor
103 * \tparam VarInputIterator Iterates over instances of type Var
104 * \pre Assumes that the set of variables in [\a var_begin, \a var_end) is the union of the variables in the factors in [\a fact_begin, \a fact_end)
105 */
106 template<typename FactorInputIterator, typename VarInputIterator>
107 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 /// Destructor
110 virtual ~FactorGraph() {}
112 /// Virtual copy constructor
113 virtual FactorGraph* clone() const { return new FactorGraph(); }
114 //@}
116 /// \name Accessors and mutators
117 //@{
118 /// Returns constant reference the \a i 'th variable
119 const Var & var(size_t i) const { return _vars[i]; }
120 /// Returns constant reference to all variables
121 const std::vector<Var> & vars() const { return _vars; }
123 /// Returns reference to \a I 'th factor
124 Factor & factor(size_t I) { return _factors[I]; }
125 /// Returns constant reference to \a I 'th factor
126 const Factor & factor(size_t I) const { return _factors[I]; }
127 /// Returns constant reference to all factors
128 const std::vector<Factor> & factors() const { return _factors; }
130 /// Returns constant reference to neighbors of the \a i 'th variable
131 const Neighbors & nbV( size_t i ) const { return G.nb1(i); }
132 /// Returns constant reference to neighbors of the \a I 'th factor
133 const Neighbors & nbF( size_t I ) const { return G.nb2(I); }
134 /// Returns constant reference to the \a _I 'th neighbor of the \a i 'th variable
135 const Neighbor & nbV( size_t i, size_t _I ) const { return G.nb1(i)[_I]; }
136 /// Returns constant reference to the \a _i 'th neighbor of the \a I 'th factor
137 const Neighbor & nbF( size_t I, size_t _i ) const { return G.nb2(I)[_i]; }
138 //@}
140 /// \name Iterator interface
141 //@{
142 /// Returns iterator pointing to first factor
143 iterator begin() { return _factors.begin(); }
144 /// Returns constant iterator pointing to first factor
145 const_iterator begin() const { return _factors.begin(); }
146 /// Returns iterator pointing beyond last factor
147 iterator end() { return _factors.end(); }
148 /// Returns constant iterator pointing beyond last factor
149 const_iterator end() const { return _factors.end(); }
150 //@}
152 /// \name Queries
153 //@{
154 /// Returns number of variables
155 size_t nrVars() const { return vars().size(); }
156 /// Returns number of factors
157 size_t nrFactors() const { return factors().size(); }
158 /// Calculates number of edges
159 /** \note Time complexity: O(nrVars())
160 */
161 size_t nrEdges() const { return G.nrEdges(); }
163 /// Returns the index of a particular variable
164 /** \note Time complexity: O(nrVars())
165 * \throw OBJECT_NOT_FOUND if the variable is not part of this factor graph
166 */
167 size_t findVar( const Var &n ) const {
168 size_t i = find( vars().begin(), vars().end(), n ) - vars().begin();
169 if( i == nrVars() )
170 DAI_THROW(OBJECT_NOT_FOUND);
171 return i;
172 }
174 /// Returns a set of indexes corresponding to a set of variables
175 /** \note Time complexity: O( nrVars() * ns.size() )
176 * \throw OBJECT_NOT_FOUND if one of the variables is not part of this factor graph
177 */
178 std::set<size_t> findVars( VarSet &ns ) const {
179 std::set<size_t> indexes;
180 for( VarSet::const_iterator n = ns.begin(); n != ns.end(); n++ )
181 indexes.insert( findVar( *n ) );
182 return indexes;
183 }
185 /// Returns index of the first factor that depends on the variables
186 /** \note Time complexity: O(nrFactors())
187 * \throw OBJECT_NOT_FOUND if no factor in this factor graph depends on those variables
188 */
189 size_t findFactor( const VarSet &ns ) const {
190 size_t I;
191 for( I = 0; I < nrFactors(); I++ )
192 if( factor(I).vars() == ns )
193 break;
194 if( I == nrFactors() )
195 DAI_THROW(OBJECT_NOT_FOUND);
196 return I;
197 }
199 /// Return all variables that occur in a factor involving the \a i 'th variable, itself included
200 VarSet Delta( size_t i ) const;
202 /// Return all variables that occur in a factor involving some variable in \a vs, \a vs itself included
203 VarSet Delta( const VarSet &vs ) const;
205 /// Return all variables that occur in a factor involving the \a i 'th variable, itself excluded
206 VarSet delta( size_t i ) const;
208 /// Return all variables that occur in a factor involving some variable in \a vs, \a vs itself excluded
209 VarSet delta( const VarSet &vs ) const {
210 return Delta( vs ) / vs;
211 }
213 /// Returns \c true if the factor graph is connected
214 bool isConnected() const { return G.isConnected(); }
216 /// Returns \c true if the factor graph is a tree (i.e., has no cycles and is connected)
217 bool isTree() const { return G.isTree(); }
219 /// Returns \c true if each factor depends on at most two variables
220 bool isPairwise() const;
222 /// Returns \c true if each variable has only two possible values
223 bool isBinary() const;
225 /// Returns the cliques (fully connected subgraphs of the corresponding Markov graph) in this factor graph
226 std::vector<VarSet> Cliques() const;
227 //@}
229 /// \name Backup/restore mechanism for factors
230 //@{
231 /// Set the content of the \a I 'th factor and make a backup of its old content if \a backup == \c true
232 virtual void setFactor( size_t I, const Factor &newFactor, bool backup = false ) {
233 DAI_ASSERT( newFactor.vars() == factor(I).vars() );
234 if( backup )
235 backupFactor( I );
236 _factors[I] = newFactor;
237 }
239 /// Set the contents of all factors as specified by \a facs and make a backup of the old contents if \a backup == \c true
240 virtual void setFactors( const std::map<size_t, Factor> & facs, bool backup = false ) {
241 for( std::map<size_t, Factor>::const_iterator fac = facs.begin(); fac != facs.end(); fac++ ) {
242 if( backup )
243 backupFactor( fac->first );
244 setFactor( fac->first, fac->second );
245 }
246 }
248 /// Makes a backup of the \a I 'th factor
249 /** \throw MULTIPLE_UNDO if a backup already exists
250 */
251 void backupFactor( size_t I );
253 /// Restores the \a I 'th factor from the backup (it should be backed up first)
254 void restoreFactor( size_t I );
256 /// Backup the factors specified by indices in \a facs
257 /** \throw MULTIPLE_UNDO if a backup already exists
258 */
259 virtual void backupFactors( const std::set<size_t> & facs );
261 /// Restore all factors to the backup copies
262 virtual void restoreFactors();
264 /// Makes a backup of all factors connected to a set of variables
265 /** \throw MULTIPLE_UNDO if a backup already exists
266 */
267 void backupFactors( const VarSet &ns );
269 /// Restores all factors connected to a set of variables from their backups
270 void restoreFactors( const VarSet &ns );
271 //@}
273 /// \name Transformations
274 //@{
275 /// Returns a copy of \c *this, where all factors that are subsumed by some larger factor are merged with the larger factors.
276 FactorGraph maximalFactors() const;
278 /// Clamp the \a i 'th variable to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{x_i,x}\f$);
279 /** \note This version changes the factor graph structure and thus returns a newly constructed FactorGraph
280 * and keeps the current one constant, contrary to clamp()
281 */
282 FactorGraph clamped( size_t i, size_t x ) const;
284 // OBSOLETE
285 /// Clamp variable \a v to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{v,x}\f$);
286 /** \deprecated Please use dai::FactorGraph::clamped(size_t,size_t) instead
287 */
288 FactorGraph clamped( const Var &v, size_t x ) const {
289 std::cerr << "Warning: this FactorGraph::clamped(const Var&,...) interface is obsolete!" << std::endl;
290 return clamped( findVar(v), x );
291 }
292 //@}
294 /// \name Operations
295 //@{
296 /// Clamp the \a i 'th variable to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{x_i, x}\f$)
297 /** If \a backup == \c true, make a backup of all factors that are changed
298 */
299 virtual void clamp( size_t i, size_t x, bool backup = false );
301 // OBSOLETE
302 /// Clamp variable \a v to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{v, x}\f$)
303 /** \deprecated Please use dai::FactorGraph::clamp(size_t,size_t,bool) instead
304 */
305 virtual void clamp( const Var &v, size_t x, bool backup = false ) {
306 std::cerr << "Warning: this FactorGraph::clamp(const Var&,...) interface is obsolete!" << std::endl;
307 clamp( findVar(v), x, backup );
308 }
310 /// Clamp a variable in a factor graph to have one out of a list of values
311 /** If \a backup == \c true, make a backup of all factors that are changed
312 */
313 void clampVar( size_t i, const std::vector<size_t> &xis, bool backup = false );
315 /// Clamp a factor 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 clampFactor( size_t I, const std::vector<size_t> &xIs, bool backup = false );
320 /// Set all factors interacting with the \a i 'th variable to 1
321 /** If \a backup == \c true, make a backup of all factors that are changed
322 */
323 virtual void makeCavity( size_t i, bool backup = false );
324 //@}
326 /// \name Input/Output
327 //@{
328 /// Reads a factor graph from a file
329 /** \see \ref fileformats-factorgraph
330 * \throw CANNOT_READ_FILE if the file cannot be opened
331 * \throw INVALID_FACTORGRAPH_FILE if the file is not valid
332 */
333 void ReadFromFile( const char *filename );
335 /// Writes a factor graph to a file
336 /** \see \ref fileformats-factorgraph
337 * \throw CANNOT_WRITE_FILE if the file cannot be written
338 */
339 void WriteToFile( const char *filename, size_t precision=15 ) const;
341 /// Writes a factor graph to an output stream
342 /** \see \ref fileformats-factorgraph
343 */
344 friend std::ostream& operator<< (std::ostream &os, const FactorGraph &fg );
346 /// Reads a factor graph from an input stream
347 /** \see \ref fileformats-factorgraph
348 * \throw INVALID_FACTORGRAPH_FILE if the input stream is not valid
349 */
350 friend std::istream& operator>> (std::istream &is, FactorGraph &fg );
352 /// Writes a factor graph to a GraphViz .dot file
353 void printDot( std::ostream& os ) const;
354 //@}
356 // OBSOLETE
357 /// \name Backwards compatibility layer (to be removed soon)
358 //@{
359 /// Prepare backwards compatibility layer for indexed edges
360 /** \deprecated Please use FactorGraph::Neighbor interface instead
361 */
362 void indexEdges() { G.indexEdges(); }
363 /// Returns edge with index \a e
364 /** \deprecated Please use FactorGraph::Neighbor interface instead
365 */
366 const Edge& edge(size_t e) const { return G.edge(e); }
367 /// Returns all edges
368 /** \deprecated Please use FactorGraph::Neighbor interface instead
369 */
370 const std::vector<Edge>& edges() const { return G.edges(); }
371 /// Converts a pair of node indices to an edge index
372 /** \deprecated Please use FactorGraph::Neighbor interface instead
373 */
374 size_t VV2E(size_t n1, size_t n2) const { return G.VV2E(n1,n2); }
375 /// Returns number of edges
376 /** \deprecated Please use FactorGraph::Neighbor interface instead
377 */
378 size_t nr_edges() const { return G.nr_edges(); }
379 //@}
381 private:
382 /// Part of constructors (creates edges, neighbors and adjacency matrix)
383 void constructGraph( size_t nrEdges );
384 };
387 template<typename FactorInputIterator, typename VarInputIterator>
388 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() {
389 // add factors
390 size_t nrEdges = 0;
391 _factors.reserve( nr_fact_hint );
392 for( FactorInputIterator p2 = fact_begin; p2 != fact_end; ++p2 ) {
393 _factors.push_back( *p2 );
394 nrEdges += p2->vars().size();
395 }
397 // add variables
398 _vars.reserve( nr_var_hint );
399 for( VarInputIterator p1 = var_begin; p1 != var_end; ++p1 )
400 _vars.push_back( *p1 );
402 // create graph structure
403 constructGraph( nrEdges );
404 }
407 } // end of namespace dai
410 #endif