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