Moved platform independent build options into Makefile.ALL and documented tests/testdai
[libdai.git] / include / dai / clustergraph.h
1 /* This file is part of libDAI - http://www.libdai.org/
2 *
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.
6 *
7 * Copyright (C) 2006-2010 Joris Mooij [joris dot mooij at libdai dot org]
8 * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
9 */
10
11
12 /// \file
13 /// \brief Defines class ClusterGraph, which is used by JTree, TreeEP and HAK
14
15
16 #ifndef __defined_libdai_clustergraph_h
17 #define __defined_libdai_clustergraph_h
18
19
20 #include <set>
21 #include <vector>
22 #include <dai/varset.h>
23 #include <dai/bipgraph.h>
24
25
26 namespace dai {
27
28
29 /// A ClusterGraph is a hypergraph with variables as nodes, and "clusters" (sets of variables) as hyperedges.
30 /** It is implemented as a bipartite graph with variable (Var) nodes and cluster (VarSet) nodes.
31 */
32 class ClusterGraph {
33 public:
34 /// Stores the neighborhood structure
35 BipartiteGraph G;
36
37 /// Stores the variables corresponding to the nodes
38 std::vector<Var> vars;
39
40 /// Stores the clusters corresponding to the hyperedges
41 std::vector<VarSet> clusters;
42
43 /// Shorthand for BipartiteGraph::Neighbor
44 typedef BipartiteGraph::Neighbor Neighbor;
45
46 /// Shorthand for BipartiteGraph::Edge
47 typedef BipartiteGraph::Edge Edge;
48
49 public:
50 /// \name Constructors and destructors
51 //@{
52 /// Default constructor
53 ClusterGraph() : G(), vars(), clusters() {}
54
55 /// Construct from vector of VarSet 's
56 ClusterGraph( const std::vector<VarSet> & cls );
57 //@}
58
59 /// \name Queries
60 //@{
61 /// Returns a constant reference to the clusters
62 const std::vector<VarSet> & toVector() const { return clusters; }
63
64 /// Returns number of clusters
65 size_t size() const {
66 return G.nrNodes2();
67 }
68
69 /// Returns the index of variable \a n
70 size_t findVar( const Var &n ) const {
71 return find( vars.begin(), vars.end(), n ) - vars.begin();
72 }
73
74 /// Returns union of clusters that contain the \a i 'th variable
75 VarSet Delta( size_t i ) const {
76 VarSet result;
77 foreach( const Neighbor &I, G.nb1(i) )
78 result |= clusters[I];
79 return result;
80 }
81
82 /// Returns union of clusters that contain the \a i 'th (except this variable itself)
83 VarSet delta( size_t i ) const {
84 return Delta( i ) / vars[i];
85 }
86
87 /// Returns \c true if variables with indices \a i1 and \a i2 are adjacent, i.e., both contained in the same cluster
88 bool adj( size_t i1, size_t i2 ) const {
89 bool result = false;
90 foreach( const Neighbor &I, G.nb1(i1) )
91 if( find( G.nb2(I).begin(), G.nb2(I).end(), i2 ) != G.nb2(I).end() ) {
92 result = true;
93 break;
94 }
95 return result;
96 }
97
98 /// Returns \c true if cluster \a I is not contained in a larger cluster
99 bool isMaximal( size_t I ) const {
100 DAI_DEBASSERT( I < G.nrNodes2() );
101 const VarSet & clI = clusters[I];
102 bool maximal = true;
103 // The following may not be optimal, since it may repeatedly test the same cluster *J
104 foreach( const Neighbor &i, G.nb2(I) ) {
105 foreach( const Neighbor &J, G.nb1(i) )
106 if( (J != I) && (clI << clusters[J]) ) {
107 maximal = false;
108 break;
109 }
110 if( !maximal )
111 break;
112 }
113 return maximal;
114 }
115 //@}
116
117 /// \name Operations
118 //@{
119 /// Inserts a cluster (if it does not already exist)
120 void insert( const VarSet &cl ) {
121 if( find( clusters.begin(), clusters.end(), cl ) == clusters.end() ) {
122 clusters.push_back( cl );
123 // add variables (if necessary) and calculate neighborhood of new cluster
124 std::vector<size_t> nbs;
125 for( VarSet::const_iterator n = cl.begin(); n != cl.end(); n++ ) {
126 size_t iter = find( vars.begin(), vars.end(), *n ) - vars.begin();
127 nbs.push_back( iter );
128 if( iter == vars.size() ) {
129 G.addNode1();
130 vars.push_back( *n );
131 }
132 }
133 G.addNode2( nbs.begin(), nbs.end(), nbs.size() );
134 }
135 }
136
137 /// Erases all clusters that are not maximal
138 ClusterGraph& eraseNonMaximal() {
139 for( size_t I = 0; I < G.nrNodes2(); ) {
140 if( !isMaximal(I) ) {
141 clusters.erase( clusters.begin() + I );
142 G.eraseNode2(I);
143 } else
144 I++;
145 }
146 return *this;
147 }
148
149 /// Erases all clusters that contain the \a i 'th variable
150 ClusterGraph& eraseSubsuming( size_t i ) {
151 while( G.nb1(i).size() ) {
152 clusters.erase( clusters.begin() + G.nb1(i)[0] );
153 G.eraseNode2( G.nb1(i)[0] );
154 }
155 return *this;
156 }
157 //@}
158
159 /// \name Input/Ouput
160 //@{
161 /// Writes a ClusterGraph to an output stream
162 friend std::ostream & operator << ( std::ostream & os, const ClusterGraph & cl ) {
163 os << cl.toVector();
164 return os;
165 }
166 //@}
167
168 /// \name Variable elimination
169 //@{
170 /// Performs Variable Elimination, only keeping track of the interactions that are created along the way.
171 /** \tparam EliminationChoice should support "size_t operator()( const ClusterGraph &cl, const std::set<size_t> &remainingVars )"
172 * \param f function object which returns the next variable index to eliminate; for example, a dai::greedyVariableElimination object.
173 * \return A set of elimination "cliques".
174 */
175 template<class EliminationChoice>
176 ClusterGraph VarElim( EliminationChoice f ) const {
177 // Make a copy
178 ClusterGraph cl(*this);
179 cl.eraseNonMaximal();
180
181 ClusterGraph result;
182
183 // Construct set of variable indices
184 std::set<size_t> varindices;
185 for( size_t i = 0; i < vars.size(); ++i )
186 varindices.insert( i );
187
188 // Do variable elimination
189 while( !varindices.empty() ) {
190 size_t i = f( cl, varindices );
191 DAI_ASSERT( i < vars.size() );
192 result.insert( cl.Delta( i ) );
193 cl.insert( cl.delta( i ) );
194 cl.eraseSubsuming( i );
195 cl.eraseNonMaximal();
196 varindices.erase( i );
197 }
198
199 return result;
200 }
201
202 /// Calculates cost of eliminating the \a i 'th variable.
203 /** The cost is measured as "number of added edges in the adjacency graph",
204 * where the adjacency graph has the variables as its nodes and connects
205 * nodes \a i1 and \a i2 iff \a i1 and \a i2 occur together in some common cluster.
206 * \deprecated Please use dai::eliminationCost_MinFill() instead.
207 */
208 size_t eliminationCost( size_t i ) const;
209
210 /// Performs Variable Elimination, only keeping track of the interactions that are created along the way.
211 /** \param ElimSeq The sequence in which to eliminate the variables
212 * \return A set of elimination "cliques"
213 * \deprecated Please use dai::ClusterGraph::VarElim( sequentialVariableElimination( ElimSeq ) ) instead.
214 */
215 ClusterGraph VarElim( const std::vector<Var> &ElimSeq ) const;
216
217 /// Performs Variable Elimination using the "MinFill" heuristic
218 /** The "MinFill" heuristic greedily minimizes the cost of eliminating a variable,
219 * measured with eliminationCost().
220 * \return A set of elimination "cliques".
221 * \deprecated Please use dai::ClusterGraph::VarElim( greedyVariableElimination( eliminationCost_MinFill ) ) instead.
222 */
223 ClusterGraph VarElim_MinFill() const;
224 //@}
225 };
226
227
228 /// Helper object for dai::ClusterGraph::VarElim()
229 /** Chooses the next variable to eliminate by picking them sequentially from a given vector of variables.
230 */
231 class sequentialVariableElimination {
232 private:
233 /// The variable elimination sequence
234 std::vector<Var> seq;
235 /// Counter
236 size_t i;
237
238 public:
239 /// Construct from vector of variables
240 sequentialVariableElimination( const std::vector<Var> s ) : seq(s), i(0) {}
241
242 /// Returns next variable in sequence
243 size_t operator()( const ClusterGraph &cl, const std::set<size_t> &/*remainingVars*/ );
244 };
245
246
247 /// Helper object for dai::ClusterGraph::VarElim()
248 /** Chooses the next variable to eliminate greedily by taking the one that minimizes
249 * a given heuristic cost function.
250 */
251 class greedyVariableElimination {
252 public:
253 /// Type of cost functions to be used for greedy variable elimination
254 typedef size_t (*eliminationCostFunction)(const ClusterGraph &, size_t);
255
256 private:
257 /// Pointer to the cost function used
258 eliminationCostFunction heuristic;
259
260 public:
261 /// Construct from cost function
262 /** \note Examples of cost functions are eliminationCost_MinFill() and eliminationCost_WeightedMinFill().
263 */
264 greedyVariableElimination( eliminationCostFunction h ) : heuristic(h) {}
265
266 /// Returns the best variable from \a remainingVars to eliminate in the cluster graph \a cl by greedily minimizing the cost function.
267 /** This function calculates the cost for eliminating each variable in \a remaingVars and returns the variable which has lowest cost.
268 */
269 size_t operator()( const ClusterGraph &cl, const std::set<size_t> &remainingVars );
270 };
271
272
273 /// Calculates cost of eliminating the \a i 'th variable from cluster graph \a cl according to the "MinNeighbors" criterion.
274 /** The cost is measured as "number of neigboring nodes in the current adjacency graph",
275 * where the adjacency graph has the variables as its nodes and connects
276 * nodes \a i1 and \a i2 iff \a i1 and \a i2 occur together in some common cluster.
277 */
278 size_t eliminationCost_MinNeighbors( const ClusterGraph &cl, size_t i );
279
280
281 /// Calculates cost of eliminating the \a i 'th variable from cluster graph \a cl according to the "MinWeight" criterion.
282 /** The cost is measured as "product of weights of neighboring nodes in the current adjacency graph",
283 * where the adjacency graph has the variables as its nodes and connects
284 * nodes \a i1 and \a i2 iff \a i1 and \a i2 occur together in some common cluster.
285 * The weight of a node is the number of states of the corresponding variable.
286 */
287 size_t eliminationCost_MinWeight( const ClusterGraph &cl, size_t i );
288
289
290 /// Calculates cost of eliminating the \a i 'th variable from cluster graph \a cl according to the "MinFill" criterion.
291 /** The cost is measured as "number of added edges in the adjacency graph",
292 * where the adjacency graph has the variables as its nodes and connects
293 * nodes \a i1 and \a i2 iff \a i1 and \a i2 occur together in some common cluster.
294 */
295 size_t eliminationCost_MinFill( const ClusterGraph &cl, size_t i );
296
297
298 /// Calculates cost of eliminating the \a i 'th variable from cluster graph \a cl according to the "WeightedMinFill" criterion.
299 /** The cost is measured as "total weight of added edges in the adjacency graph",
300 * where the adjacency graph has the variables as its nodes and connects
301 * nodes \a i1 and \a i2 iff \a i1 and \a i2 occur together in some common cluster.
302 * The weight of an edge is the product of the number of states of the variables corresponding with its nodes.
303 */
304 size_t eliminationCost_WeightedMinFill( const ClusterGraph &cl, size_t i );
305
306
307 } // end of namespace dai
308
309
310 #endif