[Frederik Eaton] Added BP_Dual, BBP and CBP algorithms
[libdai.git] / include / dai / bp_dual.h
1 #ifndef ____defined_libdai_bp_dual_h__
2 #define ____defined_libdai_bp_dual_h__
3
4 #include <dai/daialg.h>
5 #include <dai/factorgraph.h>
6 #include <dai/enum.h>
7 #include <dai/bp.h>
8
9 namespace dai {
10
11 using namespace std;
12
13 struct BP_dual_messages {
14 // messages:
15 // indexed by edge index (using VV2E)
16 vector<Prob> n;
17 vector<Real> Zn;
18 vector<Prob> m;
19 vector<Real> Zm;
20 };
21
22 struct BP_dual_beliefs {
23 // beliefs:
24 // indexed by node
25 vector<Prob> b1;
26 vector<Real> Zb1;
27 // indexed by factor
28 vector<Prob> b2;
29 vector<Real> Zb2;
30 };
31
32 void _clamp(FactorGraph &g, const Var & n, const vector<size_t> &is );
33
34 // clamp a factor to have one of a set of values
35 void _clampFactor(FactorGraph &g, size_t I, const vector<size_t> &is);
36
37 class BP_dual : public DAIAlgFG {
38 public:
39 typedef vector<size_t> _ind_t;
40
41 protected:
42
43 // indexed by edge index. for each edge i->I, contains a
44 // vector whose entries correspond to those of I, and the
45 // value of each entry is the corresponding entry of i
46 vector<_ind_t> _indices;
47
48 BP_dual_messages _msgs;
49 BP_dual_messages _new_msgs;
50 public:
51 BP_dual_beliefs _beliefs;
52
53 size_t _iters;
54 double _maxdiff;
55
56 struct Properties {
57 typedef BP::Properties::UpdateType UpdateType;
58 UpdateType updates;
59 double tol;
60 size_t maxiter;
61 size_t verbose;
62 } props;
63
64 /// List of property names
65 static const char *PropertyList[];
66 /// Name of this inference algorithm
67 static const char *Name;
68
69 public:
70 void Regenerate(); // used by constructor
71 void RegenerateIndices();
72 void RegenerateMessages();
73 void RegenerateBeliefs();
74
75 void CalcBelief1(size_t i);
76 void CalcBelief2(size_t I);
77 void CalcBeliefs(); // called after run()
78
79 void calcNewM(size_t iI);
80 void calcNewN(size_t iI);
81 void upMsgM(size_t iI);
82 void upMsgN(size_t iI);
83
84 /* DAI_ENUM(UpdateType,SEQFIX,SEQRND,SEQMAX,PARALL) */
85 typedef BP::Properties::UpdateType UpdateType;
86 UpdateType Updates() const { return props.updates; }
87 size_t Verbose() const { return props.verbose; }
88
89 /// construct BP_dual object from FactorGraph
90 BP_dual(const FactorGraph & fg, const PropertySet &opts) : DAIAlgFG(fg) {
91 setProperties(opts);
92 Regenerate();
93 }
94
95 DAI_ACCMUT(Prob & msgM(size_t I, size_t i), { return _msgs.m[VV2E(i,I)]; });
96 DAI_ACCMUT(Prob & msgN(size_t i, size_t I), { return _msgs.n[VV2E(i,I)]; });
97 DAI_ACCMUT(Prob & msgM(size_t iI), { return _msgs.m[iI]; });
98 DAI_ACCMUT(Prob & msgN(size_t iI), { return _msgs.n[iI]; });
99 DAI_ACCMUT(Real & zM(size_t I, size_t i), { return _msgs.Zm[VV2E(i,I)]; });
100 DAI_ACCMUT(Real & zN(size_t i, size_t I), { return _msgs.Zn[VV2E(i,I)]; });
101 DAI_ACCMUT(Real & zM(size_t iI), { return _msgs.Zm[iI]; });
102 DAI_ACCMUT(Real & zN(size_t iI), { return _msgs.Zn[iI]; });
103 DAI_ACCMUT(Prob & newMsgM(size_t I, size_t i), { return _new_msgs.m[VV2E(i,I)]; });
104 DAI_ACCMUT(Prob & newMsgN(size_t i, size_t I), { return _new_msgs.n[VV2E(i,I)]; });
105 DAI_ACCMUT(Real & newZM(size_t I, size_t i), { return _new_msgs.Zm[VV2E(i,I)]; });
106 DAI_ACCMUT(Real & newZN(size_t i, size_t I), { return _new_msgs.Zn[VV2E(i,I)]; });
107
108 DAI_ACCMUT(_ind_t & index(size_t i, size_t I), { return( _indices[VV2E(i,I)] ); });
109
110 Real belief1Z(size_t i) const { return _beliefs.Zb1[i]; }
111 Real belief2Z(size_t I) const { return _beliefs.Zb2[I]; }
112
113 size_t doneIters() const { return _iters; }
114
115
116 /// @name General InfAlg interface
117 //@{
118 virtual BP_dual* clone() const { return new BP_dual(*this); }
119 /* virtual BP_dual* create() const { return new BP_dual(); } */
120 virtual BP_dual* create() const { return NULL; }
121 virtual std::string identify() const;
122 virtual Factor belief (const Var &n) const { return( belief1( findVar( n ) ) ); }
123 virtual Factor belief (const VarSet &n) const;
124 virtual std::vector<Factor> beliefs() const;
125 virtual Real logZ() const;
126 virtual void init();
127 virtual void init( const VarSet &ns );
128 virtual double run();
129 virtual double maxDiff() const { return _maxdiff; }
130 virtual size_t Iterations() const { return _iters; }
131 //@}
132
133 void init(const vector<size_t>& state);
134 Factor belief1 (size_t i) const { return Factor(var(i), _beliefs.b1[i]); }
135 Factor belief2 (size_t I) const { return Factor(factor(I).vars(), _beliefs.b2[I]); }
136
137 void updateMaxDiff( double maxdiff ) { if( maxdiff > _maxdiff ) _maxdiff = maxdiff; }
138
139 /// Set Props according to the PropertySet opts, where the values can be stored as std::strings or as the type of the corresponding Props member
140 void setProperties( const PropertySet &opts );
141 PropertySet getProperties() const;
142 std::string printProperties() const;
143 };
144
145 }
146
147 #endif