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