1 /* Copyright (C) 2006-2008 Joris Mooij [joris dot mooij at tuebingen dot mpg dot de]
2 Radboud University Nijmegen, The Netherlands /
3 Max Planck Institute for Biological Cybernetics, Germany
5 This file is part of libDAI.
7 libDAI is free software; you can redistribute it and/or modify
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 libDAI is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with libDAI; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 */
23 /// \file
24 /// \brief Defines the FactorGraph class
25 /// \todo Improve documentation
28 #ifndef __defined_libdai_factorgraph_h
29 #define __defined_libdai_factorgraph_h
32 #include <iostream>
33 #include <map>
34 #include <dai/bipgraph.h>
35 #include <dai/factor.h>
38 namespace dai {
41 /// Represents a factor graph.
42 /** Both Bayesian Networks and Markov random fields can be represented in a
43 * unifying representation, called <em>factor graph</em> [\ref KFL01],
44 * implemented in libDAI by the FactorGraph class.
45 *
46 * Consider a probability distribution over \f$N\f$ discrete random variables
47 * \f$x_0,x_1,\dots,x_N\f$ that factorizes as a product of factors, each of
48 * which depends on some subset of the variables:
49 * \f[
50 * P(x_0,x_1,\dots,x_N) = \frac{1}{Z} \prod_{I=0}^M f_I(x_I), \qquad
51 * Z = \sum_{x_0}\dots\sum_{x_N} \prod_{I=0}^M f_I(X_I).
52 * \f]
53 * Each factor \f$f_I\f$ is a function from an associated subset
54 * of variables \f$X_I \subset \{x_0,x_1,\dots,x_N\}\f$ to the nonnegative
55 * real numbers.
56 *
57 * For a Bayesian network, each factor corresponds to a (conditional)
58 * probability table, whereas for a Markov random field, each factor
59 * corresponds to a maximal clique of the undirected graph.
60 *
61 * Factor graphs explicitly express the factorization structure of the
62 * corresponding probability distribution.
63 *
64 * \todo Alternative implementation of undo factor changes: the only things that have to be
65 * undone currently are setting a factor to 1 and setting a factor to a Kronecker delta. This
66 * could also be implemented in the TFactor itself, which could maintain its state
67 * (ones/delta/full) and act accordingly.
68 */
69 class FactorGraph {
70 public:
71 /// Stores the neighborhood structure
72 BipartiteGraph G;
74 /// Shorthand for BipartiteGraph::Neighbor
75 typedef BipartiteGraph::Neighbor Neighbor;
77 /// Shorthand for BipartiteGraph::Neighbors
78 typedef BipartiteGraph::Neighbors Neighbors;
80 /// Shorthand for BipartiteGraph::Edge
81 typedef BipartiteGraph::Edge Edge;
83 /// Iterator over factors
84 typedef std::vector<Factor>::iterator iterator;
86 /// Const iterator over factors
87 typedef std::vector<Factor>::const_iterator const_iterator;
90 private:
91 std::vector<Var> _vars;
92 std::vector<Factor> _factors;
93 std::map<size_t,Factor> _backup;
95 public:
96 /// Default constructor
97 FactorGraph() : G(), _vars(), _factors(), _backup() {}
99 /// Constructs a FactorGraph from a vector of factors
100 FactorGraph(const std::vector<Factor> &P);
102 /// Constructs a FactorGraph from given factor and variable iterators
103 /** \tparam FactorInputIterator Iterator with value_type Factor
104 * \tparam VarInputIterator Iterator with value_type Var
105 * \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)
106 */
107 template<typename FactorInputIterator, typename VarInputIterator>
108 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 );
110 /// Destructor
111 virtual ~FactorGraph() {}
113 /// Clone *this (virtual copy constructor)
114 virtual FactorGraph* clone() const { return new FactorGraph(); }
116 /// Returns const reference to i'th variable
117 const Var & var(size_t i) const { return _vars[i]; }
118 /// Returns const reference to all factors
119 const std::vector<Var> & vars() const { return _vars; }
120 /// Returns reference to I'th factor
121 Factor & factor(size_t I) { return _factors[I]; }
122 /// Returns const reference to I'th factor
123 const Factor & factor(size_t I) const { return _factors[I]; }
124 /// Returns const reference to all factors
125 const std::vector<Factor> & factors() const { return _factors; }
126 /// Returns iterator pointing to first factor
127 iterator begin() { return _factors.begin(); }
128 /// Returns const iterator pointing to first factor
129 const_iterator begin() const { return _factors.begin(); }
130 /// Returns iterator pointing beyond last factor
131 iterator end() { return _factors.end(); }
132 /// Returns const iterator pointing beyond last factor
133 const_iterator end() const { return _factors.end(); }
135 /// Returns number of variables
136 size_t nrVars() const { return vars().size(); }
137 /// Returns number of factors
138 size_t nrFactors() const { return factors().size(); }
139 /// Calculates number of edges
140 size_t nrEdges() const { return G.nrEdges(); }
143 const Neighbors & nbV( size_t i ) const { return G.nb1(i); }
145 Neighbors & nbV( size_t i ) { return G.nb1(i); }
147 const Neighbors & nbF( size_t I ) const { return G.nb2(I); }
149 Neighbors & nbF( size_t I ) { return G.nb2(I); }
151 const Neighbor & nbV( size_t i, size_t _I ) const { return G.nb1(i)[_I]; }
153 Neighbor & nbV( size_t i, size_t _I ) { return G.nb1(i)[_I]; }
155 const Neighbor & nbF( size_t I, size_t _i ) const { return G.nb2(I)[_i]; }
157 Neighbor & nbF( size_t I, size_t _i ) { return G.nb2(I)[_i]; }
159 /// Returns the index of a particular variable
160 size_t findVar( const Var &n ) const {
161 size_t i = find( vars().begin(), vars().end(), n ) - vars().begin();
162 if( i == nrVars() )
163 DAI_THROW(OBJECT_NOT_FOUND);
164 return i;
165 }
167 /// Returns a set of indexes corresponding to a set of variables
168 std::set<size_t> findVars( VarSet &ns ) const {
169 std::set<size_t> indexes;
170 for( VarSet::const_iterator n = ns.begin(); n != ns.end(); n++ )
171 indexes.insert( findVar( *n ) );
172 return indexes;
173 }
175 /// Returns index of the first factor that depends on the variables
176 size_t findFactor( const VarSet &ns ) const {
177 size_t I;
178 for( I = 0; I < nrFactors(); I++ )
179 if( factor(I).vars() == ns )
180 break;
181 if( I == nrFactors() )
182 DAI_THROW(OBJECT_NOT_FOUND);
183 return I;
184 }
186 /// Return all variables that occur in a factor involving the i'th variable, itself included
187 VarSet Delta( unsigned i ) const;
189 /// Return all variables that occur in a factor involving some variable in ns, ns itself included
190 VarSet Delta( const VarSet &ns ) const;
192 /// Return all variables that occur in a factor involving the i'th variable, n itself excluded
193 VarSet delta( unsigned i ) const;
195 /// Return all variables that occur in a factor involving some variable in ns, ns itself excluded
196 VarSet delta( const VarSet & ns ) const {
197 return Delta( ns ) / ns;
198 }
200 /// Set the content of the I'th factor and make a backup of its old content if backup == true
201 virtual void setFactor( size_t I, const Factor &newFactor, bool backup = false ) {
202 assert( newFactor.vars() == factor(I).vars() );
203 if( backup )
204 backupFactor( I );
205 _factors[I] = newFactor;
206 }
208 /// Set the contents of all factors as specified by facs and make a backup of the old contents if backup == true
209 virtual void setFactors( const std::map<size_t, Factor> & facs, bool backup = false ) {
210 for( std::map<size_t, Factor>::const_iterator fac = facs.begin(); fac != facs.end(); fac++ ) {
211 if( backup )
212 backupFactor( fac->first );
213 setFactor( fac->first, fac->second );
214 }
215 }
217 /// Clamp variable with index i to value x (i.e. multiply with a Kronecker delta \f$\delta_{x_i, x}\f$)
218 /** If backup == true, make a backup of all factors that are changed
219 */
220 virtual void clamp( size_t i, size_t x, bool backup = false );
222 // OBSOLETE
223 /// Only for backwards compatibility (to be removed soon)
224 virtual void clamp( const Var &v, size_t x, bool backup = false ) {
225 std::cerr << "Warning: this FactorGraph::clamp(const Var&,...) interface is obsolete!" << std::endl;
226 clamp( findVar(v), x, backup );
227 }
229 /// Clamp a variable in a factor graph to have one out of a list of values
230 /** If backup == true, make a backup of all factors that are changed
231 */
232 void clampVar( size_t i, const std::vector<size_t> &xis, bool backup = false );
234 /// Clamp a factor in a factor graph to have one out of a list of values
235 /** If backup == true, make a backup of all factors that are changed
236 */
237 void clampFactor( size_t I, const std::vector<size_t> &xIs, bool backup = false );
239 /// Set all factors interacting with the i'th variable 1
240 virtual void makeCavity( unsigned i, bool backup = false );
242 /// Backup the factors specified by indices in facs
243 virtual void backupFactors( const std::set<size_t> & facs );
245 /// Restore all factors to the backup copies
246 virtual void restoreFactors();
248 /// Returns true if the FactorGraph is connected
249 bool isConnected() const { return G.isConnected(); }
251 /// Returns true if the FactorGraph is a tree
252 bool isTree() const { return G.isTree(); }
254 /// Returns true if each factor depends on at most two variables
255 bool isPairwise() const;
257 /// Returns true if each variable has only two possible values
258 bool isBinary() const;
260 /// Reads a FactorGraph from a file
261 void ReadFromFile( const char *filename );
263 /// Writes a FactorGraph to a file
264 void WriteToFile( const char *filename, size_t precision=15 ) const;
266 /// Writes a FactorGraph to a GraphViz .dot file
267 void printDot( std::ostream& os ) const;
269 /// Returns the cliques in this FactorGraph
270 std::vector<VarSet> Cliques() const;
272 /// Clamp variable v to value x (i.e. multiply with a Kronecker delta \f$\delta_{x_v,x}\f$);
273 /** This version changes the factor graph structure and thus returns a newly constructed FactorGraph
274 * and keeps the current one constant, contrary to clamp()
275 */
276 FactorGraph clamped( const Var &v, size_t x ) const;
278 /// Returns a copy of *this, where all factors that are subsumed by some larger factor are merged with the larger factors.
279 FactorGraph maximalFactors() const;
281 /// Makes a backup of the I'th Factor
282 void restoreFactor( size_t I );
284 /// Restores the I'th Factor from the backup (it should be backed up first)
285 void backupFactor( size_t I );
287 /// Makes a backup of all factors connected to a set of variables
288 void backupFactors( const VarSet &ns );
289 /// Restores all factors connected to a set of variables from their backups
290 void restoreFactors( const VarSet &ns );
292 // Friends
293 friend std::ostream& operator << (std::ostream& os, const FactorGraph& fg);
294 friend std::istream& operator >> (std::istream& is, FactorGraph& fg);
296 // OBSOLETE
297 /// @name Backwards compatibility layer (to be removed soon)
298 //@{
299 size_t VV2E(size_t n1, size_t n2) const { return G.VV2E(n1,n2); }
300 const Edge& edge(size_t e) const { return G.edge(e); }
301 void indexEdges() { G.indexEdges(); }
302 size_t nr_edges() const { return G.nr_edges(); }
303 const std::vector<Edge>& edges() const { return G.edges(); }
304 //}@
306 private:
307 /// Part of constructors (creates edges, neighbors and adjacency matrix)
308 void constructGraph( size_t nrEdges );
309 };
312 template<typename FactorInputIterator, typename VarInputIterator>
313 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() {
315 size_t nrEdges = 0;
316 _factors.reserve( nr_fact_hint );
317 for( FactorInputIterator p2 = fact_begin; p2 != fact_end; ++p2 ) {
318 _factors.push_back( *p2 );
319 nrEdges += p2->vars().size();
320 }