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