1c5d9f3e3adb2e37aee6669694170bf377ee4532
[libdai.git] / tests / unit / bipgraph.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/bipgraph.h>
15 #include <vector>
16 #include <strstream>
17
18
19 using namespace dai;
20
21
22 #define BOOST_TEST_MODULE BipartiteGraphTest
23
24
25 #include <boost/test/unit_test.hpp>
26
27
28 BOOST_AUTO_TEST_CASE( ConstructorsTest ) {
29 // check constructors
30 typedef BipartiteGraph::Edge Edge;
31
32 BipartiteGraph G;
33 BOOST_CHECK_EQUAL( G.nrNodes1(), 0 );
34 BOOST_CHECK_EQUAL( G.nrNodes2(), 0 );
35 BOOST_CHECK_EQUAL( G.nrEdges(), 0 );
36 BOOST_CHECK( G.isConnected() );
37 BOOST_CHECK( G.isTree() );
38 G.checkConsistency();
39
40 std::vector<Edge> edges;
41 edges.push_back( Edge(0, 0) );
42 edges.push_back( Edge(0, 1) );
43 edges.push_back( Edge(1, 1) );
44 edges.push_back( Edge(1, 2) );
45 edges.push_back( Edge(1, 2) );
46 BipartiteGraph G2( 2, 3, edges.begin(), edges.end() );
47 BOOST_CHECK_EQUAL( G2.nrNodes1(), 2 );
48 BOOST_CHECK_EQUAL( G2.nrNodes2(), 3 );
49 BOOST_CHECK_EQUAL( G2.nrEdges(), 4 );
50 BOOST_CHECK( G2.isConnected() );
51 BOOST_CHECK( G2.isTree() );
52 G2.checkConsistency();
53
54 edges.push_back( Edge(1, 0) );
55 BipartiteGraph G3( 2, 3, edges.begin(), edges.end() );
56 BOOST_CHECK_EQUAL( G3.nrNodes1(), 2 );
57 BOOST_CHECK_EQUAL( G3.nrNodes2(), 3 );
58 BOOST_CHECK_EQUAL( G3.nrEdges(), 5 );
59 BOOST_CHECK( G3.isConnected() );
60 BOOST_CHECK( !G3.isTree() );
61 G3.checkConsistency();
62
63 BipartiteGraph G4( 3, 3, edges.begin(), edges.end() );
64 BOOST_CHECK_EQUAL( G4.nrNodes1(), 3 );
65 BOOST_CHECK_EQUAL( G4.nrNodes2(), 3 );
66 BOOST_CHECK_EQUAL( G4.nrEdges(), 5 );
67 BOOST_CHECK( !G4.isConnected() );
68 BOOST_CHECK( !G4.isTree() );
69 G4.checkConsistency();
70
71 G.construct( 3, 3, edges.begin(), edges.end() );
72 BOOST_CHECK_EQUAL( G.nrNodes1(), 3 );
73 BOOST_CHECK_EQUAL( G.nrNodes2(), 3 );
74 BOOST_CHECK_EQUAL( G.nrEdges(), 5 );
75 BOOST_CHECK( !G.isConnected() );
76 BOOST_CHECK( !G.isTree() );
77 G.checkConsistency();
78 }
79
80
81 BOOST_AUTO_TEST_CASE( NeighborTest ) {
82 // check nb() accessor / mutator
83 typedef BipartiteGraph::Edge Edge;
84 std::vector<Edge> edges;
85 edges.push_back( Edge(0, 0) );
86 edges.push_back( Edge(0, 1) );
87 edges.push_back( Edge(1, 1) );
88 edges.push_back( Edge(1, 2) );
89 BipartiteGraph G( 2, 3, edges.begin(), edges.end() );
90 BOOST_CHECK_EQUAL( G.nb1(0).size(), 2 );
91 BOOST_CHECK_EQUAL( G.nb1(1).size(), 2 );
92 BOOST_CHECK_EQUAL( G.nb2(0).size(), 1 );
93 BOOST_CHECK_EQUAL( G.nb2(1).size(), 2 );
94 BOOST_CHECK_EQUAL( G.nb2(2).size(), 1 );
95 BOOST_CHECK_EQUAL( G.nb1(0,0).iter, 0 );
96 BOOST_CHECK_EQUAL( G.nb1(0,0).node, 0 );
97 BOOST_CHECK_EQUAL( G.nb1(0,0).dual, 0 );
98 BOOST_CHECK_EQUAL( G.nb1(0,1).iter, 1 );
99 BOOST_CHECK_EQUAL( G.nb1(0,1).node, 1 );
100 BOOST_CHECK_EQUAL( G.nb1(0,1).dual, 0 );
101 BOOST_CHECK_EQUAL( G.nb1(1,0).iter, 0 );
102 BOOST_CHECK_EQUAL( G.nb1(1,0).node, 1 );
103 BOOST_CHECK_EQUAL( G.nb1(1,0).dual, 1 );
104 BOOST_CHECK_EQUAL( G.nb1(1,1).iter, 1 );
105 BOOST_CHECK_EQUAL( G.nb1(1,1).node, 2 );
106 BOOST_CHECK_EQUAL( G.nb1(1,1).dual, 0 );
107 BOOST_CHECK_EQUAL( G.nb2(0,0).iter, 0 );
108 BOOST_CHECK_EQUAL( G.nb2(0,0).node, 0 );
109 BOOST_CHECK_EQUAL( G.nb2(0,0).dual, 0 );
110 BOOST_CHECK_EQUAL( G.nb2(1,0).iter, 0 );
111 BOOST_CHECK_EQUAL( G.nb2(1,0).node, 0 );
112 BOOST_CHECK_EQUAL( G.nb2(1,0).dual, 1 );
113 BOOST_CHECK_EQUAL( G.nb2(1,1).iter, 1 );
114 BOOST_CHECK_EQUAL( G.nb2(1,1).node, 1 );
115 BOOST_CHECK_EQUAL( G.nb2(1,1).dual, 0 );
116 BOOST_CHECK_EQUAL( G.nb2(2,0).iter, 0 );
117 BOOST_CHECK_EQUAL( G.nb2(2,0).node, 1 );
118 BOOST_CHECK_EQUAL( G.nb2(2,0).dual, 1 );
119 }
120
121
122 BOOST_AUTO_TEST_CASE( AddEraseTest ) {
123 // check addition and erasure of nodes and edges
124 typedef BipartiteGraph::Edge Edge;
125 std::vector<Edge> edges;
126 edges.push_back( Edge( 0, 0 ) );
127 edges.push_back( Edge( 0, 1 ) );
128 edges.push_back( Edge( 1, 1 ) );
129 BipartiteGraph G( 2, 2, edges.begin(), edges.end() );
130 G.checkConsistency();
131 BOOST_CHECK_EQUAL( G.nrNodes1(), 2 );
132 BOOST_CHECK_EQUAL( G.nrNodes2(), 2 );
133 BOOST_CHECK_EQUAL( G.nrEdges(), 3 );
134 BOOST_CHECK( G.isConnected() );
135 BOOST_CHECK( G.isTree() );
136 BOOST_CHECK_EQUAL( G.addNode1(), 2 );
137 BOOST_CHECK( !G.isConnected() );
138 BOOST_CHECK( !G.isTree() );
139 BOOST_CHECK_EQUAL( G.addNode2(), 2 );
140 BOOST_CHECK( !G.isConnected() );
141 BOOST_CHECK( !G.isTree() );
142 BOOST_CHECK_EQUAL( G.addNode1(), 3 );
143 BOOST_CHECK( !G.isConnected() );
144 BOOST_CHECK( !G.isTree() );
145 G.checkConsistency();
146 std::vector<size_t> nbs;
147 nbs.push_back( 2 );
148 nbs.push_back( 0 );
149 BOOST_CHECK_EQUAL( G.addNode1( nbs.begin(), nbs.end() ), 4 );
150 G.checkConsistency();
151 BOOST_CHECK( !G.isConnected() );
152 BOOST_CHECK( !G.isTree() );
153 BOOST_CHECK_EQUAL( G.addNode2( nbs.begin(), nbs.end() ), 3 );
154 G.checkConsistency();
155 BOOST_CHECK( !G.isConnected() );
156 BOOST_CHECK( !G.isTree() );
157 G.addEdge( 3, 3 );
158 G.checkConsistency();
159 BOOST_CHECK( G.isConnected() );
160 BOOST_CHECK( G.isTree() );
161 G.addEdge( 1, 3 );
162 G.checkConsistency();
163 BOOST_CHECK( G.isConnected() );
164 BOOST_CHECK( !G.isTree() );
165 BOOST_CHECK_EQUAL( G.nrNodes1(), 5 );
166 BOOST_CHECK_EQUAL( G.nrNodes2(), 4 );
167 BOOST_CHECK_EQUAL( G.nrEdges(), 9 );
168 G.eraseEdge( 0, 3 );
169 G.checkConsistency();
170 BOOST_CHECK( G.isConnected() );
171 BOOST_CHECK( G.isTree() );
172 G.eraseEdge( 4, 2 );
173 G.checkConsistency();
174 BOOST_CHECK( !G.isConnected() );
175 BOOST_CHECK( !G.isTree() );
176 G.eraseNode2( 2 );
177 G.checkConsistency();
178 BOOST_CHECK( G.isConnected() );
179 BOOST_CHECK( G.isTree() );
180 G.eraseNode1( 0 );
181 G.checkConsistency();
182 BOOST_CHECK( !G.isConnected() );
183 BOOST_CHECK( !G.isTree() );
184 G.addEdge( 1, 0 );
185 G.checkConsistency();
186 BOOST_CHECK( G.isConnected() );
187 BOOST_CHECK( G.isTree() );
188 G.eraseNode1( 2 );
189 G.checkConsistency();
190 BOOST_CHECK( G.isConnected() );
191 BOOST_CHECK( G.isTree() );
192 G.eraseNode2( 2 );
193 G.checkConsistency();
194 BOOST_CHECK( !G.isConnected() );
195 BOOST_CHECK( !G.isTree() );
196 G.addEdge( 1, 1 );
197 G.checkConsistency();
198 BOOST_CHECK( G.isConnected() );
199 BOOST_CHECK( G.isTree() );
200 G.eraseNode2( 1 );
201 G.checkConsistency();
202 BOOST_CHECK( !G.isConnected() );
203 BOOST_CHECK( !G.isTree() );
204 G.eraseNode1( 1 );
205 G.checkConsistency();
206 BOOST_CHECK( !G.isConnected() );
207 BOOST_CHECK( !G.isTree() );
208 G.addEdge( 0, 0 );
209 G.checkConsistency();
210 BOOST_CHECK( G.isConnected() );
211 BOOST_CHECK( G.isTree() );
212 G.eraseNode2( 0 );
213 G.checkConsistency();
214 BOOST_CHECK( !G.isConnected() );
215 BOOST_CHECK( !G.isTree() );
216 G.eraseNode1( 0 );
217 G.checkConsistency();
218 BOOST_CHECK( G.isConnected() );
219 BOOST_CHECK( G.isTree() );
220 G.eraseNode1( 0 );
221 G.checkConsistency();
222 BOOST_CHECK( G.isConnected() );
223 BOOST_CHECK( G.isTree() );
224 BOOST_CHECK_EQUAL( G.nrNodes1(), 0 );
225 BOOST_CHECK_EQUAL( G.nrNodes2(), 0 );
226 BOOST_CHECK_EQUAL( G.nrEdges(), 0 );
227 }
228
229
230 BOOST_AUTO_TEST_CASE( QueriesTest ) {
231 // check queries which have not been tested in another test case
232 typedef BipartiteGraph::Edge Edge;
233 std::vector<Edge> edges;
234 edges.push_back( Edge( 0, 0 ) );
235 edges.push_back( Edge( 0, 1 ) );
236 edges.push_back( Edge( 1, 1 ) );
237 BipartiteGraph G( 3, 2, edges.begin(), edges.end() );
238 G.checkConsistency();
239 std::vector<size_t> v;
240 std::vector<size_t> v0; v0.push_back(0);
241 std::vector<size_t> v1; v1.push_back(1);
242 std::vector<size_t> v01; v01.push_back(0); v01.push_back(1);
243 BOOST_CHECK( G.delta1( 0, true ) == v01 );
244 BOOST_CHECK( G.delta1( 1, true ) == v01 );
245 BOOST_CHECK( G.delta1( 2, true ) == v );
246 BOOST_CHECK( G.delta2( 0, true ) == v01 );
247 BOOST_CHECK( G.delta2( 1, true ) == v01 );
248 BOOST_CHECK( G.delta1( 0, false ) == v1 );
249 BOOST_CHECK( G.delta1( 1, false ) == v0 );
250 BOOST_CHECK( G.delta1( 2, false ) == v );
251 BOOST_CHECK( G.delta2( 0, false ) == v1 );
252 BOOST_CHECK( G.delta2( 1, false ) == v0 );
253 }
254
255
256 BOOST_AUTO_TEST_CASE( StreamTest ) {
257 // check printDot
258 typedef BipartiteGraph::Edge Edge;
259 std::vector<Edge> edges;
260 edges.push_back( Edge(0, 0) );
261 edges.push_back( Edge(0, 1) );
262 edges.push_back( Edge(1, 1) );
263 edges.push_back( Edge(1, 2) );
264 BipartiteGraph G( 2, 3, edges.begin(), edges.end() );
265
266 std::stringstream ss;
267 G.printDot( ss );
268
269 std::string s;
270 std::getline( ss, s );
271 BOOST_CHECK_EQUAL( s, "graph G {" );
272 std::getline( ss, s );
273 BOOST_CHECK_EQUAL( s, "node[shape=circle,width=0.4,fixedsize=true];" );
274 std::getline( ss, s );
275 BOOST_CHECK_EQUAL( s, "\tx0;" );
276 std::getline( ss, s );
277 BOOST_CHECK_EQUAL( s, "\tx1;" );
278 std::getline( ss, s );
279 BOOST_CHECK_EQUAL( s, "node[shape=box,width=0.3,height=0.3,fixedsize=true];" );
280 std::getline( ss, s );
281 BOOST_CHECK_EQUAL( s, "\ty0;" );
282 std::getline( ss, s );
283 BOOST_CHECK_EQUAL( s, "\ty1;" );
284 std::getline( ss, s );
285 BOOST_CHECK_EQUAL( s, "\ty2;" );
286 std::getline( ss, s );
287 BOOST_CHECK_EQUAL( s, "\tx0 -- y0;" );
288 std::getline( ss, s );
289 BOOST_CHECK_EQUAL( s, "\tx0 -- y1;" );
290 std::getline( ss, s );
291 BOOST_CHECK_EQUAL( s, "\tx1 -- y1;" );
292 std::getline( ss, s );
293 BOOST_CHECK_EQUAL( s, "\tx1 -- y2;" );
294 std::getline( ss, s );
295 BOOST_CHECK_EQUAL( s, "}" );
296 }