3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
20 #include<lemon/concept_check.h>
22 #include<lemon/list_graph.h>
23 #include<lemon/smart_graph.h>
25 #include<lemon/concepts/digraph.h>
26 #include<lemon/concepts/graph.h>
28 #include<lemon/digraph_adaptor.h>
29 #include<lemon/graph_adaptor.h>
32 #include <lemon/bfs.h>
33 #include <lemon/path.h>
35 #include"test/test_tools.h"
36 #include"test/graph_test.h"
38 using namespace lemon;
40 void checkDigraphAdaptor() {
41 checkConcept<concepts::Digraph, DigraphAdaptor<concepts::Digraph> >();
43 typedef ListDigraph Digraph;
44 typedef DigraphAdaptor<Digraph> Adaptor;
47 Adaptor adaptor(digraph);
49 Digraph::Node n1 = digraph.addNode();
50 Digraph::Node n2 = digraph.addNode();
51 Digraph::Node n3 = digraph.addNode();
53 Digraph::Arc a1 = digraph.addArc(n1, n2);
54 Digraph::Arc a2 = digraph.addArc(n1, n3);
55 Digraph::Arc a3 = digraph.addArc(n2, n3);
57 checkGraphNodeList(adaptor, 3);
58 checkGraphArcList(adaptor, 3);
59 checkGraphConArcList(adaptor, 3);
61 checkGraphOutArcList(adaptor, n1, 2);
62 checkGraphOutArcList(adaptor, n2, 1);
63 checkGraphOutArcList(adaptor, n3, 0);
65 checkGraphInArcList(adaptor, n1, 0);
66 checkGraphInArcList(adaptor, n2, 1);
67 checkGraphInArcList(adaptor, n3, 2);
69 checkNodeIds(adaptor);
72 checkGraphNodeMap(adaptor);
73 checkGraphArcMap(adaptor);
76 void checkRevDigraphAdaptor() {
77 checkConcept<concepts::Digraph, RevDigraphAdaptor<concepts::Digraph> >();
79 typedef ListDigraph Digraph;
80 typedef RevDigraphAdaptor<Digraph> Adaptor;
83 Adaptor adaptor(digraph);
85 Digraph::Node n1 = digraph.addNode();
86 Digraph::Node n2 = digraph.addNode();
87 Digraph::Node n3 = digraph.addNode();
89 Digraph::Arc a1 = digraph.addArc(n1, n2);
90 Digraph::Arc a2 = digraph.addArc(n1, n3);
91 Digraph::Arc a3 = digraph.addArc(n2, n3);
93 checkGraphNodeList(adaptor, 3);
94 checkGraphArcList(adaptor, 3);
95 checkGraphConArcList(adaptor, 3);
97 checkGraphOutArcList(adaptor, n1, 0);
98 checkGraphOutArcList(adaptor, n2, 1);
99 checkGraphOutArcList(adaptor, n3, 2);
101 checkGraphInArcList(adaptor, n1, 2);
102 checkGraphInArcList(adaptor, n2, 1);
103 checkGraphInArcList(adaptor, n3, 0);
105 checkNodeIds(adaptor);
106 checkArcIds(adaptor);
108 checkGraphNodeMap(adaptor);
109 checkGraphArcMap(adaptor);
111 for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
112 check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
113 check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
117 void checkSubDigraphAdaptor() {
118 checkConcept<concepts::Digraph,
119 SubDigraphAdaptor<concepts::Digraph,
120 concepts::Digraph::NodeMap<bool>,
121 concepts::Digraph::ArcMap<bool> > >();
123 typedef ListDigraph Digraph;
124 typedef Digraph::NodeMap<bool> NodeFilter;
125 typedef Digraph::ArcMap<bool> ArcFilter;
126 typedef SubDigraphAdaptor<Digraph, NodeFilter, ArcFilter> Adaptor;
129 NodeFilter node_filter(digraph);
130 ArcFilter arc_filter(digraph);
131 Adaptor adaptor(digraph, node_filter, arc_filter);
133 Digraph::Node n1 = digraph.addNode();
134 Digraph::Node n2 = digraph.addNode();
135 Digraph::Node n3 = digraph.addNode();
137 Digraph::Arc a1 = digraph.addArc(n1, n2);
138 Digraph::Arc a2 = digraph.addArc(n1, n3);
139 Digraph::Arc a3 = digraph.addArc(n2, n3);
141 node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
142 arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
144 checkGraphNodeList(adaptor, 3);
145 checkGraphArcList(adaptor, 3);
146 checkGraphConArcList(adaptor, 3);
148 checkGraphOutArcList(adaptor, n1, 2);
149 checkGraphOutArcList(adaptor, n2, 1);
150 checkGraphOutArcList(adaptor, n3, 0);
152 checkGraphInArcList(adaptor, n1, 0);
153 checkGraphInArcList(adaptor, n2, 1);
154 checkGraphInArcList(adaptor, n3, 2);
156 checkNodeIds(adaptor);
157 checkArcIds(adaptor);
159 checkGraphNodeMap(adaptor);
160 checkGraphArcMap(adaptor);
162 arc_filter[a2] = false;
164 checkGraphNodeList(adaptor, 3);
165 checkGraphArcList(adaptor, 2);
166 checkGraphConArcList(adaptor, 2);
168 checkGraphOutArcList(adaptor, n1, 1);
169 checkGraphOutArcList(adaptor, n2, 1);
170 checkGraphOutArcList(adaptor, n3, 0);
172 checkGraphInArcList(adaptor, n1, 0);
173 checkGraphInArcList(adaptor, n2, 1);
174 checkGraphInArcList(adaptor, n3, 1);
176 checkNodeIds(adaptor);
177 checkArcIds(adaptor);
179 checkGraphNodeMap(adaptor);
180 checkGraphArcMap(adaptor);
182 node_filter[n1] = false;
184 checkGraphNodeList(adaptor, 2);
185 checkGraphArcList(adaptor, 1);
186 checkGraphConArcList(adaptor, 1);
188 checkGraphOutArcList(adaptor, n2, 1);
189 checkGraphOutArcList(adaptor, n3, 0);
191 checkGraphInArcList(adaptor, n2, 0);
192 checkGraphInArcList(adaptor, n3, 1);
194 checkNodeIds(adaptor);
195 checkArcIds(adaptor);
197 checkGraphNodeMap(adaptor);
198 checkGraphArcMap(adaptor);
200 node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
201 arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
203 checkGraphNodeList(adaptor, 0);
204 checkGraphArcList(adaptor, 0);
205 checkGraphConArcList(adaptor, 0);
207 checkNodeIds(adaptor);
208 checkArcIds(adaptor);
210 checkGraphNodeMap(adaptor);
211 checkGraphArcMap(adaptor);
214 void checkNodeSubDigraphAdaptor() {
215 checkConcept<concepts::Digraph,
216 NodeSubDigraphAdaptor<concepts::Digraph,
217 concepts::Digraph::NodeMap<bool> > >();
219 typedef ListDigraph Digraph;
220 typedef Digraph::NodeMap<bool> NodeFilter;
221 typedef NodeSubDigraphAdaptor<Digraph, NodeFilter> Adaptor;
224 NodeFilter node_filter(digraph);
225 Adaptor adaptor(digraph, node_filter);
227 Digraph::Node n1 = digraph.addNode();
228 Digraph::Node n2 = digraph.addNode();
229 Digraph::Node n3 = digraph.addNode();
231 Digraph::Arc a1 = digraph.addArc(n1, n2);
232 Digraph::Arc a2 = digraph.addArc(n1, n3);
233 Digraph::Arc a3 = digraph.addArc(n2, n3);
235 node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
237 checkGraphNodeList(adaptor, 3);
238 checkGraphArcList(adaptor, 3);
239 checkGraphConArcList(adaptor, 3);
241 checkGraphOutArcList(adaptor, n1, 2);
242 checkGraphOutArcList(adaptor, n2, 1);
243 checkGraphOutArcList(adaptor, n3, 0);
245 checkGraphInArcList(adaptor, n1, 0);
246 checkGraphInArcList(adaptor, n2, 1);
247 checkGraphInArcList(adaptor, n3, 2);
249 checkNodeIds(adaptor);
250 checkArcIds(adaptor);
252 checkGraphNodeMap(adaptor);
253 checkGraphArcMap(adaptor);
255 node_filter[n1] = false;
257 checkGraphNodeList(adaptor, 2);
258 checkGraphArcList(adaptor, 1);
259 checkGraphConArcList(adaptor, 1);
261 checkGraphOutArcList(adaptor, n2, 1);
262 checkGraphOutArcList(adaptor, n3, 0);
264 checkGraphInArcList(adaptor, n2, 0);
265 checkGraphInArcList(adaptor, n3, 1);
267 checkNodeIds(adaptor);
268 checkArcIds(adaptor);
270 checkGraphNodeMap(adaptor);
271 checkGraphArcMap(adaptor);
273 node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
275 checkGraphNodeList(adaptor, 0);
276 checkGraphArcList(adaptor, 0);
277 checkGraphConArcList(adaptor, 0);
279 checkNodeIds(adaptor);
280 checkArcIds(adaptor);
282 checkGraphNodeMap(adaptor);
283 checkGraphArcMap(adaptor);
286 void checkArcSubDigraphAdaptor() {
287 checkConcept<concepts::Digraph,
288 ArcSubDigraphAdaptor<concepts::Digraph,
289 concepts::Digraph::ArcMap<bool> > >();
291 typedef ListDigraph Digraph;
292 typedef Digraph::ArcMap<bool> ArcFilter;
293 typedef ArcSubDigraphAdaptor<Digraph, ArcFilter> Adaptor;
296 ArcFilter arc_filter(digraph);
297 Adaptor adaptor(digraph, arc_filter);
299 Digraph::Node n1 = digraph.addNode();
300 Digraph::Node n2 = digraph.addNode();
301 Digraph::Node n3 = digraph.addNode();
303 Digraph::Arc a1 = digraph.addArc(n1, n2);
304 Digraph::Arc a2 = digraph.addArc(n1, n3);
305 Digraph::Arc a3 = digraph.addArc(n2, n3);
307 arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
309 checkGraphNodeList(adaptor, 3);
310 checkGraphArcList(adaptor, 3);
311 checkGraphConArcList(adaptor, 3);
313 checkGraphOutArcList(adaptor, n1, 2);
314 checkGraphOutArcList(adaptor, n2, 1);
315 checkGraphOutArcList(adaptor, n3, 0);
317 checkGraphInArcList(adaptor, n1, 0);
318 checkGraphInArcList(adaptor, n2, 1);
319 checkGraphInArcList(adaptor, n3, 2);
321 checkNodeIds(adaptor);
322 checkArcIds(adaptor);
324 checkGraphNodeMap(adaptor);
325 checkGraphArcMap(adaptor);
327 arc_filter[a2] = false;
329 checkGraphNodeList(adaptor, 3);
330 checkGraphArcList(adaptor, 2);
331 checkGraphConArcList(adaptor, 2);
333 checkGraphOutArcList(adaptor, n1, 1);
334 checkGraphOutArcList(adaptor, n2, 1);
335 checkGraphOutArcList(adaptor, n3, 0);
337 checkGraphInArcList(adaptor, n1, 0);
338 checkGraphInArcList(adaptor, n2, 1);
339 checkGraphInArcList(adaptor, n3, 1);
341 checkNodeIds(adaptor);
342 checkArcIds(adaptor);
344 checkGraphNodeMap(adaptor);
345 checkGraphArcMap(adaptor);
347 arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
349 checkGraphNodeList(adaptor, 3);
350 checkGraphArcList(adaptor, 0);
351 checkGraphConArcList(adaptor, 0);
353 checkNodeIds(adaptor);
354 checkArcIds(adaptor);
356 checkGraphNodeMap(adaptor);
357 checkGraphArcMap(adaptor);
360 void checkUndirDigraphAdaptor() {
361 checkConcept<concepts::Graph, UndirDigraphAdaptor<concepts::Digraph> >();
363 typedef ListDigraph Digraph;
364 typedef UndirDigraphAdaptor<Digraph> Adaptor;
367 Adaptor adaptor(digraph);
369 Digraph::Node n1 = digraph.addNode();
370 Digraph::Node n2 = digraph.addNode();
371 Digraph::Node n3 = digraph.addNode();
373 Digraph::Arc a1 = digraph.addArc(n1, n2);
374 Digraph::Arc a2 = digraph.addArc(n1, n3);
375 Digraph::Arc a3 = digraph.addArc(n2, n3);
377 checkGraphNodeList(adaptor, 3);
378 checkGraphArcList(adaptor, 6);
379 checkGraphEdgeList(adaptor, 3);
380 checkGraphConArcList(adaptor, 6);
381 checkGraphConEdgeList(adaptor, 3);
383 checkGraphOutArcList(adaptor, n1, 2);
384 checkGraphOutArcList(adaptor, n2, 2);
385 checkGraphOutArcList(adaptor, n3, 2);
387 checkGraphInArcList(adaptor, n1, 2);
388 checkGraphInArcList(adaptor, n2, 2);
389 checkGraphInArcList(adaptor, n3, 2);
391 checkGraphIncEdgeList(adaptor, n1, 2);
392 checkGraphIncEdgeList(adaptor, n2, 2);
393 checkGraphIncEdgeList(adaptor, n3, 2);
395 checkNodeIds(adaptor);
396 checkArcIds(adaptor);
397 checkEdgeIds(adaptor);
399 checkGraphNodeMap(adaptor);
400 checkGraphArcMap(adaptor);
401 checkGraphEdgeMap(adaptor);
403 for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {
404 check(adaptor.u(e) == digraph.source(e), "Wrong undir");
405 check(adaptor.v(e) == digraph.target(e), "Wrong undir");
410 void checkResDigraphAdaptor() {
411 checkConcept<concepts::Digraph,
412 ResDigraphAdaptor<concepts::Digraph,
413 concepts::Digraph::ArcMap<int>,
414 concepts::Digraph::ArcMap<int> > >();
416 typedef ListDigraph Digraph;
417 typedef Digraph::ArcMap<int> IntArcMap;
418 typedef ResDigraphAdaptor<Digraph, IntArcMap> Adaptor;
421 IntArcMap capacity(digraph), flow(digraph);
422 Adaptor adaptor(digraph, capacity, flow);
424 Digraph::Node n1 = digraph.addNode();
425 Digraph::Node n2 = digraph.addNode();
426 Digraph::Node n3 = digraph.addNode();
427 Digraph::Node n4 = digraph.addNode();
429 Digraph::Arc a1 = digraph.addArc(n1, n2);
430 Digraph::Arc a2 = digraph.addArc(n1, n3);
431 Digraph::Arc a3 = digraph.addArc(n1, n4);
432 Digraph::Arc a4 = digraph.addArc(n2, n3);
433 Digraph::Arc a5 = digraph.addArc(n2, n4);
434 Digraph::Arc a6 = digraph.addArc(n3, n4);
443 for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
447 checkGraphNodeList(adaptor, 4);
448 checkGraphArcList(adaptor, 6);
449 checkGraphConArcList(adaptor, 6);
451 checkGraphOutArcList(adaptor, n1, 3);
452 checkGraphOutArcList(adaptor, n2, 2);
453 checkGraphOutArcList(adaptor, n3, 1);
454 checkGraphOutArcList(adaptor, n4, 0);
456 checkGraphInArcList(adaptor, n1, 0);
457 checkGraphInArcList(adaptor, n2, 1);
458 checkGraphInArcList(adaptor, n3, 2);
459 checkGraphInArcList(adaptor, n4, 3);
461 for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
462 flow[a] = capacity[a] / 2;
465 checkGraphNodeList(adaptor, 4);
466 checkGraphArcList(adaptor, 12);
467 checkGraphConArcList(adaptor, 12);
469 checkGraphOutArcList(adaptor, n1, 3);
470 checkGraphOutArcList(adaptor, n2, 3);
471 checkGraphOutArcList(adaptor, n3, 3);
472 checkGraphOutArcList(adaptor, n4, 3);
474 checkGraphInArcList(adaptor, n1, 3);
475 checkGraphInArcList(adaptor, n2, 3);
476 checkGraphInArcList(adaptor, n3, 3);
477 checkGraphInArcList(adaptor, n4, 3);
479 checkNodeIds(adaptor);
480 checkArcIds(adaptor);
482 checkGraphNodeMap(adaptor);
483 checkGraphArcMap(adaptor);
485 for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
486 flow[a] = capacity[a];
489 checkGraphNodeList(adaptor, 4);
490 checkGraphArcList(adaptor, 6);
491 checkGraphConArcList(adaptor, 6);
493 checkGraphOutArcList(adaptor, n1, 0);
494 checkGraphOutArcList(adaptor, n2, 1);
495 checkGraphOutArcList(adaptor, n3, 2);
496 checkGraphOutArcList(adaptor, n4, 3);
498 checkGraphInArcList(adaptor, n1, 3);
499 checkGraphInArcList(adaptor, n2, 2);
500 checkGraphInArcList(adaptor, n3, 1);
501 checkGraphInArcList(adaptor, n4, 0);
503 for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
510 Bfs<Adaptor> bfs(adaptor);
513 if (!bfs.reached(n4)) break;
515 Path<Adaptor> p = bfs.path(n4);
517 int min = std::numeric_limits<int>::max();
518 for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
519 if (adaptor.rescap(a) < min) min = adaptor.rescap(a);
522 for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
523 adaptor.augment(a, min);
528 check(flow_value == 18, "Wrong flow with res graph adaptor");
532 void checkSplitDigraphAdaptor() {
533 checkConcept<concepts::Digraph, SplitDigraphAdaptor<concepts::Digraph> >();
535 typedef ListDigraph Digraph;
536 typedef SplitDigraphAdaptor<Digraph> Adaptor;
539 Adaptor adaptor(digraph);
541 Digraph::Node n1 = digraph.addNode();
542 Digraph::Node n2 = digraph.addNode();
543 Digraph::Node n3 = digraph.addNode();
545 Digraph::Arc a1 = digraph.addArc(n1, n2);
546 Digraph::Arc a2 = digraph.addArc(n1, n3);
547 Digraph::Arc a3 = digraph.addArc(n2, n3);
549 checkGraphNodeList(adaptor, 6);
550 checkGraphArcList(adaptor, 6);
551 checkGraphConArcList(adaptor, 6);
553 checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
554 checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2);
555 checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
556 checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1);
557 checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
558 checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0);
560 checkGraphInArcList(adaptor, adaptor.inNode(n1), 0);
561 checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
562 checkGraphInArcList(adaptor, adaptor.inNode(n2), 1);
563 checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
564 checkGraphInArcList(adaptor, adaptor.inNode(n3), 2);
565 checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
567 checkNodeIds(adaptor);
568 checkArcIds(adaptor);
570 checkGraphNodeMap(adaptor);
571 checkGraphArcMap(adaptor);
573 for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
574 if (adaptor.origArc(a)) {
576 check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),
578 check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),
581 Digraph::Node on = a;
582 check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");
583 check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");
588 void checkGraphAdaptor() {
589 checkConcept<concepts::Graph, GraphAdaptor<concepts::Graph> >();
591 typedef ListGraph Graph;
592 typedef GraphAdaptor<Graph> Adaptor;
595 Adaptor adaptor(graph);
597 Graph::Node n1 = graph.addNode();
598 Graph::Node n2 = graph.addNode();
599 Graph::Node n3 = graph.addNode();
600 Graph::Node n4 = graph.addNode();
602 Graph::Edge a1 = graph.addEdge(n1, n2);
603 Graph::Edge a2 = graph.addEdge(n1, n3);
604 Graph::Edge a3 = graph.addEdge(n2, n3);
605 Graph::Edge a4 = graph.addEdge(n3, n4);
607 checkGraphNodeList(adaptor, 4);
608 checkGraphArcList(adaptor, 8);
609 checkGraphEdgeList(adaptor, 4);
610 checkGraphConArcList(adaptor, 8);
611 checkGraphConEdgeList(adaptor, 4);
613 checkGraphOutArcList(adaptor, n1, 2);
614 checkGraphOutArcList(adaptor, n2, 2);
615 checkGraphOutArcList(adaptor, n3, 3);
616 checkGraphOutArcList(adaptor, n4, 1);
618 checkGraphInArcList(adaptor, n1, 2);
619 checkGraphInArcList(adaptor, n2, 2);
620 checkGraphInArcList(adaptor, n3, 3);
621 checkGraphInArcList(adaptor, n4, 1);
623 checkGraphIncEdgeList(adaptor, n1, 2);
624 checkGraphIncEdgeList(adaptor, n2, 2);
625 checkGraphIncEdgeList(adaptor, n3, 3);
626 checkGraphIncEdgeList(adaptor, n4, 1);
629 checkNodeIds(adaptor);
630 checkArcIds(adaptor);
631 checkEdgeIds(adaptor);
633 checkGraphNodeMap(adaptor);
634 checkGraphArcMap(adaptor);
635 checkGraphEdgeMap(adaptor);
638 void checkSubGraphAdaptor() {
639 checkConcept<concepts::Graph,
640 SubGraphAdaptor<concepts::Graph,
641 concepts::Graph::NodeMap<bool>,
642 concepts::Graph::EdgeMap<bool> > >();
644 typedef ListGraph Graph;
645 typedef Graph::NodeMap<bool> NodeFilter;
646 typedef Graph::EdgeMap<bool> EdgeFilter;
647 typedef SubGraphAdaptor<Graph, NodeFilter, EdgeFilter> Adaptor;
650 NodeFilter node_filter(graph);
651 EdgeFilter edge_filter(graph);
652 Adaptor adaptor(graph, node_filter, edge_filter);
654 Graph::Node n1 = graph.addNode();
655 Graph::Node n2 = graph.addNode();
656 Graph::Node n3 = graph.addNode();
657 Graph::Node n4 = graph.addNode();
659 Graph::Edge e1 = graph.addEdge(n1, n2);
660 Graph::Edge e2 = graph.addEdge(n1, n3);
661 Graph::Edge e3 = graph.addEdge(n2, n3);
662 Graph::Edge e4 = graph.addEdge(n3, n4);
664 node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
665 edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
667 checkGraphNodeList(adaptor, 4);
668 checkGraphArcList(adaptor, 8);
669 checkGraphEdgeList(adaptor, 4);
670 checkGraphConArcList(adaptor, 8);
671 checkGraphConEdgeList(adaptor, 4);
673 checkGraphOutArcList(adaptor, n1, 2);
674 checkGraphOutArcList(adaptor, n2, 2);
675 checkGraphOutArcList(adaptor, n3, 3);
676 checkGraphOutArcList(adaptor, n4, 1);
678 checkGraphInArcList(adaptor, n1, 2);
679 checkGraphInArcList(adaptor, n2, 2);
680 checkGraphInArcList(adaptor, n3, 3);
681 checkGraphInArcList(adaptor, n4, 1);
683 checkGraphIncEdgeList(adaptor, n1, 2);
684 checkGraphIncEdgeList(adaptor, n2, 2);
685 checkGraphIncEdgeList(adaptor, n3, 3);
686 checkGraphIncEdgeList(adaptor, n4, 1);
688 checkNodeIds(adaptor);
689 checkArcIds(adaptor);
690 checkEdgeIds(adaptor);
692 checkGraphNodeMap(adaptor);
693 checkGraphArcMap(adaptor);
694 checkGraphEdgeMap(adaptor);
696 edge_filter[e2] = false;
698 checkGraphNodeList(adaptor, 4);
699 checkGraphArcList(adaptor, 6);
700 checkGraphEdgeList(adaptor, 3);
701 checkGraphConArcList(adaptor, 6);
702 checkGraphConEdgeList(adaptor, 3);
704 checkGraphOutArcList(adaptor, n1, 1);
705 checkGraphOutArcList(adaptor, n2, 2);
706 checkGraphOutArcList(adaptor, n3, 2);
707 checkGraphOutArcList(adaptor, n4, 1);
709 checkGraphInArcList(adaptor, n1, 1);
710 checkGraphInArcList(adaptor, n2, 2);
711 checkGraphInArcList(adaptor, n3, 2);
712 checkGraphInArcList(adaptor, n4, 1);
714 checkGraphIncEdgeList(adaptor, n1, 1);
715 checkGraphIncEdgeList(adaptor, n2, 2);
716 checkGraphIncEdgeList(adaptor, n3, 2);
717 checkGraphIncEdgeList(adaptor, n4, 1);
719 checkNodeIds(adaptor);
720 checkArcIds(adaptor);
721 checkEdgeIds(adaptor);
723 checkGraphNodeMap(adaptor);
724 checkGraphArcMap(adaptor);
725 checkGraphEdgeMap(adaptor);
727 node_filter[n1] = false;
729 checkGraphNodeList(adaptor, 3);
730 checkGraphArcList(adaptor, 4);
731 checkGraphEdgeList(adaptor, 2);
732 checkGraphConArcList(adaptor, 4);
733 checkGraphConEdgeList(adaptor, 2);
735 checkGraphOutArcList(adaptor, n2, 1);
736 checkGraphOutArcList(adaptor, n3, 2);
737 checkGraphOutArcList(adaptor, n4, 1);
739 checkGraphInArcList(adaptor, n2, 1);
740 checkGraphInArcList(adaptor, n3, 2);
741 checkGraphInArcList(adaptor, n4, 1);
743 checkGraphIncEdgeList(adaptor, n2, 1);
744 checkGraphIncEdgeList(adaptor, n3, 2);
745 checkGraphIncEdgeList(adaptor, n4, 1);
747 checkNodeIds(adaptor);
748 checkArcIds(adaptor);
749 checkEdgeIds(adaptor);
751 checkGraphNodeMap(adaptor);
752 checkGraphArcMap(adaptor);
753 checkGraphEdgeMap(adaptor);
755 node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
756 edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
758 checkGraphNodeList(adaptor, 0);
759 checkGraphArcList(adaptor, 0);
760 checkGraphEdgeList(adaptor, 0);
761 checkGraphConArcList(adaptor, 0);
762 checkGraphConEdgeList(adaptor, 0);
764 checkNodeIds(adaptor);
765 checkArcIds(adaptor);
766 checkEdgeIds(adaptor);
768 checkGraphNodeMap(adaptor);
769 checkGraphArcMap(adaptor);
770 checkGraphEdgeMap(adaptor);
773 void checkNodeSubGraphAdaptor() {
774 checkConcept<concepts::Graph,
775 NodeSubGraphAdaptor<concepts::Graph,
776 concepts::Graph::NodeMap<bool> > >();
778 typedef ListGraph Graph;
779 typedef Graph::NodeMap<bool> NodeFilter;
780 typedef NodeSubGraphAdaptor<Graph, NodeFilter> Adaptor;
783 NodeFilter node_filter(graph);
784 Adaptor adaptor(graph, node_filter);
786 Graph::Node n1 = graph.addNode();
787 Graph::Node n2 = graph.addNode();
788 Graph::Node n3 = graph.addNode();
789 Graph::Node n4 = graph.addNode();
791 Graph::Edge e1 = graph.addEdge(n1, n2);
792 Graph::Edge e2 = graph.addEdge(n1, n3);
793 Graph::Edge e3 = graph.addEdge(n2, n3);
794 Graph::Edge e4 = graph.addEdge(n3, n4);
796 node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
798 checkGraphNodeList(adaptor, 4);
799 checkGraphArcList(adaptor, 8);
800 checkGraphEdgeList(adaptor, 4);
801 checkGraphConArcList(adaptor, 8);
802 checkGraphConEdgeList(adaptor, 4);
804 checkGraphOutArcList(adaptor, n1, 2);
805 checkGraphOutArcList(adaptor, n2, 2);
806 checkGraphOutArcList(adaptor, n3, 3);
807 checkGraphOutArcList(adaptor, n4, 1);
809 checkGraphInArcList(adaptor, n1, 2);
810 checkGraphInArcList(adaptor, n2, 2);
811 checkGraphInArcList(adaptor, n3, 3);
812 checkGraphInArcList(adaptor, n4, 1);
814 checkGraphIncEdgeList(adaptor, n1, 2);
815 checkGraphIncEdgeList(adaptor, n2, 2);
816 checkGraphIncEdgeList(adaptor, n3, 3);
817 checkGraphIncEdgeList(adaptor, n4, 1);
819 checkNodeIds(adaptor);
820 checkArcIds(adaptor);
821 checkEdgeIds(adaptor);
823 checkGraphNodeMap(adaptor);
824 checkGraphArcMap(adaptor);
825 checkGraphEdgeMap(adaptor);
827 node_filter[n1] = false;
829 checkGraphNodeList(adaptor, 3);
830 checkGraphArcList(adaptor, 4);
831 checkGraphEdgeList(adaptor, 2);
832 checkGraphConArcList(adaptor, 4);
833 checkGraphConEdgeList(adaptor, 2);
835 checkGraphOutArcList(adaptor, n2, 1);
836 checkGraphOutArcList(adaptor, n3, 2);
837 checkGraphOutArcList(adaptor, n4, 1);
839 checkGraphInArcList(adaptor, n2, 1);
840 checkGraphInArcList(adaptor, n3, 2);
841 checkGraphInArcList(adaptor, n4, 1);
843 checkGraphIncEdgeList(adaptor, n2, 1);
844 checkGraphIncEdgeList(adaptor, n3, 2);
845 checkGraphIncEdgeList(adaptor, n4, 1);
847 checkNodeIds(adaptor);
848 checkArcIds(adaptor);
849 checkEdgeIds(adaptor);
851 checkGraphNodeMap(adaptor);
852 checkGraphArcMap(adaptor);
853 checkGraphEdgeMap(adaptor);
855 node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
857 checkGraphNodeList(adaptor, 0);
858 checkGraphArcList(adaptor, 0);
859 checkGraphEdgeList(adaptor, 0);
860 checkGraphConArcList(adaptor, 0);
861 checkGraphConEdgeList(adaptor, 0);
863 checkNodeIds(adaptor);
864 checkArcIds(adaptor);
865 checkEdgeIds(adaptor);
867 checkGraphNodeMap(adaptor);
868 checkGraphArcMap(adaptor);
869 checkGraphEdgeMap(adaptor);
872 void checkEdgeSubGraphAdaptor() {
873 checkConcept<concepts::Graph,
874 EdgeSubGraphAdaptor<concepts::Graph,
875 concepts::Graph::EdgeMap<bool> > >();
877 typedef ListGraph Graph;
878 typedef Graph::EdgeMap<bool> EdgeFilter;
879 typedef EdgeSubGraphAdaptor<Graph, EdgeFilter> Adaptor;
882 EdgeFilter edge_filter(graph);
883 Adaptor adaptor(graph, edge_filter);
885 Graph::Node n1 = graph.addNode();
886 Graph::Node n2 = graph.addNode();
887 Graph::Node n3 = graph.addNode();
888 Graph::Node n4 = graph.addNode();
890 Graph::Edge e1 = graph.addEdge(n1, n2);
891 Graph::Edge e2 = graph.addEdge(n1, n3);
892 Graph::Edge e3 = graph.addEdge(n2, n3);
893 Graph::Edge e4 = graph.addEdge(n3, n4);
895 edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
897 checkGraphNodeList(adaptor, 4);
898 checkGraphArcList(adaptor, 8);
899 checkGraphEdgeList(adaptor, 4);
900 checkGraphConArcList(adaptor, 8);
901 checkGraphConEdgeList(adaptor, 4);
903 checkGraphOutArcList(adaptor, n1, 2);
904 checkGraphOutArcList(adaptor, n2, 2);
905 checkGraphOutArcList(adaptor, n3, 3);
906 checkGraphOutArcList(adaptor, n4, 1);
908 checkGraphInArcList(adaptor, n1, 2);
909 checkGraphInArcList(adaptor, n2, 2);
910 checkGraphInArcList(adaptor, n3, 3);
911 checkGraphInArcList(adaptor, n4, 1);
913 checkGraphIncEdgeList(adaptor, n1, 2);
914 checkGraphIncEdgeList(adaptor, n2, 2);
915 checkGraphIncEdgeList(adaptor, n3, 3);
916 checkGraphIncEdgeList(adaptor, n4, 1);
918 checkNodeIds(adaptor);
919 checkArcIds(adaptor);
920 checkEdgeIds(adaptor);
922 checkGraphNodeMap(adaptor);
923 checkGraphArcMap(adaptor);
924 checkGraphEdgeMap(adaptor);
926 edge_filter[e2] = false;
928 checkGraphNodeList(adaptor, 4);
929 checkGraphArcList(adaptor, 6);
930 checkGraphEdgeList(adaptor, 3);
931 checkGraphConArcList(adaptor, 6);
932 checkGraphConEdgeList(adaptor, 3);
934 checkGraphOutArcList(adaptor, n1, 1);
935 checkGraphOutArcList(adaptor, n2, 2);
936 checkGraphOutArcList(adaptor, n3, 2);
937 checkGraphOutArcList(adaptor, n4, 1);
939 checkGraphInArcList(adaptor, n1, 1);
940 checkGraphInArcList(adaptor, n2, 2);
941 checkGraphInArcList(adaptor, n3, 2);
942 checkGraphInArcList(adaptor, n4, 1);
944 checkGraphIncEdgeList(adaptor, n1, 1);
945 checkGraphIncEdgeList(adaptor, n2, 2);
946 checkGraphIncEdgeList(adaptor, n3, 2);
947 checkGraphIncEdgeList(adaptor, n4, 1);
949 checkNodeIds(adaptor);
950 checkArcIds(adaptor);
951 checkEdgeIds(adaptor);
953 checkGraphNodeMap(adaptor);
954 checkGraphArcMap(adaptor);
955 checkGraphEdgeMap(adaptor);
957 edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
959 checkGraphNodeList(adaptor, 4);
960 checkGraphArcList(adaptor, 0);
961 checkGraphEdgeList(adaptor, 0);
962 checkGraphConArcList(adaptor, 0);
963 checkGraphConEdgeList(adaptor, 0);
965 checkNodeIds(adaptor);
966 checkArcIds(adaptor);
967 checkEdgeIds(adaptor);
969 checkGraphNodeMap(adaptor);
970 checkGraphArcMap(adaptor);
971 checkGraphEdgeMap(adaptor);
974 void checkDirGraphAdaptor() {
975 checkConcept<concepts::Digraph,
976 DirGraphAdaptor<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
978 typedef ListGraph Graph;
979 typedef ListGraph::EdgeMap<bool> DirMap;
980 typedef DirGraphAdaptor<Graph> Adaptor;
983 DirMap dir(graph, true);
984 Adaptor adaptor(graph, dir);
986 Graph::Node n1 = graph.addNode();
987 Graph::Node n2 = graph.addNode();
988 Graph::Node n3 = graph.addNode();
990 Graph::Edge e1 = graph.addEdge(n1, n2);
991 Graph::Edge e2 = graph.addEdge(n1, n3);
992 Graph::Edge e3 = graph.addEdge(n2, n3);
994 checkGraphNodeList(adaptor, 3);
995 checkGraphArcList(adaptor, 3);
996 checkGraphConArcList(adaptor, 3);
1000 Adaptor::Node u = adaptor.source(e1);
1001 Adaptor::Node v = adaptor.target(e1);
1004 check (u == adaptor.target(e1), "Wrong dir");
1005 check (v == adaptor.source(e1), "Wrong dir");
1007 check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");
1013 Adaptor::Node u = adaptor.source(e2);
1014 Adaptor::Node v = adaptor.target(e2);
1017 check (u == adaptor.target(e2), "Wrong dir");
1018 check (v == adaptor.source(e2), "Wrong dir");
1020 check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");
1026 Adaptor::Node u = adaptor.source(e3);
1027 Adaptor::Node v = adaptor.target(e3);
1030 check (u == adaptor.target(e3), "Wrong dir");
1031 check (v == adaptor.source(e3), "Wrong dir");
1033 check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
1037 checkGraphOutArcList(adaptor, n1, 1);
1038 checkGraphOutArcList(adaptor, n2, 1);
1039 checkGraphOutArcList(adaptor, n3, 1);
1041 checkGraphInArcList(adaptor, n1, 1);
1042 checkGraphInArcList(adaptor, n2, 1);
1043 checkGraphInArcList(adaptor, n3, 1);
1045 checkNodeIds(adaptor);
1046 checkArcIds(adaptor);
1048 checkGraphNodeMap(adaptor);
1049 checkGraphArcMap(adaptor);
1054 int main(int, const char **) {
1056 checkDigraphAdaptor();
1057 checkRevDigraphAdaptor();
1058 checkSubDigraphAdaptor();
1059 checkNodeSubDigraphAdaptor();
1060 checkArcSubDigraphAdaptor();
1061 checkUndirDigraphAdaptor();
1062 checkResDigraphAdaptor();
1063 checkSplitDigraphAdaptor();
1065 checkGraphAdaptor();
1066 checkSubGraphAdaptor();
1067 checkNodeSubGraphAdaptor();
1068 checkEdgeSubGraphAdaptor();
1069 checkDirGraphAdaptor();