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