Improved ClusterGraph and JTree (added 'maxmem' property)
[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 typedef BipartiteGraph::Edge Edge;
131 std::vector<Edge> edges;
132 edges.push_back( Edge(0, 0) );
133 edges.push_back( Edge(1, 0) );
134 edges.push_back( Edge(1, 1) );
135 edges.push_back( Edge(1, 3) );
136 edges.push_back( Edge(2, 1) );
137 edges.push_back( Edge(2, 2) );
138 edges.push_back( Edge(3, 2) );
139 edges.push_back( Edge(3, 3) );
140 BipartiteGraph G4G( 4, 4, edges.begin(), edges.end() );
141 BOOST_CHECK_EQUAL( G4.bipGraph(), G4G );
142 }
143
144
145 BOOST_AUTO_TEST_CASE( QueriesTest ) {
146 Var v0( 0, 2 );
147 Var v1( 1, 3 );
148 Var v2( 2, 2 );
149 Var v3( 3, 4 );
150 Var v4( 4, 2 );
151 std::vector<Var> vs;
152 vs.push_back( v0 );
153 vs.push_back( v1 );
154 vs.push_back( v2 );
155 vs.push_back( v3 );
156 vs.push_back( v4 );
157 VarSet v01( v0, v1 );
158 VarSet v02( v0, v2 );
159 VarSet v03( v0, v3 );
160 VarSet v04( v0, v4 );
161 VarSet v12( v1, v2 );
162 VarSet v13( v1, v3 );
163 VarSet v14( v1, v4 );
164 VarSet v23( v2, v3 );
165 VarSet v24( v2, v4 );
166 VarSet v34( v3, v4 );
167 VarSet v123 = v12 | v3;
168 std::vector<VarSet> cl;
169 cl.push_back( v01 );
170 cl.push_back( v12 );
171 cl.push_back( v123 );
172 cl.push_back( v34 );
173 cl.push_back( v04 );
174 ClusterGraph G( cl );
175
176 BOOST_CHECK_EQUAL( G.nrVars(), 5 );
177 BOOST_CHECK_EQUAL( G.vars(), vs );
178 BOOST_CHECK_EQUAL( G.var(0), v0 );
179 BOOST_CHECK_EQUAL( G.var(1), v1 );
180 BOOST_CHECK_EQUAL( G.var(2), v2 );
181 BOOST_CHECK_EQUAL( G.var(3), v3 );
182 BOOST_CHECK_EQUAL( G.var(4), v4 );
183 BOOST_CHECK_EQUAL( G.nrClusters(), 5 );
184 BOOST_CHECK_EQUAL( G.clusters(), cl );
185 BOOST_CHECK_EQUAL( G.cluster(0), v01 );
186 BOOST_CHECK_EQUAL( G.cluster(1), v12 );
187 BOOST_CHECK_EQUAL( G.cluster(2), v123 );
188 BOOST_CHECK_EQUAL( G.cluster(3), v34 );
189 BOOST_CHECK_EQUAL( G.cluster(4), v04 );
190 BOOST_CHECK_EQUAL( G.findVar( v0 ), 0 );
191 BOOST_CHECK_EQUAL( G.findVar( v1 ), 1 );
192 BOOST_CHECK_EQUAL( G.findVar( v2 ), 2 );
193 BOOST_CHECK_EQUAL( G.findVar( v3 ), 3 );
194 BOOST_CHECK_EQUAL( G.findVar( v4 ), 4 );
195 BOOST_CHECK_EQUAL( G.findCluster( v01 ), 0 );
196 BOOST_CHECK_EQUAL( G.findCluster( v12 ), 1 );
197 BOOST_CHECK_EQUAL( G.findCluster( v123 ), 2 );
198 BOOST_CHECK_EQUAL( G.findCluster( v34 ), 3 );
199 BOOST_CHECK_EQUAL( G.findCluster( v04 ), 4 );
200 BOOST_CHECK_EQUAL( G.findCluster( v02 ), 5 );
201 BOOST_CHECK_EQUAL( G.findCluster( v03 ), 5 );
202 BOOST_CHECK_EQUAL( G.findCluster( v13 ), 5 );
203 BOOST_CHECK_EQUAL( G.findCluster( v14 ), 5 );
204 BOOST_CHECK_EQUAL( G.findCluster( v23 ), 5 );
205 BOOST_CHECK_EQUAL( G.findCluster( v24 ), 5 );
206 BipartiteGraph H( 5, 5 );
207 H.addEdge( 0, 0 );
208 H.addEdge( 1, 0 );
209 H.addEdge( 1, 1 );
210 H.addEdge( 2, 1 );
211 H.addEdge( 1, 2 );
212 H.addEdge( 2, 2 );
213 H.addEdge( 3, 2 );
214 H.addEdge( 3, 3 );
215 H.addEdge( 4, 3 );
216 H.addEdge( 0, 4 );
217 H.addEdge( 4, 4 );
218 BOOST_CHECK( G.bipGraph() == H );
219
220 BOOST_CHECK_EQUAL( G.delta( 0 ), v14 );
221 BOOST_CHECK_EQUAL( G.delta( 1 ), v02 | v3 );
222 BOOST_CHECK_EQUAL( G.delta( 2 ), v13 );
223 BOOST_CHECK_EQUAL( G.delta( 3 ), v12 | v4 );
224 BOOST_CHECK_EQUAL( G.delta( 4 ), v03 );
225 BOOST_CHECK_EQUAL( G.Delta( 0 ), v14 | v0 );
226 BOOST_CHECK_EQUAL( G.Delta( 1 ), v01 | v23 );
227 BOOST_CHECK_EQUAL( G.Delta( 2 ), v13 | v2 );
228 BOOST_CHECK_EQUAL( G.Delta( 3 ), v12 | v34 );
229 BOOST_CHECK_EQUAL( G.Delta( 4 ), v03 | v4 );
230
231 BOOST_CHECK( !G.adj( 0, 0 ) );
232 BOOST_CHECK( G.adj( 0, 1 ) );
233 BOOST_CHECK( !G.adj( 0, 2 ) );
234 BOOST_CHECK( !G.adj( 0, 3 ) );
235 BOOST_CHECK( G.adj( 0, 4 ) );
236 BOOST_CHECK( G.adj( 1, 0 ) );
237 BOOST_CHECK( !G.adj( 1, 1 ) );
238 BOOST_CHECK( G.adj( 1, 2 ) );
239 BOOST_CHECK( G.adj( 1, 3 ) );
240 BOOST_CHECK( !G.adj( 1, 4 ) );
241 BOOST_CHECK( !G.adj( 2, 0 ) );
242 BOOST_CHECK( G.adj( 2, 1 ) );
243 BOOST_CHECK( !G.adj( 2, 2 ) );
244 BOOST_CHECK( G.adj( 2, 3 ) );
245 BOOST_CHECK( !G.adj( 2, 4 ) );
246 BOOST_CHECK( !G.adj( 3, 0 ) );
247 BOOST_CHECK( G.adj( 3, 1 ) );
248 BOOST_CHECK( G.adj( 3, 2 ) );
249 BOOST_CHECK( !G.adj( 3, 3 ) );
250 BOOST_CHECK( G.adj( 3, 4 ) );
251 BOOST_CHECK( G.adj( 4, 0 ) );
252 BOOST_CHECK( !G.adj( 4, 1 ) );
253 BOOST_CHECK( !G.adj( 4, 2 ) );
254 BOOST_CHECK( G.adj( 4, 3 ) );
255 BOOST_CHECK( !G.adj( 4, 4 ) );
256
257 BOOST_CHECK( G.isMaximal( 0 ) );
258 BOOST_CHECK( !G.isMaximal( 1 ) );
259 BOOST_CHECK( G.isMaximal( 2 ) );
260 BOOST_CHECK( G.isMaximal( 3 ) );
261 BOOST_CHECK( G.isMaximal( 4 ) );
262 }
263
264
265 BOOST_AUTO_TEST_CASE( OperationsTest ) {
266 Var v0( 0, 2 );
267 Var v1( 1, 3 );
268 Var v2( 2, 2 );
269 Var v3( 3, 4 );
270 Var v4( 4, 2 );
271 VarSet v01( v0, v1 );
272 VarSet v02( v0, v2 );
273 VarSet v03( v0, v3 );
274 VarSet v04( v0, v4 );
275 VarSet v12( v1, v2 );
276 VarSet v13( v1, v3 );
277 VarSet v14( v1, v4 );
278 VarSet v23( v2, v3 );
279 VarSet v24( v2, v4 );
280 VarSet v34( v3, v4 );
281 VarSet v123 = v12 | v3;
282 std::vector<VarSet> cl;
283 cl.push_back( v01 );
284 cl.push_back( v12 );
285 cl.push_back( v123 );
286 cl.push_back( v34 );
287 cl.push_back( v04 );
288 ClusterGraph G( cl );
289
290 BipartiteGraph H( 5, 5 );
291 H.addEdge( 0, 0 );
292 H.addEdge( 1, 0 );
293 H.addEdge( 1, 1 );
294 H.addEdge( 2, 1 );
295 H.addEdge( 1, 2 );
296 H.addEdge( 2, 2 );
297 H.addEdge( 3, 2 );
298 H.addEdge( 3, 3 );
299 H.addEdge( 4, 3 );
300 H.addEdge( 0, 4 );
301 H.addEdge( 4, 4 );
302 BOOST_CHECK( G.bipGraph() == H );
303
304 G.eraseNonMaximal();
305 BOOST_CHECK_EQUAL( G.nrClusters(), 4 );
306 H.eraseNode2( 1 );
307 BOOST_CHECK( G.bipGraph() == H );
308 G.eraseSubsuming( 4 );
309 BOOST_CHECK_EQUAL( G.nrClusters(), 2 );
310 H.eraseNode2( 2 );
311 H.eraseNode2( 2 );
312 BOOST_CHECK( G.bipGraph() == H );
313 G.insert( v34 );
314 BOOST_CHECK_EQUAL( G.nrClusters(), 3 );
315 G.insert( v123 );
316 BOOST_CHECK_EQUAL( G.nrClusters(), 3 );
317 H.addNode2();
318 H.addEdge( 3, 2 );
319 H.addEdge( 4, 2 );
320 BOOST_CHECK( G.bipGraph() == H );
321 G.insert( v12 );
322 G.insert( v23 );
323 BOOST_CHECK_EQUAL( G.nrClusters(), 5 );
324 H.addNode2();
325 H.addNode2();
326 H.addEdge( 1, 3 );
327 H.addEdge( 2, 3 );
328 H.addEdge( 2, 4 );
329 H.addEdge( 3, 4 );
330 BOOST_CHECK( G.bipGraph() == H );
331 G.eraseNonMaximal();
332 BOOST_CHECK_EQUAL( G.nrClusters(), 3 );
333 H.eraseNode2( 3 );
334 H.eraseNode2( 3 );
335 BOOST_CHECK( G.bipGraph() == H );
336 G.eraseSubsuming( 2 );
337 BOOST_CHECK_EQUAL( G.nrClusters(), 2 );
338 H.eraseNode2( 1 );
339 BOOST_CHECK( G.bipGraph() == H );
340 G.eraseNonMaximal();
341 BOOST_CHECK_EQUAL( G.nrClusters(), 2 );
342 BOOST_CHECK( G.bipGraph() == H );
343 G.eraseSubsuming( 0 );
344 BOOST_CHECK_EQUAL( G.nrClusters(), 1 );
345 H.eraseNode2( 0 );
346 BOOST_CHECK( G.bipGraph() == H );
347 G.eraseSubsuming( 4 );
348 BOOST_CHECK_EQUAL( G.nrClusters(), 0 );
349 H.eraseNode2( 0 );
350 BOOST_CHECK( G.bipGraph() == H );
351 }
352
353
354 BOOST_AUTO_TEST_CASE( VarElimTest ) {
355 Var v0( 0, 2 );
356 Var v1( 1, 3 );
357 Var v2( 2, 2 );
358 Var v3( 3, 4 );
359 Var v4( 4, 2 );
360 VarSet v01( v0, v1 );
361 VarSet v02( v0, v2 );
362 VarSet v03( v0, v3 );
363 VarSet v04( v0, v4 );
364 VarSet v12( v1, v2 );
365 VarSet v13( v1, v3 );
366 VarSet v14( v1, v4 );
367 VarSet v23( v2, v3 );
368 VarSet v24( v2, v4 );
369 VarSet v34( v3, v4 );
370 VarSet v123 = v12 | v3;
371 std::vector<VarSet> cl;
372 cl.push_back( v01 );
373 cl.push_back( v12 );
374 cl.push_back( v123 );
375 cl.push_back( v34 );
376 cl.push_back( v04 );
377 ClusterGraph G( cl );
378 ClusterGraph Gorg = G;
379
380 BipartiteGraph H( 5, 5 );
381 H.addEdge( 0, 0 );
382 H.addEdge( 1, 0 );
383 H.addEdge( 1, 1 );
384 H.addEdge( 2, 1 );
385 H.addEdge( 1, 2 );
386 H.addEdge( 2, 2 );
387 H.addEdge( 3, 2 );
388 H.addEdge( 3, 3 );
389 H.addEdge( 4, 3 );
390 H.addEdge( 0, 4 );
391 H.addEdge( 4, 4 );
392 BOOST_CHECK( G.bipGraph() == H );
393
394 G = Gorg;
395 BOOST_CHECK_EQUAL( G.elimVar( 0 ), v14 | v0 );
396 BOOST_CHECK_EQUAL( G.vars(), Gorg.vars() );
397 BOOST_CHECK_EQUAL( G.nrClusters(), 3 );
398 BOOST_CHECK_EQUAL( G.cluster(0), v123 );
399 BOOST_CHECK_EQUAL( G.cluster(1), v34 );
400 BOOST_CHECK_EQUAL( G.cluster(2), v14 );
401 BipartiteGraph H_0( 5, 3 );
402 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 );
403 BOOST_CHECK( G.bipGraph() == H_0 );
404
405 G = Gorg;
406 BOOST_CHECK_EQUAL( G.elimVar( 1 ), v01 | v23 );
407 BOOST_CHECK_EQUAL( G.vars(), Gorg.vars() );
408 BOOST_CHECK_EQUAL( G.nrClusters(), 3 );
409 BOOST_CHECK_EQUAL( G.cluster(0), v34 );
410 BOOST_CHECK_EQUAL( G.cluster(1), v04 );
411 BOOST_CHECK_EQUAL( G.cluster(2), v02 | v3 );
412 BipartiteGraph H_1( 5, 3 );
413 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 );
414 BOOST_CHECK( G.bipGraph() == H_1 );
415
416 G = Gorg;
417 BOOST_CHECK_EQUAL( G.elimVar( 2 ), v123 );
418 BOOST_CHECK_EQUAL( G.vars(), Gorg.vars() );
419 BOOST_CHECK_EQUAL( G.nrClusters(), 4 );
420 BOOST_CHECK_EQUAL( G.cluster(0), v01 );
421 BOOST_CHECK_EQUAL( G.cluster(1), v34 );
422 BOOST_CHECK_EQUAL( G.cluster(2), v04 );
423 BOOST_CHECK_EQUAL( G.cluster(3), v13 );
424 BipartiteGraph H_2( 5, 4 );
425 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 );
426 BOOST_CHECK( G.bipGraph() == H_2 );
427
428 G = Gorg;
429 BOOST_CHECK_EQUAL( G.elimVar( 3 ), v12 | v34 );
430 BOOST_CHECK_EQUAL( G.vars(), Gorg.vars() );
431 BOOST_CHECK_EQUAL( G.nrClusters(), 3 );
432 BOOST_CHECK_EQUAL( G.cluster(0), v01 );
433 BOOST_CHECK_EQUAL( G.cluster(1), v04 );
434 BOOST_CHECK_EQUAL( G.cluster(2), v12 | v4 );
435 BipartiteGraph H_3( 5, 3 );
436 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 );
437 BOOST_CHECK( G.bipGraph() == H_3 );
438
439 G = Gorg;
440 BOOST_CHECK_EQUAL( G.elimVar( 4 ), v03 | v4 );
441 BOOST_CHECK_EQUAL( G.vars(), Gorg.vars() );
442 BOOST_CHECK_EQUAL( G.nrClusters(), 3 );
443 BOOST_CHECK_EQUAL( G.cluster(0), v01 );
444 BOOST_CHECK_EQUAL( G.cluster(1), v123 );
445 BOOST_CHECK_EQUAL( G.cluster(2), v03 );
446 BipartiteGraph H_4( 5, 3 );
447 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 );
448 BOOST_CHECK( G.bipGraph() == H_4 );
449
450 G = Gorg;
451 BOOST_CHECK_EQUAL( eliminationCost_MinFill( G, 0 ), 1 );
452 BOOST_CHECK_EQUAL( eliminationCost_MinFill( G, 1 ), 2 );
453 BOOST_CHECK_EQUAL( eliminationCost_MinFill( G, 2 ), 0 );
454 BOOST_CHECK_EQUAL( eliminationCost_MinFill( G, 3 ), 2 );
455 BOOST_CHECK_EQUAL( eliminationCost_MinFill( G, 4 ), 1 );
456 cl.clear();
457 cl.push_back( v123 );
458 cl.push_back( v01 | v4 );
459 cl.push_back( v13 | v4 );
460 cl.push_back( v34 );
461 cl.push_back( v4 );
462 BOOST_CHECK_EQUAL( G.VarElim( greedyVariableElimination( eliminationCost_MinFill ) ).clusters(), cl );
463
464 G = Gorg;
465 BOOST_CHECK_EQUAL( eliminationCost_WeightedMinFill( G, 0 ), 2*3 );
466 BOOST_CHECK_EQUAL( eliminationCost_WeightedMinFill( G, 1 ), 2*2+2*4 );
467 BOOST_CHECK_EQUAL( eliminationCost_WeightedMinFill( G, 2 ), 0 );
468 BOOST_CHECK_EQUAL( eliminationCost_WeightedMinFill( G, 3 ), 3*2+2*2 );
469 BOOST_CHECK_EQUAL( eliminationCost_WeightedMinFill( G, 4 ), 2*4 );
470 cl.clear();
471 cl.push_back( v123 );
472 cl.push_back( v01 | v4 );
473 cl.push_back( v13 | v4 );
474 cl.push_back( v34 );
475 cl.push_back( v4 );
476 BOOST_CHECK_EQUAL( G.VarElim( greedyVariableElimination( eliminationCost_WeightedMinFill ) ).clusters(), cl );
477
478 G = Gorg;
479 BOOST_CHECK_EQUAL( eliminationCost_MinNeighbors( G, 0 ), 2 );
480 BOOST_CHECK_EQUAL( eliminationCost_MinNeighbors( G, 1 ), 3 );
481 BOOST_CHECK_EQUAL( eliminationCost_MinNeighbors( G, 2 ), 2 );
482 BOOST_CHECK_EQUAL( eliminationCost_MinNeighbors( G, 3 ), 3 );
483 BOOST_CHECK_EQUAL( eliminationCost_MinNeighbors( G, 4 ), 2 );
484 cl.clear();
485 cl.push_back( v01 | v4 );
486 cl.push_back( v123 );
487 cl.push_back( v13 | v4 );
488 cl.push_back( v34 );
489 cl.push_back( v4 );
490 BOOST_CHECK_EQUAL( G.VarElim( greedyVariableElimination( eliminationCost_MinNeighbors ) ).clusters(), cl );
491
492 G = Gorg;
493 BOOST_CHECK_EQUAL( eliminationCost_MinWeight( G, 0 ), 3*2 );
494 BOOST_CHECK_EQUAL( eliminationCost_MinWeight( G, 1 ), 2*2*4 );
495 BOOST_CHECK_EQUAL( eliminationCost_MinWeight( G, 2 ), 3*4 );
496 BOOST_CHECK_EQUAL( eliminationCost_MinWeight( G, 3 ), 3*2*2 );
497 BOOST_CHECK_EQUAL( eliminationCost_MinWeight( G, 4 ), 2*4 );
498 cl.clear();
499 cl.push_back( v01 | v4 );
500 cl.push_back( v123 );
501 cl.push_back( v13 | v4 );
502 cl.push_back( v14 );
503 cl.push_back( v4 );
504 BOOST_CHECK_EQUAL( G.VarElim( greedyVariableElimination( eliminationCost_MinWeight ) ).clusters(), cl );
505
506 G = Gorg;
507 std::vector<Var> vs;
508 vs.push_back( v4 );
509 vs.push_back( v3 );
510 vs.push_back( v2 );
511 vs.push_back( v1 );
512 vs.push_back( v0 );
513 cl.clear();
514 cl.push_back( v03 | v4 );
515 cl.push_back( v01 | v23 );
516 cl.push_back( v01 | v2 );
517 cl.push_back( v01 );
518 cl.push_back( v0 );
519 BOOST_CHECK_EQUAL( G.VarElim( sequentialVariableElimination( vs ) ).clusters(), cl );
520 }
521
522
523 BOOST_AUTO_TEST_CASE( IOTest ) {
524 Var v0( 0, 2 );
525 Var v1( 1, 3 );
526 Var v2( 2, 2 );
527 Var v3( 3, 4 );
528 VarSet v01( v0, v1 );
529 VarSet v02( v0, v2 );
530 VarSet v03( v0, v3 );
531 VarSet v12( v1, v2 );
532 VarSet v13( v1, v3 );
533 VarSet v23( v2, v3 );
534 std::vector<VarSet> cl;
535 cl.push_back( v01 );
536 cl.push_back( v12 );
537 cl.push_back( v23 );
538 cl.push_back( v13 );
539 ClusterGraph G( cl );
540
541 std::stringstream ss;
542 ss << G;
543 std::string s;
544 getline( ss, s );
545 BOOST_CHECK_EQUAL( s, "({x0, x1}, {x1, x2}, {x2, x3}, {x1, x3})" );
546 }