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-main/test/graph_adaptor_test.cc @ 456:aff6888e71c9

Last change on this file since 456:aff6888e71c9 was 440:88ed40ad0d4f, checked in by Alpar Juttner <alpar@…>, 16 years ago

Happy New Year again

  • update the copyright headers + run the source unifier
File size: 25.8 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2009
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/adaptors.h>
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
39void checkReverseDigraph() {
40  checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
41
42  typedef ListDigraph Digraph;
43  typedef ReverseDigraph<Digraph> Adaptor;
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);
55
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
80void checkSubDigraph() {
81  checkConcept<concepts::Digraph,
82    SubDigraph<concepts::Digraph,
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;
89  typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
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
125  arc_filter[a2] = false;
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
145  node_filter[n1] = false;
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
177void checkFilterNodes1() {
178  checkConcept<concepts::Digraph,
179    FilterNodes<concepts::Digraph,
180      concepts::Digraph::NodeMap<bool> > >();
181
182  typedef ListDigraph Digraph;
183  typedef Digraph::NodeMap<bool> NodeFilter;
184  typedef FilterNodes<Digraph, NodeFilter> Adaptor;
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
218  node_filter[n1] = false;
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
249void checkFilterArcs() {
250  checkConcept<concepts::Digraph,
251    FilterArcs<concepts::Digraph,
252    concepts::Digraph::ArcMap<bool> > >();
253
254  typedef ListDigraph Digraph;
255  typedef Digraph::ArcMap<bool> ArcFilter;
256  typedef FilterArcs<Digraph, ArcFilter> Adaptor;
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
290  arc_filter[a2] = false;
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
323void checkUndirector() {
324  checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
325
326  typedef ListDigraph Digraph;
327  typedef Undirector<Digraph> Adaptor;
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);
339
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
373void checkResidual() {
374  checkConcept<concepts::Digraph,
375    Residual<concepts::Digraph,
376    concepts::Digraph::ArcMap<int>,
377    concepts::Digraph::ArcMap<int> > >();
378
379  typedef ListDigraph Digraph;
380  typedef Digraph::ArcMap<int> IntArcMap;
381  typedef Residual<Digraph, IntArcMap> Adaptor;
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  }
409
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  }
427
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  }
451
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) {
472
473    Bfs<Adaptor> bfs(adaptor);
474    bfs.run(n1, n4);
475
476    if (!bfs.reached(n4)) break;
477
478    Path<Adaptor> p = bfs.path(n4);
479
480    int min = std::numeric_limits<int>::max();
481    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
482      if (adaptor.residualCapacity(a) < min)
483        min = adaptor.residualCapacity(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 checkSplitNodes() {
497  checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
498
499  typedef ListDigraph Digraph;
500  typedef SplitNodes<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 checkSubGraph() {
553  checkConcept<concepts::Graph,
554    SubGraph<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 SubGraph<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 checkFilterNodes2() {
688  checkConcept<concepts::Graph,
689    FilterNodes<concepts::Graph,
690      concepts::Graph::NodeMap<bool> > >();
691
692  typedef ListGraph Graph;
693  typedef Graph::NodeMap<bool> NodeFilter;
694  typedef FilterNodes<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 checkFilterEdges() {
787  checkConcept<concepts::Graph,
788    FilterEdges<concepts::Graph,
789    concepts::Graph::EdgeMap<bool> > >();
790
791  typedef ListGraph Graph;
792  typedef Graph::EdgeMap<bool> EdgeFilter;
793  typedef FilterEdges<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 checkOrienter() {
889  checkConcept<concepts::Digraph,
890    Orienter<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
891
892  typedef ListGraph Graph;
893  typedef ListGraph::EdgeMap<bool> DirMap;
894  typedef Orienter<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  checkReverseDigraph();
971  checkSubDigraph();
972  checkFilterNodes1();
973  checkFilterArcs();
974  checkUndirector();
975  checkResidual();
976  checkSplitNodes();
977
978  checkSubGraph();
979  checkFilterNodes2();
980  checkFilterEdges();
981  checkOrienter();
982
983  return 0;
984}
Note: See TracBrowser for help on using the repository browser.