3cc0a9f786a26bff4df9c9546f04ee1283958529
[libdai.git] / include / dai / factorgraph.h
1 /* Copyright (C) 2006-2008 Joris Mooij [j dot mooij at science dot ru dot nl]
2 Radboud University Nijmegen, The Netherlands
3
4 This file is part of libDAI.
5
6 libDAI is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 libDAI is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with libDAI; if not, write to the Free Software
18 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 */
20
21
22 #ifndef __defined_libdai_factorgraph_h
23 #define __defined_libdai_factorgraph_h
24
25
26 #include <iostream>
27 #include <map>
28 #include <dai/bipgraph.h>
29 #include <dai/factor.h>
30
31
32 namespace dai {
33
34
35 class FactorGraph {
36 public:
37 BipartiteGraph G;
38 std::vector<Var> vars;
39 typedef BipartiteGraph::Neighbor Neighbor;
40 typedef BipartiteGraph::Neighbors Neighbors;
41 typedef BipartiteGraph::Edge Edge;
42
43 private:
44 std::vector<Factor> _factors;
45 std::map<size_t,Factor> _backup;
46
47 public:
48 /// Default constructor
49 FactorGraph() : G(), vars(), _factors(), _backup() {}
50 /// Copy constructor
51 FactorGraph(const FactorGraph & x) : G(x.G), vars(x.vars), _factors(x._factors), _backup(x._backup) {}
52 /// Construct FactorGraph from vector of Factors
53 FactorGraph(const std::vector<Factor> &P);
54 // Construct a FactorGraph from given factor and variable iterators
55 template<typename FactorInputIterator, typename VarInputIterator>
56 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 );
57
58 /// Assignment operator
59 FactorGraph & operator=(const FactorGraph & x) {
60 if( this != &x ) {
61 G = x.G;
62 vars = x.vars;
63 _factors = x._factors;
64 _backup = x._backup;
65 }
66 return *this;
67 }
68 virtual ~FactorGraph() {}
69
70 /// Create (virtual default constructor)
71 virtual FactorGraph* create() const {
72 return new FactorGraph(*this);
73 }
74
75 /// Clone (virtual copy constructor)
76 virtual FactorGraph* clone() const {
77 return new FactorGraph();
78 }
79
80 // aliases
81 Var & var(size_t i) { return vars[i]; }
82 /// Get const reference to i'th variable
83 const Var & var(size_t i) const { return vars[i]; }
84 /// Get const reference to I'th factor
85 Factor & factor(size_t I) { return _factors[I]; }
86 /// Get const reference to I'th factor
87 const Factor & factor(size_t I) const { return _factors[I]; }
88 /// Get const reference to all factors
89 const std::vector<Factor> & factors() const { return _factors; }
90
91 /// Get number of variables
92 size_t nrVars() const { return vars.size(); }
93 /// Get number of factors
94 size_t nrFactors() const { return _factors.size(); }
95 size_t nrEdges() const { return G.nrEdges(); }
96
97 /// Provides read access to neighbors of variable
98 const Neighbors & nbV( size_t i ) const { return G.nb1(i); }
99 /// Provides full access to neighbors of variable
100 Neighbors & nbV( size_t i ) { return G.nb1(i); }
101 /// Provides read access to neighbors of factor
102 const Neighbors & nbF( size_t I ) const { return G.nb2(I); }
103 /// Provides full access to neighbors of factor
104 Neighbors & nbF( size_t I ) { return G.nb2(I); }
105 /// Provides read access to neighbor of variable
106 const Neighbor & nbV( size_t i, size_t _I ) const { return G.nb1(i)[_I]; }
107 /// Provides full access to neighbor of variable
108 Neighbor & nbV( size_t i, size_t _I ) { return G.nb1(i)[_I]; }
109 /// Provides read access to neighbor of factor
110 const Neighbor & nbF( size_t I, size_t _i ) const { return G.nb2(I)[_i]; }
111 /// Provides full access to neighbor of factor
112 Neighbor & nbF( size_t I, size_t _i ) { return G.nb2(I)[_i]; }
113
114 /// Get index of variable n
115 size_t findVar( const Var & n ) const {
116 size_t i = find( vars.begin(), vars.end(), n ) - vars.begin();
117 assert( i != nrVars() );
118 return i;
119 }
120
121 /// Get set of indexes for set of variables
122 std::set<size_t> findVars( VarSet &ns ) const {
123 std::set<size_t> indexes;
124 for( VarSet::const_iterator n = ns.begin(); n != ns.end(); n++ )
125 indexes.insert( findVar( *n ) );
126 return indexes;
127 }
128
129 /// Get index of first factor involving ns
130 size_t findFactor(const VarSet &ns) const {
131 size_t I;
132 for( I = 0; I < nrFactors(); I++ )
133 if( factor(I).vars() == ns )
134 break;
135 assert( I != nrFactors() );
136 return I;
137 }
138
139 /// Return all variables that occur in a factor involving the i'th variable, itself included
140 VarSet Delta( unsigned i ) const;
141
142 /// Return all variables that occur in a factor involving some variable in ns, ns itself included
143 VarSet Delta( const VarSet &ns ) const;
144
145 /// Return all variables that occur in a factor involving the i'th variable, n itself excluded
146 VarSet delta( unsigned i ) const;
147
148 /// Return all variables that occur in a factor involving some variable in ns, ns itself excluded
149 VarSet delta( const VarSet & ns ) const {
150 return Delta( ns ) / ns;
151 }
152
153 /// Set the content of the I'th factor and make a backup of its old content if backup == true
154 virtual void setFactor( size_t I, const Factor &newFactor, bool backup = false ) {
155 assert( newFactor.vars() == factor(I).vars() );
156 if( backup )
157 backupFactor( I );
158 _factors[I] = newFactor;
159 }
160
161 /// Set the contents of all factors as specified by facs and make a backup of the old contents if backup == true
162 virtual void setFactors( const std::map<size_t, Factor> & facs, bool backup = false ) {
163 for( std::map<size_t, Factor>::const_iterator fac = facs.begin(); fac != facs.end(); fac++ ) {
164 if( backup )
165 backupFactor( fac->first );
166 setFactor( fac->first, fac->second );
167 }
168 }
169
170 /// Clamp variable n to value i (i.e. multiply with a Kronecker delta \f$\delta_{x_n, i}\f$);
171 /// If backup == true, make a backup of all factors that are changed
172 virtual void clamp( const Var & n, size_t i, bool backup = false );
173
174 /// Set all factors interacting with the i'th variable 1
175 virtual void makeCavity( unsigned i, bool backup = false );
176
177 /// Backup the factors specified by indices in facs
178 virtual void backupFactors( const std::set<size_t> & facs );
179
180 /// Restore all factors to the backup copies
181 virtual void restoreFactors();
182
183 bool isConnected() const { return G.isConnected(); }
184 bool isTree() const { return G.isTree(); }
185
186 friend std::ostream& operator << (std::ostream& os, const FactorGraph& fg);
187 friend std::istream& operator >> (std::istream& is, FactorGraph& fg);
188
189 void ReadFromFile(const char *filename);
190 void WriteToFile(const char *filename) const;
191 void printDot( std::ostream& os ) const;
192
193 std::vector<VarSet> Cliques() const;
194
195 // Clamp variable v_i to value state (i.e. multiply with a Kronecker delta \f$\delta_{x_{v_i},x}\f$);
196 // This version changes the factor graph structure and thus returns a newly constructed FactorGraph
197 // and keeps the current one constant, contrary to clamp()
198 FactorGraph clamped( const Var & v_i, size_t x ) const;
199
200 FactorGraph maximalFactors() const;
201
202 bool isPairwise() const;
203 bool isBinary() const;
204
205 void restoreFactor( size_t I );
206 void backupFactor( size_t I );
207 void restoreFactors( const VarSet &ns );
208 void backupFactors( const VarSet &ns );
209 /// Part of constructors (creates edges, neighbors and adjacency matrix)
210 void createGraph( size_t nrEdges );
211 };
212
213
214 // 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)
215 template<typename FactorInputIterator, typename VarInputIterator>
216 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() {
217 // add factors
218 size_t nrEdges = 0;
219 _factors.reserve( nr_fact_hint );
220 for( FactorInputIterator p2 = fact_begin; p2 != fact_end; ++p2 ) {
221 _factors.push_back( *p2 );
222 nrEdges += p2->vars().size();
223 }
224
225 // add variables
226 vars.reserve( nr_var_hint );
227 for( VarInputIterator p1 = var_begin; p1 != var_end; ++p1 )
228 vars.push_back( *p1 );
229
230 // create graph structure
231 createGraph( nrEdges );
232 }
233
234
235 } // end of namespace dai
236
237
238 #endif