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