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