5c907e65bfdf0bf6a4c583218f2b9d7bd60963e9
[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( QueriesAndCreationTest ) {
163 // check queries and createGraph* functions
164
165 // createGraphFull
166 for( size_t N = 0; N < 20; N++ ) {
167 GraphAL G = createGraphFull( N );
168 BOOST_CHECK_EQUAL( G.nrNodes(), N );
169 BOOST_CHECK_EQUAL( G.nrEdges(), N > 0 ? N * (N-1) / 2 : 0 );
170 BOOST_CHECK( G.isConnected() );
171 BOOST_CHECK_EQUAL( G.isTree(), N < 3 );
172 for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
173 foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
174 BOOST_CHECK( G.hasEdge( n1, n2 ) );
175 BOOST_CHECK( G.hasEdge( n2, n1 ) );
176 }
177 for( size_t n2 = 0; n2 < G.nrNodes(); n2++ )
178 if( G.hasEdge( n1, n2 ) ) {
179 BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ), n2 );
180 BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ), n1 );
181 BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ).iter, G.findNb( n1, n2 ) );
182 BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ).iter, G.findNb( n2, n1 ) );
183 }
184 }
185 G.checkConsistency();
186 }
187
188 // createGraphGrid
189 for( size_t N1 = 0; N1 < 10; N1++ )
190 for( size_t N2 = 0; N2 < 10; N2++ ) {
191 GraphAL G = createGraphGrid( N1, N2, false );
192 BOOST_CHECK_EQUAL( G.nrNodes(), N1 * N2 );
193 BOOST_CHECK_EQUAL( G.nrEdges(), (N1 > 0 && N2 > 0) ? 2 * (N1-1) * (N2-1) + (N1-1) + (N2-1) : 0 );
194 BOOST_CHECK( G.isConnected() );
195 BOOST_CHECK_EQUAL( G.isTree(), (N1 <= 1) || (N2 <= 1) );
196 for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
197 foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
198 BOOST_CHECK( G.hasEdge( n1, n2 ) );
199 BOOST_CHECK( G.hasEdge( n2, n1 ) );
200 }
201 for( size_t n2 = 0; n2 < G.nrNodes(); n2++ )
202 if( G.hasEdge( n1, n2 ) ) {
203 BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ), n2 );
204 BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ), n1 );
205 BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ).iter, G.findNb( n1, n2 ) );
206 BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ).iter, G.findNb( n2, n1 ) );
207 }
208 }
209 G.checkConsistency();
210
211 G = createGraphGrid( N1, N2, true );
212 BOOST_CHECK_EQUAL( G.nrNodes(), N1 * N2 );
213 if( N1 == 0 || N2 == 0 )
214 BOOST_CHECK_EQUAL( G.nrEdges(), 0 );
215 else
216 BOOST_CHECK_EQUAL( G.nrEdges(), (N1 <= 2 ? (N1-1) : N1) * N2 + N1 * (N2 <= 2 ? (N2-1) : N2) );
217 BOOST_CHECK( G.isConnected() );
218 BOOST_CHECK_EQUAL( G.isTree(), (G.nrNodes() <= 2) );
219 for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
220 foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
221 BOOST_CHECK( G.hasEdge( n1, n2 ) );
222 BOOST_CHECK( G.hasEdge( n2, n1 ) );
223 }
224 for( size_t n2 = 0; n2 < G.nrNodes(); n2++ )
225 if( G.hasEdge( n1, n2 ) ) {
226 BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ), n2 );
227 BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ), n1 );
228 BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ).iter, G.findNb( n1, n2 ) );
229 BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ).iter, G.findNb( n2, n1 ) );
230 }
231 }
232 G.checkConsistency();
233 }
234
235 // createGraphGrid3D
236 for( size_t N1 = 0; N1 < 10; N1++ )
237 for( size_t N2 = 0; N2 < 10; N2++ )
238 for( size_t N3 = 0; N3 < 10; N3++ ) {
239 GraphAL G = createGraphGrid3D( N1, N2, N3, false );
240 BOOST_CHECK_EQUAL( G.nrNodes(), N1 * N2 * N3 );
241 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 );
242 BOOST_CHECK( G.isConnected() );
243 BOOST_CHECK_EQUAL( G.isTree(), (G.nrNodes() == 0) || (N1 <= 1 && N2 <= 1) || (N1 <= 1 && N3 <= 1) || (N2 <= 1 && N3 <= 1) );
244 for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
245 foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
246 BOOST_CHECK( G.hasEdge( n1, n2 ) );
247 BOOST_CHECK( G.hasEdge( n2, n1 ) );
248 }
249 for( size_t n2 = 0; n2 < G.nrNodes(); n2++ )
250 if( G.hasEdge( n1, n2 ) ) {
251 BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ), n2 );
252 BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ), n1 );
253 BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ).iter, G.findNb( n1, n2 ) );
254 BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ).iter, G.findNb( n2, n1 ) );
255 }
256 }
257 G.checkConsistency();
258
259 G = createGraphGrid3D( N1, N2, N3, true );
260 BOOST_CHECK_EQUAL( G.nrNodes(), N1 * N2 * N3 );
261 if( N1 == 0 || N2 == 0 || N3 == 0 )
262 BOOST_CHECK_EQUAL( G.nrEdges(), 0 );
263 else
264 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) );
265 BOOST_CHECK( G.isConnected() );
266 BOOST_CHECK_EQUAL( G.isTree(), (G.nrNodes() <= 2) );
267 for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
268 foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
269 BOOST_CHECK( G.hasEdge( n1, n2 ) );
270 BOOST_CHECK( G.hasEdge( n2, n1 ) );
271 }
272 for( size_t n2 = 0; n2 < G.nrNodes(); n2++ )
273 if( G.hasEdge( n1, n2 ) ) {
274 BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ), n2 );
275 BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ), n1 );
276 BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ).iter, G.findNb( n1, n2 ) );
277 BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ).iter, G.findNb( n2, n1 ) );
278 }
279 }
280 G.checkConsistency();
281 }
282
283 // createGraphLoop
284 for( size_t N = 0; N < 100; N++ ) {
285 GraphAL G = createGraphLoop( N );
286 BOOST_CHECK_EQUAL( G.nrNodes(), N );
287 if( N == 0 )
288 BOOST_CHECK_EQUAL( G.nrEdges(), 0 );
289 else if( N <= 2 )
290 BOOST_CHECK_EQUAL( G.nrEdges(), N-1 );
291 else
292 BOOST_CHECK_EQUAL( G.nrEdges(), N );
293 BOOST_CHECK( G.isConnected() );
294 BOOST_CHECK_EQUAL( G.isTree(), N <= 2 );
295 for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
296 foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
297 BOOST_CHECK( G.hasEdge( n1, n2 ) );
298 BOOST_CHECK( G.hasEdge( n2, n1 ) );
299 }
300 for( size_t n2 = 0; n2 < G.nrNodes(); n2++ )
301 if( G.hasEdge( n1, n2 ) ) {
302 BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ), n2 );
303 BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ), n1 );
304 BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ).iter, G.findNb( n1, n2 ) );
305 BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ).iter, G.findNb( n2, n1 ) );
306 }
307 }
308 G.checkConsistency();
309 }
310
311 // createGraphTree
312 for( size_t N = 0; N < 100; N++ ) {
313 GraphAL G = createGraphTree( N );
314 BOOST_CHECK_EQUAL( G.nrNodes(), N );
315 BOOST_CHECK_EQUAL( G.nrEdges(), N > 0 ? N - 1 : N );
316 BOOST_CHECK( G.isConnected() );
317 BOOST_CHECK( G.isTree() );
318 for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
319 foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
320 BOOST_CHECK( G.hasEdge( n1, n2 ) );
321 BOOST_CHECK( G.hasEdge( n2, n1 ) );
322 }
323 for( size_t n2 = 0; n2 < G.nrNodes(); n2++ )
324 if( G.hasEdge( n1, n2 ) ) {
325 BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ), n2 );
326 BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ), n1 );
327 BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ).iter, G.findNb( n1, n2 ) );
328 BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ).iter, G.findNb( n2, n1 ) );
329 }
330 }
331 G.checkConsistency();
332 }
333
334 // createGraphRegular
335 for( size_t N = 0; N < 100; N++ ) {
336 for( size_t d = 0; d < N && d <= 20; d++ ) {
337 if( (N * d) % 2 == 0 ) {
338 GraphAL G = createGraphRegular( N, d );
339 BOOST_CHECK_EQUAL( G.nrNodes(), N );
340 BOOST_CHECK_EQUAL( G.nrEdges(), d * N / 2 );
341 for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) {
342 BOOST_CHECK_EQUAL( G.nb(n1).size(), d );
343 foreach( const GraphAL::Neighbor &n2, G.nb(n1) ) {
344 BOOST_CHECK( G.hasEdge( n1, n2 ) );
345 BOOST_CHECK( G.hasEdge( n2, n1 ) );
346 }
347 for( size_t n2 = 0; n2 < G.nrNodes(); n2++ )
348 if( G.hasEdge( n1, n2 ) ) {
349 BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ), n2 );
350 BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ), n1 );
351 BOOST_CHECK_EQUAL( G.nb( n1, G.findNb( n1, n2 ) ).iter, G.findNb( n1, n2 ) );
352 BOOST_CHECK_EQUAL( G.nb( n2, G.findNb( n2, n1 ) ).iter, G.findNb( n2, n1 ) );
353 }
354 }
355 G.checkConsistency();
356 }
357 }
358 }
359 }
360
361
362 BOOST_AUTO_TEST_CASE( StreamTest ) {
363 // check printDot
364 GraphAL G( 4 );
365 G.addEdge( 0, 1 );
366 G.addEdge( 0, 2 );
367 G.addEdge( 1, 3 );
368 G.addEdge( 2, 3 );
369 G.addEdge( 2, 2 );
370 G.addEdge( 3, 2 );
371
372 std::stringstream ss;
373 G.printDot( ss );
374
375 std::string s;
376 std::getline( ss, s );
377 BOOST_CHECK_EQUAL( s, "graph G {" );
378 std::getline( ss, s );
379 BOOST_CHECK_EQUAL( s, "node[shape=circle,width=0.4,fixedsize=true];" );
380 std::getline( ss, s );
381 BOOST_CHECK_EQUAL( s, "\tx0;" );
382 std::getline( ss, s );
383 BOOST_CHECK_EQUAL( s, "\tx1;" );
384 std::getline( ss, s );
385 BOOST_CHECK_EQUAL( s, "\tx2;" );
386 std::getline( ss, s );
387 BOOST_CHECK_EQUAL( s, "\tx3;" );
388 std::getline( ss, s );
389 BOOST_CHECK_EQUAL( s, "\tx0 -- x1;" );
390 std::getline( ss, s );
391 BOOST_CHECK_EQUAL( s, "\tx0 -- x2;" );
392 std::getline( ss, s );
393 BOOST_CHECK_EQUAL( s, "\tx1 -- x3;" );
394 std::getline( ss, s );
395 BOOST_CHECK_EQUAL( s, "\tx2 -- x3;" );
396 std::getline( ss, s );
397 BOOST_CHECK_EQUAL( s, "}" );
398 }