libDAI
bp.h
Go to the documentation of this file.
1 /* This file is part of libDAI - http://www.libdai.org/
2  *
3  * Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
4  *
5  * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
6  */
7 
8 
12 
13 
14 #ifndef __defined_libdai_bp_h
15 #define __defined_libdai_bp_h
16 
17 
18 #include <string>
19 #include <dai/daialg.h>
20 #include <dai/factorgraph.h>
21 #include <dai/properties.h>
22 #include <dai/enum.h>
23 
24 
25 namespace dai {
26 
27 
29 
59 class BP : public DAIAlgFG {
60  protected:
62  typedef std::vector<size_t> ind_t;
64  struct EdgeProp {
73  };
75  std::vector<std::vector<EdgeProp> > _edges;
77  typedef std::multimap<Real, std::pair<std::size_t, std::size_t> > LutType;
79  std::vector<std::vector<LutType::iterator> > _edge2lut;
85  size_t _iters;
87  std::vector<std::pair<std::size_t, std::size_t> > _sentMessages;
89  std::vector<Factor> _oldBeliefsV;
91  std::vector<Factor> _oldBeliefsF;
93  std::vector<Edge> _updateSeq;
94 
95  public:
97  struct Properties {
99 
105  DAI_ENUM(UpdateType,SEQFIX,SEQRND,SEQMAX,PARALL);
106 
108 
112  DAI_ENUM(InfType,SUMPROD,MAXPROD);
113 
115  size_t verbose;
116 
118  size_t maxiter;
119 
121  double maxtime;
122 
125 
127  bool logdomain;
128 
131 
133  UpdateType updates;
134 
136  InfType inference;
137  } props;
138 
141 
142  public:
144 
145 
147 
149 
152  BP( const FactorGraph & fg, const PropertySet &opts ) : DAIAlgFG(fg), _edges(), _maxdiff(0.0), _iters(0U), _sentMessages(), _oldBeliefsV(), _oldBeliefsF(), _updateSeq(), props(), recordSentMessages(false) {
153  setProperties( opts );
154  construct();
155  }
156 
159  for( LutType::iterator l = _lut.begin(); l != _lut.end(); ++l )
160  _edge2lut[l->second.first][l->second.second] = l;
161  }
162 
164  BP& operator=( const BP &x ) {
165  if( this != &x ) {
166  DAIAlgFG::operator=( x );
167  _edges = x._edges;
168  _lut = x._lut;
169  for( LutType::iterator l = _lut.begin(); l != _lut.end(); ++l )
170  _edge2lut[l->second.first][l->second.second] = l;
171  _maxdiff = x._maxdiff;
172  _iters = x._iters;
177  props = x.props;
179  }
180  return *this;
181  }
183 
185 
186  virtual BP* clone() const { return new BP(*this); }
187  virtual BP* construct( const FactorGraph &fg, const PropertySet &opts ) const { return new BP( fg, opts ); }
188  virtual std::string name() const { return "BP"; }
189  virtual Factor belief( const Var &v ) const { return beliefV( findVar( v ) ); }
190  virtual Factor belief( const VarSet &vs ) const;
191  virtual Factor beliefV( size_t i ) const;
192  virtual Factor beliefF( size_t I ) const;
193  virtual std::vector<Factor> beliefs() const;
194  virtual Real logZ() const;
197  std::vector<std::size_t> findMaximum() const { return dai::findMaximum( *this ); }
198  virtual void init();
199  virtual void init( const VarSet &ns );
200  virtual Real run();
201  virtual Real maxDiff() const { return _maxdiff; }
202  virtual size_t Iterations() const { return _iters; }
203  virtual void setMaxIter( size_t maxiter ) { props.maxiter = maxiter; }
204  virtual void setProperties( const PropertySet &opts );
205  virtual PropertySet getProperties() const;
206  virtual std::string printProperties() const;
208 
210 
211 
212  const std::vector<std::pair<std::size_t, std::size_t> >& getSentMessages() const {
213  return _sentMessages;
214  }
215 
217  void clearSentMessages() { _sentMessages.clear(); }
219 
220  protected:
222  const Prob & message(size_t i, size_t _I) const { return _edges[i][_I].message; }
224  Prob & message(size_t i, size_t _I) { return _edges[i][_I].message; }
226  const Prob & newMessage(size_t i, size_t _I) const { return _edges[i][_I].newMessage; }
228  Prob & newMessage(size_t i, size_t _I) { return _edges[i][_I].newMessage; }
230  const ind_t & index(size_t i, size_t _I) const { return _edges[i][_I].index; }
232  ind_t & index(size_t i, size_t _I) { return _edges[i][_I].index; }
234  const Real & residual(size_t i, size_t _I) const { return _edges[i][_I].residual; }
236  Real & residual(size_t i, size_t _I) { return _edges[i][_I].residual; }
237 
239 
242  virtual Prob calcIncomingMessageProduct( size_t I, bool without_i, size_t i ) const;
244  virtual void calcNewMessage( size_t i, size_t _I );
246  void updateMessage( size_t i, size_t _I );
248  void updateResidual( size_t i, size_t _I, Real r );
250  void findMaxResidual( size_t &i, size_t &_I );
252  virtual void calcBeliefV( size_t i, Prob &p ) const;
254  virtual void calcBeliefF( size_t I, Prob &p ) const {
255  p = calcIncomingMessageProduct( I, false, 0 );
256  }
257 
259  virtual void construct();
260 };
261 
262 
263 } // end of namespace dai
264 
265 
266 #endif