bb7b3b29b4b2f2b7d1690aed02af86ee2bb9a282
[libdai.git] / tests / unit / dag_test.cpp
1 /* This file is part of libDAI - http://www.libdai.org/
2 *
3 * Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
4 *
5 * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
6 */
7
8
9 #include <dai/dag.h>
10 #include <vector>
11 #include <set>
12 #include <strstream>
13
14
15 using namespace dai;
16
17
18 #define BOOST_TEST_MODULE DAGTest
19
20
21 #include <boost/test/unit_test.hpp>
22
23
24 BOOST_AUTO_TEST_CASE( ConstructorsTest ) {
25 // check constructors
26 DAG G0;
27 BOOST_CHECK_EQUAL( G0.nrNodes(), 0 );
28 BOOST_CHECK_EQUAL( G0.nrEdges(), 0 );
29 BOOST_CHECK_EQUAL( G0.isConnected(), true );
30 G0.checkConsistency();
31
32 DAG G2( 2 );
33 BOOST_CHECK_EQUAL( G2.nrNodes(), 2 );
34 BOOST_CHECK_EQUAL( G2.nrEdges(), 0 );
35 BOOST_CHECK_EQUAL( G2.isConnected(), false );
36 G2.checkConsistency();
37 BOOST_CHECK( !(G2 == G0) );
38
39 std::vector<Edge> edges;
40 edges.push_back( Edge( 0, 1 ) );
41 edges.push_back( Edge( 1, 2 ) );
42 edges.push_back( Edge( 2, 1 ) );
43 edges.push_back( Edge( 1, 2 ) );
44 DAG G3( 3, edges.begin(), edges.end() );
45 BOOST_CHECK_EQUAL( G3.nrNodes(), 3 );
46 BOOST_CHECK_EQUAL( G3.nrEdges(), 2 );
47 BOOST_CHECK_EQUAL( G3.isConnected(), true );
48 G3.checkConsistency();
49 BOOST_CHECK( !(G3 == G0) );
50 BOOST_CHECK( !(G3 == G2) );
51
52 DAG G4( G3 );
53 BOOST_CHECK( !(G4 == G0) );
54 BOOST_CHECK( !(G4 == G2) );
55 BOOST_CHECK( G4 == G3 );
56
57 DAG G5 = G3;
58 BOOST_CHECK( !(G5 == G0) );
59 BOOST_CHECK( !(G5 == G2) );
60 BOOST_CHECK( G5 == G3 );
61 }
62
63
64 BOOST_AUTO_TEST_CASE( NeighborTest ) {
65 // check pa(), ch() accessors / mutators
66 std::vector<Edge> edges;
67 edges.push_back( Edge( 0, 2 ) );
68 edges.push_back( Edge( 1, 2 ) );
69 edges.push_back( Edge( 1, 3 ) );
70 DAG G( 4, edges.begin(), edges.end() );
71
72 BOOST_CHECK_EQUAL( G.pa(0).size(), 0 );
73 BOOST_CHECK_EQUAL( G.pa(1).size(), 0 );
74 BOOST_CHECK_EQUAL( G.pa(2).size(), 2 );
75 BOOST_CHECK_EQUAL( G.pa(3).size(), 1 );
76 BOOST_CHECK_EQUAL( G.pa(2,0).iter, 0 );
77 BOOST_CHECK_EQUAL( G.pa(2,0).node, 0 );
78 BOOST_CHECK_EQUAL( G.pa(2,0).dual, 0 );
79 BOOST_CHECK_EQUAL( G.pa(2,1).iter, 1 );
80 BOOST_CHECK_EQUAL( G.pa(2,1).node, 1 );
81 BOOST_CHECK_EQUAL( G.pa(2,1).dual, 0 );
82 BOOST_CHECK_EQUAL( G.pa(3,0).iter, 0 );
83 BOOST_CHECK_EQUAL( G.pa(3,0).node, 1 );
84 BOOST_CHECK_EQUAL( G.pa(3,0).dual, 1 );
85
86 BOOST_CHECK( G.paSet(0) == SmallSet<size_t>() );
87 BOOST_CHECK( G.paSet(1) == SmallSet<size_t>() );
88 BOOST_CHECK( G.paSet(2) == SmallSet<size_t>(0,1) );
89 BOOST_CHECK( G.paSet(3) == SmallSet<size_t>(1) );
90
91 BOOST_CHECK_EQUAL( G.ch(0).size(), 1 );
92 BOOST_CHECK_EQUAL( G.ch(1).size(), 2 );
93 BOOST_CHECK_EQUAL( G.ch(2).size(), 0 );
94 BOOST_CHECK_EQUAL( G.ch(3).size(), 0 );
95 BOOST_CHECK_EQUAL( G.ch(0,0).iter, 0 );
96 BOOST_CHECK_EQUAL( G.ch(0,0).node, 2 );
97 BOOST_CHECK_EQUAL( G.ch(0,0).dual, 0 );
98 BOOST_CHECK_EQUAL( G.ch(1,0).iter, 0 );
99 BOOST_CHECK_EQUAL( G.ch(1,0).node, 2 );
100 BOOST_CHECK_EQUAL( G.ch(1,0).dual, 1 );
101 BOOST_CHECK_EQUAL( G.ch(1,1).iter, 1 );
102 BOOST_CHECK_EQUAL( G.ch(1,1).node, 3 );
103 BOOST_CHECK_EQUAL( G.ch(1,1).dual, 0 );
104
105 BOOST_CHECK( G.chSet(0) == SmallSet<size_t>(2) );
106 BOOST_CHECK( G.chSet(1) == SmallSet<size_t>(2,3) );
107 BOOST_CHECK( G.chSet(2) == SmallSet<size_t>() );
108 BOOST_CHECK( G.chSet(3) == SmallSet<size_t>() );
109 }
110
111
112 BOOST_AUTO_TEST_CASE( AddEraseTest ) {
113 // check addition and erasure of nodes and edges
114 std::vector<Edge> edges;
115 edges.push_back( Edge( 0, 1 ) );
116 edges.push_back( Edge( 1, 2 ) );
117 edges.push_back( Edge( 1, 0 ) );
118 DAG G( 2 );
119 G.construct( 3, edges.begin(), edges.end() );
120 G.checkConsistency();
121 BOOST_CHECK_EQUAL( G.nrNodes(), 3 );
122 BOOST_CHECK_EQUAL( G.nrEdges(), 2 );
123 BOOST_CHECK_EQUAL( G, DAG(3).addEdge(0,1).addEdge(1,2) );
124 BOOST_CHECK_EQUAL( G.addNode(), 3 );
125 BOOST_CHECK_EQUAL( G, DAG(4).addEdge(0,1).addEdge(1,2) );
126 G.checkConsistency();
127 std::vector<size_t> pa;
128 pa.push_back( 3 );
129 BOOST_CHECK_EQUAL( G.addNode( pa.begin(), pa.end() ), 4 );
130 BOOST_CHECK_EQUAL( G, DAG(5).addEdge(0,1).addEdge(1,2).addEdge(3,4) );
131 BOOST_CHECK_EQUAL( G.addNode(), 5 );
132 BOOST_CHECK_EQUAL( G, DAG(6).addEdge(0,1).addEdge(1,2).addEdge(3,4) );
133 G.checkConsistency();
134 G.addEdge( 0, 4 );
135 BOOST_CHECK_EQUAL( G, DAG(6).addEdge(0,1).addEdge(1,2).addEdge(3,4).addEdge(0,4) );
136 G.checkConsistency();
137 G.addEdge( 0, 5 );
138 BOOST_CHECK_EQUAL( G, DAG(6).addEdge(0,1).addEdge(1,2).addEdge(3,4).addEdge(0,4).addEdge(0,5) );
139 G.checkConsistency();
140 BOOST_CHECK_EQUAL( G.nrNodes(), 6 );
141 BOOST_CHECK_EQUAL( G.nrEdges(), 5 );
142 G.addEdge( 2, 3 );
143 BOOST_CHECK_EQUAL( G, DAG(6).addEdge(0,1).addEdge(1,2).addEdge(3,4).addEdge(0,4).addEdge(0,5).addEdge(2,3) );
144 G.addEdge( 3, 0 );
145 BOOST_CHECK_EQUAL( G, DAG(6).addEdge(0,1).addEdge(1,2).addEdge(3,4).addEdge(0,4).addEdge(0,5).addEdge(2,3) );
146
147 G.addEdge( 5, 3 );
148 BOOST_CHECK_EQUAL( G, DAG(6).addEdge(0,1).addEdge(1,2).addEdge(3,4).addEdge(0,4).addEdge(0,5).addEdge(2,3).addEdge(5,3) );
149 G.eraseNode( 0 );
150 BOOST_CHECK_EQUAL( G, DAG(5).addEdge(0,1).addEdge(1,2).addEdge(4,2).addEdge(2,3) );
151 G.checkConsistency();
152 G.eraseEdge( 0, 1 );
153 BOOST_CHECK_EQUAL( G, DAG(5).addEdge(1,2).addEdge(4,2).addEdge(2,3) );
154 G.checkConsistency();
155 BOOST_CHECK( !G.isConnected() );
156 G.eraseNode( 0 );
157 BOOST_CHECK_EQUAL( G, DAG(4).addEdge(0,1).addEdge(3,1).addEdge(1,2) );
158 G.checkConsistency();
159 G.addEdge( 3, 2 );
160 BOOST_CHECK_EQUAL( G, DAG(4).addEdge(0,1).addEdge(3,1).addEdge(1,2).addEdge(3,2) );
161 G.checkConsistency();
162 G.eraseNode( 1 );
163 BOOST_CHECK_EQUAL( G, DAG(3).addEdge(2,1) );
164 G.checkConsistency();
165 BOOST_CHECK( !G.isConnected() );
166 G.eraseNode( 2 );
167 BOOST_CHECK_EQUAL( G, DAG(2) );
168 G.checkConsistency();
169 BOOST_CHECK( !G.isConnected() );
170 G.addEdge( 1, 0 );
171 BOOST_CHECK_EQUAL( G, DAG(2).addEdge(1,0) );
172 G.checkConsistency();
173 BOOST_CHECK( G.isConnected() );
174 G.eraseNode( 1 );
175 BOOST_CHECK_EQUAL( G, DAG(1) );
176 G.checkConsistency();
177 BOOST_CHECK( G.isConnected() );
178 G.eraseNode( 0 );
179 BOOST_CHECK_EQUAL( G, DAG() );
180 BOOST_CHECK( G.isConnected() );
181 BOOST_CHECK_EQUAL( G.nrNodes(), 0 );
182 BOOST_CHECK_EQUAL( G.nrEdges(), 0 );
183
184 G.addNode();
185 G.addNode();
186 G.addNode();
187 G.addNode();
188 G.addEdge( 0, 1 );
189 G.addEdge( 2, 3 );
190 G.addEdge( 0, 3 );
191 G.checkConsistency();
192 G.eraseNode( 2 );
193 G.checkConsistency();
194 }
195
196
197 BOOST_AUTO_TEST_CASE( RandomAddEraseTest ) {
198 // check adding and erasing nodes and edges randomly
199 DAG G;
200 for( size_t maxN = 2; maxN < 50; maxN++ )
201 for( size_t repeats = 0; repeats < 10000; repeats++ ) {
202 size_t action = rnd( 5 );
203 size_t N = G.nrNodes();
204 size_t M = G.nrEdges();
205 size_t maxM = N * (N - 1) / 2;
206 if( action == 0 ) {
207 // add node
208 if( N < maxN )
209 G.addNode();
210 } else if( action == 1 ) {
211 // erase node
212 if( N > 0 )
213 G.eraseNode( rnd( N ) );
214 } else if( action == 2 || action == 3 ) {
215 // add edge
216 if( N >= 2 && M < maxM ) {
217 size_t n1 = 0;
218 size_t n2 = 0;
219 do {
220 n1 = rnd( N );
221 n2 = rnd( N );
222 } while( n1 == n2 || G.ch(n1).size() >= N - 1 || G.pa(n2).size() >= N - 1 || G.hasEdge( n1, n2 ) || G.existsDirectedPath( n2, n1 ) );
223 G.addEdge( n1, n2 );
224 }
225 } else if( action == 4 ) {
226 // erase edge
227 if( M > 0 ) {
228 size_t n1 = 0;
229 do {
230 n1 = rnd( N );
231 } while( G.ch(n1).size() == 0 );
232 size_t n2 = 0;
233 do {
234 n2 = rnd( N );
235 } while( !G.hasEdge( n1, n2 ) );
236 G.eraseEdge( n1, n2 );
237 }
238 }
239 G.checkConsistency();
240 }
241 }
242
243
244 BOOST_AUTO_TEST_CASE( QueriesTest ) {
245 // check queries which have not been tested in another test case
246 std::vector<Edge> edges;
247 edges.push_back( Edge( 0, 1 ) );
248 edges.push_back( Edge( 0, 3 ) );
249 edges.push_back( Edge( 2, 3 ) );
250 DAG G( 4, edges.begin(), edges.end() );
251 G.checkConsistency();
252
253 BOOST_CHECK( !G.hasEdge( 0, 0 ) );
254 BOOST_CHECK( G.hasEdge( 0, 1 ) );
255 BOOST_CHECK( !G.hasEdge( 0, 2 ) );
256 BOOST_CHECK( G.hasEdge( 0, 3 ) );
257 BOOST_CHECK( !G.hasEdge( 1, 0 ) );
258 BOOST_CHECK( !G.hasEdge( 1, 1 ) );
259 BOOST_CHECK( !G.hasEdge( 1, 2 ) );
260 BOOST_CHECK( !G.hasEdge( 1, 3 ) );
261 BOOST_CHECK( !G.hasEdge( 2, 0 ) );
262 BOOST_CHECK( !G.hasEdge( 2, 1 ) );
263 BOOST_CHECK( !G.hasEdge( 2, 2 ) );
264 BOOST_CHECK( G.hasEdge( 2, 3 ) );
265 BOOST_CHECK( !G.hasEdge( 3, 0 ) );
266 BOOST_CHECK( !G.hasEdge( 3, 1 ) );
267 BOOST_CHECK( !G.hasEdge( 3, 2 ) );
268 BOOST_CHECK( !G.hasEdge( 3, 3 ) );
269
270 BOOST_CHECK_THROW( G.findPa( 0, 0 ), Exception );
271 BOOST_CHECK_THROW( G.findPa( 0, 1 ), Exception );
272 BOOST_CHECK_THROW( G.findPa( 0, 2 ), Exception );
273 BOOST_CHECK_THROW( G.findPa( 0, 3 ), Exception );
274 BOOST_CHECK_EQUAL( G.findPa( 1, 0 ), 0 );
275 BOOST_CHECK_THROW( G.findPa( 1, 1 ), Exception );
276 BOOST_CHECK_THROW( G.findPa( 1, 2 ), Exception );
277 BOOST_CHECK_THROW( G.findPa( 1, 3 ), Exception );
278 BOOST_CHECK_THROW( G.findPa( 2, 0 ), Exception );
279 BOOST_CHECK_THROW( G.findPa( 2, 1 ), Exception );
280 BOOST_CHECK_THROW( G.findPa( 2, 2 ), Exception );
281 BOOST_CHECK_THROW( G.findPa( 2, 3 ), Exception );
282 BOOST_CHECK_EQUAL( G.findPa( 3, 0 ), 0 );
283 BOOST_CHECK_THROW( G.findPa( 3, 1 ), Exception );
284 BOOST_CHECK_EQUAL( G.findPa( 3, 2 ), 1 );
285 BOOST_CHECK_THROW( G.findPa( 3, 3 ), Exception );
286
287 BOOST_CHECK_THROW( G.findCh( 0, 0 ), Exception );
288 BOOST_CHECK_EQUAL( G.findCh( 0, 1 ), 0 );
289 BOOST_CHECK_THROW( G.findCh( 0, 2 ), Exception );
290 BOOST_CHECK_EQUAL( G.findCh( 0, 3 ), 1 );
291 BOOST_CHECK_THROW( G.findCh( 1, 0 ), Exception );
292 BOOST_CHECK_THROW( G.findCh( 1, 1 ), Exception );
293 BOOST_CHECK_THROW( G.findCh( 1, 2 ), Exception );
294 BOOST_CHECK_THROW( G.findCh( 1, 3 ), Exception );
295 BOOST_CHECK_THROW( G.findCh( 2, 0 ), Exception );
296 BOOST_CHECK_THROW( G.findCh( 2, 1 ), Exception );
297 BOOST_CHECK_THROW( G.findCh( 2, 2 ), Exception );
298 BOOST_CHECK_EQUAL( G.findCh( 2, 3 ), 0 );
299 BOOST_CHECK_THROW( G.findCh( 3, 0 ), Exception );
300 BOOST_CHECK_THROW( G.findCh( 3, 1 ), Exception );
301 BOOST_CHECK_THROW( G.findCh( 3, 2 ), Exception );
302 BOOST_CHECK_THROW( G.findCh( 3, 3 ), Exception );
303
304 BOOST_CHECK( G.existsDirectedPath( 0, 0 ) );
305 BOOST_CHECK( G.existsDirectedPath( 0, 1 ) );
306 BOOST_CHECK( !G.existsDirectedPath( 0, 2 ) );
307 BOOST_CHECK( G.existsDirectedPath( 0, 3 ) );
308 BOOST_CHECK( !G.existsDirectedPath( 1, 0 ) );
309 BOOST_CHECK( G.existsDirectedPath( 1, 1 ) );
310 BOOST_CHECK( !G.existsDirectedPath( 1, 2 ) );
311 BOOST_CHECK( !G.existsDirectedPath( 1, 3 ) );
312 BOOST_CHECK( !G.existsDirectedPath( 2, 0 ) );
313 BOOST_CHECK( !G.existsDirectedPath( 2, 1 ) );
314 BOOST_CHECK( G.existsDirectedPath( 2, 2 ) );
315 BOOST_CHECK( G.existsDirectedPath( 2, 3 ) );
316 BOOST_CHECK( !G.existsDirectedPath( 3, 0 ) );
317 BOOST_CHECK( !G.existsDirectedPath( 3, 1 ) );
318 BOOST_CHECK( !G.existsDirectedPath( 3, 2 ) );
319 BOOST_CHECK( G.existsDirectedPath( 3, 3 ) );
320
321 std::set<size_t> s;
322 G.addNode();
323 G.addEdge( 3, 4 );
324 G.addNode();
325 G.addEdge( 1, 4 );
326 G.addEdge( 1, 5 );
327 BOOST_CHECK( G.descendants( 4 ) == s );
328 BOOST_CHECK( G.descendants( 5 ) == s );
329 s.insert( 4 );
330 BOOST_CHECK( G.descendants( 3 ) == s );
331 s.insert( 5 );
332 BOOST_CHECK( G.descendants( 1 ) == s );
333 s.erase( 5 );
334 s.insert( 3 );
335 BOOST_CHECK( G.descendants( 2 ) == s );
336 s.insert( 1 );
337 s.insert( 5 );
338 BOOST_CHECK( G.descendants( 0 ) == s );
339
340 s.clear();
341 BOOST_CHECK( G.ancestors( 0 ) == s );
342 BOOST_CHECK( G.ancestors( 2 ) == s );
343 s.insert( 0 );
344 BOOST_CHECK( G.ancestors( 1 ) == s );
345 s.insert( 2 );
346 BOOST_CHECK( G.ancestors( 3 ) == s );
347 s.erase( 2 );
348 s.insert( 1 );
349 BOOST_CHECK( G.ancestors( 5 ) == s );
350 s.insert( 2 );
351 s.insert( 3 );
352 BOOST_CHECK( G.ancestors( 4 ) == s );
353 }
354
355
356 BOOST_AUTO_TEST_CASE( StreamTest ) {
357 // check printDot
358 DAG G( 4 );
359 G.addEdge( 0, 1 );
360 G.addEdge( 0, 2 );
361 G.addEdge( 1, 3 );
362 G.addEdge( 2, 3 );
363 G.addEdge( 2, 2 );
364 G.addEdge( 3, 2 );
365
366 std::stringstream ss;
367 std::string s;
368
369 G.printDot( ss );
370 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "digraph DAG {" );
371 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "node[shape=circle,width=0.4,fixedsize=true];" );
372 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx0;" );
373 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx1;" );
374 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx2;" );
375 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx3;" );
376 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx0 -> x1;" );
377 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx0 -> x2;" );
378 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx1 -> x3;" );
379 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx2 -> x3;" );
380 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "}" );
381
382 ss << G;
383 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "digraph DAG {" );
384 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "node[shape=circle,width=0.4,fixedsize=true];" );
385 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx0;" );
386 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx1;" );
387 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx2;" );
388 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx3;" );
389 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx0 -> x1;" );
390 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx0 -> x2;" );
391 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx1 -> x3;" );
392 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "\tx2 -> x3;" );
393 std::getline( ss, s ); BOOST_CHECK_EQUAL( s, "}" );
394
395 BOOST_CHECK_EQUAL( G.toString(), "digraph DAG {\nnode[shape=circle,width=0.4,fixedsize=true];\n\tx0;\n\tx1;\n\tx2;\n\tx3;\n\tx0 -> x1;\n\tx0 -> x2;\n\tx1 -> x3;\n\tx2 -> x3;\n}\n" );
396 }