1 /* Copyright (C) 2006-2008 Joris Mooij [j dot mooij at science dot ru dot nl]
2 Radboud University Nijmegen, The Netherlands
4 This file is part of libDAI.
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.
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.
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
22 #ifndef __defined_libdai_factorgraph_h
23 #define __defined_libdai_factorgraph_h
28 #include <dai/bipgraph.h>
29 #include <dai/factor.h>
38 std::vector
<Var
> vars
;
39 typedef BipartiteGraph::Neighbor Neighbor
;
40 typedef BipartiteGraph::Neighbors Neighbors
;
41 typedef BipartiteGraph::Edge Edge
;
44 std::vector
<Factor
> _factors
;
45 std::map
<size_t,Factor
> _backup
;
48 /// Default constructor
49 FactorGraph() : G(), vars(), _factors(), _backup() {}
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 );
58 /// Assignment operator
59 FactorGraph
& operator=(const FactorGraph
& x
) {
63 _factors
= x
._factors
;
68 virtual ~FactorGraph() {}
70 /// Create (virtual default constructor)
71 virtual FactorGraph
* create() const {
72 return new FactorGraph(*this);
75 /// Clone (virtual copy constructor)
76 virtual FactorGraph
* clone() const {
77 return new FactorGraph();
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
; }
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(); }
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
]; }
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() );
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
) );
129 /// Get index of first factor involving ns
130 size_t findFactor(const VarSet
&ns
) const {
132 for( I
= 0; I
< nrFactors(); I
++ )
133 if( factor(I
).vars() == ns
)
135 assert( I
!= nrFactors() );
139 /// Return all variables that occur in a factor involving the i'th variable, itself included
140 VarSet
Delta( unsigned i
) const;
142 /// Return all variables that occur in a factor involving some variable in ns, ns itself included
143 VarSet
Delta( const VarSet
&ns
) const;
145 /// Return all variables that occur in a factor involving the i'th variable, n itself excluded
146 VarSet
delta( unsigned i
) const;
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
;
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() );
158 _factors
[I
] = newFactor
;
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
++ ) {
165 backupFactor( fac
->first
);
166 setFactor( fac
->first
, fac
->second
);
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 );
174 /// Set all factors interacting with the i'th variable 1
175 virtual void makeCavity( unsigned i
, bool backup
= false );
177 /// Backup the factors specified by indices in facs
178 virtual void backupFactors( const std::set
<size_t> & facs
);
180 /// Restore all factors to the backup copies
181 virtual void restoreFactors();
183 bool isConnected() const { return G
.isConnected(); }
184 bool isTree() const { return G
.isTree(); }
186 friend std::ostream
& operator << (std::ostream
& os
, const FactorGraph
& fg
);
187 friend std::istream
& operator >> (std::istream
& is
, FactorGraph
& fg
);
189 void ReadFromFile(const char *filename
);
190 void WriteToFile(const char *filename
) const;
191 void printDot( std::ostream
& os
) const;
193 std::vector
<VarSet
> Cliques() const;
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;
200 FactorGraph
maximalFactors() const;
202 bool isPairwise() const;
203 bool isBinary() const;
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
);
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() {
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();
226 vars
.reserve( nr_var_hint
);
227 for( VarInputIterator p1
= var_begin
; p1
!= var_end
; ++p1
)
228 vars
.push_back( *p1
);
230 // create graph structure
231 createGraph( nrEdges
);
235 } // end of namespace dai