Some improvements to jtree and regiongraph and started work on regiongraph unit tests
[libdai.git] / tests / unit / bipgraph.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 #define BOOST_TEST_DYN_LINK
12
13
14 #include <dai/bipgraph.h>
15 #include <vector>
16 #include <strstream>
17
18
19 using namespace dai;
20
21
22 #define BOOST_TEST_MODULE BipartiteGraphTest
23
24
25 #include <boost/test/unit_test.hpp>
26
27
28 BOOST_AUTO_TEST_CASE( ConstructorsTest ) {
29 // check constructors
30 typedef BipartiteGraph::Edge Edge;
31
32 BipartiteGraph G;
33 BOOST_CHECK_EQUAL( G.nrNodes1(), 0 );
34 BOOST_CHECK_EQUAL( G.nrNodes2(), 0 );
35 BOOST_CHECK_EQUAL( G.nrEdges(), 0 );
36 BOOST_CHECK( G.isConnected() );
37 BOOST_CHECK( G.isTree() );
38 G.checkConsistency();
39
40 BipartiteGraph G1( 2, 3 );
41 BOOST_CHECK_EQUAL( G1.nrNodes1(), 2 );
42 BOOST_CHECK_EQUAL( G1.nrNodes2(), 3 );
43 BOOST_CHECK_EQUAL( G1.nrEdges(), 0 );
44 BOOST_CHECK( !G1.isConnected() );
45 BOOST_CHECK( !G1.isTree() );
46 BOOST_CHECK( !(G1 == G) );
47 G1.checkConsistency();
48
49 std::vector<Edge> edges;
50 edges.push_back( Edge(0, 0) );
51 edges.push_back( Edge(0, 1) );
52 edges.push_back( Edge(1, 1) );
53 edges.push_back( Edge(1, 2) );
54 edges.push_back( Edge(1, 2) );
55 BipartiteGraph G2( 2, 3, edges.begin(), edges.end() );
56 BOOST_CHECK_EQUAL( G2.nrNodes1(), 2 );
57 BOOST_CHECK_EQUAL( G2.nrNodes2(), 3 );
58 BOOST_CHECK_EQUAL( G2.nrEdges(), 4 );
59 BOOST_CHECK( G2.isConnected() );
60 BOOST_CHECK( G2.isTree() );
61 BOOST_CHECK( !(G2 == G) );
62 BOOST_CHECK( !(G2 == G1) );
63 G2.checkConsistency();
64
65 edges.push_back( Edge(1, 0) );
66 BipartiteGraph G3( 2, 3, edges.begin(), edges.end() );
67 BOOST_CHECK_EQUAL( G3.nrNodes1(), 2 );
68 BOOST_CHECK_EQUAL( G3.nrNodes2(), 3 );
69 BOOST_CHECK_EQUAL( G3.nrEdges(), 5 );
70 BOOST_CHECK( G3.isConnected() );
71 BOOST_CHECK( !G3.isTree() );
72 BOOST_CHECK( !(G3 == G) );
73 BOOST_CHECK( !(G3 == G1) );
74 BOOST_CHECK( !(G3 == G2) );
75 G3.checkConsistency();
76
77 BipartiteGraph G4( 3, 3, edges.begin(), edges.end() );
78 BOOST_CHECK_EQUAL( G4.nrNodes1(), 3 );
79 BOOST_CHECK_EQUAL( G4.nrNodes2(), 3 );
80 BOOST_CHECK_EQUAL( G4.nrEdges(), 5 );
81 BOOST_CHECK( !G4.isConnected() );
82 BOOST_CHECK( !G4.isTree() );
83 BOOST_CHECK( !(G4 == G) );
84 BOOST_CHECK( !(G4 == G1) );
85 BOOST_CHECK( !(G4 == G2) );
86 BOOST_CHECK( !(G4 == G3) );
87 G4.checkConsistency();
88
89 G.construct( 3, 3, edges.begin(), edges.end() );
90 BOOST_CHECK_EQUAL( G.nrNodes1(), 3 );
91 BOOST_CHECK_EQUAL( G.nrNodes2(), 3 );
92 BOOST_CHECK_EQUAL( G.nrEdges(), 5 );
93 BOOST_CHECK( !G.isConnected() );
94 BOOST_CHECK( !G.isTree() );
95 BOOST_CHECK( !(G == G1) );
96 BOOST_CHECK( !(G == G2) );
97 BOOST_CHECK( !(G == G3) );
98 BOOST_CHECK( G == G4 );
99 G.checkConsistency();
100
101 BipartiteGraph G5( G4 );
102 BOOST_CHECK( G5 == G4 );
103
104 BipartiteGraph G6 = G4;
105 BOOST_CHECK( G6 == G4 );
106 }
107
108
109 BOOST_AUTO_TEST_CASE( NeighborTest ) {
110 // check nb() accessor / mutator
111 typedef BipartiteGraph::Edge Edge;
112 std::vector<Edge> edges;
113 edges.push_back( Edge(0, 0) );
114 edges.push_back( Edge(0, 1) );
115 edges.push_back( Edge(1, 1) );
116 edges.push_back( Edge(1, 2) );
117 BipartiteGraph G( 2, 3, edges.begin(), edges.end() );
118 BOOST_CHECK_EQUAL( G.nb1(0).size(), 2 );
119 BOOST_CHECK_EQUAL( G.nb1(1).size(), 2 );
120 BOOST_CHECK_EQUAL( G.nb2(0).size(), 1 );
121 BOOST_CHECK_EQUAL( G.nb2(1).size(), 2 );
122 BOOST_CHECK_EQUAL( G.nb2(2).size(), 1 );
123 BOOST_CHECK_EQUAL( G.nb1(0,0).iter, 0 );
124 BOOST_CHECK_EQUAL( G.nb1(0,0).node, 0 );
125 BOOST_CHECK_EQUAL( G.nb1(0,0).dual, 0 );
126 BOOST_CHECK_EQUAL( G.nb1(0,1).iter, 1 );
127 BOOST_CHECK_EQUAL( G.nb1(0,1).node, 1 );
128 BOOST_CHECK_EQUAL( G.nb1(0,1).dual, 0 );
129 BOOST_CHECK_EQUAL( G.nb1(1,0).iter, 0 );
130 BOOST_CHECK_EQUAL( G.nb1(1,0).node, 1 );
131 BOOST_CHECK_EQUAL( G.nb1(1,0).dual, 1 );
132 BOOST_CHECK_EQUAL( G.nb1(1,1).iter, 1 );
133 BOOST_CHECK_EQUAL( G.nb1(1,1).node, 2 );
134 BOOST_CHECK_EQUAL( G.nb1(1,1).dual, 0 );
135 BOOST_CHECK_EQUAL( G.nb2(0,0).iter, 0 );
136 BOOST_CHECK_EQUAL( G.nb2(0,0).node, 0 );
137 BOOST_CHECK_EQUAL( G.nb2(0,0).dual, 0 );
138 BOOST_CHECK_EQUAL( G.nb2(1,0).iter, 0 );
139 BOOST_CHECK_EQUAL( G.nb2(1,0).node, 0 );
140 BOOST_CHECK_EQUAL( G.nb2(1,0).dual, 1 );
141 BOOST_CHECK_EQUAL( G.nb2(1,1).iter, 1 );
142 BOOST_CHECK_EQUAL( G.nb2(1,1).node, 1 );
143 BOOST_CHECK_EQUAL( G.nb2(1,1).dual, 0 );
144 BOOST_CHECK_EQUAL( G.nb2(2,0).iter, 0 );
145 BOOST_CHECK_EQUAL( G.nb2(2,0).node, 1 );
146 BOOST_CHECK_EQUAL( G.nb2(2,0).dual, 1 );
147 }
148
149
150 BOOST_AUTO_TEST_CASE( AddEraseTest ) {
151 // check addition and erasure of nodes and edges
152 typedef BipartiteGraph::Edge Edge;
153 std::vector<Edge> edges;
154 edges.push_back( Edge( 0, 0 ) );
155 edges.push_back( Edge( 0, 1 ) );
156 edges.push_back( Edge( 1, 1 ) );
157 BipartiteGraph G( 2, 2, edges.begin(), edges.end() );
158 G.checkConsistency();
159 BOOST_CHECK_EQUAL( G.nrNodes1(), 2 );
160 BOOST_CHECK_EQUAL( G.nrNodes2(), 2 );
161 BOOST_CHECK_EQUAL( G.nrEdges(), 3 );
162 BOOST_CHECK( G.isConnected() );
163 BOOST_CHECK( G.isTree() );
164 BOOST_CHECK_EQUAL( G.addNode1(), 2 );
165 BOOST_CHECK( !G.isConnected() );
166 BOOST_CHECK( !G.isTree() );
167 BOOST_CHECK_EQUAL( G.addNode2(), 2 );
168 BOOST_CHECK( !G.isConnected() );
169 BOOST_CHECK( !G.isTree() );
170 BOOST_CHECK_EQUAL( G.addNode1(), 3 );
171 BOOST_CHECK( !G.isConnected() );
172 BOOST_CHECK( !G.isTree() );
173 G.checkConsistency();
174 std::vector<size_t> nbs;
175 nbs.push_back( 2 );
176 nbs.push_back( 0 );
177 BOOST_CHECK_EQUAL( G.addNode1( nbs.begin(), nbs.end() ), 4 );
178 G.checkConsistency();
179 BOOST_CHECK( !G.isConnected() );
180 BOOST_CHECK( !G.isTree() );
181 BOOST_CHECK_EQUAL( G.addNode2( nbs.begin(), nbs.end() ), 3 );
182 G.checkConsistency();
183 BOOST_CHECK( !G.isConnected() );
184 BOOST_CHECK( !G.isTree() );
185 G.addEdge( 3, 3 );
186 G.checkConsistency();
187 BOOST_CHECK( G.isConnected() );
188 BOOST_CHECK( G.isTree() );
189 G.addEdge( 1, 3 );
190 G.checkConsistency();
191 BOOST_CHECK( G.isConnected() );
192 BOOST_CHECK( !G.isTree() );
193 BOOST_CHECK_EQUAL( G.nrNodes1(), 5 );
194 BOOST_CHECK_EQUAL( G.nrNodes2(), 4 );
195 BOOST_CHECK_EQUAL( G.nrEdges(), 9 );
196 G.eraseEdge( 0, 3 );
197 G.checkConsistency();
198 BOOST_CHECK( G.isConnected() );
199 BOOST_CHECK( G.isTree() );
200 G.eraseEdge( 4, 2 );
201 G.checkConsistency();
202 BOOST_CHECK( !G.isConnected() );
203 BOOST_CHECK( !G.isTree() );
204 G.eraseNode2( 2 );
205 G.checkConsistency();
206 BOOST_CHECK( G.isConnected() );
207 BOOST_CHECK( G.isTree() );
208 G.eraseNode1( 0 );
209 G.checkConsistency();
210 BOOST_CHECK( !G.isConnected() );
211 BOOST_CHECK( !G.isTree() );
212 G.addEdge( 1, 0 );
213 G.checkConsistency();
214 BOOST_CHECK( G.isConnected() );
215 BOOST_CHECK( G.isTree() );
216 G.eraseNode1( 2 );
217 G.checkConsistency();
218 BOOST_CHECK( G.isConnected() );
219 BOOST_CHECK( G.isTree() );
220 G.eraseNode2( 2 );
221 G.checkConsistency();
222 BOOST_CHECK( !G.isConnected() );
223 BOOST_CHECK( !G.isTree() );
224 G.addEdge( 1, 1 );
225 G.checkConsistency();
226 BOOST_CHECK( G.isConnected() );
227 BOOST_CHECK( G.isTree() );
228 G.eraseNode2( 1 );
229 G.checkConsistency();
230 BOOST_CHECK( !G.isConnected() );
231 BOOST_CHECK( !G.isTree() );
232 G.eraseNode1( 1 );
233 G.checkConsistency();
234 BOOST_CHECK( !G.isConnected() );
235 BOOST_CHECK( !G.isTree() );
236 G.addEdge( 0, 0 );
237 G.checkConsistency();
238 BOOST_CHECK( G.isConnected() );
239 BOOST_CHECK( G.isTree() );
240 G.eraseNode2( 0 );
241 G.checkConsistency();
242 BOOST_CHECK( !G.isConnected() );
243 BOOST_CHECK( !G.isTree() );
244 G.eraseNode1( 0 );
245 G.checkConsistency();
246 BOOST_CHECK( G.isConnected() );
247 BOOST_CHECK( G.isTree() );
248 G.eraseNode1( 0 );
249 G.checkConsistency();
250 BOOST_CHECK( G.isConnected() );
251 BOOST_CHECK( G.isTree() );
252 BOOST_CHECK_EQUAL( G.nrNodes1(), 0 );
253 BOOST_CHECK_EQUAL( G.nrNodes2(), 0 );
254 BOOST_CHECK_EQUAL( G.nrEdges(), 0 );
255 }
256
257
258 BOOST_AUTO_TEST_CASE( RandomAddEraseTest ) {
259 // check adding and erasing nodes and edges randomly
260 BipartiteGraph G;
261 for( size_t maxN1 = 2; maxN1 < 10; maxN1++ )
262 for( size_t maxN2 = 2; maxN2 < 10; maxN2++ )
263 for( size_t repeats = 0; repeats < 100000; repeats++ ) {
264 size_t action = rnd( 5 );
265 size_t N1 = G.nrNodes1();
266 size_t N2 = G.nrNodes2();
267 size_t M = G.nrEdges();
268 size_t maxM = N1 * N2;
269 if( action == 0 ) {
270 // add node
271 if( rnd( 2 ) == 0 ) {
272 // add node of type 1
273 if( N1 < maxN1 )
274 G.addNode1();
275 } else {
276 // add node of type 2
277 if( N2 < maxN2 )
278 G.addNode2();
279 }
280 } else if( action == 1 ) {
281 // erase node
282 if( rnd( 2 ) == 0 ) {
283 // erase node of type 1
284 if( N1 > 0 )
285 G.eraseNode1( rnd( N1 ) );
286 } else {
287 // erase node of type 2
288 if( N2 > 0 )
289 G.eraseNode2( rnd( N2 ) );
290 }
291 } else if( action == 2 || action == 3 ) {
292 // add edge
293 if( N1 >= 1 && N2 >= 1 && M < maxM ) {
294 size_t n1 = 0;
295 size_t n2 = 0;
296 if( rnd( 2 ) == 0 ) {
297 do {
298 n1 = rnd( N1 );
299 } while( G.nb1(n1).size() >= N2 );
300 do {
301 n2 = rnd( N2 );
302 } while( G.hasEdge( n1, n2 ) );
303 } else {
304 do {
305 n2 = rnd( N2 );
306 } while( G.nb2(n2).size() >= N1 );
307 do {
308 n1 = rnd( N1 );
309 } while( G.hasEdge( n1, n2 ) );
310 }
311 G.addEdge( n1, n2 );
312 }
313 } else if( action == 4 ) {
314 // erase edge
315 if( M > 0 ) {
316 size_t n1 = 0;
317 size_t n2 = 0;
318 if( rnd( 2 ) == 0 ) {
319 do {
320 n1 = rnd( N1 );
321 } while( G.nb1(n1).size() == 0 );
322 do {
323 n2 = rnd( N2 );
324 } while( !G.hasEdge( n1, n2 ) );
325 } else {
326 do {
327 n2 = rnd( N2 );
328 } while( G.nb2(n2).size() == 0 );
329 do {
330 n1 = rnd( N1 );
331 } while( !G.hasEdge( n1, n2 ) );
332 }
333 G.eraseEdge( n1, n2 );
334 }
335 }
336 G.checkConsistency();
337 }
338 }
339
340
341 BOOST_AUTO_TEST_CASE( QueriesTest ) {
342 // check queries which have not been tested in another test case
343 typedef BipartiteGraph::Edge Edge;
344 std::vector<Edge> edges;
345 edges.push_back( Edge( 0, 1 ) );
346 edges.push_back( Edge( 1, 1 ) );
347 edges.push_back( Edge( 0, 0 ) );
348 BipartiteGraph G( 3, 2, edges.begin(), edges.end() );
349 G.checkConsistency();
350 SmallSet<size_t> v;
351 SmallSet<size_t> v0( 0 );
352 SmallSet<size_t> v1( 1 );
353 SmallSet<size_t> v01( 0, 1 );
354 BOOST_CHECK_EQUAL( G.delta1( 0, true ), v01 );
355 BOOST_CHECK_EQUAL( G.delta1( 1, true ), v01 );
356 BOOST_CHECK_EQUAL( G.delta1( 2, true ), v );
357 BOOST_CHECK_EQUAL( G.delta2( 0, true ), v01 );
358 BOOST_CHECK_EQUAL( G.delta2( 1, true ), v01 );
359 BOOST_CHECK_EQUAL( G.delta1( 0, false ), v1 );
360 BOOST_CHECK_EQUAL( G.delta1( 1, false ), v0 );
361 BOOST_CHECK_EQUAL( G.delta1( 2, false ), v );
362 BOOST_CHECK_EQUAL( G.delta2( 0, false ), v1 );
363 BOOST_CHECK_EQUAL( G.delta2( 1, false ), v0 );
364 BOOST_CHECK( G.hasEdge( 0, 0 ) );
365 BOOST_CHECK( G.hasEdge( 0, 1 ) );
366 BOOST_CHECK( G.hasEdge( 1, 1 ) );
367 BOOST_CHECK( !G.hasEdge( 1, 0 ) );
368 BOOST_CHECK( !G.hasEdge( 2, 0 ) );
369 BOOST_CHECK( !G.hasEdge( 2, 1 ) );
370 BOOST_CHECK_EQUAL( G.findNb1( 0, 0 ), 1 );
371 BOOST_CHECK_EQUAL( G.findNb1( 0, 1 ), 0 );
372 BOOST_CHECK_EQUAL( G.findNb1( 1, 1 ), 0 );
373 BOOST_CHECK_EQUAL( G.findNb2( 0, 0 ), 0 );
374 BOOST_CHECK_EQUAL( G.findNb2( 0, 1 ), 0 );
375 BOOST_CHECK_EQUAL( G.findNb2( 1, 1 ), 1 );
376 }
377
378
379 BOOST_AUTO_TEST_CASE( StreamTest ) {
380 // check printDot
381 typedef BipartiteGraph::Edge Edge;
382 std::vector<Edge> edges;
383 edges.push_back( Edge(0, 0) );
384 edges.push_back( Edge(0, 1) );
385 edges.push_back( Edge(1, 1) );
386 edges.push_back( Edge(1, 2) );
387 BipartiteGraph G( 2, 3, edges.begin(), edges.end() );
388
389 std::stringstream ss;
390 G.printDot( ss );
391
392 std::string s;
393 std::getline( ss, s );
394 BOOST_CHECK_EQUAL( s, "graph G {" );
395 std::getline( ss, s );
396 BOOST_CHECK_EQUAL( s, "node[shape=circle,width=0.4,fixedsize=true];" );
397 std::getline( ss, s );
398 BOOST_CHECK_EQUAL( s, "\tx0;" );
399 std::getline( ss, s );
400 BOOST_CHECK_EQUAL( s, "\tx1;" );
401 std::getline( ss, s );
402 BOOST_CHECK_EQUAL( s, "node[shape=box,width=0.3,height=0.3,fixedsize=true];" );
403 std::getline( ss, s );
404 BOOST_CHECK_EQUAL( s, "\ty0;" );
405 std::getline( ss, s );
406 BOOST_CHECK_EQUAL( s, "\ty1;" );
407 std::getline( ss, s );
408 BOOST_CHECK_EQUAL( s, "\ty2;" );
409 std::getline( ss, s );
410 BOOST_CHECK_EQUAL( s, "\tx0 -- y0;" );
411 std::getline( ss, s );
412 BOOST_CHECK_EQUAL( s, "\tx0 -- y1;" );
413 std::getline( ss, s );
414 BOOST_CHECK_EQUAL( s, "\tx1 -- y1;" );
415 std::getline( ss, s );
416 BOOST_CHECK_EQUAL( s, "\tx1 -- y2;" );
417 std::getline( ss, s );
418 BOOST_CHECK_EQUAL( s, "}" );
419 }