|
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library. |
|
4 * |
|
5 * Copyright (C) 2003-2008 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #include <iostream> |
|
20 #include <vector> |
|
21 |
|
22 #include <lemon/concepts/digraph.h> |
|
23 #include <lemon/concepts/graph.h> |
|
24 #include <lemon/concept_check.h> |
|
25 |
|
26 #include <lemon/list_graph.h> |
|
27 |
|
28 #include <lemon/edge_set.h> |
|
29 |
|
30 #include "graph_test.h" |
|
31 #include "test_tools.h" |
|
32 |
|
33 using namespace lemon; |
|
34 |
|
35 void checkSmartArcSet() { |
|
36 checkConcept<concepts::Digraph, SmartArcSet<concepts::Digraph> >(); |
|
37 |
|
38 typedef ListDigraph Digraph; |
|
39 typedef SmartArcSet<Digraph> ArcSet; |
|
40 |
|
41 Digraph digraph; |
|
42 Digraph::Node |
|
43 n1 = digraph.addNode(), |
|
44 n2 = digraph.addNode(); |
|
45 |
|
46 Digraph::Arc ga1 = digraph.addArc(n1, n2); |
|
47 |
|
48 ArcSet arc_set(digraph); |
|
49 |
|
50 Digraph::Arc ga2 = digraph.addArc(n2, n1); |
|
51 |
|
52 checkGraphNodeList(arc_set, 2); |
|
53 checkGraphArcList(arc_set, 0); |
|
54 |
|
55 Digraph::Node |
|
56 n3 = digraph.addNode(); |
|
57 checkGraphNodeList(arc_set, 3); |
|
58 checkGraphArcList(arc_set, 0); |
|
59 |
|
60 ArcSet::Arc a1 = arc_set.addArc(n1, n2); |
|
61 check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc"); |
|
62 checkGraphNodeList(arc_set, 3); |
|
63 checkGraphArcList(arc_set, 1); |
|
64 |
|
65 checkGraphOutArcList(arc_set, n1, 1); |
|
66 checkGraphOutArcList(arc_set, n2, 0); |
|
67 checkGraphOutArcList(arc_set, n3, 0); |
|
68 |
|
69 checkGraphInArcList(arc_set, n1, 0); |
|
70 checkGraphInArcList(arc_set, n2, 1); |
|
71 checkGraphInArcList(arc_set, n3, 0); |
|
72 |
|
73 checkGraphConArcList(arc_set, 1); |
|
74 |
|
75 ArcSet::Arc a2 = arc_set.addArc(n2, n1), |
|
76 a3 = arc_set.addArc(n2, n3), |
|
77 a4 = arc_set.addArc(n2, n3); |
|
78 checkGraphNodeList(arc_set, 3); |
|
79 checkGraphArcList(arc_set, 4); |
|
80 |
|
81 checkGraphOutArcList(arc_set, n1, 1); |
|
82 checkGraphOutArcList(arc_set, n2, 3); |
|
83 checkGraphOutArcList(arc_set, n3, 0); |
|
84 |
|
85 checkGraphInArcList(arc_set, n1, 1); |
|
86 checkGraphInArcList(arc_set, n2, 1); |
|
87 checkGraphInArcList(arc_set, n3, 2); |
|
88 |
|
89 checkGraphConArcList(arc_set, 4); |
|
90 |
|
91 checkNodeIds(arc_set); |
|
92 checkArcIds(arc_set); |
|
93 checkGraphNodeMap(arc_set); |
|
94 checkGraphArcMap(arc_set); |
|
95 |
|
96 check(arc_set.valid(), "Wrong validity"); |
|
97 digraph.erase(n1); |
|
98 check(!arc_set.valid(), "Wrong validity"); |
|
99 } |
|
100 |
|
101 void checkListArcSet() { |
|
102 checkConcept<concepts::Digraph, SmartArcSet<concepts::Digraph> >(); |
|
103 |
|
104 typedef ListDigraph Digraph; |
|
105 typedef ListArcSet<Digraph> ArcSet; |
|
106 |
|
107 Digraph digraph; |
|
108 Digraph::Node |
|
109 n1 = digraph.addNode(), |
|
110 n2 = digraph.addNode(); |
|
111 |
|
112 Digraph::Arc ga1 = digraph.addArc(n1, n2); |
|
113 |
|
114 ArcSet arc_set(digraph); |
|
115 |
|
116 Digraph::Arc ga2 = digraph.addArc(n2, n1); |
|
117 |
|
118 checkGraphNodeList(arc_set, 2); |
|
119 checkGraphArcList(arc_set, 0); |
|
120 |
|
121 Digraph::Node |
|
122 n3 = digraph.addNode(); |
|
123 checkGraphNodeList(arc_set, 3); |
|
124 checkGraphArcList(arc_set, 0); |
|
125 |
|
126 ArcSet::Arc a1 = arc_set.addArc(n1, n2); |
|
127 check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc"); |
|
128 checkGraphNodeList(arc_set, 3); |
|
129 checkGraphArcList(arc_set, 1); |
|
130 |
|
131 checkGraphOutArcList(arc_set, n1, 1); |
|
132 checkGraphOutArcList(arc_set, n2, 0); |
|
133 checkGraphOutArcList(arc_set, n3, 0); |
|
134 |
|
135 checkGraphInArcList(arc_set, n1, 0); |
|
136 checkGraphInArcList(arc_set, n2, 1); |
|
137 checkGraphInArcList(arc_set, n3, 0); |
|
138 |
|
139 checkGraphConArcList(arc_set, 1); |
|
140 |
|
141 ArcSet::Arc a2 = arc_set.addArc(n2, n1), |
|
142 a3 = arc_set.addArc(n2, n3), |
|
143 a4 = arc_set.addArc(n2, n3); |
|
144 checkGraphNodeList(arc_set, 3); |
|
145 checkGraphArcList(arc_set, 4); |
|
146 |
|
147 checkGraphOutArcList(arc_set, n1, 1); |
|
148 checkGraphOutArcList(arc_set, n2, 3); |
|
149 checkGraphOutArcList(arc_set, n3, 0); |
|
150 |
|
151 checkGraphInArcList(arc_set, n1, 1); |
|
152 checkGraphInArcList(arc_set, n2, 1); |
|
153 checkGraphInArcList(arc_set, n3, 2); |
|
154 |
|
155 checkGraphConArcList(arc_set, 4); |
|
156 |
|
157 checkNodeIds(arc_set); |
|
158 checkArcIds(arc_set); |
|
159 checkGraphNodeMap(arc_set); |
|
160 checkGraphArcMap(arc_set); |
|
161 |
|
162 digraph.erase(n1); |
|
163 |
|
164 checkGraphNodeList(arc_set, 2); |
|
165 checkGraphArcList(arc_set, 2); |
|
166 |
|
167 checkGraphOutArcList(arc_set, n2, 2); |
|
168 checkGraphOutArcList(arc_set, n3, 0); |
|
169 |
|
170 checkGraphInArcList(arc_set, n2, 0); |
|
171 checkGraphInArcList(arc_set, n3, 2); |
|
172 |
|
173 checkNodeIds(arc_set); |
|
174 checkArcIds(arc_set); |
|
175 checkGraphNodeMap(arc_set); |
|
176 checkGraphArcMap(arc_set); |
|
177 |
|
178 checkGraphConArcList(arc_set, 2); |
|
179 } |
|
180 |
|
181 void checkSmartEdgeSet() { |
|
182 checkConcept<concepts::Digraph, SmartEdgeSet<concepts::Digraph> >(); |
|
183 |
|
184 typedef ListDigraph Digraph; |
|
185 typedef SmartEdgeSet<Digraph> EdgeSet; |
|
186 |
|
187 Digraph digraph; |
|
188 Digraph::Node |
|
189 n1 = digraph.addNode(), |
|
190 n2 = digraph.addNode(); |
|
191 |
|
192 Digraph::Arc ga1 = digraph.addArc(n1, n2); |
|
193 |
|
194 EdgeSet edge_set(digraph); |
|
195 |
|
196 Digraph::Arc ga2 = digraph.addArc(n2, n1); |
|
197 |
|
198 checkGraphNodeList(edge_set, 2); |
|
199 checkGraphArcList(edge_set, 0); |
|
200 checkGraphEdgeList(edge_set, 0); |
|
201 |
|
202 Digraph::Node |
|
203 n3 = digraph.addNode(); |
|
204 checkGraphNodeList(edge_set, 3); |
|
205 checkGraphArcList(edge_set, 0); |
|
206 checkGraphEdgeList(edge_set, 0); |
|
207 |
|
208 EdgeSet::Edge e1 = edge_set.addEdge(n1, n2); |
|
209 check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) || |
|
210 (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge"); |
|
211 checkGraphNodeList(edge_set, 3); |
|
212 checkGraphArcList(edge_set, 2); |
|
213 checkGraphEdgeList(edge_set, 1); |
|
214 |
|
215 checkGraphOutArcList(edge_set, n1, 1); |
|
216 checkGraphOutArcList(edge_set, n2, 1); |
|
217 checkGraphOutArcList(edge_set, n3, 0); |
|
218 |
|
219 checkGraphInArcList(edge_set, n1, 1); |
|
220 checkGraphInArcList(edge_set, n2, 1); |
|
221 checkGraphInArcList(edge_set, n3, 0); |
|
222 |
|
223 checkGraphIncEdgeList(edge_set, n1, 1); |
|
224 checkGraphIncEdgeList(edge_set, n2, 1); |
|
225 checkGraphIncEdgeList(edge_set, n3, 0); |
|
226 |
|
227 checkGraphConEdgeList(edge_set, 1); |
|
228 checkGraphConArcList(edge_set, 2); |
|
229 |
|
230 EdgeSet::Edge e2 = edge_set.addEdge(n2, n1), |
|
231 e3 = edge_set.addEdge(n2, n3), |
|
232 e4 = edge_set.addEdge(n2, n3); |
|
233 checkGraphNodeList(edge_set, 3); |
|
234 checkGraphEdgeList(edge_set, 4); |
|
235 |
|
236 checkGraphOutArcList(edge_set, n1, 2); |
|
237 checkGraphOutArcList(edge_set, n2, 4); |
|
238 checkGraphOutArcList(edge_set, n3, 2); |
|
239 |
|
240 checkGraphInArcList(edge_set, n1, 2); |
|
241 checkGraphInArcList(edge_set, n2, 4); |
|
242 checkGraphInArcList(edge_set, n3, 2); |
|
243 |
|
244 checkGraphIncEdgeList(edge_set, n1, 2); |
|
245 checkGraphIncEdgeList(edge_set, n2, 4); |
|
246 checkGraphIncEdgeList(edge_set, n3, 2); |
|
247 |
|
248 checkGraphConEdgeList(edge_set, 4); |
|
249 checkGraphConArcList(edge_set, 8); |
|
250 |
|
251 checkArcDirections(edge_set); |
|
252 |
|
253 checkNodeIds(edge_set); |
|
254 checkArcIds(edge_set); |
|
255 checkEdgeIds(edge_set); |
|
256 checkGraphNodeMap(edge_set); |
|
257 checkGraphArcMap(edge_set); |
|
258 checkGraphEdgeMap(edge_set); |
|
259 |
|
260 check(edge_set.valid(), "Wrong validity"); |
|
261 digraph.erase(n1); |
|
262 check(!edge_set.valid(), "Wrong validity"); |
|
263 } |
|
264 |
|
265 void checkListEdgeSet() { |
|
266 checkConcept<concepts::Digraph, ListEdgeSet<concepts::Digraph> >(); |
|
267 |
|
268 typedef ListDigraph Digraph; |
|
269 typedef ListEdgeSet<Digraph> EdgeSet; |
|
270 |
|
271 Digraph digraph; |
|
272 Digraph::Node |
|
273 n1 = digraph.addNode(), |
|
274 n2 = digraph.addNode(); |
|
275 |
|
276 Digraph::Arc ga1 = digraph.addArc(n1, n2); |
|
277 |
|
278 EdgeSet edge_set(digraph); |
|
279 |
|
280 Digraph::Arc ga2 = digraph.addArc(n2, n1); |
|
281 |
|
282 checkGraphNodeList(edge_set, 2); |
|
283 checkGraphArcList(edge_set, 0); |
|
284 checkGraphEdgeList(edge_set, 0); |
|
285 |
|
286 Digraph::Node |
|
287 n3 = digraph.addNode(); |
|
288 checkGraphNodeList(edge_set, 3); |
|
289 checkGraphArcList(edge_set, 0); |
|
290 checkGraphEdgeList(edge_set, 0); |
|
291 |
|
292 EdgeSet::Edge e1 = edge_set.addEdge(n1, n2); |
|
293 check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) || |
|
294 (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge"); |
|
295 checkGraphNodeList(edge_set, 3); |
|
296 checkGraphArcList(edge_set, 2); |
|
297 checkGraphEdgeList(edge_set, 1); |
|
298 |
|
299 checkGraphOutArcList(edge_set, n1, 1); |
|
300 checkGraphOutArcList(edge_set, n2, 1); |
|
301 checkGraphOutArcList(edge_set, n3, 0); |
|
302 |
|
303 checkGraphInArcList(edge_set, n1, 1); |
|
304 checkGraphInArcList(edge_set, n2, 1); |
|
305 checkGraphInArcList(edge_set, n3, 0); |
|
306 |
|
307 checkGraphIncEdgeList(edge_set, n1, 1); |
|
308 checkGraphIncEdgeList(edge_set, n2, 1); |
|
309 checkGraphIncEdgeList(edge_set, n3, 0); |
|
310 |
|
311 checkGraphConEdgeList(edge_set, 1); |
|
312 checkGraphConArcList(edge_set, 2); |
|
313 |
|
314 EdgeSet::Edge e2 = edge_set.addEdge(n2, n1), |
|
315 e3 = edge_set.addEdge(n2, n3), |
|
316 e4 = edge_set.addEdge(n2, n3); |
|
317 checkGraphNodeList(edge_set, 3); |
|
318 checkGraphEdgeList(edge_set, 4); |
|
319 |
|
320 checkGraphOutArcList(edge_set, n1, 2); |
|
321 checkGraphOutArcList(edge_set, n2, 4); |
|
322 checkGraphOutArcList(edge_set, n3, 2); |
|
323 |
|
324 checkGraphInArcList(edge_set, n1, 2); |
|
325 checkGraphInArcList(edge_set, n2, 4); |
|
326 checkGraphInArcList(edge_set, n3, 2); |
|
327 |
|
328 checkGraphIncEdgeList(edge_set, n1, 2); |
|
329 checkGraphIncEdgeList(edge_set, n2, 4); |
|
330 checkGraphIncEdgeList(edge_set, n3, 2); |
|
331 |
|
332 checkGraphConEdgeList(edge_set, 4); |
|
333 checkGraphConArcList(edge_set, 8); |
|
334 |
|
335 checkArcDirections(edge_set); |
|
336 |
|
337 checkNodeIds(edge_set); |
|
338 checkArcIds(edge_set); |
|
339 checkEdgeIds(edge_set); |
|
340 checkGraphNodeMap(edge_set); |
|
341 checkGraphArcMap(edge_set); |
|
342 checkGraphEdgeMap(edge_set); |
|
343 |
|
344 digraph.erase(n1); |
|
345 |
|
346 checkGraphNodeList(edge_set, 2); |
|
347 checkGraphArcList(edge_set, 4); |
|
348 checkGraphEdgeList(edge_set, 2); |
|
349 |
|
350 checkGraphOutArcList(edge_set, n2, 2); |
|
351 checkGraphOutArcList(edge_set, n3, 2); |
|
352 |
|
353 checkGraphInArcList(edge_set, n2, 2); |
|
354 checkGraphInArcList(edge_set, n3, 2); |
|
355 |
|
356 checkGraphIncEdgeList(edge_set, n2, 2); |
|
357 checkGraphIncEdgeList(edge_set, n3, 2); |
|
358 |
|
359 checkNodeIds(edge_set); |
|
360 checkArcIds(edge_set); |
|
361 checkEdgeIds(edge_set); |
|
362 checkGraphNodeMap(edge_set); |
|
363 checkGraphArcMap(edge_set); |
|
364 checkGraphEdgeMap(edge_set); |
|
365 |
|
366 checkGraphConEdgeList(edge_set, 2); |
|
367 checkGraphConArcList(edge_set, 4); |
|
368 |
|
369 } |
|
370 |
|
371 |
|
372 int main() { |
|
373 |
|
374 checkSmartArcSet(); |
|
375 checkListArcSet(); |
|
376 checkSmartEdgeSet(); |
|
377 checkListEdgeSet(); |
|
378 |
|
379 return 0; |
|
380 } |