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-2009 |
|
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<lemon/concept_check.h> |
|
21 |
|
22 #include<lemon/list_graph.h> |
|
23 #include<lemon/smart_graph.h> |
|
24 |
|
25 #include<lemon/concepts/digraph.h> |
|
26 #include<lemon/concepts/graph.h> |
|
27 |
|
28 #include<lemon/adaptors.h> |
|
29 |
|
30 #include <limits> |
|
31 #include <lemon/bfs.h> |
|
32 #include <lemon/path.h> |
|
33 |
|
34 #include"test/test_tools.h" |
|
35 #include"test/graph_test.h" |
|
36 |
|
37 using namespace lemon; |
|
38 |
|
39 void checkReverseDigraph() { |
|
40 checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >(); |
|
41 |
|
42 typedef ListDigraph Digraph; |
|
43 typedef ReverseDigraph<Digraph> Adaptor; |
|
44 |
|
45 Digraph digraph; |
|
46 Adaptor adaptor(digraph); |
|
47 |
|
48 Digraph::Node n1 = digraph.addNode(); |
|
49 Digraph::Node n2 = digraph.addNode(); |
|
50 Digraph::Node n3 = digraph.addNode(); |
|
51 |
|
52 Digraph::Arc a1 = digraph.addArc(n1, n2); |
|
53 Digraph::Arc a2 = digraph.addArc(n1, n3); |
|
54 Digraph::Arc a3 = digraph.addArc(n2, n3); |
|
55 |
|
56 checkGraphNodeList(adaptor, 3); |
|
57 checkGraphArcList(adaptor, 3); |
|
58 checkGraphConArcList(adaptor, 3); |
|
59 |
|
60 checkGraphOutArcList(adaptor, n1, 0); |
|
61 checkGraphOutArcList(adaptor, n2, 1); |
|
62 checkGraphOutArcList(adaptor, n3, 2); |
|
63 |
|
64 checkGraphInArcList(adaptor, n1, 2); |
|
65 checkGraphInArcList(adaptor, n2, 1); |
|
66 checkGraphInArcList(adaptor, n3, 0); |
|
67 |
|
68 checkNodeIds(adaptor); |
|
69 checkArcIds(adaptor); |
|
70 |
|
71 checkGraphNodeMap(adaptor); |
|
72 checkGraphArcMap(adaptor); |
|
73 |
|
74 for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { |
|
75 check(adaptor.source(a) == digraph.target(a), "Wrong reverse"); |
|
76 check(adaptor.target(a) == digraph.source(a), "Wrong reverse"); |
|
77 } |
|
78 } |
|
79 |
|
80 void checkSubDigraph() { |
|
81 checkConcept<concepts::Digraph, |
|
82 SubDigraph<concepts::Digraph, |
|
83 concepts::Digraph::NodeMap<bool>, |
|
84 concepts::Digraph::ArcMap<bool> > >(); |
|
85 |
|
86 typedef ListDigraph Digraph; |
|
87 typedef Digraph::NodeMap<bool> NodeFilter; |
|
88 typedef Digraph::ArcMap<bool> ArcFilter; |
|
89 typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor; |
|
90 |
|
91 Digraph digraph; |
|
92 NodeFilter node_filter(digraph); |
|
93 ArcFilter arc_filter(digraph); |
|
94 Adaptor adaptor(digraph, node_filter, arc_filter); |
|
95 |
|
96 Digraph::Node n1 = digraph.addNode(); |
|
97 Digraph::Node n2 = digraph.addNode(); |
|
98 Digraph::Node n3 = digraph.addNode(); |
|
99 |
|
100 Digraph::Arc a1 = digraph.addArc(n1, n2); |
|
101 Digraph::Arc a2 = digraph.addArc(n1, n3); |
|
102 Digraph::Arc a3 = digraph.addArc(n2, n3); |
|
103 |
|
104 node_filter[n1] = node_filter[n2] = node_filter[n3] = true; |
|
105 arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true; |
|
106 |
|
107 checkGraphNodeList(adaptor, 3); |
|
108 checkGraphArcList(adaptor, 3); |
|
109 checkGraphConArcList(adaptor, 3); |
|
110 |
|
111 checkGraphOutArcList(adaptor, n1, 2); |
|
112 checkGraphOutArcList(adaptor, n2, 1); |
|
113 checkGraphOutArcList(adaptor, n3, 0); |
|
114 |
|
115 checkGraphInArcList(adaptor, n1, 0); |
|
116 checkGraphInArcList(adaptor, n2, 1); |
|
117 checkGraphInArcList(adaptor, n3, 2); |
|
118 |
|
119 checkNodeIds(adaptor); |
|
120 checkArcIds(adaptor); |
|
121 |
|
122 checkGraphNodeMap(adaptor); |
|
123 checkGraphArcMap(adaptor); |
|
124 |
|
125 arc_filter[a2] = false; |
|
126 |
|
127 checkGraphNodeList(adaptor, 3); |
|
128 checkGraphArcList(adaptor, 2); |
|
129 checkGraphConArcList(adaptor, 2); |
|
130 |
|
131 checkGraphOutArcList(adaptor, n1, 1); |
|
132 checkGraphOutArcList(adaptor, n2, 1); |
|
133 checkGraphOutArcList(adaptor, n3, 0); |
|
134 |
|
135 checkGraphInArcList(adaptor, n1, 0); |
|
136 checkGraphInArcList(adaptor, n2, 1); |
|
137 checkGraphInArcList(adaptor, n3, 1); |
|
138 |
|
139 checkNodeIds(adaptor); |
|
140 checkArcIds(adaptor); |
|
141 |
|
142 checkGraphNodeMap(adaptor); |
|
143 checkGraphArcMap(adaptor); |
|
144 |
|
145 node_filter[n1] = false; |
|
146 |
|
147 checkGraphNodeList(adaptor, 2); |
|
148 checkGraphArcList(adaptor, 1); |
|
149 checkGraphConArcList(adaptor, 1); |
|
150 |
|
151 checkGraphOutArcList(adaptor, n2, 1); |
|
152 checkGraphOutArcList(adaptor, n3, 0); |
|
153 |
|
154 checkGraphInArcList(adaptor, n2, 0); |
|
155 checkGraphInArcList(adaptor, n3, 1); |
|
156 |
|
157 checkNodeIds(adaptor); |
|
158 checkArcIds(adaptor); |
|
159 |
|
160 checkGraphNodeMap(adaptor); |
|
161 checkGraphArcMap(adaptor); |
|
162 |
|
163 node_filter[n1] = node_filter[n2] = node_filter[n3] = false; |
|
164 arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false; |
|
165 |
|
166 checkGraphNodeList(adaptor, 0); |
|
167 checkGraphArcList(adaptor, 0); |
|
168 checkGraphConArcList(adaptor, 0); |
|
169 |
|
170 checkNodeIds(adaptor); |
|
171 checkArcIds(adaptor); |
|
172 |
|
173 checkGraphNodeMap(adaptor); |
|
174 checkGraphArcMap(adaptor); |
|
175 } |
|
176 |
|
177 void checkFilterNodes1() { |
|
178 checkConcept<concepts::Digraph, |
|
179 FilterNodes<concepts::Digraph, |
|
180 concepts::Digraph::NodeMap<bool> > >(); |
|
181 |
|
182 typedef ListDigraph Digraph; |
|
183 typedef Digraph::NodeMap<bool> NodeFilter; |
|
184 typedef FilterNodes<Digraph, NodeFilter> Adaptor; |
|
185 |
|
186 Digraph digraph; |
|
187 NodeFilter node_filter(digraph); |
|
188 Adaptor adaptor(digraph, node_filter); |
|
189 |
|
190 Digraph::Node n1 = digraph.addNode(); |
|
191 Digraph::Node n2 = digraph.addNode(); |
|
192 Digraph::Node n3 = digraph.addNode(); |
|
193 |
|
194 Digraph::Arc a1 = digraph.addArc(n1, n2); |
|
195 Digraph::Arc a2 = digraph.addArc(n1, n3); |
|
196 Digraph::Arc a3 = digraph.addArc(n2, n3); |
|
197 |
|
198 node_filter[n1] = node_filter[n2] = node_filter[n3] = true; |
|
199 |
|
200 checkGraphNodeList(adaptor, 3); |
|
201 checkGraphArcList(adaptor, 3); |
|
202 checkGraphConArcList(adaptor, 3); |
|
203 |
|
204 checkGraphOutArcList(adaptor, n1, 2); |
|
205 checkGraphOutArcList(adaptor, n2, 1); |
|
206 checkGraphOutArcList(adaptor, n3, 0); |
|
207 |
|
208 checkGraphInArcList(adaptor, n1, 0); |
|
209 checkGraphInArcList(adaptor, n2, 1); |
|
210 checkGraphInArcList(adaptor, n3, 2); |
|
211 |
|
212 checkNodeIds(adaptor); |
|
213 checkArcIds(adaptor); |
|
214 |
|
215 checkGraphNodeMap(adaptor); |
|
216 checkGraphArcMap(adaptor); |
|
217 |
|
218 node_filter[n1] = false; |
|
219 |
|
220 checkGraphNodeList(adaptor, 2); |
|
221 checkGraphArcList(adaptor, 1); |
|
222 checkGraphConArcList(adaptor, 1); |
|
223 |
|
224 checkGraphOutArcList(adaptor, n2, 1); |
|
225 checkGraphOutArcList(adaptor, n3, 0); |
|
226 |
|
227 checkGraphInArcList(adaptor, n2, 0); |
|
228 checkGraphInArcList(adaptor, n3, 1); |
|
229 |
|
230 checkNodeIds(adaptor); |
|
231 checkArcIds(adaptor); |
|
232 |
|
233 checkGraphNodeMap(adaptor); |
|
234 checkGraphArcMap(adaptor); |
|
235 |
|
236 node_filter[n1] = node_filter[n2] = node_filter[n3] = false; |
|
237 |
|
238 checkGraphNodeList(adaptor, 0); |
|
239 checkGraphArcList(adaptor, 0); |
|
240 checkGraphConArcList(adaptor, 0); |
|
241 |
|
242 checkNodeIds(adaptor); |
|
243 checkArcIds(adaptor); |
|
244 |
|
245 checkGraphNodeMap(adaptor); |
|
246 checkGraphArcMap(adaptor); |
|
247 } |
|
248 |
|
249 void checkFilterArcs() { |
|
250 checkConcept<concepts::Digraph, |
|
251 FilterArcs<concepts::Digraph, |
|
252 concepts::Digraph::ArcMap<bool> > >(); |
|
253 |
|
254 typedef ListDigraph Digraph; |
|
255 typedef Digraph::ArcMap<bool> ArcFilter; |
|
256 typedef FilterArcs<Digraph, ArcFilter> Adaptor; |
|
257 |
|
258 Digraph digraph; |
|
259 ArcFilter arc_filter(digraph); |
|
260 Adaptor adaptor(digraph, arc_filter); |
|
261 |
|
262 Digraph::Node n1 = digraph.addNode(); |
|
263 Digraph::Node n2 = digraph.addNode(); |
|
264 Digraph::Node n3 = digraph.addNode(); |
|
265 |
|
266 Digraph::Arc a1 = digraph.addArc(n1, n2); |
|
267 Digraph::Arc a2 = digraph.addArc(n1, n3); |
|
268 Digraph::Arc a3 = digraph.addArc(n2, n3); |
|
269 |
|
270 arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true; |
|
271 |
|
272 checkGraphNodeList(adaptor, 3); |
|
273 checkGraphArcList(adaptor, 3); |
|
274 checkGraphConArcList(adaptor, 3); |
|
275 |
|
276 checkGraphOutArcList(adaptor, n1, 2); |
|
277 checkGraphOutArcList(adaptor, n2, 1); |
|
278 checkGraphOutArcList(adaptor, n3, 0); |
|
279 |
|
280 checkGraphInArcList(adaptor, n1, 0); |
|
281 checkGraphInArcList(adaptor, n2, 1); |
|
282 checkGraphInArcList(adaptor, n3, 2); |
|
283 |
|
284 checkNodeIds(adaptor); |
|
285 checkArcIds(adaptor); |
|
286 |
|
287 checkGraphNodeMap(adaptor); |
|
288 checkGraphArcMap(adaptor); |
|
289 |
|
290 arc_filter[a2] = false; |
|
291 |
|
292 checkGraphNodeList(adaptor, 3); |
|
293 checkGraphArcList(adaptor, 2); |
|
294 checkGraphConArcList(adaptor, 2); |
|
295 |
|
296 checkGraphOutArcList(adaptor, n1, 1); |
|
297 checkGraphOutArcList(adaptor, n2, 1); |
|
298 checkGraphOutArcList(adaptor, n3, 0); |
|
299 |
|
300 checkGraphInArcList(adaptor, n1, 0); |
|
301 checkGraphInArcList(adaptor, n2, 1); |
|
302 checkGraphInArcList(adaptor, n3, 1); |
|
303 |
|
304 checkNodeIds(adaptor); |
|
305 checkArcIds(adaptor); |
|
306 |
|
307 checkGraphNodeMap(adaptor); |
|
308 checkGraphArcMap(adaptor); |
|
309 |
|
310 arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false; |
|
311 |
|
312 checkGraphNodeList(adaptor, 3); |
|
313 checkGraphArcList(adaptor, 0); |
|
314 checkGraphConArcList(adaptor, 0); |
|
315 |
|
316 checkNodeIds(adaptor); |
|
317 checkArcIds(adaptor); |
|
318 |
|
319 checkGraphNodeMap(adaptor); |
|
320 checkGraphArcMap(adaptor); |
|
321 } |
|
322 |
|
323 void checkUndirector() { |
|
324 checkConcept<concepts::Graph, Undirector<concepts::Digraph> >(); |
|
325 |
|
326 typedef ListDigraph Digraph; |
|
327 typedef Undirector<Digraph> Adaptor; |
|
328 |
|
329 Digraph digraph; |
|
330 Adaptor adaptor(digraph); |
|
331 |
|
332 Digraph::Node n1 = digraph.addNode(); |
|
333 Digraph::Node n2 = digraph.addNode(); |
|
334 Digraph::Node n3 = digraph.addNode(); |
|
335 |
|
336 Digraph::Arc a1 = digraph.addArc(n1, n2); |
|
337 Digraph::Arc a2 = digraph.addArc(n1, n3); |
|
338 Digraph::Arc a3 = digraph.addArc(n2, n3); |
|
339 |
|
340 checkGraphNodeList(adaptor, 3); |
|
341 checkGraphArcList(adaptor, 6); |
|
342 checkGraphEdgeList(adaptor, 3); |
|
343 checkGraphConArcList(adaptor, 6); |
|
344 checkGraphConEdgeList(adaptor, 3); |
|
345 |
|
346 checkGraphOutArcList(adaptor, n1, 2); |
|
347 checkGraphOutArcList(adaptor, n2, 2); |
|
348 checkGraphOutArcList(adaptor, n3, 2); |
|
349 |
|
350 checkGraphInArcList(adaptor, n1, 2); |
|
351 checkGraphInArcList(adaptor, n2, 2); |
|
352 checkGraphInArcList(adaptor, n3, 2); |
|
353 |
|
354 checkGraphIncEdgeList(adaptor, n1, 2); |
|
355 checkGraphIncEdgeList(adaptor, n2, 2); |
|
356 checkGraphIncEdgeList(adaptor, n3, 2); |
|
357 |
|
358 checkNodeIds(adaptor); |
|
359 checkArcIds(adaptor); |
|
360 checkEdgeIds(adaptor); |
|
361 |
|
362 checkGraphNodeMap(adaptor); |
|
363 checkGraphArcMap(adaptor); |
|
364 checkGraphEdgeMap(adaptor); |
|
365 |
|
366 for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) { |
|
367 check(adaptor.u(e) == digraph.source(e), "Wrong undir"); |
|
368 check(adaptor.v(e) == digraph.target(e), "Wrong undir"); |
|
369 } |
|
370 |
|
371 } |
|
372 |
|
373 void checkResidual() { |
|
374 checkConcept<concepts::Digraph, |
|
375 Residual<concepts::Digraph, |
|
376 concepts::Digraph::ArcMap<int>, |
|
377 concepts::Digraph::ArcMap<int> > >(); |
|
378 |
|
379 typedef ListDigraph Digraph; |
|
380 typedef Digraph::ArcMap<int> IntArcMap; |
|
381 typedef Residual<Digraph, IntArcMap> Adaptor; |
|
382 |
|
383 Digraph digraph; |
|
384 IntArcMap capacity(digraph), flow(digraph); |
|
385 Adaptor adaptor(digraph, capacity, flow); |
|
386 |
|
387 Digraph::Node n1 = digraph.addNode(); |
|
388 Digraph::Node n2 = digraph.addNode(); |
|
389 Digraph::Node n3 = digraph.addNode(); |
|
390 Digraph::Node n4 = digraph.addNode(); |
|
391 |
|
392 Digraph::Arc a1 = digraph.addArc(n1, n2); |
|
393 Digraph::Arc a2 = digraph.addArc(n1, n3); |
|
394 Digraph::Arc a3 = digraph.addArc(n1, n4); |
|
395 Digraph::Arc a4 = digraph.addArc(n2, n3); |
|
396 Digraph::Arc a5 = digraph.addArc(n2, n4); |
|
397 Digraph::Arc a6 = digraph.addArc(n3, n4); |
|
398 |
|
399 capacity[a1] = 8; |
|
400 capacity[a2] = 6; |
|
401 capacity[a3] = 4; |
|
402 capacity[a4] = 4; |
|
403 capacity[a5] = 6; |
|
404 capacity[a6] = 10; |
|
405 |
|
406 for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { |
|
407 flow[a] = 0; |
|
408 } |
|
409 |
|
410 checkGraphNodeList(adaptor, 4); |
|
411 checkGraphArcList(adaptor, 6); |
|
412 checkGraphConArcList(adaptor, 6); |
|
413 |
|
414 checkGraphOutArcList(adaptor, n1, 3); |
|
415 checkGraphOutArcList(adaptor, n2, 2); |
|
416 checkGraphOutArcList(adaptor, n3, 1); |
|
417 checkGraphOutArcList(adaptor, n4, 0); |
|
418 |
|
419 checkGraphInArcList(adaptor, n1, 0); |
|
420 checkGraphInArcList(adaptor, n2, 1); |
|
421 checkGraphInArcList(adaptor, n3, 2); |
|
422 checkGraphInArcList(adaptor, n4, 3); |
|
423 |
|
424 for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { |
|
425 flow[a] = capacity[a] / 2; |
|
426 } |
|
427 |
|
428 checkGraphNodeList(adaptor, 4); |
|
429 checkGraphArcList(adaptor, 12); |
|
430 checkGraphConArcList(adaptor, 12); |
|
431 |
|
432 checkGraphOutArcList(adaptor, n1, 3); |
|
433 checkGraphOutArcList(adaptor, n2, 3); |
|
434 checkGraphOutArcList(adaptor, n3, 3); |
|
435 checkGraphOutArcList(adaptor, n4, 3); |
|
436 |
|
437 checkGraphInArcList(adaptor, n1, 3); |
|
438 checkGraphInArcList(adaptor, n2, 3); |
|
439 checkGraphInArcList(adaptor, n3, 3); |
|
440 checkGraphInArcList(adaptor, n4, 3); |
|
441 |
|
442 checkNodeIds(adaptor); |
|
443 checkArcIds(adaptor); |
|
444 |
|
445 checkGraphNodeMap(adaptor); |
|
446 checkGraphArcMap(adaptor); |
|
447 |
|
448 for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { |
|
449 flow[a] = capacity[a]; |
|
450 } |
|
451 |
|
452 checkGraphNodeList(adaptor, 4); |
|
453 checkGraphArcList(adaptor, 6); |
|
454 checkGraphConArcList(adaptor, 6); |
|
455 |
|
456 checkGraphOutArcList(adaptor, n1, 0); |
|
457 checkGraphOutArcList(adaptor, n2, 1); |
|
458 checkGraphOutArcList(adaptor, n3, 2); |
|
459 checkGraphOutArcList(adaptor, n4, 3); |
|
460 |
|
461 checkGraphInArcList(adaptor, n1, 3); |
|
462 checkGraphInArcList(adaptor, n2, 2); |
|
463 checkGraphInArcList(adaptor, n3, 1); |
|
464 checkGraphInArcList(adaptor, n4, 0); |
|
465 |
|
466 for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { |
|
467 flow[a] = 0; |
|
468 } |
|
469 |
|
470 int flow_value = 0; |
|
471 while (true) { |
|
472 |
|
473 Bfs<Adaptor> bfs(adaptor); |
|
474 bfs.run(n1, n4); |
|
475 |
|
476 if (!bfs.reached(n4)) break; |
|
477 |
|
478 Path<Adaptor> p = bfs.path(n4); |
|
479 |
|
480 int min = std::numeric_limits<int>::max(); |
|
481 for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) { |
|
482 if (adaptor.residualCapacity(a) < min) |
|
483 min = adaptor.residualCapacity(a); |
|
484 } |
|
485 |
|
486 for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) { |
|
487 adaptor.augment(a, min); |
|
488 } |
|
489 flow_value += min; |
|
490 } |
|
491 |
|
492 check(flow_value == 18, "Wrong flow with res graph adaptor"); |
|
493 |
|
494 } |
|
495 |
|
496 void checkSplitNodes() { |
|
497 checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >(); |
|
498 |
|
499 typedef ListDigraph Digraph; |
|
500 typedef SplitNodes<Digraph> Adaptor; |
|
501 |
|
502 Digraph digraph; |
|
503 Adaptor adaptor(digraph); |
|
504 |
|
505 Digraph::Node n1 = digraph.addNode(); |
|
506 Digraph::Node n2 = digraph.addNode(); |
|
507 Digraph::Node n3 = digraph.addNode(); |
|
508 |
|
509 Digraph::Arc a1 = digraph.addArc(n1, n2); |
|
510 Digraph::Arc a2 = digraph.addArc(n1, n3); |
|
511 Digraph::Arc a3 = digraph.addArc(n2, n3); |
|
512 |
|
513 checkGraphNodeList(adaptor, 6); |
|
514 checkGraphArcList(adaptor, 6); |
|
515 checkGraphConArcList(adaptor, 6); |
|
516 |
|
517 checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1); |
|
518 checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2); |
|
519 checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1); |
|
520 checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1); |
|
521 checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1); |
|
522 checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0); |
|
523 |
|
524 checkGraphInArcList(adaptor, adaptor.inNode(n1), 0); |
|
525 checkGraphInArcList(adaptor, adaptor.outNode(n1), 1); |
|
526 checkGraphInArcList(adaptor, adaptor.inNode(n2), 1); |
|
527 checkGraphInArcList(adaptor, adaptor.outNode(n2), 1); |
|
528 checkGraphInArcList(adaptor, adaptor.inNode(n3), 2); |
|
529 checkGraphInArcList(adaptor, adaptor.outNode(n3), 1); |
|
530 |
|
531 checkNodeIds(adaptor); |
|
532 checkArcIds(adaptor); |
|
533 |
|
534 checkGraphNodeMap(adaptor); |
|
535 checkGraphArcMap(adaptor); |
|
536 |
|
537 for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { |
|
538 if (adaptor.origArc(a)) { |
|
539 Digraph::Arc oa = a; |
|
540 check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)), |
|
541 "Wrong split"); |
|
542 check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)), |
|
543 "Wrong split"); |
|
544 } else { |
|
545 Digraph::Node on = a; |
|
546 check(adaptor.source(a) == adaptor.inNode(on), "Wrong split"); |
|
547 check(adaptor.target(a) == adaptor.outNode(on), "Wrong split"); |
|
548 } |
|
549 } |
|
550 } |
|
551 |
|
552 void checkSubGraph() { |
|
553 checkConcept<concepts::Graph, |
|
554 SubGraph<concepts::Graph, |
|
555 concepts::Graph::NodeMap<bool>, |
|
556 concepts::Graph::EdgeMap<bool> > >(); |
|
557 |
|
558 typedef ListGraph Graph; |
|
559 typedef Graph::NodeMap<bool> NodeFilter; |
|
560 typedef Graph::EdgeMap<bool> EdgeFilter; |
|
561 typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor; |
|
562 |
|
563 Graph graph; |
|
564 NodeFilter node_filter(graph); |
|
565 EdgeFilter edge_filter(graph); |
|
566 Adaptor adaptor(graph, node_filter, edge_filter); |
|
567 |
|
568 Graph::Node n1 = graph.addNode(); |
|
569 Graph::Node n2 = graph.addNode(); |
|
570 Graph::Node n3 = graph.addNode(); |
|
571 Graph::Node n4 = graph.addNode(); |
|
572 |
|
573 Graph::Edge e1 = graph.addEdge(n1, n2); |
|
574 Graph::Edge e2 = graph.addEdge(n1, n3); |
|
575 Graph::Edge e3 = graph.addEdge(n2, n3); |
|
576 Graph::Edge e4 = graph.addEdge(n3, n4); |
|
577 |
|
578 node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true; |
|
579 edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true; |
|
580 |
|
581 checkGraphNodeList(adaptor, 4); |
|
582 checkGraphArcList(adaptor, 8); |
|
583 checkGraphEdgeList(adaptor, 4); |
|
584 checkGraphConArcList(adaptor, 8); |
|
585 checkGraphConEdgeList(adaptor, 4); |
|
586 |
|
587 checkGraphOutArcList(adaptor, n1, 2); |
|
588 checkGraphOutArcList(adaptor, n2, 2); |
|
589 checkGraphOutArcList(adaptor, n3, 3); |
|
590 checkGraphOutArcList(adaptor, n4, 1); |
|
591 |
|
592 checkGraphInArcList(adaptor, n1, 2); |
|
593 checkGraphInArcList(adaptor, n2, 2); |
|
594 checkGraphInArcList(adaptor, n3, 3); |
|
595 checkGraphInArcList(adaptor, n4, 1); |
|
596 |
|
597 checkGraphIncEdgeList(adaptor, n1, 2); |
|
598 checkGraphIncEdgeList(adaptor, n2, 2); |
|
599 checkGraphIncEdgeList(adaptor, n3, 3); |
|
600 checkGraphIncEdgeList(adaptor, n4, 1); |
|
601 |
|
602 checkNodeIds(adaptor); |
|
603 checkArcIds(adaptor); |
|
604 checkEdgeIds(adaptor); |
|
605 |
|
606 checkGraphNodeMap(adaptor); |
|
607 checkGraphArcMap(adaptor); |
|
608 checkGraphEdgeMap(adaptor); |
|
609 |
|
610 edge_filter[e2] = false; |
|
611 |
|
612 checkGraphNodeList(adaptor, 4); |
|
613 checkGraphArcList(adaptor, 6); |
|
614 checkGraphEdgeList(adaptor, 3); |
|
615 checkGraphConArcList(adaptor, 6); |
|
616 checkGraphConEdgeList(adaptor, 3); |
|
617 |
|
618 checkGraphOutArcList(adaptor, n1, 1); |
|
619 checkGraphOutArcList(adaptor, n2, 2); |
|
620 checkGraphOutArcList(adaptor, n3, 2); |
|
621 checkGraphOutArcList(adaptor, n4, 1); |
|
622 |
|
623 checkGraphInArcList(adaptor, n1, 1); |
|
624 checkGraphInArcList(adaptor, n2, 2); |
|
625 checkGraphInArcList(adaptor, n3, 2); |
|
626 checkGraphInArcList(adaptor, n4, 1); |
|
627 |
|
628 checkGraphIncEdgeList(adaptor, n1, 1); |
|
629 checkGraphIncEdgeList(adaptor, n2, 2); |
|
630 checkGraphIncEdgeList(adaptor, n3, 2); |
|
631 checkGraphIncEdgeList(adaptor, n4, 1); |
|
632 |
|
633 checkNodeIds(adaptor); |
|
634 checkArcIds(adaptor); |
|
635 checkEdgeIds(adaptor); |
|
636 |
|
637 checkGraphNodeMap(adaptor); |
|
638 checkGraphArcMap(adaptor); |
|
639 checkGraphEdgeMap(adaptor); |
|
640 |
|
641 node_filter[n1] = false; |
|
642 |
|
643 checkGraphNodeList(adaptor, 3); |
|
644 checkGraphArcList(adaptor, 4); |
|
645 checkGraphEdgeList(adaptor, 2); |
|
646 checkGraphConArcList(adaptor, 4); |
|
647 checkGraphConEdgeList(adaptor, 2); |
|
648 |
|
649 checkGraphOutArcList(adaptor, n2, 1); |
|
650 checkGraphOutArcList(adaptor, n3, 2); |
|
651 checkGraphOutArcList(adaptor, n4, 1); |
|
652 |
|
653 checkGraphInArcList(adaptor, n2, 1); |
|
654 checkGraphInArcList(adaptor, n3, 2); |
|
655 checkGraphInArcList(adaptor, n4, 1); |
|
656 |
|
657 checkGraphIncEdgeList(adaptor, n2, 1); |
|
658 checkGraphIncEdgeList(adaptor, n3, 2); |
|
659 checkGraphIncEdgeList(adaptor, n4, 1); |
|
660 |
|
661 checkNodeIds(adaptor); |
|
662 checkArcIds(adaptor); |
|
663 checkEdgeIds(adaptor); |
|
664 |
|
665 checkGraphNodeMap(adaptor); |
|
666 checkGraphArcMap(adaptor); |
|
667 checkGraphEdgeMap(adaptor); |
|
668 |
|
669 node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false; |
|
670 edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false; |
|
671 |
|
672 checkGraphNodeList(adaptor, 0); |
|
673 checkGraphArcList(adaptor, 0); |
|
674 checkGraphEdgeList(adaptor, 0); |
|
675 checkGraphConArcList(adaptor, 0); |
|
676 checkGraphConEdgeList(adaptor, 0); |
|
677 |
|
678 checkNodeIds(adaptor); |
|
679 checkArcIds(adaptor); |
|
680 checkEdgeIds(adaptor); |
|
681 |
|
682 checkGraphNodeMap(adaptor); |
|
683 checkGraphArcMap(adaptor); |
|
684 checkGraphEdgeMap(adaptor); |
|
685 } |
|
686 |
|
687 void checkFilterNodes2() { |
|
688 checkConcept<concepts::Graph, |
|
689 FilterNodes<concepts::Graph, |
|
690 concepts::Graph::NodeMap<bool> > >(); |
|
691 |
|
692 typedef ListGraph Graph; |
|
693 typedef Graph::NodeMap<bool> NodeFilter; |
|
694 typedef FilterNodes<Graph, NodeFilter> Adaptor; |
|
695 |
|
696 Graph graph; |
|
697 NodeFilter node_filter(graph); |
|
698 Adaptor adaptor(graph, node_filter); |
|
699 |
|
700 Graph::Node n1 = graph.addNode(); |
|
701 Graph::Node n2 = graph.addNode(); |
|
702 Graph::Node n3 = graph.addNode(); |
|
703 Graph::Node n4 = graph.addNode(); |
|
704 |
|
705 Graph::Edge e1 = graph.addEdge(n1, n2); |
|
706 Graph::Edge e2 = graph.addEdge(n1, n3); |
|
707 Graph::Edge e3 = graph.addEdge(n2, n3); |
|
708 Graph::Edge e4 = graph.addEdge(n3, n4); |
|
709 |
|
710 node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true; |
|
711 |
|
712 checkGraphNodeList(adaptor, 4); |
|
713 checkGraphArcList(adaptor, 8); |
|
714 checkGraphEdgeList(adaptor, 4); |
|
715 checkGraphConArcList(adaptor, 8); |
|
716 checkGraphConEdgeList(adaptor, 4); |
|
717 |
|
718 checkGraphOutArcList(adaptor, n1, 2); |
|
719 checkGraphOutArcList(adaptor, n2, 2); |
|
720 checkGraphOutArcList(adaptor, n3, 3); |
|
721 checkGraphOutArcList(adaptor, n4, 1); |
|
722 |
|
723 checkGraphInArcList(adaptor, n1, 2); |
|
724 checkGraphInArcList(adaptor, n2, 2); |
|
725 checkGraphInArcList(adaptor, n3, 3); |
|
726 checkGraphInArcList(adaptor, n4, 1); |
|
727 |
|
728 checkGraphIncEdgeList(adaptor, n1, 2); |
|
729 checkGraphIncEdgeList(adaptor, n2, 2); |
|
730 checkGraphIncEdgeList(adaptor, n3, 3); |
|
731 checkGraphIncEdgeList(adaptor, n4, 1); |
|
732 |
|
733 checkNodeIds(adaptor); |
|
734 checkArcIds(adaptor); |
|
735 checkEdgeIds(adaptor); |
|
736 |
|
737 checkGraphNodeMap(adaptor); |
|
738 checkGraphArcMap(adaptor); |
|
739 checkGraphEdgeMap(adaptor); |
|
740 |
|
741 node_filter[n1] = false; |
|
742 |
|
743 checkGraphNodeList(adaptor, 3); |
|
744 checkGraphArcList(adaptor, 4); |
|
745 checkGraphEdgeList(adaptor, 2); |
|
746 checkGraphConArcList(adaptor, 4); |
|
747 checkGraphConEdgeList(adaptor, 2); |
|
748 |
|
749 checkGraphOutArcList(adaptor, n2, 1); |
|
750 checkGraphOutArcList(adaptor, n3, 2); |
|
751 checkGraphOutArcList(adaptor, n4, 1); |
|
752 |
|
753 checkGraphInArcList(adaptor, n2, 1); |
|
754 checkGraphInArcList(adaptor, n3, 2); |
|
755 checkGraphInArcList(adaptor, n4, 1); |
|
756 |
|
757 checkGraphIncEdgeList(adaptor, n2, 1); |
|
758 checkGraphIncEdgeList(adaptor, n3, 2); |
|
759 checkGraphIncEdgeList(adaptor, n4, 1); |
|
760 |
|
761 checkNodeIds(adaptor); |
|
762 checkArcIds(adaptor); |
|
763 checkEdgeIds(adaptor); |
|
764 |
|
765 checkGraphNodeMap(adaptor); |
|
766 checkGraphArcMap(adaptor); |
|
767 checkGraphEdgeMap(adaptor); |
|
768 |
|
769 node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false; |
|
770 |
|
771 checkGraphNodeList(adaptor, 0); |
|
772 checkGraphArcList(adaptor, 0); |
|
773 checkGraphEdgeList(adaptor, 0); |
|
774 checkGraphConArcList(adaptor, 0); |
|
775 checkGraphConEdgeList(adaptor, 0); |
|
776 |
|
777 checkNodeIds(adaptor); |
|
778 checkArcIds(adaptor); |
|
779 checkEdgeIds(adaptor); |
|
780 |
|
781 checkGraphNodeMap(adaptor); |
|
782 checkGraphArcMap(adaptor); |
|
783 checkGraphEdgeMap(adaptor); |
|
784 } |
|
785 |
|
786 void checkFilterEdges() { |
|
787 checkConcept<concepts::Graph, |
|
788 FilterEdges<concepts::Graph, |
|
789 concepts::Graph::EdgeMap<bool> > >(); |
|
790 |
|
791 typedef ListGraph Graph; |
|
792 typedef Graph::EdgeMap<bool> EdgeFilter; |
|
793 typedef FilterEdges<Graph, EdgeFilter> Adaptor; |
|
794 |
|
795 Graph graph; |
|
796 EdgeFilter edge_filter(graph); |
|
797 Adaptor adaptor(graph, edge_filter); |
|
798 |
|
799 Graph::Node n1 = graph.addNode(); |
|
800 Graph::Node n2 = graph.addNode(); |
|
801 Graph::Node n3 = graph.addNode(); |
|
802 Graph::Node n4 = graph.addNode(); |
|
803 |
|
804 Graph::Edge e1 = graph.addEdge(n1, n2); |
|
805 Graph::Edge e2 = graph.addEdge(n1, n3); |
|
806 Graph::Edge e3 = graph.addEdge(n2, n3); |
|
807 Graph::Edge e4 = graph.addEdge(n3, n4); |
|
808 |
|
809 edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true; |
|
810 |
|
811 checkGraphNodeList(adaptor, 4); |
|
812 checkGraphArcList(adaptor, 8); |
|
813 checkGraphEdgeList(adaptor, 4); |
|
814 checkGraphConArcList(adaptor, 8); |
|
815 checkGraphConEdgeList(adaptor, 4); |
|
816 |
|
817 checkGraphOutArcList(adaptor, n1, 2); |
|
818 checkGraphOutArcList(adaptor, n2, 2); |
|
819 checkGraphOutArcList(adaptor, n3, 3); |
|
820 checkGraphOutArcList(adaptor, n4, 1); |
|
821 |
|
822 checkGraphInArcList(adaptor, n1, 2); |
|
823 checkGraphInArcList(adaptor, n2, 2); |
|
824 checkGraphInArcList(adaptor, n3, 3); |
|
825 checkGraphInArcList(adaptor, n4, 1); |
|
826 |
|
827 checkGraphIncEdgeList(adaptor, n1, 2); |
|
828 checkGraphIncEdgeList(adaptor, n2, 2); |
|
829 checkGraphIncEdgeList(adaptor, n3, 3); |
|
830 checkGraphIncEdgeList(adaptor, n4, 1); |
|
831 |
|
832 checkNodeIds(adaptor); |
|
833 checkArcIds(adaptor); |
|
834 checkEdgeIds(adaptor); |
|
835 |
|
836 checkGraphNodeMap(adaptor); |
|
837 checkGraphArcMap(adaptor); |
|
838 checkGraphEdgeMap(adaptor); |
|
839 |
|
840 edge_filter[e2] = false; |
|
841 |
|
842 checkGraphNodeList(adaptor, 4); |
|
843 checkGraphArcList(adaptor, 6); |
|
844 checkGraphEdgeList(adaptor, 3); |
|
845 checkGraphConArcList(adaptor, 6); |
|
846 checkGraphConEdgeList(adaptor, 3); |
|
847 |
|
848 checkGraphOutArcList(adaptor, n1, 1); |
|
849 checkGraphOutArcList(adaptor, n2, 2); |
|
850 checkGraphOutArcList(adaptor, n3, 2); |
|
851 checkGraphOutArcList(adaptor, n4, 1); |
|
852 |
|
853 checkGraphInArcList(adaptor, n1, 1); |
|
854 checkGraphInArcList(adaptor, n2, 2); |
|
855 checkGraphInArcList(adaptor, n3, 2); |
|
856 checkGraphInArcList(adaptor, n4, 1); |
|
857 |
|
858 checkGraphIncEdgeList(adaptor, n1, 1); |
|
859 checkGraphIncEdgeList(adaptor, n2, 2); |
|
860 checkGraphIncEdgeList(adaptor, n3, 2); |
|
861 checkGraphIncEdgeList(adaptor, n4, 1); |
|
862 |
|
863 checkNodeIds(adaptor); |
|
864 checkArcIds(adaptor); |
|
865 checkEdgeIds(adaptor); |
|
866 |
|
867 checkGraphNodeMap(adaptor); |
|
868 checkGraphArcMap(adaptor); |
|
869 checkGraphEdgeMap(adaptor); |
|
870 |
|
871 edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false; |
|
872 |
|
873 checkGraphNodeList(adaptor, 4); |
|
874 checkGraphArcList(adaptor, 0); |
|
875 checkGraphEdgeList(adaptor, 0); |
|
876 checkGraphConArcList(adaptor, 0); |
|
877 checkGraphConEdgeList(adaptor, 0); |
|
878 |
|
879 checkNodeIds(adaptor); |
|
880 checkArcIds(adaptor); |
|
881 checkEdgeIds(adaptor); |
|
882 |
|
883 checkGraphNodeMap(adaptor); |
|
884 checkGraphArcMap(adaptor); |
|
885 checkGraphEdgeMap(adaptor); |
|
886 } |
|
887 |
|
888 void checkOrienter() { |
|
889 checkConcept<concepts::Digraph, |
|
890 Orienter<concepts::Graph, concepts::Graph::EdgeMap<bool> > >(); |
|
891 |
|
892 typedef ListGraph Graph; |
|
893 typedef ListGraph::EdgeMap<bool> DirMap; |
|
894 typedef Orienter<Graph> Adaptor; |
|
895 |
|
896 Graph graph; |
|
897 DirMap dir(graph, true); |
|
898 Adaptor adaptor(graph, dir); |
|
899 |
|
900 Graph::Node n1 = graph.addNode(); |
|
901 Graph::Node n2 = graph.addNode(); |
|
902 Graph::Node n3 = graph.addNode(); |
|
903 |
|
904 Graph::Edge e1 = graph.addEdge(n1, n2); |
|
905 Graph::Edge e2 = graph.addEdge(n1, n3); |
|
906 Graph::Edge e3 = graph.addEdge(n2, n3); |
|
907 |
|
908 checkGraphNodeList(adaptor, 3); |
|
909 checkGraphArcList(adaptor, 3); |
|
910 checkGraphConArcList(adaptor, 3); |
|
911 |
|
912 { |
|
913 dir[e1] = true; |
|
914 Adaptor::Node u = adaptor.source(e1); |
|
915 Adaptor::Node v = adaptor.target(e1); |
|
916 |
|
917 dir[e1] = false; |
|
918 check (u == adaptor.target(e1), "Wrong dir"); |
|
919 check (v == adaptor.source(e1), "Wrong dir"); |
|
920 |
|
921 check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir"); |
|
922 dir[e1] = n1 == u; |
|
923 } |
|
924 |
|
925 { |
|
926 dir[e2] = true; |
|
927 Adaptor::Node u = adaptor.source(e2); |
|
928 Adaptor::Node v = adaptor.target(e2); |
|
929 |
|
930 dir[e2] = false; |
|
931 check (u == adaptor.target(e2), "Wrong dir"); |
|
932 check (v == adaptor.source(e2), "Wrong dir"); |
|
933 |
|
934 check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir"); |
|
935 dir[e2] = n3 == u; |
|
936 } |
|
937 |
|
938 { |
|
939 dir[e3] = true; |
|
940 Adaptor::Node u = adaptor.source(e3); |
|
941 Adaptor::Node v = adaptor.target(e3); |
|
942 |
|
943 dir[e3] = false; |
|
944 check (u == adaptor.target(e3), "Wrong dir"); |
|
945 check (v == adaptor.source(e3), "Wrong dir"); |
|
946 |
|
947 check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir"); |
|
948 dir[e3] = n2 == u; |
|
949 } |
|
950 |
|
951 checkGraphOutArcList(adaptor, n1, 1); |
|
952 checkGraphOutArcList(adaptor, n2, 1); |
|
953 checkGraphOutArcList(adaptor, n3, 1); |
|
954 |
|
955 checkGraphInArcList(adaptor, n1, 1); |
|
956 checkGraphInArcList(adaptor, n2, 1); |
|
957 checkGraphInArcList(adaptor, n3, 1); |
|
958 |
|
959 checkNodeIds(adaptor); |
|
960 checkArcIds(adaptor); |
|
961 |
|
962 checkGraphNodeMap(adaptor); |
|
963 checkGraphArcMap(adaptor); |
|
964 |
|
965 } |
|
966 |
|
967 |
|
968 int main(int, const char **) { |
|
969 |
|
970 checkReverseDigraph(); |
|
971 checkSubDigraph(); |
|
972 checkFilterNodes1(); |
|
973 checkFilterArcs(); |
|
974 checkUndirector(); |
|
975 checkResidual(); |
|
976 checkSplitNodes(); |
|
977 |
|
978 checkSubGraph(); |
|
979 checkFilterNodes2(); |
|
980 checkFilterEdges(); |
|
981 checkOrienter(); |
|
982 |
|
983 return 0; |
|
984 } |
|