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
14 /// \todo Improve documentation
17 #ifndef __defined_libdai_factorgraph_h
18 #define __defined_libdai_factorgraph_h
21 #include <iostream>
22 #include <map>
23 #include <dai/bipgraph.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\f$ that factorizes as a product of factors, each of
37 * which depends on some subset of the variables:
38 * \f[
39 * P(x_0,x_1,\dots,x_N) = \frac{1}{Z} \prod_{I=0}^M f_I(x_I), \qquad
40 * Z = \sum_{x_0}\dots\sum_{x_N} \prod_{I=0}^M 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\}\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.
52 *
53 * \todo Alternative implementation of undo factor changes: the only things that have to be
54 * undone currently are setting a factor to 1 and setting a factor to a Kronecker delta. This
55 * could also be implemented in the TFactor itself, which could maintain its state
56 * (ones/delta/full) and act accordingly.
57 */
58 class FactorGraph {
59 public:
60 /// Stores the neighborhood structure
61 BipartiteGraph G;
63 /// Shorthand for BipartiteGraph::Neighbor
64 typedef BipartiteGraph::Neighbor Neighbor;
66 /// Shorthand for BipartiteGraph::Neighbors
67 typedef BipartiteGraph::Neighbors Neighbors;
69 /// Shorthand for BipartiteGraph::Edge
70 typedef BipartiteGraph::Edge Edge;
72 /// Iterator over factors
73 typedef std::vector<Factor>::iterator iterator;
75 /// Const iterator over factors
76 typedef std::vector<Factor>::const_iterator const_iterator;
79 private:
80 std::vector<Var> _vars;
81 std::vector<Factor> _factors;
82 std::map<size_t,Factor> _backup;
84 public:
85 /// Default constructor
86 FactorGraph() : G(), _vars(), _factors(), _backup() {}
88 /// Constructs a FactorGraph from a vector of factors
89 FactorGraph(const std::vector<Factor> &P);
91 /// Constructs a FactorGraph from given factor and variable iterators
92 /** \tparam FactorInputIterator Iterator with value_type Factor
93 * \tparam VarInputIterator Iterator with value_type Var
94 * \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)
95 */
96 template<typename FactorInputIterator, typename VarInputIterator>
97 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 );
99 /// Destructor
100 virtual ~FactorGraph() {}
102 /// Clone *this (virtual copy constructor)
103 virtual FactorGraph* clone() const { return new FactorGraph(); }
105 /// Returns const reference to i'th variable
106 const Var & var(size_t i) const { return _vars[i]; }
107 /// Returns const reference to all factors
108 const std::vector<Var> & vars() const { return _vars; }
109 /// Returns reference to I'th factor
110 Factor & factor(size_t I) { return _factors[I]; }
111 /// Returns const reference to I'th factor
112 const Factor & factor(size_t I) const { return _factors[I]; }
113 /// Returns const reference to all factors
114 const std::vector<Factor> & factors() const { return _factors; }
115 /// Returns iterator pointing to first factor
116 iterator begin() { return _factors.begin(); }
117 /// Returns const iterator pointing to first factor
118 const_iterator begin() const { return _factors.begin(); }
119 /// Returns iterator pointing beyond last factor
120 iterator end() { return _factors.end(); }
121 /// Returns const iterator pointing beyond last factor
122 const_iterator end() const { return _factors.end(); }
124 /// Returns number of variables
125 size_t nrVars() const { return vars().size(); }
126 /// Returns number of factors
127 size_t nrFactors() const { return factors().size(); }
128 /// Calculates number of edges
129 size_t nrEdges() const { return G.nrEdges(); }
132 const Neighbors & nbV( size_t i ) const { return G.nb1(i); }
133 /// Provides full access to neighbors of variable
134 Neighbors & nbV( size_t i ) { return G.nb1(i); }
136 const Neighbors & nbF( size_t I ) const { return G.nb2(I); }
137 /// Provides full access to neighbors of factor
138 Neighbors & nbF( size_t I ) { return G.nb2(I); }
140 const Neighbor & nbV( size_t i, size_t _I ) const { return G.nb1(i)[_I]; }
141 /// Provides full access to neighbor of variable
142 Neighbor & nbV( size_t i, size_t _I ) { return G.nb1(i)[_I]; }
144 const Neighbor & nbF( size_t I, size_t _i ) const { return G.nb2(I)[_i]; }
145 /// Provides full access to neighbor of factor
146 Neighbor & nbF( size_t I, size_t _i ) { return G.nb2(I)[_i]; }
148 /// Returns the index of a particular variable
149 size_t findVar( const Var &n ) const {
150 size_t i = find( vars().begin(), vars().end(), n ) - vars().begin();
151 if( i == nrVars() )
152 DAI_THROW(OBJECT_NOT_FOUND);
153 return i;
154 }
156 /// Returns a set of indexes corresponding to a set of variables
157 std::set<size_t> findVars( VarSet &ns ) const {
158 std::set<size_t> indexes;
159 for( VarSet::const_iterator n = ns.begin(); n != ns.end(); n++ )
160 indexes.insert( findVar( *n ) );
161 return indexes;
162 }
164 /// Returns index of the first factor that depends on the variables
165 size_t findFactor( const VarSet &ns ) const {
166 size_t I;
167 for( I = 0; I < nrFactors(); I++ )
168 if( factor(I).vars() == ns )
169 break;
170 if( I == nrFactors() )
171 DAI_THROW(OBJECT_NOT_FOUND);
172 return I;
173 }
175 /// Return all variables that occur in a factor involving the i'th variable, itself included
176 VarSet Delta( unsigned i ) const;
178 /// Return all variables that occur in a factor involving some variable in ns, ns itself included
179 VarSet Delta( const VarSet &ns ) const;
181 /// Return all variables that occur in a factor involving the i'th variable, n itself excluded
182 VarSet delta( unsigned i ) const;
184 /// Return all variables that occur in a factor involving some variable in ns, ns itself excluded
185 VarSet delta( const VarSet & ns ) const {
186 return Delta( ns ) / ns;
187 }
189 /// Set the content of the I'th factor and make a backup of its old content if backup == true
190 virtual void setFactor( size_t I, const Factor &newFactor, bool backup = false ) {
191 DAI_ASSERT( newFactor.vars() == factor(I).vars() );
192 if( backup )
193 backupFactor( I );
194 _factors[I] = newFactor;
195 }
197 /// Set the contents of all factors as specified by facs and make a backup of the old contents if backup == true
198 virtual void setFactors( const std::map<size_t, Factor> & facs, bool backup = false ) {
199 for( std::map<size_t, Factor>::const_iterator fac = facs.begin(); fac != facs.end(); fac++ ) {
200 if( backup )
201 backupFactor( fac->first );
202 setFactor( fac->first, fac->second );
203 }
204 }
206 /// Clamp variable with index i to value x (i.e. multiply with a Kronecker delta \f$\delta_{x_i, x}\f$)
207 /** If backup == true, make a backup of all factors that are changed
208 */
209 virtual void clamp( size_t i, size_t x, bool backup = false );
211 // OBSOLETE
212 /// Only for backwards compatibility (to be removed soon)
213 virtual void clamp( const Var &v, size_t x, bool backup = false ) {
214 std::cerr << "Warning: this FactorGraph::clamp(const Var&,...) interface is obsolete!" << std::endl;
215 clamp( findVar(v), x, backup );
216 }
218 /// Clamp a variable in a factor graph to have one out of a list of values
219 /** If backup == true, make a backup of all factors that are changed
220 */
221 void clampVar( size_t i, const std::vector<size_t> &xis, bool backup = false );
223 /// Clamp a factor in a factor graph to have one out of a list of values
224 /** If backup == true, make a backup of all factors that are changed
225 */
226 void clampFactor( size_t I, const std::vector<size_t> &xIs, bool backup = false );
228 /// Set all factors interacting with the i'th variable 1
229 virtual void makeCavity( unsigned i, bool backup = false );
231 /// Backup the factors specified by indices in facs
232 virtual void backupFactors( const std::set<size_t> & facs );
234 /// Restore all factors to the backup copies
235 virtual void restoreFactors();
237 /// Returns true if the FactorGraph is connected
238 bool isConnected() const { return G.isConnected(); }
240 /// Returns true if the FactorGraph is a tree
241 bool isTree() const { return G.isTree(); }
243 /// Returns true if each factor depends on at most two variables
244 bool isPairwise() const;
246 /// Returns true if each variable has only two possible values
247 bool isBinary() const;
249 /// Reads a FactorGraph from a file
250 void ReadFromFile( const char *filename );
252 /// Writes a FactorGraph to a file
253 void WriteToFile( const char *filename, size_t precision=15 ) const;
255 /// Writes a FactorGraph to a GraphViz .dot file
256 void printDot( std::ostream& os ) const;
258 /// Returns the cliques in this FactorGraph
259 std::vector<VarSet> Cliques() const;
261 /// Clamp variable v to value x (i.e. multiply with a Kronecker delta \f$\delta_{x_v,x}\f$);
262 /** This version changes the factor graph structure and thus returns a newly constructed FactorGraph
263 * and keeps the current one constant, contrary to clamp()
264 */
265 FactorGraph clamped( const Var &v, size_t x ) const;
267 /// Returns a copy of *this, where all factors that are subsumed by some larger factor are merged with the larger factors.
268 FactorGraph maximalFactors() const;
270 /// Makes a backup of the I'th Factor
271 void restoreFactor( size_t I );
273 /// Restores the I'th Factor from the backup (it should be backed up first)
274 void backupFactor( size_t I );
276 /// Makes a backup of all factors connected to a set of variables
277 void backupFactors( const VarSet &ns );
278 /// Restores all factors connected to a set of variables from their backups
279 void restoreFactors( const VarSet &ns );
281 /// Writes a FactorGraph to an output stream
282 friend std::ostream& operator<< (std::ostream &os, const FactorGraph &fg );
283 /// Reads a FactorGraph from an input stream
284 friend std::istream& operator>> (std::istream &is, FactorGraph &fg );
286 // OBSOLETE
287 /// @name Backwards compatibility layer (to be removed soon)
288 //@{
289 size_t VV2E(size_t n1, size_t n2) const { return G.VV2E(n1,n2); }
290 const Edge& edge(size_t e) const { return G.edge(e); }
291 void indexEdges() { G.indexEdges(); }
292 size_t nr_edges() const { return G.nr_edges(); }
293 const std::vector<Edge>& edges() const { return G.edges(); }
294 //}@
296 private:
297 /// Part of constructors (creates edges, neighbors and adjacency matrix)
298 void constructGraph( size_t nrEdges );
299 };
302 template<typename FactorInputIterator, typename VarInputIterator>
303 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() {
304 // add factors
305 size_t nrEdges = 0;
306 _factors.reserve( nr_fact_hint );
307 for( FactorInputIterator p2 = fact_begin; p2 != fact_end; ++p2 ) {
308 _factors.push_back( *p2 );
309 nrEdges += p2->vars().size();
310 }
312 // add variables
313 _vars.reserve( nr_var_hint );
314 for( VarInputIterator p1 = var_begin; p1 != var_end; ++p1 )
315 _vars.push_back( *p1 );
317 // create graph structure
318 constructGraph( nrEdges );
319 }
322 } // end of namespace dai
325 #endif