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 @ 424:346991bf7ddd

Last change on this file since 424:346991bf7ddd was 416:76287c8caa26, checked in by Balazs Dezso <deba@…>, 16 years ago

Reorganication of graph adaptors and doc improvements (#67)

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