Fixed two problems related to g++ 4.0.0 on Darwin 9.8.0
[libdai.git] / tests / unit / clustergraph_test.cpp
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) 2010 Joris Mooij [joris dot mooij at libdai dot org]
8 */
9
10
11 #include <dai/clustergraph.h>
12 #include <vector>
13 #include <strstream>
14
15
16 using namespace dai;
17
18
19 const double tol = 1e-8;
20
21
22 #define BOOST_TEST_MODULE ClusterGraphTest
23
24
25 #include <boost/test/unit_test.hpp>
26 #include <boost/test/floating_point_comparison.hpp>
27
28
29 BOOST_AUTO_TEST_CASE( ConstructorsTest ) {
30 ClusterGraph G;
31 BOOST_CHECK_EQUAL( G.clusters(), std::vector<VarSet>() );
32 BOOST_CHECK( G.bipGraph() == BipartiteGraph() );
33 BOOST_CHECK_EQUAL( G.nrVars(), 0 );
34 BOOST_CHECK_EQUAL( G.nrClusters(), 0 );
35 #ifdef DAI_DEBUG
36 BOOST_CHECK_THROW( G.var( 0 ), Exception );
37 BOOST_CHECK_THROW( G.cluster( 0 ), Exception );
38 #endif
39 BOOST_CHECK_THROW( G.findVar( Var( 0, 2 ) ), Exception );
40
41 Var v0( 0, 2 );
42 Var v1( 1, 3 );
43 Var v2( 2, 2 );
44 Var v3( 3, 4 );
45 std::vector<Var> vs;
46 vs.push_back( v0 );
47 vs.push_back( v1 );
48 vs.push_back( v2 );
49 vs.push_back( v3 );
50 VarSet v01( v0, v1 );
51 VarSet v02( v0, v2 );
52 VarSet v03( v0, v3 );
53 VarSet v12( v1, v2 );
54 VarSet v13( v1, v3 );
55 VarSet v23( v2, v3 );
56 std::vector<VarSet> cl;
57 cl.push_back( v01 );
58 cl.push_back( v12 );
59 cl.push_back( v23 );
60 cl.push_back( v13 );
61 ClusterGraph G2( cl );
62 BOOST_CHECK_EQUAL( G2.nrVars(), 4 );
63 BOOST_CHECK_EQUAL( G2.nrClusters(), 4 );
64 BOOST_CHECK_EQUAL( G2.vars(), vs );
65 BOOST_CHECK_EQUAL( G2.clusters(), cl );
66 BOOST_CHECK_EQUAL( G2.findVar( v0 ), 0 );
67 BOOST_CHECK_EQUAL( G2.findVar( v1 ), 1 );
68 BOOST_CHECK_EQUAL( G2.findVar( v2 ), 2 );
69 BOOST_CHECK_EQUAL( G2.findVar( v3 ), 3 );
70
71 ClusterGraph Gb( G );
72 BOOST_CHECK( G.bipGraph() == Gb.bipGraph() );
73 BOOST_CHECK( G.vars() == Gb.vars() );
74 BOOST_CHECK( G.clusters() == Gb.clusters() );
75
76 ClusterGraph Gc = G;
77 BOOST_CHECK( G.bipGraph() == Gc.bipGraph() );
78 BOOST_CHECK( G.vars() == Gc.vars() );
79 BOOST_CHECK( G.clusters() == Gc.clusters() );
80
81 ClusterGraph G2b( G2 );
82 BOOST_CHECK( G2.bipGraph() == G2b.bipGraph() );
83 BOOST_CHECK( G2.vars() == G2b.vars() );
84 BOOST_CHECK( G2.clusters() == G2b.clusters() );
85
86 ClusterGraph G2c = G2;
87 BOOST_CHECK( G2.bipGraph() == G2c.bipGraph() );
88 BOOST_CHECK( G2.vars() == G2c.vars() );
89 BOOST_CHECK( G2.clusters() == G2c.clusters() );
90 }
91
92
93 BOOST_AUTO_TEST_CASE( QueriesTest ) {
94 Var v0( 0, 2 );
95 Var v1( 1, 3 );
96 Var v2( 2, 2 );
97 Var v3( 3, 4 );
98 Var v4( 4, 2 );
99 std::vector<Var> vs;
100 vs.push_back( v0 );
101 vs.push_back( v1 );
102 vs.push_back( v2 );
103 vs.push_back( v3 );
104 vs.push_back( v4 );
105 VarSet v01( v0, v1 );
106 VarSet v02( v0, v2 );
107 VarSet v03( v0, v3 );
108 VarSet v04( v0, v4 );
109 VarSet v12( v1, v2 );
110 VarSet v13( v1, v3 );
111 VarSet v14( v1, v4 );
112 VarSet v23( v2, v3 );
113 VarSet v24( v2, v4 );
114 VarSet v34( v3, v4 );
115 VarSet v123 = v12 | v3;
116 std::vector<VarSet> cl;
117 cl.push_back( v01 );
118 cl.push_back( v12 );
119 cl.push_back( v123 );
120 cl.push_back( v34 );
121 cl.push_back( v04 );
122 ClusterGraph G( cl );
123
124 BOOST_CHECK_EQUAL( G.nrVars(), 5 );
125 BOOST_CHECK_EQUAL( G.vars(), vs );
126 BOOST_CHECK_EQUAL( G.var(0), v0 );
127 BOOST_CHECK_EQUAL( G.var(1), v1 );
128 BOOST_CHECK_EQUAL( G.var(2), v2 );
129 BOOST_CHECK_EQUAL( G.var(3), v3 );
130 BOOST_CHECK_EQUAL( G.var(4), v4 );
131 BOOST_CHECK_EQUAL( G.nrClusters(), 5 );
132 BOOST_CHECK_EQUAL( G.clusters(), cl );
133 BOOST_CHECK_EQUAL( G.cluster(0), v01 );
134 BOOST_CHECK_EQUAL( G.cluster(1), v12 );
135 BOOST_CHECK_EQUAL( G.cluster(2), v123 );
136 BOOST_CHECK_EQUAL( G.cluster(3), v34 );
137 BOOST_CHECK_EQUAL( G.cluster(4), v04 );
138 BOOST_CHECK_EQUAL( G.findVar( v0 ), 0 );
139 BOOST_CHECK_EQUAL( G.findVar( v1 ), 1 );
140 BOOST_CHECK_EQUAL( G.findVar( v2 ), 2 );
141 BOOST_CHECK_EQUAL( G.findVar( v3 ), 3 );
142 BOOST_CHECK_EQUAL( G.findVar( v4 ), 4 );
143 BipartiteGraph H( 5, 5 );
144 H.addEdge( 0, 0 );
145 H.addEdge( 1, 0 );
146 H.addEdge( 1, 1 );
147 H.addEdge( 2, 1 );
148 H.addEdge( 1, 2 );
149 H.addEdge( 2, 2 );
150 H.addEdge( 3, 2 );
151 H.addEdge( 3, 3 );
152 H.addEdge( 4, 3 );
153 H.addEdge( 0, 4 );
154 H.addEdge( 4, 4 );
155 BOOST_CHECK( G.bipGraph() == H );
156
157 BOOST_CHECK_EQUAL( G.delta( 0 ), v14 );
158 BOOST_CHECK_EQUAL( G.delta( 1 ), v02 | v3 );
159 BOOST_CHECK_EQUAL( G.delta( 2 ), v13 );
160 BOOST_CHECK_EQUAL( G.delta( 3 ), v12 | v4 );
161 BOOST_CHECK_EQUAL( G.delta( 4 ), v03 );
162 BOOST_CHECK_EQUAL( G.Delta( 0 ), v14 | v0 );
163 BOOST_CHECK_EQUAL( G.Delta( 1 ), v01 | v23 );
164 BOOST_CHECK_EQUAL( G.Delta( 2 ), v13 | v2 );
165 BOOST_CHECK_EQUAL( G.Delta( 3 ), v12 | v34 );
166 BOOST_CHECK_EQUAL( G.Delta( 4 ), v03 | v4 );
167
168 BOOST_CHECK( !G.adj( 0, 0 ) );
169 BOOST_CHECK( G.adj( 0, 1 ) );
170 BOOST_CHECK( !G.adj( 0, 2 ) );
171 BOOST_CHECK( !G.adj( 0, 3 ) );
172 BOOST_CHECK( G.adj( 0, 4 ) );
173 BOOST_CHECK( G.adj( 1, 0 ) );
174 BOOST_CHECK( !G.adj( 1, 1 ) );
175 BOOST_CHECK( G.adj( 1, 2 ) );
176 BOOST_CHECK( G.adj( 1, 3 ) );
177 BOOST_CHECK( !G.adj( 1, 4 ) );
178 BOOST_CHECK( !G.adj( 2, 0 ) );
179 BOOST_CHECK( G.adj( 2, 1 ) );
180 BOOST_CHECK( !G.adj( 2, 2 ) );
181 BOOST_CHECK( G.adj( 2, 3 ) );
182 BOOST_CHECK( !G.adj( 2, 4 ) );
183 BOOST_CHECK( !G.adj( 3, 0 ) );
184 BOOST_CHECK( G.adj( 3, 1 ) );
185 BOOST_CHECK( G.adj( 3, 2 ) );
186 BOOST_CHECK( !G.adj( 3, 3 ) );
187 BOOST_CHECK( G.adj( 3, 4 ) );
188 BOOST_CHECK( G.adj( 4, 0 ) );
189 BOOST_CHECK( !G.adj( 4, 1 ) );
190 BOOST_CHECK( !G.adj( 4, 2 ) );
191 BOOST_CHECK( G.adj( 4, 3 ) );
192 BOOST_CHECK( !G.adj( 4, 4 ) );
193
194 BOOST_CHECK( G.isMaximal( 0 ) );
195 BOOST_CHECK( !G.isMaximal( 1 ) );
196 BOOST_CHECK( G.isMaximal( 2 ) );
197 BOOST_CHECK( G.isMaximal( 3 ) );
198 BOOST_CHECK( G.isMaximal( 4 ) );
199 }
200
201
202 BOOST_AUTO_TEST_CASE( OperationsTest ) {
203 Var v0( 0, 2 );
204 Var v1( 1, 3 );
205 Var v2( 2, 2 );
206 Var v3( 3, 4 );
207 Var v4( 4, 2 );
208 VarSet v01( v0, v1 );
209 VarSet v02( v0, v2 );
210 VarSet v03( v0, v3 );
211 VarSet v04( v0, v4 );
212 VarSet v12( v1, v2 );
213 VarSet v13( v1, v3 );
214 VarSet v14( v1, v4 );
215 VarSet v23( v2, v3 );
216 VarSet v24( v2, v4 );
217 VarSet v34( v3, v4 );
218 VarSet v123 = v12 | v3;
219 std::vector<VarSet> cl;
220 cl.push_back( v01 );
221 cl.push_back( v12 );
222 cl.push_back( v123 );
223 cl.push_back( v34 );
224 cl.push_back( v04 );
225 ClusterGraph G( cl );
226
227 BipartiteGraph H( 5, 5 );
228 H.addEdge( 0, 0 );
229 H.addEdge( 1, 0 );
230 H.addEdge( 1, 1 );
231 H.addEdge( 2, 1 );
232 H.addEdge( 1, 2 );
233 H.addEdge( 2, 2 );
234 H.addEdge( 3, 2 );
235 H.addEdge( 3, 3 );
236 H.addEdge( 4, 3 );
237 H.addEdge( 0, 4 );
238 H.addEdge( 4, 4 );
239 BOOST_CHECK( G.bipGraph() == H );
240
241 G.eraseNonMaximal();
242 BOOST_CHECK_EQUAL( G.nrClusters(), 4 );
243 H.eraseNode2( 1 );
244 BOOST_CHECK( G.bipGraph() == H );
245 G.eraseSubsuming( 4 );
246 BOOST_CHECK_EQUAL( G.nrClusters(), 2 );
247 H.eraseNode2( 2 );
248 H.eraseNode2( 2 );
249 BOOST_CHECK( G.bipGraph() == H );
250 G.insert( v34 );
251 BOOST_CHECK_EQUAL( G.nrClusters(), 3 );
252 G.insert( v123 );
253 BOOST_CHECK_EQUAL( G.nrClusters(), 3 );
254 H.addNode2();
255 H.addEdge( 3, 2 );
256 H.addEdge( 4, 2 );
257 BOOST_CHECK( G.bipGraph() == H );
258 G.insert( v12 );
259 G.insert( v23 );
260 BOOST_CHECK_EQUAL( G.nrClusters(), 5 );
261 H.addNode2();
262 H.addNode2();
263 H.addEdge( 1, 3 );
264 H.addEdge( 2, 3 );
265 H.addEdge( 2, 4 );
266 H.addEdge( 3, 4 );
267 BOOST_CHECK( G.bipGraph() == H );
268 G.eraseNonMaximal();
269 BOOST_CHECK_EQUAL( G.nrClusters(), 3 );
270 H.eraseNode2( 3 );
271 H.eraseNode2( 3 );
272 BOOST_CHECK( G.bipGraph() == H );
273 G.eraseSubsuming( 2 );
274 BOOST_CHECK_EQUAL( G.nrClusters(), 2 );
275 H.eraseNode2( 1 );
276 BOOST_CHECK( G.bipGraph() == H );
277 G.eraseNonMaximal();
278 BOOST_CHECK_EQUAL( G.nrClusters(), 2 );
279 BOOST_CHECK( G.bipGraph() == H );
280 G.eraseSubsuming( 0 );
281 BOOST_CHECK_EQUAL( G.nrClusters(), 1 );
282 H.eraseNode2( 0 );
283 BOOST_CHECK( G.bipGraph() == H );
284 G.eraseSubsuming( 4 );
285 BOOST_CHECK_EQUAL( G.nrClusters(), 0 );
286 H.eraseNode2( 0 );
287 BOOST_CHECK( G.bipGraph() == H );
288 }
289
290
291 BOOST_AUTO_TEST_CASE( VarElimTest ) {
292 Var v0( 0, 2 );
293 Var v1( 1, 3 );
294 Var v2( 2, 2 );
295 Var v3( 3, 4 );
296 Var v4( 4, 2 );
297 VarSet v01( v0, v1 );
298 VarSet v02( v0, v2 );
299 VarSet v03( v0, v3 );
300 VarSet v04( v0, v4 );
301 VarSet v12( v1, v2 );
302 VarSet v13( v1, v3 );
303 VarSet v14( v1, v4 );
304 VarSet v23( v2, v3 );
305 VarSet v24( v2, v4 );
306 VarSet v34( v3, v4 );
307 VarSet v123 = v12 | v3;
308 std::vector<VarSet> cl;
309 cl.push_back( v01 );
310 cl.push_back( v12 );
311 cl.push_back( v123 );
312 cl.push_back( v34 );
313 cl.push_back( v04 );
314 ClusterGraph G( cl );
315 ClusterGraph Gorg = G;
316
317 BipartiteGraph H( 5, 5 );
318 H.addEdge( 0, 0 );
319 H.addEdge( 1, 0 );
320 H.addEdge( 1, 1 );
321 H.addEdge( 2, 1 );
322 H.addEdge( 1, 2 );
323 H.addEdge( 2, 2 );
324 H.addEdge( 3, 2 );
325 H.addEdge( 3, 3 );
326 H.addEdge( 4, 3 );
327 H.addEdge( 0, 4 );
328 H.addEdge( 4, 4 );
329 BOOST_CHECK( G.bipGraph() == H );
330
331 BOOST_CHECK_EQUAL( eliminationCost_MinFill( G, 0 ), 1 );
332 BOOST_CHECK_EQUAL( eliminationCost_MinFill( G, 1 ), 2 );
333 BOOST_CHECK_EQUAL( eliminationCost_MinFill( G, 2 ), 0 );
334 BOOST_CHECK_EQUAL( eliminationCost_MinFill( G, 3 ), 2 );
335 BOOST_CHECK_EQUAL( eliminationCost_MinFill( G, 4 ), 1 );
336 cl.clear();
337 cl.push_back( v123 );
338 cl.push_back( v01 | v4 );
339 cl.push_back( v13 | v4 );
340 cl.push_back( v34 );
341 cl.push_back( v4 );
342 BOOST_CHECK_EQUAL( G.VarElim( greedyVariableElimination( eliminationCost_MinFill ) ).clusters(), cl );
343
344 G = Gorg;
345 BOOST_CHECK_EQUAL( eliminationCost_WeightedMinFill( G, 0 ), 2*3 );
346 BOOST_CHECK_EQUAL( eliminationCost_WeightedMinFill( G, 1 ), 2*2+2*4 );
347 BOOST_CHECK_EQUAL( eliminationCost_WeightedMinFill( G, 2 ), 0 );
348 BOOST_CHECK_EQUAL( eliminationCost_WeightedMinFill( G, 3 ), 3*2+2*2 );
349 BOOST_CHECK_EQUAL( eliminationCost_WeightedMinFill( G, 4 ), 2*4 );
350 cl.clear();
351 cl.push_back( v123 );
352 cl.push_back( v01 | v4 );
353 cl.push_back( v13 | v4 );
354 cl.push_back( v34 );
355 cl.push_back( v4 );
356 BOOST_CHECK_EQUAL( G.VarElim( greedyVariableElimination( eliminationCost_WeightedMinFill ) ).clusters(), cl );
357
358 G = Gorg;
359 BOOST_CHECK_EQUAL( eliminationCost_MinNeighbors( G, 0 ), 2 );
360 BOOST_CHECK_EQUAL( eliminationCost_MinNeighbors( G, 1 ), 3 );
361 BOOST_CHECK_EQUAL( eliminationCost_MinNeighbors( G, 2 ), 2 );
362 BOOST_CHECK_EQUAL( eliminationCost_MinNeighbors( G, 3 ), 3 );
363 BOOST_CHECK_EQUAL( eliminationCost_MinNeighbors( G, 4 ), 2 );
364 cl.clear();
365 cl.push_back( v01 | v4 );
366 cl.push_back( v123 );
367 cl.push_back( v13 | v4 );
368 cl.push_back( v34 );
369 cl.push_back( v4 );
370 BOOST_CHECK_EQUAL( G.VarElim( greedyVariableElimination( eliminationCost_MinNeighbors ) ).clusters(), cl );
371
372 G = Gorg;
373 BOOST_CHECK_EQUAL( eliminationCost_MinWeight( G, 0 ), 3*2 );
374 BOOST_CHECK_EQUAL( eliminationCost_MinWeight( G, 1 ), 2*2*4 );
375 BOOST_CHECK_EQUAL( eliminationCost_MinWeight( G, 2 ), 3*4 );
376 BOOST_CHECK_EQUAL( eliminationCost_MinWeight( G, 3 ), 3*2*2 );
377 BOOST_CHECK_EQUAL( eliminationCost_MinWeight( G, 4 ), 2*4 );
378 cl.clear();
379 cl.push_back( v01 | v4 );
380 cl.push_back( v123 );
381 cl.push_back( v13 | v4 );
382 cl.push_back( v14 );
383 cl.push_back( v4 );
384 BOOST_CHECK_EQUAL( G.VarElim( greedyVariableElimination( eliminationCost_MinWeight ) ).clusters(), cl );
385
386 G = Gorg;
387 std::vector<Var> vs;
388 vs.push_back( v4 );
389 vs.push_back( v3 );
390 vs.push_back( v2 );
391 vs.push_back( v1 );
392 vs.push_back( v0 );
393 cl.clear();
394 cl.push_back( v03 | v4 );
395 cl.push_back( v01 | v23 );
396 cl.push_back( v01 | v2 );
397 cl.push_back( v01 );
398 cl.push_back( v0 );
399 BOOST_CHECK_EQUAL( G.VarElim( sequentialVariableElimination( vs ) ).clusters(), cl );
400 }
401
402
403 BOOST_AUTO_TEST_CASE( IOTest ) {
404 Var v0( 0, 2 );
405 Var v1( 1, 3 );
406 Var v2( 2, 2 );
407 Var v3( 3, 4 );
408 VarSet v01( v0, v1 );
409 VarSet v02( v0, v2 );
410 VarSet v03( v0, v3 );
411 VarSet v12( v1, v2 );
412 VarSet v13( v1, v3 );
413 VarSet v23( v2, v3 );
414 std::vector<VarSet> cl;
415 cl.push_back( v01 );
416 cl.push_back( v12 );
417 cl.push_back( v23 );
418 cl.push_back( v13 );
419 ClusterGraph G( cl );
420
421 std::stringstream ss;
422 ss << G;
423 std::string s;
424 getline( ss, s );
425 BOOST_CHECK_EQUAL( s, "({x0, x1}, {x1, x2}, {x2, x3}, {x1, x3})" );
426 }