COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

source: lemon-1.2/test/graph_adaptor_test.cc @ 414:05357da973ce

Last change on this file since 414:05357da973ce was 414:05357da973ce, checked in by Balazs Dezso <deba@…>, 17 years ago

Port graph adaptors from svn -r3498 (#67)
File size: 28.5 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 checkDigraphAdaptor() {
41  checkConcept<concepts::Digraph, DigraphAdaptor<concepts::Digraph> >();
42
43  typedef ListDigraph Digraph;
44  typedef DigraphAdaptor<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, 2);
62  checkGraphOutArcList(adaptor, n2, 1);
63  checkGraphOutArcList(adaptor, n3, 0);
64
65  checkGraphInArcList(adaptor, n1, 0);
66  checkGraphInArcList(adaptor, n2, 1);
67  checkGraphInArcList(adaptor, n3, 2);
68
69  checkNodeIds(adaptor);
70  checkArcIds(adaptor);
71
72  checkGraphNodeMap(adaptor);
73  checkGraphArcMap(adaptor);
74}
75
76void checkRevDigraphAdaptor() {
77  checkConcept<concepts::Digraph, RevDigraphAdaptor<concepts::Digraph> >();
78
79  typedef ListDigraph Digraph;
80  typedef RevDigraphAdaptor<Digraph> Adaptor;
81
82  Digraph digraph;
83  Adaptor adaptor(digraph);
84
85  Digraph::Node n1 = digraph.addNode();
86  Digraph::Node n2 = digraph.addNode();
87  Digraph::Node n3 = digraph.addNode();
88
89  Digraph::Arc a1 = digraph.addArc(n1, n2);
90  Digraph::Arc a2 = digraph.addArc(n1, n3);
91  Digraph::Arc a3 = digraph.addArc(n2, n3);
92 
93  checkGraphNodeList(adaptor, 3);
94  checkGraphArcList(adaptor, 3);
95  checkGraphConArcList(adaptor, 3);
96
97  checkGraphOutArcList(adaptor, n1, 0);
98  checkGraphOutArcList(adaptor, n2, 1);
99  checkGraphOutArcList(adaptor, n3, 2);
100
101  checkGraphInArcList(adaptor, n1, 2);
102  checkGraphInArcList(adaptor, n2, 1);
103  checkGraphInArcList(adaptor, n3, 0);
104
105  checkNodeIds(adaptor);
106  checkArcIds(adaptor);
107
108  checkGraphNodeMap(adaptor);
109  checkGraphArcMap(adaptor);
110
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");
114  }
115}
116
117void checkSubDigraphAdaptor() {
118  checkConcept<concepts::Digraph,
119    SubDigraphAdaptor<concepts::Digraph,
120    concepts::Digraph::NodeMap<bool>,
121    concepts::Digraph::ArcMap<bool> > >();
122
123  typedef ListDigraph Digraph;
124  typedef Digraph::NodeMap<bool> NodeFilter;
125  typedef Digraph::ArcMap<bool> ArcFilter;
126  typedef SubDigraphAdaptor<Digraph, NodeFilter, ArcFilter> Adaptor;
127
128  Digraph digraph;
129  NodeFilter node_filter(digraph);
130  ArcFilter arc_filter(digraph);
131  Adaptor adaptor(digraph, node_filter, arc_filter);
132
133  Digraph::Node n1 = digraph.addNode();
134  Digraph::Node n2 = digraph.addNode();
135  Digraph::Node n3 = digraph.addNode();
136
137  Digraph::Arc a1 = digraph.addArc(n1, n2);
138  Digraph::Arc a2 = digraph.addArc(n1, n3);
139  Digraph::Arc a3 = digraph.addArc(n2, n3);
140
141  node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
142  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
143 
144  checkGraphNodeList(adaptor, 3);
145  checkGraphArcList(adaptor, 3);
146  checkGraphConArcList(adaptor, 3);
147
148  checkGraphOutArcList(adaptor, n1, 2);
149  checkGraphOutArcList(adaptor, n2, 1);
150  checkGraphOutArcList(adaptor, n3, 0);
151
152  checkGraphInArcList(adaptor, n1, 0);
153  checkGraphInArcList(adaptor, n2, 1);
154  checkGraphInArcList(adaptor, n3, 2);
155
156  checkNodeIds(adaptor);
157  checkArcIds(adaptor);
158
159  checkGraphNodeMap(adaptor);
160  checkGraphArcMap(adaptor);
161
162  arc_filter[a2] = false;
163
164  checkGraphNodeList(adaptor, 3);
165  checkGraphArcList(adaptor, 2);
166  checkGraphConArcList(adaptor, 2);
167
168  checkGraphOutArcList(adaptor, n1, 1);
169  checkGraphOutArcList(adaptor, n2, 1);
170  checkGraphOutArcList(adaptor, n3, 0);
171
172  checkGraphInArcList(adaptor, n1, 0);
173  checkGraphInArcList(adaptor, n2, 1);
174  checkGraphInArcList(adaptor, n3, 1);
175
176  checkNodeIds(adaptor);
177  checkArcIds(adaptor);
178
179  checkGraphNodeMap(adaptor);
180  checkGraphArcMap(adaptor);
181
182  node_filter[n1] = false;
183
184  checkGraphNodeList(adaptor, 2);
185  checkGraphArcList(adaptor, 1);
186  checkGraphConArcList(adaptor, 1);
187
188  checkGraphOutArcList(adaptor, n2, 1);
189  checkGraphOutArcList(adaptor, n3, 0);
190
191  checkGraphInArcList(adaptor, n2, 0);
192  checkGraphInArcList(adaptor, n3, 1);
193
194  checkNodeIds(adaptor);
195  checkArcIds(adaptor);
196
197  checkGraphNodeMap(adaptor);
198  checkGraphArcMap(adaptor);
199
200  node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
201  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
202
203  checkGraphNodeList(adaptor, 0);
204  checkGraphArcList(adaptor, 0);
205  checkGraphConArcList(adaptor, 0);
206
207  checkNodeIds(adaptor);
208  checkArcIds(adaptor);
209
210  checkGraphNodeMap(adaptor);
211  checkGraphArcMap(adaptor);
212}
213
214void checkNodeSubDigraphAdaptor() {
215  checkConcept<concepts::Digraph,
216    NodeSubDigraphAdaptor<concepts::Digraph,
217      concepts::Digraph::NodeMap<bool> > >();
218
219  typedef ListDigraph Digraph;
220  typedef Digraph::NodeMap<bool> NodeFilter;
221  typedef NodeSubDigraphAdaptor<Digraph, NodeFilter> Adaptor;
222
223  Digraph digraph;
224  NodeFilter node_filter(digraph);
225  Adaptor adaptor(digraph, node_filter);
226
227  Digraph::Node n1 = digraph.addNode();
228  Digraph::Node n2 = digraph.addNode();
229  Digraph::Node n3 = digraph.addNode();
230
231  Digraph::Arc a1 = digraph.addArc(n1, n2);
232  Digraph::Arc a2 = digraph.addArc(n1, n3);
233  Digraph::Arc a3 = digraph.addArc(n2, n3);
234
235  node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
236 
237  checkGraphNodeList(adaptor, 3);
238  checkGraphArcList(adaptor, 3);
239  checkGraphConArcList(adaptor, 3);
240
241  checkGraphOutArcList(adaptor, n1, 2);
242  checkGraphOutArcList(adaptor, n2, 1);
243  checkGraphOutArcList(adaptor, n3, 0);
244
245  checkGraphInArcList(adaptor, n1, 0);
246  checkGraphInArcList(adaptor, n2, 1);
247  checkGraphInArcList(adaptor, n3, 2);
248
249  checkNodeIds(adaptor);
250  checkArcIds(adaptor);
251
252  checkGraphNodeMap(adaptor);
253  checkGraphArcMap(adaptor);
254
255  node_filter[n1] = false;
256
257  checkGraphNodeList(adaptor, 2);
258  checkGraphArcList(adaptor, 1);
259  checkGraphConArcList(adaptor, 1);
260
261  checkGraphOutArcList(adaptor, n2, 1);
262  checkGraphOutArcList(adaptor, n3, 0);
263
264  checkGraphInArcList(adaptor, n2, 0);
265  checkGraphInArcList(adaptor, n3, 1);
266
267  checkNodeIds(adaptor);
268  checkArcIds(adaptor);
269
270  checkGraphNodeMap(adaptor);
271  checkGraphArcMap(adaptor);
272
273  node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
274
275  checkGraphNodeList(adaptor, 0);
276  checkGraphArcList(adaptor, 0);
277  checkGraphConArcList(adaptor, 0);
278
279  checkNodeIds(adaptor);
280  checkArcIds(adaptor);
281
282  checkGraphNodeMap(adaptor);
283  checkGraphArcMap(adaptor);
284}
285
286void checkArcSubDigraphAdaptor() {
287  checkConcept<concepts::Digraph,
288    ArcSubDigraphAdaptor<concepts::Digraph,
289    concepts::Digraph::ArcMap<bool> > >();
290
291  typedef ListDigraph Digraph;
292  typedef Digraph::ArcMap<bool> ArcFilter;
293  typedef ArcSubDigraphAdaptor<Digraph, ArcFilter> Adaptor;
294
295  Digraph digraph;
296  ArcFilter arc_filter(digraph);
297  Adaptor adaptor(digraph, arc_filter);
298
299  Digraph::Node n1 = digraph.addNode();
300  Digraph::Node n2 = digraph.addNode();
301  Digraph::Node n3 = digraph.addNode();
302
303  Digraph::Arc a1 = digraph.addArc(n1, n2);
304  Digraph::Arc a2 = digraph.addArc(n1, n3);
305  Digraph::Arc a3 = digraph.addArc(n2, n3);
306
307  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
308 
309  checkGraphNodeList(adaptor, 3);
310  checkGraphArcList(adaptor, 3);
311  checkGraphConArcList(adaptor, 3);
312
313  checkGraphOutArcList(adaptor, n1, 2);
314  checkGraphOutArcList(adaptor, n2, 1);
315  checkGraphOutArcList(adaptor, n3, 0);
316
317  checkGraphInArcList(adaptor, n1, 0);
318  checkGraphInArcList(adaptor, n2, 1);
319  checkGraphInArcList(adaptor, n3, 2);
320
321  checkNodeIds(adaptor);
322  checkArcIds(adaptor);
323
324  checkGraphNodeMap(adaptor);
325  checkGraphArcMap(adaptor);
326
327  arc_filter[a2] = false;
328
329  checkGraphNodeList(adaptor, 3);
330  checkGraphArcList(adaptor, 2);
331  checkGraphConArcList(adaptor, 2);
332
333  checkGraphOutArcList(adaptor, n1, 1);
334  checkGraphOutArcList(adaptor, n2, 1);
335  checkGraphOutArcList(adaptor, n3, 0);
336
337  checkGraphInArcList(adaptor, n1, 0);
338  checkGraphInArcList(adaptor, n2, 1);
339  checkGraphInArcList(adaptor, n3, 1);
340
341  checkNodeIds(adaptor);
342  checkArcIds(adaptor);
343
344  checkGraphNodeMap(adaptor);
345  checkGraphArcMap(adaptor);
346
347  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
348
349  checkGraphNodeList(adaptor, 3);
350  checkGraphArcList(adaptor, 0);
351  checkGraphConArcList(adaptor, 0);
352
353  checkNodeIds(adaptor);
354  checkArcIds(adaptor);
355
356  checkGraphNodeMap(adaptor);
357  checkGraphArcMap(adaptor);
358}
359
360void checkUndirDigraphAdaptor() {
361  checkConcept<concepts::Graph, UndirDigraphAdaptor<concepts::Digraph> >();
362
363  typedef ListDigraph Digraph;
364  typedef UndirDigraphAdaptor<Digraph> Adaptor;
365
366  Digraph digraph;
367  Adaptor adaptor(digraph);
368
369  Digraph::Node n1 = digraph.addNode();
370  Digraph::Node n2 = digraph.addNode();
371  Digraph::Node n3 = digraph.addNode();
372
373  Digraph::Arc a1 = digraph.addArc(n1, n2);
374  Digraph::Arc a2 = digraph.addArc(n1, n3);
375  Digraph::Arc a3 = digraph.addArc(n2, n3);
376 
377  checkGraphNodeList(adaptor, 3);
378  checkGraphArcList(adaptor, 6);
379  checkGraphEdgeList(adaptor, 3);
380  checkGraphConArcList(adaptor, 6);
381  checkGraphConEdgeList(adaptor, 3);
382
383  checkGraphOutArcList(adaptor, n1, 2);
384  checkGraphOutArcList(adaptor, n2, 2);
385  checkGraphOutArcList(adaptor, n3, 2);
386
387  checkGraphInArcList(adaptor, n1, 2);
388  checkGraphInArcList(adaptor, n2, 2);
389  checkGraphInArcList(adaptor, n3, 2);
390
391  checkGraphIncEdgeList(adaptor, n1, 2);
392  checkGraphIncEdgeList(adaptor, n2, 2);
393  checkGraphIncEdgeList(adaptor, n3, 2);
394
395  checkNodeIds(adaptor);
396  checkArcIds(adaptor);
397  checkEdgeIds(adaptor);
398
399  checkGraphNodeMap(adaptor);
400  checkGraphArcMap(adaptor);
401  checkGraphEdgeMap(adaptor);
402
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");
406  }
407
408}
409
410void checkResDigraphAdaptor() {
411  checkConcept<concepts::Digraph,
412    ResDigraphAdaptor<concepts::Digraph,
413    concepts::Digraph::ArcMap<int>,
414    concepts::Digraph::ArcMap<int> > >();
415
416  typedef ListDigraph Digraph;
417  typedef Digraph::ArcMap<int> IntArcMap;
418  typedef ResDigraphAdaptor<Digraph, IntArcMap> Adaptor;
419
420  Digraph digraph;
421  IntArcMap capacity(digraph), flow(digraph);
422  Adaptor adaptor(digraph, capacity, flow);
423
424  Digraph::Node n1 = digraph.addNode();
425  Digraph::Node n2 = digraph.addNode();
426  Digraph::Node n3 = digraph.addNode();
427  Digraph::Node n4 = digraph.addNode();
428
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);
435
436  capacity[a1] = 8;
437  capacity[a2] = 6;
438  capacity[a3] = 4;
439  capacity[a4] = 4;
440  capacity[a5] = 6;
441  capacity[a6] = 10;
442
443  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
444    flow[a] = 0;
445  }
446 
447  checkGraphNodeList(adaptor, 4);
448  checkGraphArcList(adaptor, 6);
449  checkGraphConArcList(adaptor, 6);
450
451  checkGraphOutArcList(adaptor, n1, 3);
452  checkGraphOutArcList(adaptor, n2, 2);
453  checkGraphOutArcList(adaptor, n3, 1);
454  checkGraphOutArcList(adaptor, n4, 0);
455
456  checkGraphInArcList(adaptor, n1, 0);
457  checkGraphInArcList(adaptor, n2, 1);
458  checkGraphInArcList(adaptor, n3, 2);
459  checkGraphInArcList(adaptor, n4, 3);
460
461  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
462    flow[a] = capacity[a] / 2;
463  }
464 
465  checkGraphNodeList(adaptor, 4);
466  checkGraphArcList(adaptor, 12);
467  checkGraphConArcList(adaptor, 12);
468
469  checkGraphOutArcList(adaptor, n1, 3);
470  checkGraphOutArcList(adaptor, n2, 3);
471  checkGraphOutArcList(adaptor, n3, 3);
472  checkGraphOutArcList(adaptor, n4, 3);
473
474  checkGraphInArcList(adaptor, n1, 3);
475  checkGraphInArcList(adaptor, n2, 3);
476  checkGraphInArcList(adaptor, n3, 3);
477  checkGraphInArcList(adaptor, n4, 3);
478
479  checkNodeIds(adaptor);
480  checkArcIds(adaptor);
481
482  checkGraphNodeMap(adaptor);
483  checkGraphArcMap(adaptor);
484
485  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
486    flow[a] = capacity[a];
487  }
488 
489  checkGraphNodeList(adaptor, 4);
490  checkGraphArcList(adaptor, 6);
491  checkGraphConArcList(adaptor, 6);
492
493  checkGraphOutArcList(adaptor, n1, 0);
494  checkGraphOutArcList(adaptor, n2, 1);
495  checkGraphOutArcList(adaptor, n3, 2);
496  checkGraphOutArcList(adaptor, n4, 3);
497
498  checkGraphInArcList(adaptor, n1, 3);
499  checkGraphInArcList(adaptor, n2, 2);
500  checkGraphInArcList(adaptor, n3, 1);
501  checkGraphInArcList(adaptor, n4, 0);
502
503  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
504    flow[a] = 0;
505  }
506
507  int flow_value = 0;
508  while (true) {
509   
510    Bfs<Adaptor> bfs(adaptor);
511    bfs.run(n1, n4);
512   
513    if (!bfs.reached(n4)) break;
514
515    Path<Adaptor> p = bfs.path(n4);
516   
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);
520    }
521
522    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
523      adaptor.augment(a, min);
524    }
525    flow_value += min;
526  }
527
528  check(flow_value == 18, "Wrong flow with res graph adaptor");
529
530}
531
532void checkSplitDigraphAdaptor() {
533  checkConcept<concepts::Digraph, SplitDigraphAdaptor<concepts::Digraph> >();
534
535  typedef ListDigraph Digraph;
536  typedef SplitDigraphAdaptor<Digraph> Adaptor;
537
538  Digraph digraph;
539  Adaptor adaptor(digraph);
540
541  Digraph::Node n1 = digraph.addNode();
542  Digraph::Node n2 = digraph.addNode();
543  Digraph::Node n3 = digraph.addNode();
544
545  Digraph::Arc a1 = digraph.addArc(n1, n2);
546  Digraph::Arc a2 = digraph.addArc(n1, n3);
547  Digraph::Arc a3 = digraph.addArc(n2, n3);
548 
549  checkGraphNodeList(adaptor, 6);
550  checkGraphArcList(adaptor, 6);
551  checkGraphConArcList(adaptor, 6);
552
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);
559
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);
566
567  checkNodeIds(adaptor);
568  checkArcIds(adaptor);
569 
570  checkGraphNodeMap(adaptor);
571  checkGraphArcMap(adaptor);
572
573  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
574    if (adaptor.origArc(a)) {
575      Digraph::Arc oa = a;
576      check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),
577            "Wrong split");
578      check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),
579            "Wrong split");
580    } else {
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");
584    }
585  }
586}
587
588void checkGraphAdaptor() {
589  checkConcept<concepts::Graph, GraphAdaptor<concepts::Graph> >();
590
591  typedef ListGraph Graph;
592  typedef GraphAdaptor<Graph> Adaptor;
593
594  Graph graph;
595  Adaptor adaptor(graph);
596
597  Graph::Node n1 = graph.addNode();
598  Graph::Node n2 = graph.addNode();
599  Graph::Node n3 = graph.addNode();
600  Graph::Node n4 = graph.addNode();
601
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);
606 
607  checkGraphNodeList(adaptor, 4);
608  checkGraphArcList(adaptor, 8);
609  checkGraphEdgeList(adaptor, 4);
610  checkGraphConArcList(adaptor, 8);
611  checkGraphConEdgeList(adaptor, 4);
612
613  checkGraphOutArcList(adaptor, n1, 2);
614  checkGraphOutArcList(adaptor, n2, 2);
615  checkGraphOutArcList(adaptor, n3, 3);
616  checkGraphOutArcList(adaptor, n4, 1);
617
618  checkGraphInArcList(adaptor, n1, 2);
619  checkGraphInArcList(adaptor, n2, 2);
620  checkGraphInArcList(adaptor, n3, 3);
621  checkGraphInArcList(adaptor, n4, 1);
622
623  checkGraphIncEdgeList(adaptor, n1, 2);
624  checkGraphIncEdgeList(adaptor, n2, 2);
625  checkGraphIncEdgeList(adaptor, n3, 3);
626  checkGraphIncEdgeList(adaptor, n4, 1);
627
628
629  checkNodeIds(adaptor);
630  checkArcIds(adaptor);
631  checkEdgeIds(adaptor);
632
633  checkGraphNodeMap(adaptor);
634  checkGraphArcMap(adaptor);
635  checkGraphEdgeMap(adaptor);
636}
637
638void checkSubGraphAdaptor() {
639  checkConcept<concepts::Graph,
640    SubGraphAdaptor<concepts::Graph,
641    concepts::Graph::NodeMap<bool>,
642    concepts::Graph::EdgeMap<bool> > >();
643
644  typedef ListGraph Graph;
645  typedef Graph::NodeMap<bool> NodeFilter;
646  typedef Graph::EdgeMap<bool> EdgeFilter;
647  typedef SubGraphAdaptor<Graph, NodeFilter, EdgeFilter> Adaptor;
648
649  Graph graph;
650  NodeFilter node_filter(graph);
651  EdgeFilter edge_filter(graph);
652  Adaptor adaptor(graph, node_filter, edge_filter);
653
654  Graph::Node n1 = graph.addNode();
655  Graph::Node n2 = graph.addNode();
656  Graph::Node n3 = graph.addNode();
657  Graph::Node n4 = graph.addNode();
658
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);
663
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;
666 
667  checkGraphNodeList(adaptor, 4);
668  checkGraphArcList(adaptor, 8);
669  checkGraphEdgeList(adaptor, 4);
670  checkGraphConArcList(adaptor, 8);
671  checkGraphConEdgeList(adaptor, 4);
672
673  checkGraphOutArcList(adaptor, n1, 2);
674  checkGraphOutArcList(adaptor, n2, 2);
675  checkGraphOutArcList(adaptor, n3, 3);
676  checkGraphOutArcList(adaptor, n4, 1);
677
678  checkGraphInArcList(adaptor, n1, 2);
679  checkGraphInArcList(adaptor, n2, 2);
680  checkGraphInArcList(adaptor, n3, 3);
681  checkGraphInArcList(adaptor, n4, 1);
682
683  checkGraphIncEdgeList(adaptor, n1, 2);
684  checkGraphIncEdgeList(adaptor, n2, 2);
685  checkGraphIncEdgeList(adaptor, n3, 3);
686  checkGraphIncEdgeList(adaptor, n4, 1);
687
688  checkNodeIds(adaptor);
689  checkArcIds(adaptor);
690  checkEdgeIds(adaptor);
691
692  checkGraphNodeMap(adaptor);
693  checkGraphArcMap(adaptor);
694  checkGraphEdgeMap(adaptor);
695
696  edge_filter[e2] = false;
697
698  checkGraphNodeList(adaptor, 4);
699  checkGraphArcList(adaptor, 6);
700  checkGraphEdgeList(adaptor, 3);
701  checkGraphConArcList(adaptor, 6);
702  checkGraphConEdgeList(adaptor, 3);
703
704  checkGraphOutArcList(adaptor, n1, 1);
705  checkGraphOutArcList(adaptor, n2, 2);
706  checkGraphOutArcList(adaptor, n3, 2);
707  checkGraphOutArcList(adaptor, n4, 1);
708
709  checkGraphInArcList(adaptor, n1, 1);
710  checkGraphInArcList(adaptor, n2, 2);
711  checkGraphInArcList(adaptor, n3, 2);
712  checkGraphInArcList(adaptor, n4, 1);
713
714  checkGraphIncEdgeList(adaptor, n1, 1);
715  checkGraphIncEdgeList(adaptor, n2, 2);
716  checkGraphIncEdgeList(adaptor, n3, 2);
717  checkGraphIncEdgeList(adaptor, n4, 1);
718
719  checkNodeIds(adaptor);
720  checkArcIds(adaptor);
721  checkEdgeIds(adaptor);
722
723  checkGraphNodeMap(adaptor);
724  checkGraphArcMap(adaptor);
725  checkGraphEdgeMap(adaptor);
726
727  node_filter[n1] = false;
728
729  checkGraphNodeList(adaptor, 3);
730  checkGraphArcList(adaptor, 4);
731  checkGraphEdgeList(adaptor, 2);
732  checkGraphConArcList(adaptor, 4);
733  checkGraphConEdgeList(adaptor, 2);
734
735  checkGraphOutArcList(adaptor, n2, 1);
736  checkGraphOutArcList(adaptor, n3, 2);
737  checkGraphOutArcList(adaptor, n4, 1);
738
739  checkGraphInArcList(adaptor, n2, 1);
740  checkGraphInArcList(adaptor, n3, 2);
741  checkGraphInArcList(adaptor, n4, 1);
742
743  checkGraphIncEdgeList(adaptor, n2, 1);
744  checkGraphIncEdgeList(adaptor, n3, 2);
745  checkGraphIncEdgeList(adaptor, n4, 1);
746
747  checkNodeIds(adaptor);
748  checkArcIds(adaptor);
749  checkEdgeIds(adaptor);
750
751  checkGraphNodeMap(adaptor);
752  checkGraphArcMap(adaptor);
753  checkGraphEdgeMap(adaptor);
754
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;
757
758  checkGraphNodeList(adaptor, 0);
759  checkGraphArcList(adaptor, 0);
760  checkGraphEdgeList(adaptor, 0);
761  checkGraphConArcList(adaptor, 0);
762  checkGraphConEdgeList(adaptor, 0);
763
764  checkNodeIds(adaptor);
765  checkArcIds(adaptor);
766  checkEdgeIds(adaptor);
767
768  checkGraphNodeMap(adaptor);
769  checkGraphArcMap(adaptor);
770  checkGraphEdgeMap(adaptor);
771}
772
773void checkNodeSubGraphAdaptor() {
774  checkConcept<concepts::Graph,
775    NodeSubGraphAdaptor<concepts::Graph,
776      concepts::Graph::NodeMap<bool> > >();
777
778  typedef ListGraph Graph;
779  typedef Graph::NodeMap<bool> NodeFilter;
780  typedef NodeSubGraphAdaptor<Graph, NodeFilter> Adaptor;
781
782  Graph graph;
783  NodeFilter node_filter(graph);
784  Adaptor adaptor(graph, node_filter);
785
786  Graph::Node n1 = graph.addNode();
787  Graph::Node n2 = graph.addNode();
788  Graph::Node n3 = graph.addNode();
789  Graph::Node n4 = graph.addNode();
790
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);
795
796  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
797 
798  checkGraphNodeList(adaptor, 4);
799  checkGraphArcList(adaptor, 8);
800  checkGraphEdgeList(adaptor, 4);
801  checkGraphConArcList(adaptor, 8);
802  checkGraphConEdgeList(adaptor, 4);
803
804  checkGraphOutArcList(adaptor, n1, 2);
805  checkGraphOutArcList(adaptor, n2, 2);
806  checkGraphOutArcList(adaptor, n3, 3);
807  checkGraphOutArcList(adaptor, n4, 1);
808
809  checkGraphInArcList(adaptor, n1, 2);
810  checkGraphInArcList(adaptor, n2, 2);
811  checkGraphInArcList(adaptor, n3, 3);
812  checkGraphInArcList(adaptor, n4, 1);
813
814  checkGraphIncEdgeList(adaptor, n1, 2);
815  checkGraphIncEdgeList(adaptor, n2, 2);
816  checkGraphIncEdgeList(adaptor, n3, 3);
817  checkGraphIncEdgeList(adaptor, n4, 1);
818
819  checkNodeIds(adaptor);
820  checkArcIds(adaptor);
821  checkEdgeIds(adaptor);
822
823  checkGraphNodeMap(adaptor);
824  checkGraphArcMap(adaptor);
825  checkGraphEdgeMap(adaptor);
826
827  node_filter[n1] = false;
828
829  checkGraphNodeList(adaptor, 3);
830  checkGraphArcList(adaptor, 4);
831  checkGraphEdgeList(adaptor, 2);
832  checkGraphConArcList(adaptor, 4);
833  checkGraphConEdgeList(adaptor, 2);
834
835  checkGraphOutArcList(adaptor, n2, 1);
836  checkGraphOutArcList(adaptor, n3, 2);
837  checkGraphOutArcList(adaptor, n4, 1);
838
839  checkGraphInArcList(adaptor, n2, 1);
840  checkGraphInArcList(adaptor, n3, 2);
841  checkGraphInArcList(adaptor, n4, 1);
842
843  checkGraphIncEdgeList(adaptor, n2, 1);
844  checkGraphIncEdgeList(adaptor, n3, 2);
845  checkGraphIncEdgeList(adaptor, n4, 1);
846
847  checkNodeIds(adaptor);
848  checkArcIds(adaptor);
849  checkEdgeIds(adaptor);
850
851  checkGraphNodeMap(adaptor);
852  checkGraphArcMap(adaptor);
853  checkGraphEdgeMap(adaptor);
854
855  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
856
857  checkGraphNodeList(adaptor, 0);
858  checkGraphArcList(adaptor, 0);
859  checkGraphEdgeList(adaptor, 0);
860  checkGraphConArcList(adaptor, 0);
861  checkGraphConEdgeList(adaptor, 0);
862
863  checkNodeIds(adaptor);
864  checkArcIds(adaptor);
865  checkEdgeIds(adaptor);
866
867  checkGraphNodeMap(adaptor);
868  checkGraphArcMap(adaptor);
869  checkGraphEdgeMap(adaptor);
870}
871
872void checkEdgeSubGraphAdaptor() {
873  checkConcept<concepts::Graph,
874    EdgeSubGraphAdaptor<concepts::Graph,
875    concepts::Graph::EdgeMap<bool> > >();
876
877  typedef ListGraph Graph;
878  typedef Graph::EdgeMap<bool> EdgeFilter;
879  typedef EdgeSubGraphAdaptor<Graph, EdgeFilter> Adaptor;
880
881  Graph graph;
882  EdgeFilter edge_filter(graph);
883  Adaptor adaptor(graph, edge_filter);
884
885  Graph::Node n1 = graph.addNode();
886  Graph::Node n2 = graph.addNode();
887  Graph::Node n3 = graph.addNode();
888  Graph::Node n4 = graph.addNode();
889
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);
894
895  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
896 
897  checkGraphNodeList(adaptor, 4);
898  checkGraphArcList(adaptor, 8);
899  checkGraphEdgeList(adaptor, 4);
900  checkGraphConArcList(adaptor, 8);
901  checkGraphConEdgeList(adaptor, 4);
902
903  checkGraphOutArcList(adaptor, n1, 2);
904  checkGraphOutArcList(adaptor, n2, 2);
905  checkGraphOutArcList(adaptor, n3, 3);
906  checkGraphOutArcList(adaptor, n4, 1);
907
908  checkGraphInArcList(adaptor, n1, 2);
909  checkGraphInArcList(adaptor, n2, 2);
910  checkGraphInArcList(adaptor, n3, 3);
911  checkGraphInArcList(adaptor, n4, 1);
912
913  checkGraphIncEdgeList(adaptor, n1, 2);
914  checkGraphIncEdgeList(adaptor, n2, 2);
915  checkGraphIncEdgeList(adaptor, n3, 3);
916  checkGraphIncEdgeList(adaptor, n4, 1);
917
918  checkNodeIds(adaptor);
919  checkArcIds(adaptor);
920  checkEdgeIds(adaptor);
921
922  checkGraphNodeMap(adaptor);
923  checkGraphArcMap(adaptor);
924  checkGraphEdgeMap(adaptor);
925
926  edge_filter[e2] = false;
927
928  checkGraphNodeList(adaptor, 4);
929  checkGraphArcList(adaptor, 6);
930  checkGraphEdgeList(adaptor, 3);
931  checkGraphConArcList(adaptor, 6);
932  checkGraphConEdgeList(adaptor, 3);
933
934  checkGraphOutArcList(adaptor, n1, 1);
935  checkGraphOutArcList(adaptor, n2, 2);
936  checkGraphOutArcList(adaptor, n3, 2);
937  checkGraphOutArcList(adaptor, n4, 1);
938
939  checkGraphInArcList(adaptor, n1, 1);
940  checkGraphInArcList(adaptor, n2, 2);
941  checkGraphInArcList(adaptor, n3, 2);
942  checkGraphInArcList(adaptor, n4, 1);
943
944  checkGraphIncEdgeList(adaptor, n1, 1);
945  checkGraphIncEdgeList(adaptor, n2, 2);
946  checkGraphIncEdgeList(adaptor, n3, 2);
947  checkGraphIncEdgeList(adaptor, n4, 1);
948
949  checkNodeIds(adaptor);
950  checkArcIds(adaptor);
951  checkEdgeIds(adaptor);
952
953  checkGraphNodeMap(adaptor);
954  checkGraphArcMap(adaptor);
955  checkGraphEdgeMap(adaptor);
956
957  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
958
959  checkGraphNodeList(adaptor, 4);
960  checkGraphArcList(adaptor, 0);
961  checkGraphEdgeList(adaptor, 0);
962  checkGraphConArcList(adaptor, 0);
963  checkGraphConEdgeList(adaptor, 0);
964
965  checkNodeIds(adaptor);
966  checkArcIds(adaptor);
967  checkEdgeIds(adaptor);
968
969  checkGraphNodeMap(adaptor);
970  checkGraphArcMap(adaptor);
971  checkGraphEdgeMap(adaptor);
972}
973
974void checkDirGraphAdaptor() {
975  checkConcept<concepts::Digraph,
976    DirGraphAdaptor<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
977
978  typedef ListGraph Graph;
979  typedef ListGraph::EdgeMap<bool> DirMap;
980  typedef DirGraphAdaptor<Graph> Adaptor;
981
982  Graph graph;
983  DirMap dir(graph, true);
984  Adaptor adaptor(graph, dir);
985
986  Graph::Node n1 = graph.addNode();
987  Graph::Node n2 = graph.addNode();
988  Graph::Node n3 = graph.addNode();
989
990  Graph::Edge e1 = graph.addEdge(n1, n2);
991  Graph::Edge e2 = graph.addEdge(n1, n3);
992  Graph::Edge e3 = graph.addEdge(n2, n3);
993 
994  checkGraphNodeList(adaptor, 3);
995  checkGraphArcList(adaptor, 3);
996  checkGraphConArcList(adaptor, 3);
997 
998  {
999    dir[e1] = true;
1000    Adaptor::Node u = adaptor.source(e1);
1001    Adaptor::Node v = adaptor.target(e1);
1002   
1003    dir[e1] = false;
1004    check (u == adaptor.target(e1), "Wrong dir");
1005    check (v == adaptor.source(e1), "Wrong dir");
1006
1007    check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");
1008    dir[e1] = n1 == u;
1009  }
1010
1011  {
1012    dir[e2] = true;
1013    Adaptor::Node u = adaptor.source(e2);
1014    Adaptor::Node v = adaptor.target(e2);
1015   
1016    dir[e2] = false;
1017    check (u == adaptor.target(e2), "Wrong dir");
1018    check (v == adaptor.source(e2), "Wrong dir");
1019
1020    check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");
1021    dir[e2] = n3 == u;
1022  }
1023
1024  {
1025    dir[e3] = true;
1026    Adaptor::Node u = adaptor.source(e3);
1027    Adaptor::Node v = adaptor.target(e3);
1028   
1029    dir[e3] = false;
1030    check (u == adaptor.target(e3), "Wrong dir");
1031    check (v == adaptor.source(e3), "Wrong dir");
1032
1033    check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
1034    dir[e3] = n2 == u;
1035  }
1036
1037  checkGraphOutArcList(adaptor, n1, 1);
1038  checkGraphOutArcList(adaptor, n2, 1);
1039  checkGraphOutArcList(adaptor, n3, 1);
1040
1041  checkGraphInArcList(adaptor, n1, 1);
1042  checkGraphInArcList(adaptor, n2, 1);
1043  checkGraphInArcList(adaptor, n3, 1);
1044
1045  checkNodeIds(adaptor);
1046  checkArcIds(adaptor);
1047
1048  checkGraphNodeMap(adaptor);
1049  checkGraphArcMap(adaptor);
1050
1051}
1052
1053
1054int main(int, const char **) {
1055
1056  checkDigraphAdaptor();
1057  checkRevDigraphAdaptor();
1058  checkSubDigraphAdaptor();
1059  checkNodeSubDigraphAdaptor();
1060  checkArcSubDigraphAdaptor();
1061  checkUndirDigraphAdaptor();
1062  checkResDigraphAdaptor();
1063  checkSplitDigraphAdaptor();
1064
1065  checkGraphAdaptor();
1066  checkSubGraphAdaptor();
1067  checkNodeSubGraphAdaptor();
1068  checkEdgeSubGraphAdaptor();
1069  checkDirGraphAdaptor();
1070
1071  return 0;
1072}
Note: See TracBrowser for help on using the repository browser.