1 /* This file is part of libDAI - http://www.libdai.org/
3 * libDAI is licensed under the terms of the GNU General Public License version
4 * 2, or (at your option) any later version. libDAI is distributed without any
5 * warranty. See the file COPYING for more details.
7 * Copyright (C) 2006-2009 Joris Mooij [joris dot mooij at libdai dot org]
8 * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
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
22 #include <dai/bipgraph.h>
23 #include <dai/factor.h>
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.
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:
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).
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
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.
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.
55 * So basically, a FactorGraph consists of a BipartiteGraph, a vector of Var 's
56 * and a vector of TFactor 's.
58 * \idea 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. Update: it seems that the proposed functionality
62 * would not be enough for CBP, for which it would make more sense to add more levels of
67 /// Stores the neighborhood structure
70 /// Shorthand for BipartiteGraph::Neighbor
71 typedef BipartiteGraph::Neighbor Neighbor
;
73 /// Shorthand for BipartiteGraph::Neighbors
74 typedef BipartiteGraph::Neighbors Neighbors
;
76 /// Shorthand for BipartiteGraph::Edge
77 typedef BipartiteGraph::Edge Edge
;
79 /// Iterator over factors
80 typedef std::vector
<Factor
>::iterator iterator
;
82 /// Constant iterator over factors
83 typedef std::vector
<Factor
>::const_iterator const_iterator
;
87 /// Stores the variables
88 std::vector
<Var
> _vars
;
89 /// Stores the factors
90 std::vector
<Factor
> _factors
;
91 /// Stores backups of some factors
92 std::map
<size_t,Factor
> _backup
;
95 /// \name Constructors and destructors
97 /// Default constructor
98 FactorGraph() : G(), _vars(), _factors(), _backup() {}
100 /// Constructs a factor graph from a vector of factors
101 FactorGraph( const std::vector
<Factor
> &P
);
103 /// Constructs a factor graph from given factor and variable iterators
104 /** \tparam FactorInputIterator Iterates over instances of type dai::Factor
105 * \tparam VarInputIterator Iterates over instances of type Var
106 * \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)
108 template<typename FactorInputIterator
, typename VarInputIterator
>
109 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 );
112 virtual ~FactorGraph() {}
114 /// Virtual copy constructor
115 virtual FactorGraph
* clone() const { return new FactorGraph(); }
118 /// \name Accessors and mutators
120 /// Returns constant reference the \a i 'th variable
121 const Var
& var(size_t i
) const { return _vars
[i
]; }
122 /// Returns constant reference to all variables
123 const std::vector
<Var
> & vars() const { return _vars
; }
125 /// Returns reference to \a I 'th factor
126 Factor
& factor(size_t I
) { return _factors
[I
]; }
127 /// Returns constant reference to \a I 'th factor
128 const Factor
& factor(size_t I
) const { return _factors
[I
]; }
129 /// Returns constant reference to all factors
130 const std::vector
<Factor
> & factors() const { return _factors
; }
132 /// Returns constant reference to neighbors of the \a i 'th variable
133 const Neighbors
& nbV( size_t i
) const { return G
.nb1(i
); }
134 /// Returns constant reference to neighbors of the \a I 'th factor
135 const Neighbors
& nbF( size_t I
) const { return G
.nb2(I
); }
136 /// Returns constant reference to the \a _I 'th neighbor of the \a i 'th variable
137 const Neighbor
& nbV( size_t i
, size_t _I
) const { return G
.nb1(i
)[_I
]; }
138 /// Returns constant reference to the \a _i 'th neighbor of the \a I 'th factor
139 const Neighbor
& nbF( size_t I
, size_t _i
) const { return G
.nb2(I
)[_i
]; }
142 /// \name Iterator interface
144 /// Returns iterator pointing to first factor
145 iterator
begin() { return _factors
.begin(); }
146 /// Returns constant iterator pointing to first factor
147 const_iterator
begin() const { return _factors
.begin(); }
148 /// Returns iterator pointing beyond last factor
149 iterator
end() { return _factors
.end(); }
150 /// Returns constant iterator pointing beyond last factor
151 const_iterator
end() const { return _factors
.end(); }
156 /// Returns number of variables
157 size_t nrVars() const { return vars().size(); }
158 /// Returns number of factors
159 size_t nrFactors() const { return factors().size(); }
160 /// Calculates number of edges
161 /** \note Time complexity: O(nrVars())
163 size_t nrEdges() const { return G
.nrEdges(); }
165 /// Returns the index of a particular variable
166 /** \note Time complexity: O(nrVars())
167 * \throw OBJECT_NOT_FOUND if the variable is not part of this factor graph
169 size_t findVar( const Var
&n
) const {
170 size_t i
= find( vars().begin(), vars().end(), n
) - vars().begin();
172 DAI_THROW(OBJECT_NOT_FOUND
);
176 /// Returns a set of indexes corresponding to a set of variables
177 /** \note Time complexity: O( nrVars() * ns.size() )
178 * \throw OBJECT_NOT_FOUND if one of the variables is not part of this factor graph
180 std::set
<size_t> findVars( VarSet
&ns
) const {
181 std::set
<size_t> indexes
;
182 for( VarSet::const_iterator n
= ns
.begin(); n
!= ns
.end(); n
++ )
183 indexes
.insert( findVar( *n
) );
187 /// Returns index of the first factor that depends on the variables
188 /** \note Time complexity: O(nrFactors())
189 * \throw OBJECT_NOT_FOUND if no factor in this factor graph depends on those variables
191 size_t findFactor( const VarSet
&ns
) const {
193 for( I
= 0; I
< nrFactors(); I
++ )
194 if( factor(I
).vars() == ns
)
196 if( I
== nrFactors() )
197 DAI_THROW(OBJECT_NOT_FOUND
);
201 /// Return all variables that occur in a factor involving the \a i 'th variable, itself included
202 VarSet
Delta( size_t i
) const;
204 /// Return all variables that occur in a factor involving some variable in \a vs, \a vs itself included
205 VarSet
Delta( const VarSet
&vs
) const;
207 /// Return all variables that occur in a factor involving the \a i 'th variable, itself excluded
208 VarSet
delta( size_t i
) const;
210 /// Return all variables that occur in a factor involving some variable in \a vs, \a vs itself excluded
211 VarSet
delta( const VarSet
&vs
) const {
212 return Delta( vs
) / vs
;
215 /// Returns \c true if the factor graph is connected
216 bool isConnected() const { return G
.isConnected(); }
218 /// Returns \c true if the factor graph is a tree (i.e., has no cycles and is connected)
219 bool isTree() const { return G
.isTree(); }
221 /// Returns \c true if each factor depends on at most two variables
222 bool isPairwise() const;
224 /// Returns \c true if each variable has only two possible values
225 bool isBinary() const;
227 /// Returns the cliques (fully connected subgraphs of the corresponding Markov graph) in this factor graph
228 std::vector
<VarSet
> Cliques() const;
231 /// \name Backup/restore mechanism for factors
233 /// Set the content of the \a I 'th factor and make a backup of its old content if \a backup == \c true
234 virtual void setFactor( size_t I
, const Factor
&newFactor
, bool backup
= false ) {
235 DAI_ASSERT( newFactor
.vars() == factor(I
).vars() );
238 _factors
[I
] = newFactor
;
241 /// Set the contents of all factors as specified by \a facs and make a backup of the old contents if \a backup == \c true
242 virtual void setFactors( const std::map
<size_t, Factor
> & facs
, bool backup
= false ) {
243 for( std::map
<size_t, Factor
>::const_iterator fac
= facs
.begin(); fac
!= facs
.end(); fac
++ ) {
245 backupFactor( fac
->first
);
246 setFactor( fac
->first
, fac
->second
);
250 /// Makes a backup of the \a I 'th factor
251 /** \throw MULTIPLE_UNDO if a backup already exists
253 void backupFactor( size_t I
);
255 /// Restores the \a I 'th factor from the backup (it should be backed up first)
256 void restoreFactor( size_t I
);
258 /// Backup the factors specified by indices in \a facs
259 /** \throw MULTIPLE_UNDO if a backup already exists
261 virtual void backupFactors( const std::set
<size_t> & facs
);
263 /// Restore all factors to the backup copies
264 virtual void restoreFactors();
266 /// Makes a backup of all factors connected to a set of variables
267 /** \throw MULTIPLE_UNDO if a backup already exists
269 void backupFactors( const VarSet
&ns
);
271 /// Restores all factors connected to a set of variables from their backups
272 void restoreFactors( const VarSet
&ns
);
275 /// \name Transformations
277 /// Returns a copy of \c *this, where all factors that are subsumed by some larger factor are merged with the larger factors.
278 FactorGraph
maximalFactors() const;
280 /// Clamp the \a i 'th variable to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{x_i,x}\f$);
281 /** \note This version changes the factor graph structure and thus returns a newly constructed FactorGraph
282 * and keeps the current one constant, contrary to clamp()
284 FactorGraph
clamped( size_t i
, size_t x
) const;
287 /// Clamp variable \a v to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{v,x}\f$);
288 /** \deprecated Please use dai::FactorGraph::clamped(size_t,size_t) instead
290 FactorGraph
clamped( const Var
&v
, size_t x
) const {
291 std::cerr
<< "Warning: this FactorGraph::clamped(const Var&,...) interface is obsolete!" << std::endl
;
292 return clamped( findVar(v
), x
);
298 /// Clamp the \a i 'th variable to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{x_i, x}\f$)
299 /** If \a backup == \c true, make a backup of all factors that are changed
301 virtual void clamp( size_t i
, size_t x
, bool backup
= false );
304 /// Clamp variable \a v to value \a x (i.e. multiply with a Kronecker delta \f$\delta_{v, x}\f$)
305 /** \deprecated Please use dai::FactorGraph::clamp(size_t,size_t,bool) instead
307 virtual void clamp( const Var
&v
, size_t x
, bool backup
= false ) {
308 std::cerr
<< "Warning: this FactorGraph::clamp(const Var&,...) interface is obsolete!" << std::endl
;
309 clamp( findVar(v
), x
, backup
);
312 /// Clamp a variable in a factor graph to have one out of a list of values
313 /** If \a backup == \c true, make a backup of all factors that are changed
315 void clampVar( size_t i
, const std::vector
<size_t> &xis
, bool backup
= false );
317 /// Clamp a factor in a factor graph to have one out of a list of values
318 /** If \a backup == \c true, make a backup of all factors that are changed
320 void clampFactor( size_t I
, const std::vector
<size_t> &xIs
, bool backup
= false );
322 /// Set all factors interacting with the \a i 'th variable to 1
323 /** If \a backup == \c true, make a backup of all factors that are changed
325 virtual void makeCavity( size_t i
, bool backup
= false );
328 /// \name Input/Output
330 /// Reads a factor graph from a file
331 /** \see \ref fileformats-factorgraph
332 * \throw CANNOT_READ_FILE if the file cannot be opened
333 * \throw INVALID_FACTORGRAPH_FILE if the file is not valid
335 void ReadFromFile( const char *filename
);
337 /// Writes a factor graph to a file
338 /** \see \ref fileformats-factorgraph
339 * \throw CANNOT_WRITE_FILE if the file cannot be written
341 void WriteToFile( const char *filename
, size_t precision
=15 ) const;
343 /// Writes a factor graph to an output stream
344 /** \see \ref fileformats-factorgraph
346 friend std::ostream
& operator<< (std::ostream
&os
, const FactorGraph
&fg
);
348 /// Reads a factor graph from an input stream
349 /** \see \ref fileformats-factorgraph
350 * \throw INVALID_FACTORGRAPH_FILE if the input stream is not valid
352 friend std::istream
& operator>> (std::istream
&is
, FactorGraph
&fg
);
354 /// Writes a factor graph to a GraphViz .dot file
355 void printDot( std::ostream
& os
) const;
359 /// \name Backwards compatibility layer (to be removed soon)
361 /// Prepare backwards compatibility layer for indexed edges
362 /** \deprecated Please use FactorGraph::Neighbor interface instead
364 void indexEdges() { G
.indexEdges(); }
365 /// Returns edge with index \a e
366 /** \deprecated Please use FactorGraph::Neighbor interface instead
368 const Edge
& edge(size_t e
) const { return G
.edge(e
); }
369 /// Returns all edges
370 /** \deprecated Please use FactorGraph::Neighbor interface instead
372 const std::vector
<Edge
>& edges() const { return G
.edges(); }
373 /// Converts a pair of node indices to an edge index
374 /** \deprecated Please use FactorGraph::Neighbor interface instead
376 size_t VV2E(size_t n1
, size_t n2
) const { return G
.VV2E(n1
,n2
); }
377 /// Returns number of edges
378 /** \deprecated Please use FactorGraph::Neighbor interface instead
380 size_t nr_edges() const { return G
.nr_edges(); }
384 /// Part of constructors (creates edges, neighbors and adjacency matrix)
385 void constructGraph( size_t nrEdges
);
389 template<typename FactorInputIterator
, typename VarInputIterator
>
390 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() {
393 _factors
.reserve( nr_fact_hint
);
394 for( FactorInputIterator p2
= fact_begin
; p2
!= fact_end
; ++p2
) {
395 _factors
.push_back( *p2
);
396 nrEdges
+= p2
->vars().size();
400 _vars
.reserve( nr_var_hint
);
401 for( VarInputIterator p1
= var_begin
; p1
!= var_end
; ++p1
)
402 _vars
.push_back( *p1
);
404 // create graph structure
405 constructGraph( nrEdges
);
409 /** \example example.cpp
410 * This example illustrates how to read a factor graph from a file and how to
411 * run several inference algorithms (junction tree, loopy belief propagation,
412 * and the max-product algorithm) on it.
416 } // end of namespace dai