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