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