COIN-OR::LEMON - Graph Library

source: lemon-1.2/test/graph_adaptor_test.cc @ 415:4b6112235fad

Last change on this file since 415:4b6112235fad was 415:4b6112235fad, checked in by Balazs Dezso <deba@…>, 15 years ago

Improvements in graph adaptors (#67)

Remove DigraphAdaptor? and GraphAdaptor?
Remove docs of base classes
Move the member documentations to real adaptors
Minor improvements in documentation

File size: 26.2 KB
Line 
1/* -*- C++ -*-
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<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/digraph_adaptor.h>
29#include<lemon/graph_adaptor.h>
30
31#include <limits>
32#include <lemon/bfs.h>
33#include <lemon/path.h>
34
35#include"test/test_tools.h"
36#include"test/graph_test.h"
37
38using namespace lemon;
39
40void checkRevDigraphAdaptor() {
41  checkConcept<concepts::Digraph, RevDigraphAdaptor<concepts::Digraph> >();
42
43  typedef ListDigraph Digraph;
44  typedef RevDigraphAdaptor<Digraph> Adaptor;
45
46  Digraph digraph;
47  Adaptor adaptor(digraph);
48
49  Digraph::Node n1 = digraph.addNode();
50  Digraph::Node n2 = digraph.addNode();
51  Digraph::Node n3 = digraph.addNode();
52
53  Digraph::Arc a1 = digraph.addArc(n1, n2);
54  Digraph::Arc a2 = digraph.addArc(n1, n3);
55  Digraph::Arc a3 = digraph.addArc(n2, n3);
56 
57  checkGraphNodeList(adaptor, 3);
58  checkGraphArcList(adaptor, 3);
59  checkGraphConArcList(adaptor, 3);
60
61  checkGraphOutArcList(adaptor, n1, 0);
62  checkGraphOutArcList(adaptor, n2, 1);
63  checkGraphOutArcList(adaptor, n3, 2);
64
65  checkGraphInArcList(adaptor, n1, 2);
66  checkGraphInArcList(adaptor, n2, 1);
67  checkGraphInArcList(adaptor, n3, 0);
68
69  checkNodeIds(adaptor);
70  checkArcIds(adaptor);
71
72  checkGraphNodeMap(adaptor);
73  checkGraphArcMap(adaptor);
74
75  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
76    check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
77    check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
78  }
79}
80
81void checkSubDigraphAdaptor() {
82  checkConcept<concepts::Digraph,
83    SubDigraphAdaptor<concepts::Digraph,
84    concepts::Digraph::NodeMap<bool>,
85    concepts::Digraph::ArcMap<bool> > >();
86
87  typedef ListDigraph Digraph;
88  typedef Digraph::NodeMap<bool> NodeFilter;
89  typedef Digraph::ArcMap<bool> ArcFilter;
90  typedef SubDigraphAdaptor<Digraph, NodeFilter, ArcFilter> Adaptor;
91
92  Digraph digraph;
93  NodeFilter node_filter(digraph);
94  ArcFilter arc_filter(digraph);
95  Adaptor adaptor(digraph, node_filter, arc_filter);
96
97  Digraph::Node n1 = digraph.addNode();
98  Digraph::Node n2 = digraph.addNode();
99  Digraph::Node n3 = digraph.addNode();
100
101  Digraph::Arc a1 = digraph.addArc(n1, n2);
102  Digraph::Arc a2 = digraph.addArc(n1, n3);
103  Digraph::Arc a3 = digraph.addArc(n2, n3);
104
105  node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
106  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
107 
108  checkGraphNodeList(adaptor, 3);
109  checkGraphArcList(adaptor, 3);
110  checkGraphConArcList(adaptor, 3);
111
112  checkGraphOutArcList(adaptor, n1, 2);
113  checkGraphOutArcList(adaptor, n2, 1);
114  checkGraphOutArcList(adaptor, n3, 0);
115
116  checkGraphInArcList(adaptor, n1, 0);
117  checkGraphInArcList(adaptor, n2, 1);
118  checkGraphInArcList(adaptor, n3, 2);
119
120  checkNodeIds(adaptor);
121  checkArcIds(adaptor);
122
123  checkGraphNodeMap(adaptor);
124  checkGraphArcMap(adaptor);
125
126  arc_filter[a2] = false;
127
128  checkGraphNodeList(adaptor, 3);
129  checkGraphArcList(adaptor, 2);
130  checkGraphConArcList(adaptor, 2);
131
132  checkGraphOutArcList(adaptor, n1, 1);
133  checkGraphOutArcList(adaptor, n2, 1);
134  checkGraphOutArcList(adaptor, n3, 0);
135
136  checkGraphInArcList(adaptor, n1, 0);
137  checkGraphInArcList(adaptor, n2, 1);
138  checkGraphInArcList(adaptor, n3, 1);
139
140  checkNodeIds(adaptor);
141  checkArcIds(adaptor);
142
143  checkGraphNodeMap(adaptor);
144  checkGraphArcMap(adaptor);
145
146  node_filter[n1] = false;
147
148  checkGraphNodeList(adaptor, 2);
149  checkGraphArcList(adaptor, 1);
150  checkGraphConArcList(adaptor, 1);
151
152  checkGraphOutArcList(adaptor, n2, 1);
153  checkGraphOutArcList(adaptor, n3, 0);
154
155  checkGraphInArcList(adaptor, n2, 0);
156  checkGraphInArcList(adaptor, n3, 1);
157
158  checkNodeIds(adaptor);
159  checkArcIds(adaptor);
160
161  checkGraphNodeMap(adaptor);
162  checkGraphArcMap(adaptor);
163
164  node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
165  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
166
167  checkGraphNodeList(adaptor, 0);
168  checkGraphArcList(adaptor, 0);
169  checkGraphConArcList(adaptor, 0);
170
171  checkNodeIds(adaptor);
172  checkArcIds(adaptor);
173
174  checkGraphNodeMap(adaptor);
175  checkGraphArcMap(adaptor);
176}
177
178void checkNodeSubDigraphAdaptor() {
179  checkConcept<concepts::Digraph,
180    NodeSubDigraphAdaptor<concepts::Digraph,
181      concepts::Digraph::NodeMap<bool> > >();
182
183  typedef ListDigraph Digraph;
184  typedef Digraph::NodeMap<bool> NodeFilter;
185  typedef NodeSubDigraphAdaptor<Digraph, NodeFilter> Adaptor;
186
187  Digraph digraph;
188  NodeFilter node_filter(digraph);
189  Adaptor adaptor(digraph, node_filter);
190
191  Digraph::Node n1 = digraph.addNode();
192  Digraph::Node n2 = digraph.addNode();
193  Digraph::Node n3 = digraph.addNode();
194
195  Digraph::Arc a1 = digraph.addArc(n1, n2);
196  Digraph::Arc a2 = digraph.addArc(n1, n3);
197  Digraph::Arc a3 = digraph.addArc(n2, n3);
198
199  node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
200 
201  checkGraphNodeList(adaptor, 3);
202  checkGraphArcList(adaptor, 3);
203  checkGraphConArcList(adaptor, 3);
204
205  checkGraphOutArcList(adaptor, n1, 2);
206  checkGraphOutArcList(adaptor, n2, 1);
207  checkGraphOutArcList(adaptor, n3, 0);
208
209  checkGraphInArcList(adaptor, n1, 0);
210  checkGraphInArcList(adaptor, n2, 1);
211  checkGraphInArcList(adaptor, n3, 2);
212
213  checkNodeIds(adaptor);
214  checkArcIds(adaptor);
215
216  checkGraphNodeMap(adaptor);
217  checkGraphArcMap(adaptor);
218
219  node_filter[n1] = false;
220
221  checkGraphNodeList(adaptor, 2);
222  checkGraphArcList(adaptor, 1);
223  checkGraphConArcList(adaptor, 1);
224
225  checkGraphOutArcList(adaptor, n2, 1);
226  checkGraphOutArcList(adaptor, n3, 0);
227
228  checkGraphInArcList(adaptor, n2, 0);
229  checkGraphInArcList(adaptor, n3, 1);
230
231  checkNodeIds(adaptor);
232  checkArcIds(adaptor);
233
234  checkGraphNodeMap(adaptor);
235  checkGraphArcMap(adaptor);
236
237  node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
238
239  checkGraphNodeList(adaptor, 0);
240  checkGraphArcList(adaptor, 0);
241  checkGraphConArcList(adaptor, 0);
242
243  checkNodeIds(adaptor);
244  checkArcIds(adaptor);
245
246  checkGraphNodeMap(adaptor);
247  checkGraphArcMap(adaptor);
248}
249
250void checkArcSubDigraphAdaptor() {
251  checkConcept<concepts::Digraph,
252    ArcSubDigraphAdaptor<concepts::Digraph,
253    concepts::Digraph::ArcMap<bool> > >();
254
255  typedef ListDigraph Digraph;
256  typedef Digraph::ArcMap<bool> ArcFilter;
257  typedef ArcSubDigraphAdaptor<Digraph, ArcFilter> Adaptor;
258
259  Digraph digraph;
260  ArcFilter arc_filter(digraph);
261  Adaptor adaptor(digraph, arc_filter);
262
263  Digraph::Node n1 = digraph.addNode();
264  Digraph::Node n2 = digraph.addNode();
265  Digraph::Node n3 = digraph.addNode();
266
267  Digraph::Arc a1 = digraph.addArc(n1, n2);
268  Digraph::Arc a2 = digraph.addArc(n1, n3);
269  Digraph::Arc a3 = digraph.addArc(n2, n3);
270
271  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
272 
273  checkGraphNodeList(adaptor, 3);
274  checkGraphArcList(adaptor, 3);
275  checkGraphConArcList(adaptor, 3);
276
277  checkGraphOutArcList(adaptor, n1, 2);
278  checkGraphOutArcList(adaptor, n2, 1);
279  checkGraphOutArcList(adaptor, n3, 0);
280
281  checkGraphInArcList(adaptor, n1, 0);
282  checkGraphInArcList(adaptor, n2, 1);
283  checkGraphInArcList(adaptor, n3, 2);
284
285  checkNodeIds(adaptor);
286  checkArcIds(adaptor);
287
288  checkGraphNodeMap(adaptor);
289  checkGraphArcMap(adaptor);
290
291  arc_filter[a2] = false;
292
293  checkGraphNodeList(adaptor, 3);
294  checkGraphArcList(adaptor, 2);
295  checkGraphConArcList(adaptor, 2);
296
297  checkGraphOutArcList(adaptor, n1, 1);
298  checkGraphOutArcList(adaptor, n2, 1);
299  checkGraphOutArcList(adaptor, n3, 0);
300
301  checkGraphInArcList(adaptor, n1, 0);
302  checkGraphInArcList(adaptor, n2, 1);
303  checkGraphInArcList(adaptor, n3, 1);
304
305  checkNodeIds(adaptor);
306  checkArcIds(adaptor);
307
308  checkGraphNodeMap(adaptor);
309  checkGraphArcMap(adaptor);
310
311  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
312
313  checkGraphNodeList(adaptor, 3);
314  checkGraphArcList(adaptor, 0);
315  checkGraphConArcList(adaptor, 0);
316
317  checkNodeIds(adaptor);
318  checkArcIds(adaptor);
319
320  checkGraphNodeMap(adaptor);
321  checkGraphArcMap(adaptor);
322}
323
324void checkUndirDigraphAdaptor() {
325  checkConcept<concepts::Graph, UndirDigraphAdaptor<concepts::Digraph> >();
326
327  typedef ListDigraph Digraph;
328  typedef UndirDigraphAdaptor<Digraph> Adaptor;
329
330  Digraph digraph;
331  Adaptor adaptor(digraph);
332
333  Digraph::Node n1 = digraph.addNode();
334  Digraph::Node n2 = digraph.addNode();
335  Digraph::Node n3 = digraph.addNode();
336
337  Digraph::Arc a1 = digraph.addArc(n1, n2);
338  Digraph::Arc a2 = digraph.addArc(n1, n3);
339  Digraph::Arc a3 = digraph.addArc(n2, n3);
340 
341  checkGraphNodeList(adaptor, 3);
342  checkGraphArcList(adaptor, 6);
343  checkGraphEdgeList(adaptor, 3);
344  checkGraphConArcList(adaptor, 6);
345  checkGraphConEdgeList(adaptor, 3);
346
347  checkGraphOutArcList(adaptor, n1, 2);
348  checkGraphOutArcList(adaptor, n2, 2);
349  checkGraphOutArcList(adaptor, n3, 2);
350
351  checkGraphInArcList(adaptor, n1, 2);
352  checkGraphInArcList(adaptor, n2, 2);
353  checkGraphInArcList(adaptor, n3, 2);
354
355  checkGraphIncEdgeList(adaptor, n1, 2);
356  checkGraphIncEdgeList(adaptor, n2, 2);
357  checkGraphIncEdgeList(adaptor, n3, 2);
358
359  checkNodeIds(adaptor);
360  checkArcIds(adaptor);
361  checkEdgeIds(adaptor);
362
363  checkGraphNodeMap(adaptor);
364  checkGraphArcMap(adaptor);
365  checkGraphEdgeMap(adaptor);
366
367  for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {
368    check(adaptor.u(e) == digraph.source(e), "Wrong undir");
369    check(adaptor.v(e) == digraph.target(e), "Wrong undir");
370  }
371
372}
373
374void checkResDigraphAdaptor() {
375  checkConcept<concepts::Digraph,
376    ResDigraphAdaptor<concepts::Digraph,
377    concepts::Digraph::ArcMap<int>,
378    concepts::Digraph::ArcMap<int> > >();
379
380  typedef ListDigraph Digraph;
381  typedef Digraph::ArcMap<int> IntArcMap;
382  typedef ResDigraphAdaptor<Digraph, IntArcMap> Adaptor;
383
384  Digraph digraph;
385  IntArcMap capacity(digraph), flow(digraph);
386  Adaptor adaptor(digraph, capacity, flow);
387
388  Digraph::Node n1 = digraph.addNode();
389  Digraph::Node n2 = digraph.addNode();
390  Digraph::Node n3 = digraph.addNode();
391  Digraph::Node n4 = digraph.addNode();
392
393  Digraph::Arc a1 = digraph.addArc(n1, n2);
394  Digraph::Arc a2 = digraph.addArc(n1, n3);
395  Digraph::Arc a3 = digraph.addArc(n1, n4);
396  Digraph::Arc a4 = digraph.addArc(n2, n3);
397  Digraph::Arc a5 = digraph.addArc(n2, n4);
398  Digraph::Arc a6 = digraph.addArc(n3, n4);
399
400  capacity[a1] = 8;
401  capacity[a2] = 6;
402  capacity[a3] = 4;
403  capacity[a4] = 4;
404  capacity[a5] = 6;
405  capacity[a6] = 10;
406
407  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
408    flow[a] = 0;
409  }
410 
411  checkGraphNodeList(adaptor, 4);
412  checkGraphArcList(adaptor, 6);
413  checkGraphConArcList(adaptor, 6);
414
415  checkGraphOutArcList(adaptor, n1, 3);
416  checkGraphOutArcList(adaptor, n2, 2);
417  checkGraphOutArcList(adaptor, n3, 1);
418  checkGraphOutArcList(adaptor, n4, 0);
419
420  checkGraphInArcList(adaptor, n1, 0);
421  checkGraphInArcList(adaptor, n2, 1);
422  checkGraphInArcList(adaptor, n3, 2);
423  checkGraphInArcList(adaptor, n4, 3);
424
425  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
426    flow[a] = capacity[a] / 2;
427  }
428 
429  checkGraphNodeList(adaptor, 4);
430  checkGraphArcList(adaptor, 12);
431  checkGraphConArcList(adaptor, 12);
432
433  checkGraphOutArcList(adaptor, n1, 3);
434  checkGraphOutArcList(adaptor, n2, 3);
435  checkGraphOutArcList(adaptor, n3, 3);
436  checkGraphOutArcList(adaptor, n4, 3);
437
438  checkGraphInArcList(adaptor, n1, 3);
439  checkGraphInArcList(adaptor, n2, 3);
440  checkGraphInArcList(adaptor, n3, 3);
441  checkGraphInArcList(adaptor, n4, 3);
442
443  checkNodeIds(adaptor);
444  checkArcIds(adaptor);
445
446  checkGraphNodeMap(adaptor);
447  checkGraphArcMap(adaptor);
448
449  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
450    flow[a] = capacity[a];
451  }
452 
453  checkGraphNodeList(adaptor, 4);
454  checkGraphArcList(adaptor, 6);
455  checkGraphConArcList(adaptor, 6);
456
457  checkGraphOutArcList(adaptor, n1, 0);
458  checkGraphOutArcList(adaptor, n2, 1);
459  checkGraphOutArcList(adaptor, n3, 2);
460  checkGraphOutArcList(adaptor, n4, 3);
461
462  checkGraphInArcList(adaptor, n1, 3);
463  checkGraphInArcList(adaptor, n2, 2);
464  checkGraphInArcList(adaptor, n3, 1);
465  checkGraphInArcList(adaptor, n4, 0);
466
467  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
468    flow[a] = 0;
469  }
470
471  int flow_value = 0;
472  while (true) {
473   
474    Bfs<Adaptor> bfs(adaptor);
475    bfs.run(n1, n4);
476   
477    if (!bfs.reached(n4)) break;
478
479    Path<Adaptor> p = bfs.path(n4);
480   
481    int min = std::numeric_limits<int>::max();
482    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
483      if (adaptor.rescap(a) < min) min = adaptor.rescap(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
496void checkSplitDigraphAdaptor() {
497  checkConcept<concepts::Digraph, SplitDigraphAdaptor<concepts::Digraph> >();
498
499  typedef ListDigraph Digraph;
500  typedef SplitDigraphAdaptor<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
552void checkSubGraphAdaptor() {
553  checkConcept<concepts::Graph,
554    SubGraphAdaptor<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 SubGraphAdaptor<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
687void checkNodeSubGraphAdaptor() {
688  checkConcept<concepts::Graph,
689    NodeSubGraphAdaptor<concepts::Graph,
690      concepts::Graph::NodeMap<bool> > >();
691
692  typedef ListGraph Graph;
693  typedef Graph::NodeMap<bool> NodeFilter;
694  typedef NodeSubGraphAdaptor<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
786void checkEdgeSubGraphAdaptor() {
787  checkConcept<concepts::Graph,
788    EdgeSubGraphAdaptor<concepts::Graph,
789    concepts::Graph::EdgeMap<bool> > >();
790
791  typedef ListGraph Graph;
792  typedef Graph::EdgeMap<bool> EdgeFilter;
793  typedef EdgeSubGraphAdaptor<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
888void checkDirGraphAdaptor() {
889  checkConcept<concepts::Digraph,
890    DirGraphAdaptor<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
891
892  typedef ListGraph Graph;
893  typedef ListGraph::EdgeMap<bool> DirMap;
894  typedef DirGraphAdaptor<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
968int main(int, const char **) {
969
970  checkRevDigraphAdaptor();
971  checkSubDigraphAdaptor();
972  checkNodeSubDigraphAdaptor();
973  checkArcSubDigraphAdaptor();
974  checkUndirDigraphAdaptor();
975  checkResDigraphAdaptor();
976  checkSplitDigraphAdaptor();
977
978  checkSubGraphAdaptor();
979  checkNodeSubGraphAdaptor();
980  checkEdgeSubGraphAdaptor();
981  checkDirGraphAdaptor();
982
983  return 0;
984}
Note: See TracBrowser for help on using the repository browser.