23 #include<lemon/smart_graph.h> |
23 #include<lemon/smart_graph.h> |
24 |
24 |
25 #include<lemon/concepts/digraph.h> |
25 #include<lemon/concepts/digraph.h> |
26 #include<lemon/concepts/graph.h> |
26 #include<lemon/concepts/graph.h> |
27 |
27 |
28 #include<lemon/digraph_adaptor.h> |
28 #include<lemon/adaptors.h> |
29 #include<lemon/graph_adaptor.h> |
|
30 |
29 |
31 #include <limits> |
30 #include <limits> |
32 #include <lemon/bfs.h> |
31 #include <lemon/bfs.h> |
33 #include <lemon/path.h> |
32 #include <lemon/path.h> |
34 |
33 |
35 #include"test/test_tools.h" |
34 #include"test/test_tools.h" |
36 #include"test/graph_test.h" |
35 #include"test/graph_test.h" |
37 |
36 |
38 using namespace lemon; |
37 using namespace lemon; |
39 |
38 |
40 void checkRevDigraphAdaptor() { |
39 void checkReverseDigraph() { |
41 checkConcept<concepts::Digraph, RevDigraphAdaptor<concepts::Digraph> >(); |
40 checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >(); |
42 |
41 |
43 typedef ListDigraph Digraph; |
42 typedef ListDigraph Digraph; |
44 typedef RevDigraphAdaptor<Digraph> Adaptor; |
43 typedef ReverseDigraph<Digraph> Adaptor; |
45 |
44 |
46 Digraph digraph; |
45 Digraph digraph; |
47 Adaptor adaptor(digraph); |
46 Adaptor adaptor(digraph); |
48 |
47 |
49 Digraph::Node n1 = digraph.addNode(); |
48 Digraph::Node n1 = digraph.addNode(); |
51 Digraph::Node n3 = digraph.addNode(); |
50 Digraph::Node n3 = digraph.addNode(); |
52 |
51 |
53 Digraph::Arc a1 = digraph.addArc(n1, n2); |
52 Digraph::Arc a1 = digraph.addArc(n1, n2); |
54 Digraph::Arc a2 = digraph.addArc(n1, n3); |
53 Digraph::Arc a2 = digraph.addArc(n1, n3); |
55 Digraph::Arc a3 = digraph.addArc(n2, n3); |
54 Digraph::Arc a3 = digraph.addArc(n2, n3); |
56 |
55 |
57 checkGraphNodeList(adaptor, 3); |
56 checkGraphNodeList(adaptor, 3); |
58 checkGraphArcList(adaptor, 3); |
57 checkGraphArcList(adaptor, 3); |
59 checkGraphConArcList(adaptor, 3); |
58 checkGraphConArcList(adaptor, 3); |
60 |
59 |
61 checkGraphOutArcList(adaptor, n1, 0); |
60 checkGraphOutArcList(adaptor, n1, 0); |
76 check(adaptor.source(a) == digraph.target(a), "Wrong reverse"); |
75 check(adaptor.source(a) == digraph.target(a), "Wrong reverse"); |
77 check(adaptor.target(a) == digraph.source(a), "Wrong reverse"); |
76 check(adaptor.target(a) == digraph.source(a), "Wrong reverse"); |
78 } |
77 } |
79 } |
78 } |
80 |
79 |
81 void checkSubDigraphAdaptor() { |
80 void checkSubDigraph() { |
82 checkConcept<concepts::Digraph, |
81 checkConcept<concepts::Digraph, |
83 SubDigraphAdaptor<concepts::Digraph, |
82 SubDigraph<concepts::Digraph, |
84 concepts::Digraph::NodeMap<bool>, |
83 concepts::Digraph::NodeMap<bool>, |
85 concepts::Digraph::ArcMap<bool> > >(); |
84 concepts::Digraph::ArcMap<bool> > >(); |
86 |
85 |
87 typedef ListDigraph Digraph; |
86 typedef ListDigraph Digraph; |
88 typedef Digraph::NodeMap<bool> NodeFilter; |
87 typedef Digraph::NodeMap<bool> NodeFilter; |
89 typedef Digraph::ArcMap<bool> ArcFilter; |
88 typedef Digraph::ArcMap<bool> ArcFilter; |
90 typedef SubDigraphAdaptor<Digraph, NodeFilter, ArcFilter> Adaptor; |
89 typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor; |
91 |
90 |
92 Digraph digraph; |
91 Digraph digraph; |
93 NodeFilter node_filter(digraph); |
92 NodeFilter node_filter(digraph); |
94 ArcFilter arc_filter(digraph); |
93 ArcFilter arc_filter(digraph); |
95 Adaptor adaptor(digraph, node_filter, arc_filter); |
94 Adaptor adaptor(digraph, node_filter, arc_filter); |
121 checkArcIds(adaptor); |
120 checkArcIds(adaptor); |
122 |
121 |
123 checkGraphNodeMap(adaptor); |
122 checkGraphNodeMap(adaptor); |
124 checkGraphArcMap(adaptor); |
123 checkGraphArcMap(adaptor); |
125 |
124 |
126 arc_filter[a2] = false; |
125 arc_filter[a2] = false; |
127 |
126 |
128 checkGraphNodeList(adaptor, 3); |
127 checkGraphNodeList(adaptor, 3); |
129 checkGraphArcList(adaptor, 2); |
128 checkGraphArcList(adaptor, 2); |
130 checkGraphConArcList(adaptor, 2); |
129 checkGraphConArcList(adaptor, 2); |
131 |
130 |
141 checkArcIds(adaptor); |
140 checkArcIds(adaptor); |
142 |
141 |
143 checkGraphNodeMap(adaptor); |
142 checkGraphNodeMap(adaptor); |
144 checkGraphArcMap(adaptor); |
143 checkGraphArcMap(adaptor); |
145 |
144 |
146 node_filter[n1] = false; |
145 node_filter[n1] = false; |
147 |
146 |
148 checkGraphNodeList(adaptor, 2); |
147 checkGraphNodeList(adaptor, 2); |
149 checkGraphArcList(adaptor, 1); |
148 checkGraphArcList(adaptor, 1); |
150 checkGraphConArcList(adaptor, 1); |
149 checkGraphConArcList(adaptor, 1); |
151 |
150 |
173 |
172 |
174 checkGraphNodeMap(adaptor); |
173 checkGraphNodeMap(adaptor); |
175 checkGraphArcMap(adaptor); |
174 checkGraphArcMap(adaptor); |
176 } |
175 } |
177 |
176 |
178 void checkNodeSubDigraphAdaptor() { |
177 void checkFilterNodes1() { |
179 checkConcept<concepts::Digraph, |
178 checkConcept<concepts::Digraph, |
180 NodeSubDigraphAdaptor<concepts::Digraph, |
179 FilterNodes<concepts::Digraph, |
181 concepts::Digraph::NodeMap<bool> > >(); |
180 concepts::Digraph::NodeMap<bool> > >(); |
182 |
181 |
183 typedef ListDigraph Digraph; |
182 typedef ListDigraph Digraph; |
184 typedef Digraph::NodeMap<bool> NodeFilter; |
183 typedef Digraph::NodeMap<bool> NodeFilter; |
185 typedef NodeSubDigraphAdaptor<Digraph, NodeFilter> Adaptor; |
184 typedef FilterNodes<Digraph, NodeFilter> Adaptor; |
186 |
185 |
187 Digraph digraph; |
186 Digraph digraph; |
188 NodeFilter node_filter(digraph); |
187 NodeFilter node_filter(digraph); |
189 Adaptor adaptor(digraph, node_filter); |
188 Adaptor adaptor(digraph, node_filter); |
190 |
189 |
214 checkArcIds(adaptor); |
213 checkArcIds(adaptor); |
215 |
214 |
216 checkGraphNodeMap(adaptor); |
215 checkGraphNodeMap(adaptor); |
217 checkGraphArcMap(adaptor); |
216 checkGraphArcMap(adaptor); |
218 |
217 |
219 node_filter[n1] = false; |
218 node_filter[n1] = false; |
220 |
219 |
221 checkGraphNodeList(adaptor, 2); |
220 checkGraphNodeList(adaptor, 2); |
222 checkGraphArcList(adaptor, 1); |
221 checkGraphArcList(adaptor, 1); |
223 checkGraphConArcList(adaptor, 1); |
222 checkGraphConArcList(adaptor, 1); |
224 |
223 |
245 |
244 |
246 checkGraphNodeMap(adaptor); |
245 checkGraphNodeMap(adaptor); |
247 checkGraphArcMap(adaptor); |
246 checkGraphArcMap(adaptor); |
248 } |
247 } |
249 |
248 |
250 void checkArcSubDigraphAdaptor() { |
249 void checkFilterArcs() { |
251 checkConcept<concepts::Digraph, |
250 checkConcept<concepts::Digraph, |
252 ArcSubDigraphAdaptor<concepts::Digraph, |
251 FilterArcs<concepts::Digraph, |
253 concepts::Digraph::ArcMap<bool> > >(); |
252 concepts::Digraph::ArcMap<bool> > >(); |
254 |
253 |
255 typedef ListDigraph Digraph; |
254 typedef ListDigraph Digraph; |
256 typedef Digraph::ArcMap<bool> ArcFilter; |
255 typedef Digraph::ArcMap<bool> ArcFilter; |
257 typedef ArcSubDigraphAdaptor<Digraph, ArcFilter> Adaptor; |
256 typedef FilterArcs<Digraph, ArcFilter> Adaptor; |
258 |
257 |
259 Digraph digraph; |
258 Digraph digraph; |
260 ArcFilter arc_filter(digraph); |
259 ArcFilter arc_filter(digraph); |
261 Adaptor adaptor(digraph, arc_filter); |
260 Adaptor adaptor(digraph, arc_filter); |
262 |
261 |
286 checkArcIds(adaptor); |
285 checkArcIds(adaptor); |
287 |
286 |
288 checkGraphNodeMap(adaptor); |
287 checkGraphNodeMap(adaptor); |
289 checkGraphArcMap(adaptor); |
288 checkGraphArcMap(adaptor); |
290 |
289 |
291 arc_filter[a2] = false; |
290 arc_filter[a2] = false; |
292 |
291 |
293 checkGraphNodeList(adaptor, 3); |
292 checkGraphNodeList(adaptor, 3); |
294 checkGraphArcList(adaptor, 2); |
293 checkGraphArcList(adaptor, 2); |
295 checkGraphConArcList(adaptor, 2); |
294 checkGraphConArcList(adaptor, 2); |
296 |
295 |
319 |
318 |
320 checkGraphNodeMap(adaptor); |
319 checkGraphNodeMap(adaptor); |
321 checkGraphArcMap(adaptor); |
320 checkGraphArcMap(adaptor); |
322 } |
321 } |
323 |
322 |
324 void checkUndirDigraphAdaptor() { |
323 void checkUndirector() { |
325 checkConcept<concepts::Graph, UndirDigraphAdaptor<concepts::Digraph> >(); |
324 checkConcept<concepts::Graph, Undirector<concepts::Digraph> >(); |
326 |
325 |
327 typedef ListDigraph Digraph; |
326 typedef ListDigraph Digraph; |
328 typedef UndirDigraphAdaptor<Digraph> Adaptor; |
327 typedef Undirector<Digraph> Adaptor; |
329 |
328 |
330 Digraph digraph; |
329 Digraph digraph; |
331 Adaptor adaptor(digraph); |
330 Adaptor adaptor(digraph); |
332 |
331 |
333 Digraph::Node n1 = digraph.addNode(); |
332 Digraph::Node n1 = digraph.addNode(); |
335 Digraph::Node n3 = digraph.addNode(); |
334 Digraph::Node n3 = digraph.addNode(); |
336 |
335 |
337 Digraph::Arc a1 = digraph.addArc(n1, n2); |
336 Digraph::Arc a1 = digraph.addArc(n1, n2); |
338 Digraph::Arc a2 = digraph.addArc(n1, n3); |
337 Digraph::Arc a2 = digraph.addArc(n1, n3); |
339 Digraph::Arc a3 = digraph.addArc(n2, n3); |
338 Digraph::Arc a3 = digraph.addArc(n2, n3); |
340 |
339 |
341 checkGraphNodeList(adaptor, 3); |
340 checkGraphNodeList(adaptor, 3); |
342 checkGraphArcList(adaptor, 6); |
341 checkGraphArcList(adaptor, 6); |
343 checkGraphEdgeList(adaptor, 3); |
342 checkGraphEdgeList(adaptor, 3); |
344 checkGraphConArcList(adaptor, 6); |
343 checkGraphConArcList(adaptor, 6); |
345 checkGraphConEdgeList(adaptor, 3); |
344 checkGraphConEdgeList(adaptor, 3); |
369 check(adaptor.v(e) == digraph.target(e), "Wrong undir"); |
368 check(adaptor.v(e) == digraph.target(e), "Wrong undir"); |
370 } |
369 } |
371 |
370 |
372 } |
371 } |
373 |
372 |
374 void checkResDigraphAdaptor() { |
373 void checkResidual() { |
375 checkConcept<concepts::Digraph, |
374 checkConcept<concepts::Digraph, |
376 ResDigraphAdaptor<concepts::Digraph, |
375 Residual<concepts::Digraph, |
377 concepts::Digraph::ArcMap<int>, |
376 concepts::Digraph::ArcMap<int>, |
378 concepts::Digraph::ArcMap<int> > >(); |
377 concepts::Digraph::ArcMap<int> > >(); |
379 |
378 |
380 typedef ListDigraph Digraph; |
379 typedef ListDigraph Digraph; |
381 typedef Digraph::ArcMap<int> IntArcMap; |
380 typedef Digraph::ArcMap<int> IntArcMap; |
382 typedef ResDigraphAdaptor<Digraph, IntArcMap> Adaptor; |
381 typedef Residual<Digraph, IntArcMap> Adaptor; |
383 |
382 |
384 Digraph digraph; |
383 Digraph digraph; |
385 IntArcMap capacity(digraph), flow(digraph); |
384 IntArcMap capacity(digraph), flow(digraph); |
386 Adaptor adaptor(digraph, capacity, flow); |
385 Adaptor adaptor(digraph, capacity, flow); |
387 |
386 |
405 capacity[a6] = 10; |
404 capacity[a6] = 10; |
406 |
405 |
407 for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { |
406 for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { |
408 flow[a] = 0; |
407 flow[a] = 0; |
409 } |
408 } |
410 |
409 |
411 checkGraphNodeList(adaptor, 4); |
410 checkGraphNodeList(adaptor, 4); |
412 checkGraphArcList(adaptor, 6); |
411 checkGraphArcList(adaptor, 6); |
413 checkGraphConArcList(adaptor, 6); |
412 checkGraphConArcList(adaptor, 6); |
414 |
413 |
415 checkGraphOutArcList(adaptor, n1, 3); |
414 checkGraphOutArcList(adaptor, n1, 3); |
423 checkGraphInArcList(adaptor, n4, 3); |
422 checkGraphInArcList(adaptor, n4, 3); |
424 |
423 |
425 for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { |
424 for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { |
426 flow[a] = capacity[a] / 2; |
425 flow[a] = capacity[a] / 2; |
427 } |
426 } |
428 |
427 |
429 checkGraphNodeList(adaptor, 4); |
428 checkGraphNodeList(adaptor, 4); |
430 checkGraphArcList(adaptor, 12); |
429 checkGraphArcList(adaptor, 12); |
431 checkGraphConArcList(adaptor, 12); |
430 checkGraphConArcList(adaptor, 12); |
432 |
431 |
433 checkGraphOutArcList(adaptor, n1, 3); |
432 checkGraphOutArcList(adaptor, n1, 3); |
447 checkGraphArcMap(adaptor); |
446 checkGraphArcMap(adaptor); |
448 |
447 |
449 for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { |
448 for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { |
450 flow[a] = capacity[a]; |
449 flow[a] = capacity[a]; |
451 } |
450 } |
452 |
451 |
453 checkGraphNodeList(adaptor, 4); |
452 checkGraphNodeList(adaptor, 4); |
454 checkGraphArcList(adaptor, 6); |
453 checkGraphArcList(adaptor, 6); |
455 checkGraphConArcList(adaptor, 6); |
454 checkGraphConArcList(adaptor, 6); |
456 |
455 |
457 checkGraphOutArcList(adaptor, n1, 0); |
456 checkGraphOutArcList(adaptor, n1, 0); |
468 flow[a] = 0; |
467 flow[a] = 0; |
469 } |
468 } |
470 |
469 |
471 int flow_value = 0; |
470 int flow_value = 0; |
472 while (true) { |
471 while (true) { |
473 |
472 |
474 Bfs<Adaptor> bfs(adaptor); |
473 Bfs<Adaptor> bfs(adaptor); |
475 bfs.run(n1, n4); |
474 bfs.run(n1, n4); |
476 |
475 |
477 if (!bfs.reached(n4)) break; |
476 if (!bfs.reached(n4)) break; |
478 |
477 |
479 Path<Adaptor> p = bfs.path(n4); |
478 Path<Adaptor> p = bfs.path(n4); |
480 |
479 |
481 int min = std::numeric_limits<int>::max(); |
480 int min = std::numeric_limits<int>::max(); |
482 for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) { |
481 for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) { |
483 if (adaptor.rescap(a) < min) min = adaptor.rescap(a); |
482 if (adaptor.residualCapacity(a) < min) |
|
483 min = adaptor.residualCapacity(a); |
484 } |
484 } |
485 |
485 |
486 for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) { |
486 for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) { |
487 adaptor.augment(a, min); |
487 adaptor.augment(a, min); |
488 } |
488 } |
491 |
491 |
492 check(flow_value == 18, "Wrong flow with res graph adaptor"); |
492 check(flow_value == 18, "Wrong flow with res graph adaptor"); |
493 |
493 |
494 } |
494 } |
495 |
495 |
496 void checkSplitDigraphAdaptor() { |
496 void checkSplitNodes() { |
497 checkConcept<concepts::Digraph, SplitDigraphAdaptor<concepts::Digraph> >(); |
497 checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >(); |
498 |
498 |
499 typedef ListDigraph Digraph; |
499 typedef ListDigraph Digraph; |
500 typedef SplitDigraphAdaptor<Digraph> Adaptor; |
500 typedef SplitNodes<Digraph> Adaptor; |
501 |
501 |
502 Digraph digraph; |
502 Digraph digraph; |
503 Adaptor adaptor(digraph); |
503 Adaptor adaptor(digraph); |
504 |
504 |
505 Digraph::Node n1 = digraph.addNode(); |
505 Digraph::Node n1 = digraph.addNode(); |
507 Digraph::Node n3 = digraph.addNode(); |
507 Digraph::Node n3 = digraph.addNode(); |
508 |
508 |
509 Digraph::Arc a1 = digraph.addArc(n1, n2); |
509 Digraph::Arc a1 = digraph.addArc(n1, n2); |
510 Digraph::Arc a2 = digraph.addArc(n1, n3); |
510 Digraph::Arc a2 = digraph.addArc(n1, n3); |
511 Digraph::Arc a3 = digraph.addArc(n2, n3); |
511 Digraph::Arc a3 = digraph.addArc(n2, n3); |
512 |
512 |
513 checkGraphNodeList(adaptor, 6); |
513 checkGraphNodeList(adaptor, 6); |
514 checkGraphArcList(adaptor, 6); |
514 checkGraphArcList(adaptor, 6); |
515 checkGraphConArcList(adaptor, 6); |
515 checkGraphConArcList(adaptor, 6); |
516 |
516 |
517 checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1); |
517 checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1); |
528 checkGraphInArcList(adaptor, adaptor.inNode(n3), 2); |
528 checkGraphInArcList(adaptor, adaptor.inNode(n3), 2); |
529 checkGraphInArcList(adaptor, adaptor.outNode(n3), 1); |
529 checkGraphInArcList(adaptor, adaptor.outNode(n3), 1); |
530 |
530 |
531 checkNodeIds(adaptor); |
531 checkNodeIds(adaptor); |
532 checkArcIds(adaptor); |
532 checkArcIds(adaptor); |
533 |
533 |
534 checkGraphNodeMap(adaptor); |
534 checkGraphNodeMap(adaptor); |
535 checkGraphArcMap(adaptor); |
535 checkGraphArcMap(adaptor); |
536 |
536 |
537 for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { |
537 for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) { |
538 if (adaptor.origArc(a)) { |
538 if (adaptor.origArc(a)) { |
539 Digraph::Arc oa = a; |
539 Digraph::Arc oa = a; |
540 check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)), |
540 check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)), |
541 "Wrong split"); |
541 "Wrong split"); |
542 check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)), |
542 check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)), |
543 "Wrong split"); |
543 "Wrong split"); |
544 } else { |
544 } else { |
545 Digraph::Node on = a; |
545 Digraph::Node on = a; |
546 check(adaptor.source(a) == adaptor.inNode(on), "Wrong split"); |
546 check(adaptor.source(a) == adaptor.inNode(on), "Wrong split"); |
547 check(adaptor.target(a) == adaptor.outNode(on), "Wrong split"); |
547 check(adaptor.target(a) == adaptor.outNode(on), "Wrong split"); |
548 } |
548 } |
549 } |
549 } |
550 } |
550 } |
551 |
551 |
552 void checkSubGraphAdaptor() { |
552 void checkSubGraph() { |
553 checkConcept<concepts::Graph, |
553 checkConcept<concepts::Graph, |
554 SubGraphAdaptor<concepts::Graph, |
554 SubGraph<concepts::Graph, |
555 concepts::Graph::NodeMap<bool>, |
555 concepts::Graph::NodeMap<bool>, |
556 concepts::Graph::EdgeMap<bool> > >(); |
556 concepts::Graph::EdgeMap<bool> > >(); |
557 |
557 |
558 typedef ListGraph Graph; |
558 typedef ListGraph Graph; |
559 typedef Graph::NodeMap<bool> NodeFilter; |
559 typedef Graph::NodeMap<bool> NodeFilter; |
560 typedef Graph::EdgeMap<bool> EdgeFilter; |
560 typedef Graph::EdgeMap<bool> EdgeFilter; |
561 typedef SubGraphAdaptor<Graph, NodeFilter, EdgeFilter> Adaptor; |
561 typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor; |
562 |
562 |
563 Graph graph; |
563 Graph graph; |
564 NodeFilter node_filter(graph); |
564 NodeFilter node_filter(graph); |
565 EdgeFilter edge_filter(graph); |
565 EdgeFilter edge_filter(graph); |
566 Adaptor adaptor(graph, node_filter, edge_filter); |
566 Adaptor adaptor(graph, node_filter, edge_filter); |
605 |
605 |
606 checkGraphNodeMap(adaptor); |
606 checkGraphNodeMap(adaptor); |
607 checkGraphArcMap(adaptor); |
607 checkGraphArcMap(adaptor); |
608 checkGraphEdgeMap(adaptor); |
608 checkGraphEdgeMap(adaptor); |
609 |
609 |
610 edge_filter[e2] = false; |
610 edge_filter[e2] = false; |
611 |
611 |
612 checkGraphNodeList(adaptor, 4); |
612 checkGraphNodeList(adaptor, 4); |
613 checkGraphArcList(adaptor, 6); |
613 checkGraphArcList(adaptor, 6); |
614 checkGraphEdgeList(adaptor, 3); |
614 checkGraphEdgeList(adaptor, 3); |
615 checkGraphConArcList(adaptor, 6); |
615 checkGraphConArcList(adaptor, 6); |
636 |
636 |
637 checkGraphNodeMap(adaptor); |
637 checkGraphNodeMap(adaptor); |
638 checkGraphArcMap(adaptor); |
638 checkGraphArcMap(adaptor); |
639 checkGraphEdgeMap(adaptor); |
639 checkGraphEdgeMap(adaptor); |
640 |
640 |
641 node_filter[n1] = false; |
641 node_filter[n1] = false; |
642 |
642 |
643 checkGraphNodeList(adaptor, 3); |
643 checkGraphNodeList(adaptor, 3); |
644 checkGraphArcList(adaptor, 4); |
644 checkGraphArcList(adaptor, 4); |
645 checkGraphEdgeList(adaptor, 2); |
645 checkGraphEdgeList(adaptor, 2); |
646 checkGraphConArcList(adaptor, 4); |
646 checkGraphConArcList(adaptor, 4); |
682 checkGraphNodeMap(adaptor); |
682 checkGraphNodeMap(adaptor); |
683 checkGraphArcMap(adaptor); |
683 checkGraphArcMap(adaptor); |
684 checkGraphEdgeMap(adaptor); |
684 checkGraphEdgeMap(adaptor); |
685 } |
685 } |
686 |
686 |
687 void checkNodeSubGraphAdaptor() { |
687 void checkFilterNodes2() { |
688 checkConcept<concepts::Graph, |
688 checkConcept<concepts::Graph, |
689 NodeSubGraphAdaptor<concepts::Graph, |
689 FilterNodes<concepts::Graph, |
690 concepts::Graph::NodeMap<bool> > >(); |
690 concepts::Graph::NodeMap<bool> > >(); |
691 |
691 |
692 typedef ListGraph Graph; |
692 typedef ListGraph Graph; |
693 typedef Graph::NodeMap<bool> NodeFilter; |
693 typedef Graph::NodeMap<bool> NodeFilter; |
694 typedef NodeSubGraphAdaptor<Graph, NodeFilter> Adaptor; |
694 typedef FilterNodes<Graph, NodeFilter> Adaptor; |
695 |
695 |
696 Graph graph; |
696 Graph graph; |
697 NodeFilter node_filter(graph); |
697 NodeFilter node_filter(graph); |
698 Adaptor adaptor(graph, node_filter); |
698 Adaptor adaptor(graph, node_filter); |
699 |
699 |
736 |
736 |
737 checkGraphNodeMap(adaptor); |
737 checkGraphNodeMap(adaptor); |
738 checkGraphArcMap(adaptor); |
738 checkGraphArcMap(adaptor); |
739 checkGraphEdgeMap(adaptor); |
739 checkGraphEdgeMap(adaptor); |
740 |
740 |
741 node_filter[n1] = false; |
741 node_filter[n1] = false; |
742 |
742 |
743 checkGraphNodeList(adaptor, 3); |
743 checkGraphNodeList(adaptor, 3); |
744 checkGraphArcList(adaptor, 4); |
744 checkGraphArcList(adaptor, 4); |
745 checkGraphEdgeList(adaptor, 2); |
745 checkGraphEdgeList(adaptor, 2); |
746 checkGraphConArcList(adaptor, 4); |
746 checkGraphConArcList(adaptor, 4); |
781 checkGraphNodeMap(adaptor); |
781 checkGraphNodeMap(adaptor); |
782 checkGraphArcMap(adaptor); |
782 checkGraphArcMap(adaptor); |
783 checkGraphEdgeMap(adaptor); |
783 checkGraphEdgeMap(adaptor); |
784 } |
784 } |
785 |
785 |
786 void checkEdgeSubGraphAdaptor() { |
786 void checkFilterEdges() { |
787 checkConcept<concepts::Graph, |
787 checkConcept<concepts::Graph, |
788 EdgeSubGraphAdaptor<concepts::Graph, |
788 FilterEdges<concepts::Graph, |
789 concepts::Graph::EdgeMap<bool> > >(); |
789 concepts::Graph::EdgeMap<bool> > >(); |
790 |
790 |
791 typedef ListGraph Graph; |
791 typedef ListGraph Graph; |
792 typedef Graph::EdgeMap<bool> EdgeFilter; |
792 typedef Graph::EdgeMap<bool> EdgeFilter; |
793 typedef EdgeSubGraphAdaptor<Graph, EdgeFilter> Adaptor; |
793 typedef FilterEdges<Graph, EdgeFilter> Adaptor; |
794 |
794 |
795 Graph graph; |
795 Graph graph; |
796 EdgeFilter edge_filter(graph); |
796 EdgeFilter edge_filter(graph); |
797 Adaptor adaptor(graph, edge_filter); |
797 Adaptor adaptor(graph, edge_filter); |
798 |
798 |
835 |
835 |
836 checkGraphNodeMap(adaptor); |
836 checkGraphNodeMap(adaptor); |
837 checkGraphArcMap(adaptor); |
837 checkGraphArcMap(adaptor); |
838 checkGraphEdgeMap(adaptor); |
838 checkGraphEdgeMap(adaptor); |
839 |
839 |
840 edge_filter[e2] = false; |
840 edge_filter[e2] = false; |
841 |
841 |
842 checkGraphNodeList(adaptor, 4); |
842 checkGraphNodeList(adaptor, 4); |
843 checkGraphArcList(adaptor, 6); |
843 checkGraphArcList(adaptor, 6); |
844 checkGraphEdgeList(adaptor, 3); |
844 checkGraphEdgeList(adaptor, 3); |
845 checkGraphConArcList(adaptor, 6); |
845 checkGraphConArcList(adaptor, 6); |
883 checkGraphNodeMap(adaptor); |
883 checkGraphNodeMap(adaptor); |
884 checkGraphArcMap(adaptor); |
884 checkGraphArcMap(adaptor); |
885 checkGraphEdgeMap(adaptor); |
885 checkGraphEdgeMap(adaptor); |
886 } |
886 } |
887 |
887 |
888 void checkDirGraphAdaptor() { |
888 void checkOrienter() { |
889 checkConcept<concepts::Digraph, |
889 checkConcept<concepts::Digraph, |
890 DirGraphAdaptor<concepts::Graph, concepts::Graph::EdgeMap<bool> > >(); |
890 Orienter<concepts::Graph, concepts::Graph::EdgeMap<bool> > >(); |
891 |
891 |
892 typedef ListGraph Graph; |
892 typedef ListGraph Graph; |
893 typedef ListGraph::EdgeMap<bool> DirMap; |
893 typedef ListGraph::EdgeMap<bool> DirMap; |
894 typedef DirGraphAdaptor<Graph> Adaptor; |
894 typedef Orienter<Graph> Adaptor; |
895 |
895 |
896 Graph graph; |
896 Graph graph; |
897 DirMap dir(graph, true); |
897 DirMap dir(graph, true); |
898 Adaptor adaptor(graph, dir); |
898 Adaptor adaptor(graph, dir); |
899 |
899 |
902 Graph::Node n3 = graph.addNode(); |
902 Graph::Node n3 = graph.addNode(); |
903 |
903 |
904 Graph::Edge e1 = graph.addEdge(n1, n2); |
904 Graph::Edge e1 = graph.addEdge(n1, n2); |
905 Graph::Edge e2 = graph.addEdge(n1, n3); |
905 Graph::Edge e2 = graph.addEdge(n1, n3); |
906 Graph::Edge e3 = graph.addEdge(n2, n3); |
906 Graph::Edge e3 = graph.addEdge(n2, n3); |
907 |
907 |
908 checkGraphNodeList(adaptor, 3); |
908 checkGraphNodeList(adaptor, 3); |
909 checkGraphArcList(adaptor, 3); |
909 checkGraphArcList(adaptor, 3); |
910 checkGraphConArcList(adaptor, 3); |
910 checkGraphConArcList(adaptor, 3); |
911 |
911 |
912 { |
912 { |
913 dir[e1] = true; |
913 dir[e1] = true; |
914 Adaptor::Node u = adaptor.source(e1); |
914 Adaptor::Node u = adaptor.source(e1); |
915 Adaptor::Node v = adaptor.target(e1); |
915 Adaptor::Node v = adaptor.target(e1); |
916 |
916 |
917 dir[e1] = false; |
917 dir[e1] = false; |
918 check (u == adaptor.target(e1), "Wrong dir"); |
918 check (u == adaptor.target(e1), "Wrong dir"); |
919 check (v == adaptor.source(e1), "Wrong dir"); |
919 check (v == adaptor.source(e1), "Wrong dir"); |
920 |
920 |
921 check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir"); |
921 check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir"); |
924 |
924 |
925 { |
925 { |
926 dir[e2] = true; |
926 dir[e2] = true; |
927 Adaptor::Node u = adaptor.source(e2); |
927 Adaptor::Node u = adaptor.source(e2); |
928 Adaptor::Node v = adaptor.target(e2); |
928 Adaptor::Node v = adaptor.target(e2); |
929 |
929 |
930 dir[e2] = false; |
930 dir[e2] = false; |
931 check (u == adaptor.target(e2), "Wrong dir"); |
931 check (u == adaptor.target(e2), "Wrong dir"); |
932 check (v == adaptor.source(e2), "Wrong dir"); |
932 check (v == adaptor.source(e2), "Wrong dir"); |
933 |
933 |
934 check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir"); |
934 check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir"); |
937 |
937 |
938 { |
938 { |
939 dir[e3] = true; |
939 dir[e3] = true; |
940 Adaptor::Node u = adaptor.source(e3); |
940 Adaptor::Node u = adaptor.source(e3); |
941 Adaptor::Node v = adaptor.target(e3); |
941 Adaptor::Node v = adaptor.target(e3); |
942 |
942 |
943 dir[e3] = false; |
943 dir[e3] = false; |
944 check (u == adaptor.target(e3), "Wrong dir"); |
944 check (u == adaptor.target(e3), "Wrong dir"); |
945 check (v == adaptor.source(e3), "Wrong dir"); |
945 check (v == adaptor.source(e3), "Wrong dir"); |
946 |
946 |
947 check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir"); |
947 check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir"); |
965 } |
965 } |
966 |
966 |
967 |
967 |
968 int main(int, const char **) { |
968 int main(int, const char **) { |
969 |
969 |
970 checkRevDigraphAdaptor(); |
970 checkReverseDigraph(); |
971 checkSubDigraphAdaptor(); |
971 checkSubDigraph(); |
972 checkNodeSubDigraphAdaptor(); |
972 checkFilterNodes1(); |
973 checkArcSubDigraphAdaptor(); |
973 checkFilterArcs(); |
974 checkUndirDigraphAdaptor(); |
974 checkUndirector(); |
975 checkResDigraphAdaptor(); |
975 checkResidual(); |
976 checkSplitDigraphAdaptor(); |
976 checkSplitNodes(); |
977 |
977 |
978 checkSubGraphAdaptor(); |
978 checkSubGraph(); |
979 checkNodeSubGraphAdaptor(); |
979 checkFilterNodes2(); |
980 checkEdgeSubGraphAdaptor(); |
980 checkFilterEdges(); |
981 checkDirGraphAdaptor(); |
981 checkOrienter(); |
982 |
982 |
983 return 0; |
983 return 0; |
984 } |
984 } |