Extended SWIG python interface (inspired by Kyle Ellrott): inference is possible...
[libdai.git] / tests / unit / clustergraph_test.cpp
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
9 #include <dai/clustergraph.h>
10 #include <vector>
11 #include <strstream>
12
13
14 using namespace dai;
15
16
17 const double tol = 1e-8;
18
19
20 #define BOOST_TEST_MODULE ClusterGraphTest
21
22
23 #include <boost/test/unit_test.hpp>
24 #include <boost/test/floating_point_comparison.hpp>
25
26
27 BOOST_AUTO_TEST_CASE( ConstructorsTest ) {
28 Var v0( 0, 2 );
29 Var v1( 1, 3 );
30 Var v2( 2, 2 );
31 Var v3( 3, 4 );
32
33 ClusterGraph G;
34 BOOST_CHECK_EQUAL( G.clusters(), std::vector<VarSet>() );
35 BOOST_CHECK( G.bipGraph() == BipartiteGraph() );
36 BOOST_CHECK_EQUAL( G.nrVars(), 0 );
37 BOOST_CHECK_EQUAL( G.nrClusters(), 0 );
38 #ifdef DAI_DEBUG
39 BOOST_CHECK_THROW( G.var( 0 ), Exception );
40 BOOST_CHECK_THROW( G.cluster( 0 ), Exception );
41 #endif
42 BOOST_CHECK_EQUAL( G.findVar( v0 ), 0 );
43 BOOST_CHECK_EQUAL( G.findCluster( v0 ), 0 );
44 BOOST_CHECK_EQUAL( G.findCluster( VarSet(v0,v1) ), 0 );
45
46 std::vector<Var> vs;
47 vs.push_back( v0 );
48 vs.push_back( v1 );
49 vs.push_back( v2 );
50 vs.push_back( v3 );
51 VarSet v01( v0, v1 );
52 VarSet v02( v0, v2 );
53 VarSet v03( v0, v3 );
54 VarSet v12( v1, v2 );
55 VarSet v13( v1, v3 );
56 VarSet v23( v2, v3 );
57 std::vector<VarSet> cl;
58 cl.push_back( v01 );
59 cl.push_back( v12 );
60 cl.push_back( v23 );
61 cl.push_back( v13 );
62 ClusterGraph G2( cl );
63 BOOST_CHECK_EQUAL( G2.nrVars(), 4 );
64 BOOST_CHECK_EQUAL( G2.nrClusters(), 4 );
65 BOOST_CHECK_EQUAL( G2.vars(), vs );
66 BOOST_CHECK_EQUAL( G2.clusters(), cl );
67 BOOST_CHECK_EQUAL( G2.findVar( v0 ), 0 );
68 BOOST_CHECK_EQUAL( G2.findVar( v1 ), 1 );
69 BOOST_CHECK_EQUAL( G2.findVar( v2 ), 2 );
70 BOOST_CHECK_EQUAL( G2.findVar( v3 ), 3 );
71 BOOST_CHECK_EQUAL( G2.findVar( Var(4, 2) ), 4 );
72 BOOST_CHECK_EQUAL( G2.findCluster( v01 ), 0 );
73 BOOST_CHECK_EQUAL( G2.findCluster( v12 ), 1 );
74 BOOST_CHECK_EQUAL( G2.findCluster( v23 ), 2 );
75 BOOST_CHECK_EQUAL( G2.findCluster( v13 ), 3 );
76 BOOST_CHECK_EQUAL( G2.findCluster( v02 ), 4 );
77 BOOST_CHECK_EQUAL( G2.findCluster( v03 ), 4 );
78
79 ClusterGraph Gb( G );
80 BOOST_CHECK( G.bipGraph() == Gb.bipGraph() );
81 BOOST_CHECK( G.vars() == Gb.vars() );
82 BOOST_CHECK( G.clusters() == Gb.clusters() );
83
84 ClusterGraph Gc = G;
85 BOOST_CHECK( G.bipGraph() == Gc.bipGraph() );
86 BOOST_CHECK( G.vars() == Gc.vars() );
87 BOOST_CHECK( G.clusters() == Gc.clusters() );
88
89 ClusterGraph G2b( G2 );
90 BOOST_CHECK( G2.bipGraph() == G2b.bipGraph() );
91 BOOST_CHECK( G2.vars() == G2b.vars() );
92 BOOST_CHECK( G2.clusters() == G2b.clusters() );
93
94 ClusterGraph G2c = G2;
95 BOOST_CHECK( G2.bipGraph() == G2c.bipGraph() );
96 BOOST_CHECK( G2.vars() == G2c.vars() );
97 BOOST_CHECK( G2.clusters() == G2c.clusters() );
98
99 std::vector<Factor> facs;
100 facs.push_back( Factor( v01 ) );
101 facs.push_back( Factor( v12 ) );
102 facs.push_back( Factor( v1 ) );
103 facs.push_back( Factor( v2 ) );
104 facs.push_back( Factor( v23 ) );
105 facs.push_back( Factor( v13 ) );
106 FactorGraph F3( facs );
107 ClusterGraph G3( F3, false );
108 BOOST_CHECK_EQUAL( G3.bipGraph(), F3.bipGraph() );
109 BOOST_CHECK_EQUAL( G3.nrVars(), F3.nrVars() );
110 for( size_t i = 0; i < 4; i++ )
111 BOOST_CHECK_EQUAL( G3.var(i), F3.var(i) );
112 BOOST_CHECK_EQUAL( G3.vars(), F3.vars() );
113 BOOST_CHECK_EQUAL( G3.nrClusters(), F3.nrFactors() );
114 for( size_t I = 0; I < 6; I++ )
115 BOOST_CHECK_EQUAL( G3.cluster(I), F3.factor(I).vars() );
116
117 ClusterGraph G4( FactorGraph( facs ), true );
118 BOOST_CHECK_EQUAL( G4.nrVars(), 4 );
119 BOOST_CHECK_EQUAL( G4.var(0), v0 );
120 BOOST_CHECK_EQUAL( G4.var(1), v1 );
121 BOOST_CHECK_EQUAL( G4.var(2), v2 );
122 BOOST_CHECK_EQUAL( G4.var(3), v3 );
123 BOOST_CHECK_EQUAL( G4.nrClusters(), 4 );
124 BOOST_CHECK_EQUAL( G4.cluster(0), v01 );
125 BOOST_CHECK_EQUAL( G4.cluster(1), v12 );
126 BOOST_CHECK_EQUAL( G4.cluster(2), v23 );
127 BOOST_CHECK_EQUAL( G4.cluster(3), v13 );
128 std::vector<Edge> edges;
129 edges.push_back( Edge(0, 0) );
130 edges.push_back( Edge(1, 0) );
131 edges.push_back( Edge(1, 1) );
132 edges.push_back( Edge(1, 3) );
133 edges.push_back( Edge(2, 1) );
134 edges.push_back( Edge(2, 2) );
135 edges.push_back( Edge(3, 2) );
136 edges.push_back( Edge(3, 3) );
137 BipartiteGraph G4G( 4, 4, edges.begin(), edges.end() );
138 BOOST_CHECK_EQUAL( G4.bipGraph(), G4G );
139 }
140
141
142 BOOST_AUTO_TEST_CASE( QueriesTest ) {
143 Var v0( 0, 2 );
144 Var v1( 1, 3 );
145 Var v2( 2, 2 );
146 Var v3( 3, 4 );
147 Var v4( 4, 2 );
148 std::vector<Var> vs;
149 vs.push_back( v0 );
150 vs.push_back( v1 );
151 vs.push_back( v2 );
152 vs.push_back( v3 );
153 vs.push_back( v4 );
154 VarSet v01( v0, v1 );
155 VarSet v02( v0, v2 );
156 VarSet v03( v0, v3 );
157 VarSet v04( v0, v4 );
158 VarSet v12( v1, v2 );
159 VarSet v13( v1, v3 );
160 VarSet v14( v1, v4 );
161 VarSet v23( v2, v3 );
162 VarSet v24( v2, v4 );
163 VarSet v34( v3, v4 );
164 VarSet v123 = v12 | v3;
165 std::vector<VarSet> cl;
166 cl.push_back( v01 );
167 cl.push_back( v12 );
168 cl.push_back( v123 );
169 cl.push_back( v34 );
170 cl.push_back( v04 );
171 ClusterGraph G( cl );
172
173 BOOST_CHECK_EQUAL( G.nrVars(), 5 );
174 BOOST_CHECK_EQUAL( G.vars(), vs );
175 BOOST_CHECK_EQUAL( G.var(0), v0 );
176 BOOST_CHECK_EQUAL( G.var(1), v1 );
177 BOOST_CHECK_EQUAL( G.var(2), v2 );
178 BOOST_CHECK_EQUAL( G.var(3), v3 );
179 BOOST_CHECK_EQUAL( G.var(4), v4 );
180 BOOST_CHECK_EQUAL( G.nrClusters(), 5 );
181 BOOST_CHECK_EQUAL( G.clusters(), cl );
182 BOOST_CHECK_EQUAL( G.cluster(0), v01 );
183 BOOST_CHECK_EQUAL( G.cluster(1), v12 );
184 BOOST_CHECK_EQUAL( G.cluster(2), v123 );
185 BOOST_CHECK_EQUAL( G.cluster(3), v34 );
186 BOOST_CHECK_EQUAL( G.cluster(4), v04 );
187 BOOST_CHECK_EQUAL( G.findVar( v0 ), 0 );
188 BOOST_CHECK_EQUAL( G.findVar( v1 ), 1 );
189 BOOST_CHECK_EQUAL( G.findVar( v2 ), 2 );
190 BOOST_CHECK_EQUAL( G.findVar( v3 ), 3 );
191 BOOST_CHECK_EQUAL( G.findVar( v4 ), 4 );
192 BOOST_CHECK_EQUAL( G.findCluster( v01 ), 0 );
193 BOOST_CHECK_EQUAL( G.findCluster( v12 ), 1 );
194 BOOST_CHECK_EQUAL( G.findCluster( v123 ), 2 );
195 BOOST_CHECK_EQUAL( G.findCluster( v34 ), 3 );
196 BOOST_CHECK_EQUAL( G.findCluster( v04 ), 4 );
197 BOOST_CHECK_EQUAL( G.findCluster( v02 ), 5 );
198 BOOST_CHECK_EQUAL( G.findCluster( v03 ), 5 );
199 BOOST_CHECK_EQUAL( G.findCluster( v13 ), 5 );
200 BOOST_CHECK_EQUAL( G.findCluster( v14 ), 5 );
201 BOOST_CHECK_EQUAL( G.findCluster( v23 ), 5 );
202 BOOST_CHECK_EQUAL( G.findCluster( v24 ), 5 );
203 BipartiteGraph H( 5, 5 );
204 H.addEdge( 0, 0 );
205 H.addEdge( 1, 0 );
206 H.addEdge( 1, 1 );
207 H.addEdge( 2, 1 );
208 H.addEdge( 1, 2 );
209 H.addEdge( 2, 2 );
210 H.addEdge( 3, 2 );
211 H.addEdge( 3, 3 );
212 H.addEdge( 4, 3 );
213 H.addEdge( 0, 4 );
214 H.addEdge( 4, 4 );
215 BOOST_CHECK( G.bipGraph() == H );
216
217 BOOST_CHECK_EQUAL( G.delta( 0 ), v14 );
218 BOOST_CHECK_EQUAL( G.delta( 1 ), v02 | v3 );
219 BOOST_CHECK_EQUAL( G.delta( 2 ), v13 );
220 BOOST_CHECK_EQUAL( G.delta( 3 ), v12 | v4 );
221 BOOST_CHECK_EQUAL( G.delta( 4 ), v03 );
222 BOOST_CHECK_EQUAL( G.Delta( 0 ), v14 | v0 );
223 BOOST_CHECK_EQUAL( G.Delta( 1 ), v01 | v23 );
224 BOOST_CHECK_EQUAL( G.Delta( 2 ), v13 | v2 );
225 BOOST_CHECK_EQUAL( G.Delta( 3 ), v12 | v34 );
226 BOOST_CHECK_EQUAL( G.Delta( 4 ), v03 | v4 );
227
228 BOOST_CHECK( !G.adj( 0, 0 ) );
229 BOOST_CHECK( G.adj( 0, 1 ) );
230 BOOST_CHECK( !G.adj( 0, 2 ) );
231 BOOST_CHECK( !G.adj( 0, 3 ) );
232 BOOST_CHECK( G.adj( 0, 4 ) );
233 BOOST_CHECK( G.adj( 1, 0 ) );
234 BOOST_CHECK( !G.adj( 1, 1 ) );
235 BOOST_CHECK( G.adj( 1, 2 ) );
236 BOOST_CHECK( G.adj( 1, 3 ) );
237 BOOST_CHECK( !G.adj( 1, 4 ) );
238 BOOST_CHECK( !G.adj( 2, 0 ) );
239 BOOST_CHECK( G.adj( 2, 1 ) );
240 BOOST_CHECK( !G.adj( 2, 2 ) );
241 BOOST_CHECK( G.adj( 2, 3 ) );
242 BOOST_CHECK( !G.adj( 2, 4 ) );
243 BOOST_CHECK( !G.adj( 3, 0 ) );
244 BOOST_CHECK( G.adj( 3, 1 ) );
245 BOOST_CHECK( G.adj( 3, 2 ) );
246 BOOST_CHECK( !G.adj( 3, 3 ) );
247 BOOST_CHECK( G.adj( 3, 4 ) );
248 BOOST_CHECK( G.adj( 4, 0 ) );
249 BOOST_CHECK( !G.adj( 4, 1 ) );
250 BOOST_CHECK( !G.adj( 4, 2 ) );
251 BOOST_CHECK( G.adj( 4, 3 ) );
252 BOOST_CHECK( !G.adj( 4, 4 ) );
253
254 BOOST_CHECK( G.isMaximal( 0 ) );
255 BOOST_CHECK( !G.isMaximal( 1 ) );
256 BOOST_CHECK( G.isMaximal( 2 ) );
257 BOOST_CHECK( G.isMaximal( 3 ) );
258 BOOST_CHECK( G.isMaximal( 4 ) );
259 }
260
261
262 BOOST_AUTO_TEST_CASE( OperationsTest ) {
263 Var v0( 0, 2 );
264 Var v1( 1, 3 );
265 Var v2( 2, 2 );
266 Var v3( 3, 4 );
267 Var v4( 4, 2 );
268 VarSet v01( v0, v1 );
269 VarSet v02( v0, v2 );
270 VarSet v03( v0, v3 );
271 VarSet v04( v0, v4 );
272 VarSet v12( v1, v2 );
273 VarSet v13( v1, v3 );
274 VarSet v14( v1, v4 );
275 VarSet v23( v2, v3 );
276 VarSet v24( v2, v4 );
277 VarSet v34( v3, v4 );
278 VarSet v123 = v12 | v3;
279 std::vector<VarSet> cl;
280 cl.push_back( v01 );
281 cl.push_back( v12 );
282 cl.push_back( v123 );
283 cl.push_back( v34 );
284 cl.push_back( v04 );
285 ClusterGraph G( cl );
286
287 BipartiteGraph H( 5, 5 );
288 H.addEdge( 0, 0 );
289 H.addEdge( 1, 0 );
290 H.addEdge( 1, 1 );
291 H.addEdge( 2, 1 );
292 H.addEdge( 1, 2 );
293 H.addEdge( 2, 2 );
294 H.addEdge( 3, 2 );
295 H.addEdge( 3, 3 );
296 H.addEdge( 4, 3 );
297 H.addEdge( 0, 4 );
298 H.addEdge( 4, 4 );
299 BOOST_CHECK( G.bipGraph() == H );
300
301 G.eraseNonMaximal();
302 BOOST_CHECK_EQUAL( G.nrClusters(), 4 );
303 H.eraseNode2( 1 );
304 BOOST_CHECK( G.bipGraph() == H );
305 G.eraseSubsuming( 4 );
306 BOOST_CHECK_EQUAL( G.nrClusters(), 2 );
307 H.eraseNode2( 2 );
308 H.eraseNode2( 2 );
309 BOOST_CHECK( G.bipGraph() == H );
310 G.insert( v34 );
311 BOOST_CHECK_EQUAL( G.nrClusters(), 3 );
312 G.insert( v123 );
313 BOOST_CHECK_EQUAL( G.nrClusters(), 3 );
314 H.addNode2();
315 H.addEdge( 3, 2 );
316 H.addEdge( 4, 2 );
317 BOOST_CHECK( G.bipGraph() == H );
318 G.insert( v12 );
319 G.insert( v23 );
320 BOOST_CHECK_EQUAL( G.nrClusters(), 5 );
321 H.addNode2();
322 H.addNode2();
323 H.addEdge( 1, 3 );
324 H.addEdge( 2, 3 );
325 H.addEdge( 2, 4 );
326 H.addEdge( 3, 4 );
327 BOOST_CHECK( G.bipGraph() == H );
328 G.eraseNonMaximal();
329 BOOST_CHECK_EQUAL( G.nrClusters(), 3 );
330 H.eraseNode2( 3 );
331 H.eraseNode2( 3 );
332 BOOST_CHECK( G.bipGraph() == H );
333 G.eraseSubsuming( 2 );
334 BOOST_CHECK_EQUAL( G.nrClusters(), 2 );
335 H.eraseNode2( 1 );
336 BOOST_CHECK( G.bipGraph() == H );
337 G.eraseNonMaximal();
338 BOOST_CHECK_EQUAL( G.nrClusters(), 2 );
339 BOOST_CHECK( G.bipGraph() == H );
340 G.eraseSubsuming( 0 );
341 BOOST_CHECK_EQUAL( G.nrClusters(), 1 );
342 H.eraseNode2( 0 );
343 BOOST_CHECK( G.bipGraph() == H );
344 G.eraseSubsuming( 4 );
345 BOOST_CHECK_EQUAL( G.nrClusters(), 0 );
346 H.eraseNode2( 0 );
347 BOOST_CHECK( G.bipGraph() == H );
348 }
349
350
351 BOOST_AUTO_TEST_CASE( VarElimTest ) {
352 Var v0( 0, 2 );
353 Var v1( 1, 3 );
354 Var v2( 2, 2 );
355 Var v3( 3, 4 );
356 Var v4( 4, 2 );
357 VarSet v01( v0, v1 );
358 VarSet v02( v0, v2 );
359 VarSet v03( v0, v3 );
360 VarSet v04( v0, v4 );
361 VarSet v12( v1, v2 );
362 VarSet v13( v1, v3 );
363 VarSet v14( v1, v4 );
364 VarSet v23( v2, v3 );
365 VarSet v24( v2, v4 );
366 VarSet v34( v3, v4 );
367 VarSet v123 = v12 | v3;
368 std::vector<VarSet> cl;
369 cl.push_back( v01 );
370 cl.push_back( v12 );
371 cl.push_back( v123 );
372 cl.push_back( v34 );
373 cl.push_back( v04 );
374 ClusterGraph G( cl );
375 ClusterGraph Gorg = G;
376
377 BipartiteGraph H( 5, 5 );
378 H.addEdge( 0, 0 );
379 H.addEdge( 1, 0 );
380 H.addEdge( 1, 1 );
381 H.addEdge( 2, 1 );
382 H.addEdge( 1, 2 );
383 H.addEdge( 2, 2 );
384 H.addEdge( 3, 2 );
385 H.addEdge( 3, 3 );
386 H.addEdge( 4, 3 );
387 H.addEdge( 0, 4 );
388 H.addEdge( 4, 4 );
389 BOOST_CHECK( G.bipGraph() == H );
390
391 G = Gorg;
392 BOOST_CHECK_EQUAL( G.elimVar( 0 ), v14 | v0 );
393 BOOST_CHECK_EQUAL( G.vars(), Gorg.vars() );
394 BOOST_CHECK_EQUAL( G.nrClusters(), 3 );
395 BOOST_CHECK_EQUAL( G.cluster(0), v123 );
396 BOOST_CHECK_EQUAL( G.cluster(1), v34 );
397 BOOST_CHECK_EQUAL( G.cluster(2), v14 );
398 BipartiteGraph H_0( 5, 3 );
399 H_0.addEdge( 1, 0 ); H_0.addEdge( 2, 0 ); H_0.addEdge( 3, 0 ); H_0.addEdge( 3, 1 ); H_0.addEdge( 4, 1 ); H_0.addEdge( 1, 2 ); H_0.addEdge( 4, 2 );
400 BOOST_CHECK( G.bipGraph() == H_0 );
401
402 G = Gorg;
403 BOOST_CHECK_EQUAL( G.elimVar( 1 ), v01 | v23 );
404 BOOST_CHECK_EQUAL( G.vars(), Gorg.vars() );
405 BOOST_CHECK_EQUAL( G.nrClusters(), 3 );
406 BOOST_CHECK_EQUAL( G.cluster(0), v34 );
407 BOOST_CHECK_EQUAL( G.cluster(1), v04 );
408 BOOST_CHECK_EQUAL( G.cluster(2), v02 | v3 );
409 BipartiteGraph H_1( 5, 3 );
410 H_1.addEdge( 3, 0 ); H_1.addEdge( 4, 0 ); H_1.addEdge( 0, 1 ); H_1.addEdge( 4, 1 ); H_1.addEdge( 0, 2 ); H_1.addEdge( 2, 2 ); H_1.addEdge( 3, 2 );
411 BOOST_CHECK( G.bipGraph() == H_1 );
412
413 G = Gorg;
414 BOOST_CHECK_EQUAL( G.elimVar( 2 ), v123 );
415 BOOST_CHECK_EQUAL( G.vars(), Gorg.vars() );
416 BOOST_CHECK_EQUAL( G.nrClusters(), 4 );
417 BOOST_CHECK_EQUAL( G.cluster(0), v01 );
418 BOOST_CHECK_EQUAL( G.cluster(1), v34 );
419 BOOST_CHECK_EQUAL( G.cluster(2), v04 );
420 BOOST_CHECK_EQUAL( G.cluster(3), v13 );
421 BipartiteGraph H_2( 5, 4 );
422 H_2.addEdge( 0, 0 ); H_2.addEdge( 1, 0 ); H_2.addEdge( 3, 1 ); H_2.addEdge( 4, 1 ); H_2.addEdge( 0, 2 ); H_2.addEdge( 4, 2 ); H_2.addEdge( 1, 3 ); H_2.addEdge( 3, 3 );
423 BOOST_CHECK( G.bipGraph() == H_2 );
424
425 G = Gorg;
426 BOOST_CHECK_EQUAL( G.elimVar( 3 ), v12 | v34 );
427 BOOST_CHECK_EQUAL( G.vars(), Gorg.vars() );
428 BOOST_CHECK_EQUAL( G.nrClusters(), 3 );
429 BOOST_CHECK_EQUAL( G.cluster(0), v01 );
430 BOOST_CHECK_EQUAL( G.cluster(1), v04 );
431 BOOST_CHECK_EQUAL( G.cluster(2), v12 | v4 );
432 BipartiteGraph H_3( 5, 3 );
433 H_3.addEdge( 0, 0 ); H_3.addEdge( 1, 0 ); H_3.addEdge( 0, 1 ); H_3.addEdge( 4, 1 ); H_3.addEdge( 1, 2 ); H_3.addEdge( 2, 2 ); H_3.addEdge( 4, 2 );
434 BOOST_CHECK( G.bipGraph() == H_3 );
435
436 G = Gorg;
437 BOOST_CHECK_EQUAL( G.elimVar( 4 ), v03 | v4 );
438 BOOST_CHECK_EQUAL( G.vars(), Gorg.vars() );
439 BOOST_CHECK_EQUAL( G.nrClusters(), 3 );
440 BOOST_CHECK_EQUAL( G.cluster(0), v01 );
441 BOOST_CHECK_EQUAL( G.cluster(1), v123 );
442 BOOST_CHECK_EQUAL( G.cluster(2), v03 );
443 BipartiteGraph H_4( 5, 3 );
444 H_4.addEdge( 0, 0 ); H_4.addEdge( 1, 0 ); H_4.addEdge( 1, 1 ); H_4.addEdge( 2, 1 ); H_4.addEdge( 3, 1 ); H_4.addEdge( 0, 2 ); H_4.addEdge( 3, 2 );
445 BOOST_CHECK( G.bipGraph() == H_4 );
446
447 G = Gorg;
448 BOOST_CHECK_EQUAL( eliminationCost_MinFill( G, 0 ), 1 );
449 BOOST_CHECK_EQUAL( eliminationCost_MinFill( G, 1 ), 2 );
450 BOOST_CHECK_EQUAL( eliminationCost_MinFill( G, 2 ), 0 );
451 BOOST_CHECK_EQUAL( eliminationCost_MinFill( G, 3 ), 2 );
452 BOOST_CHECK_EQUAL( eliminationCost_MinFill( G, 4 ), 1 );
453 cl.clear();
454 cl.push_back( v123 );
455 cl.push_back( v01 | v4 );
456 cl.push_back( v13 | v4 );
457 cl.push_back( v34 );
458 cl.push_back( v4 );
459 BOOST_CHECK_EQUAL( G.VarElim( greedyVariableElimination( eliminationCost_MinFill ) ).clusters(), cl );
460
461 G = Gorg;
462 BOOST_CHECK_EQUAL( eliminationCost_WeightedMinFill( G, 0 ), 2*3 );
463 BOOST_CHECK_EQUAL( eliminationCost_WeightedMinFill( G, 1 ), 2*2+2*4 );
464 BOOST_CHECK_EQUAL( eliminationCost_WeightedMinFill( G, 2 ), 0 );
465 BOOST_CHECK_EQUAL( eliminationCost_WeightedMinFill( G, 3 ), 3*2+2*2 );
466 BOOST_CHECK_EQUAL( eliminationCost_WeightedMinFill( G, 4 ), 2*4 );
467 cl.clear();
468 cl.push_back( v123 );
469 cl.push_back( v01 | v4 );
470 cl.push_back( v13 | v4 );
471 cl.push_back( v34 );
472 cl.push_back( v4 );
473 BOOST_CHECK_EQUAL( G.VarElim( greedyVariableElimination( eliminationCost_WeightedMinFill ) ).clusters(), cl );
474
475 G = Gorg;
476 BOOST_CHECK_EQUAL( eliminationCost_MinNeighbors( G, 0 ), 2 );
477 BOOST_CHECK_EQUAL( eliminationCost_MinNeighbors( G, 1 ), 3 );
478 BOOST_CHECK_EQUAL( eliminationCost_MinNeighbors( G, 2 ), 2 );
479 BOOST_CHECK_EQUAL( eliminationCost_MinNeighbors( G, 3 ), 3 );
480 BOOST_CHECK_EQUAL( eliminationCost_MinNeighbors( G, 4 ), 2 );
481 cl.clear();
482 cl.push_back( v01 | v4 );
483 cl.push_back( v123 );
484 cl.push_back( v13 | v4 );
485 cl.push_back( v34 );
486 cl.push_back( v4 );
487 BOOST_CHECK_EQUAL( G.VarElim( greedyVariableElimination( eliminationCost_MinNeighbors ) ).clusters(), cl );
488
489 G = Gorg;
490 BOOST_CHECK_EQUAL( eliminationCost_MinWeight( G, 0 ), 3*2 );
491 BOOST_CHECK_EQUAL( eliminationCost_MinWeight( G, 1 ), 2*2*4 );
492 BOOST_CHECK_EQUAL( eliminationCost_MinWeight( G, 2 ), 3*4 );
493 BOOST_CHECK_EQUAL( eliminationCost_MinWeight( G, 3 ), 3*2*2 );
494 BOOST_CHECK_EQUAL( eliminationCost_MinWeight( G, 4 ), 2*4 );
495 cl.clear();
496 cl.push_back( v01 | v4 );
497 cl.push_back( v123 );
498 cl.push_back( v13 | v4 );
499 cl.push_back( v14 );
500 cl.push_back( v4 );
501 BOOST_CHECK_EQUAL( G.VarElim( greedyVariableElimination( eliminationCost_MinWeight ) ).clusters(), cl );
502
503 G = Gorg;
504 std::vector<Var> vs;
505 vs.push_back( v4 );
506 vs.push_back( v3 );
507 vs.push_back( v2 );
508 vs.push_back( v1 );
509 vs.push_back( v0 );
510 cl.clear();
511 cl.push_back( v03 | v4 );
512 cl.push_back( v01 | v23 );
513 cl.push_back( v01 | v2 );
514 cl.push_back( v01 );
515 cl.push_back( v0 );
516 BOOST_CHECK_EQUAL( G.VarElim( sequentialVariableElimination( vs ) ).clusters(), cl );
517 }
518
519
520 BOOST_AUTO_TEST_CASE( IOTest ) {
521 Var v0( 0, 2 );
522 Var v1( 1, 3 );
523 Var v2( 2, 2 );
524 Var v3( 3, 4 );
525 VarSet v01( v0, v1 );
526 VarSet v02( v0, v2 );
527 VarSet v03( v0, v3 );
528 VarSet v12( v1, v2 );
529 VarSet v13( v1, v3 );
530 VarSet v23( v2, v3 );
531 std::vector<VarSet> cl;
532 cl.push_back( v01 );
533 cl.push_back( v12 );
534 cl.push_back( v23 );
535 cl.push_back( v13 );
536 ClusterGraph G( cl );
537
538 std::stringstream ss;
539 ss << G;
540 std::string s;
541 getline( ss, s );
542 BOOST_CHECK_EQUAL( s, "({x0, x1}, {x1, x2}, {x2, x3}, {x1, x3})" );
543
544 BOOST_CHECK_EQUAL( G.toString(), "({x0, x1}, {x1, x2}, {x2, x3}, {x1, x3})" );
545 }