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/adaptors_test.cc @ 1089:552e3d1242c6

Last change on this file since 1089:552e3d1242c6 was 1083:3e711ee55d31, checked in by Alpar Juttner <alpar@…>, 11 years ago

Add explicit namespace to ignore_unused_variable_warning() usages (#294)
File size: 43.0 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 <limits>
21
22#include <lemon/list_graph.h>
23#include <lemon/grid_graph.h>
24#include <lemon/bfs.h>
25#include <lemon/path.h>
26
27#include <lemon/concepts/digraph.h>
28#include <lemon/concepts/graph.h>
29#include <lemon/concepts/graph_components.h>
30#include <lemon/concepts/maps.h>
31#include <lemon/concept_check.h>
32
33#include <lemon/adaptors.h>
34
35#include "test/test_tools.h"
36#include "test/graph_test.h"
37
38using namespace lemon;
39
40void checkReverseDigraph() {
41  // Check concepts
42  checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
43  checkConcept<concepts::Digraph, ReverseDigraph<ListDigraph> >();
44  checkConcept<concepts::AlterableDigraphComponent<>,
45               ReverseDigraph<ListDigraph> >();
46  checkConcept<concepts::ExtendableDigraphComponent<>,
47               ReverseDigraph<ListDigraph> >();
48  checkConcept<concepts::ErasableDigraphComponent<>,
49               ReverseDigraph<ListDigraph> >();
50  checkConcept<concepts::ClearableDigraphComponent<>,
51               ReverseDigraph<ListDigraph> >();
52
53  // Create a digraph and an adaptor
54  typedef ListDigraph Digraph;
55  typedef ReverseDigraph<Digraph> Adaptor;
56
57  Digraph digraph;
58  Adaptor adaptor(digraph);
59
60  // Add nodes and arcs to the original digraph
61  Digraph::Node n1 = digraph.addNode();
62  Digraph::Node n2 = digraph.addNode();
63  Digraph::Node n3 = digraph.addNode();
64
65  Digraph::Arc a1 = digraph.addArc(n1, n2);
66  Digraph::Arc a2 = digraph.addArc(n1, n3);
67  Digraph::Arc a3 = digraph.addArc(n2, n3);
68  ::lemon::ignore_unused_variable_warning(a3);
69
70  // Check the adaptor
71  checkGraphNodeList(adaptor, 3);
72  checkGraphArcList(adaptor, 3);
73  checkGraphConArcList(adaptor, 3);
74
75  checkGraphOutArcList(adaptor, n1, 0);
76  checkGraphOutArcList(adaptor, n2, 1);
77  checkGraphOutArcList(adaptor, n3, 2);
78
79  checkGraphInArcList(adaptor, n1, 2);
80  checkGraphInArcList(adaptor, n2, 1);
81  checkGraphInArcList(adaptor, n3, 0);
82
83  checkNodeIds(adaptor);
84  checkArcIds(adaptor);
85
86  checkGraphNodeMap(adaptor);
87  checkGraphArcMap(adaptor);
88
89  // Check the orientation of the arcs
90  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
91    check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
92    check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
93  }
94
95  // Add and erase nodes and arcs in the digraph through the adaptor
96  Adaptor::Node n4 = adaptor.addNode();
97
98  Adaptor::Arc a4 = adaptor.addArc(n4, n3);
99  Adaptor::Arc a5 = adaptor.addArc(n2, n4);
100  Adaptor::Arc a6 = adaptor.addArc(n2, n4);
101  Adaptor::Arc a7 = adaptor.addArc(n1, n4);
102  Adaptor::Arc a8 = adaptor.addArc(n1, n2);
103  ::lemon::ignore_unused_variable_warning(a6,a7,a8);
104
105  adaptor.erase(a1);
106  adaptor.erase(n3);
107
108  // Check the adaptor
109  checkGraphNodeList(adaptor, 3);
110  checkGraphArcList(adaptor, 4);
111  checkGraphConArcList(adaptor, 4);
112
113  checkGraphOutArcList(adaptor, n1, 2);
114  checkGraphOutArcList(adaptor, n2, 2);
115  checkGraphOutArcList(adaptor, n4, 0);
116
117  checkGraphInArcList(adaptor, n1, 0);
118  checkGraphInArcList(adaptor, n2, 1);
119  checkGraphInArcList(adaptor, n4, 3);
120
121  checkNodeIds(adaptor);
122  checkArcIds(adaptor);
123
124  checkGraphNodeMap(adaptor);
125  checkGraphArcMap(adaptor);
126
127  // Check the digraph
128  checkGraphNodeList(digraph, 3);
129  checkGraphArcList(digraph, 4);
130  checkGraphConArcList(digraph, 4);
131
132  checkGraphOutArcList(digraph, n1, 0);
133  checkGraphOutArcList(digraph, n2, 1);
134  checkGraphOutArcList(digraph, n4, 3);
135
136  checkGraphInArcList(digraph, n1, 2);
137  checkGraphInArcList(digraph, n2, 2);
138  checkGraphInArcList(digraph, n4, 0);
139
140  checkNodeIds(digraph);
141  checkArcIds(digraph);
142
143  checkGraphNodeMap(digraph);
144  checkGraphArcMap(digraph);
145
146  // Check the conversion of nodes and arcs
147  Digraph::Node nd = n4;
148  nd = n4;
149  Adaptor::Node na = n1;
150  na = n2;
151  Digraph::Arc ad = a4;
152  ad = a5;
153  Adaptor::Arc aa = a1;
154  aa = a2;
155}
156
157void checkSubDigraph() {
158  // Check concepts
159  checkConcept<concepts::Digraph, SubDigraph<concepts::Digraph> >();
160  checkConcept<concepts::Digraph, SubDigraph<ListDigraph> >();
161  checkConcept<concepts::AlterableDigraphComponent<>,
162               SubDigraph<ListDigraph> >();
163  checkConcept<concepts::ExtendableDigraphComponent<>,
164               SubDigraph<ListDigraph> >();
165  checkConcept<concepts::ErasableDigraphComponent<>,
166               SubDigraph<ListDigraph> >();
167  checkConcept<concepts::ClearableDigraphComponent<>,
168               SubDigraph<ListDigraph> >();
169
170  // Create a digraph and an adaptor
171  typedef ListDigraph Digraph;
172  typedef Digraph::NodeMap<bool> NodeFilter;
173  typedef Digraph::ArcMap<bool> ArcFilter;
174  typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
175
176  Digraph digraph;
177  NodeFilter node_filter(digraph);
178  ArcFilter arc_filter(digraph);
179  Adaptor adaptor(digraph, node_filter, arc_filter);
180
181  // Add nodes and arcs to the original digraph and the adaptor
182  Digraph::Node n1 = digraph.addNode();
183  Digraph::Node n2 = digraph.addNode();
184  Adaptor::Node n3 = adaptor.addNode();
185
186  node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
187
188  Digraph::Arc a1 = digraph.addArc(n1, n2);
189  Digraph::Arc a2 = digraph.addArc(n1, n3);
190  Adaptor::Arc a3 = adaptor.addArc(n2, n3);
191
192  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
193
194  checkGraphNodeList(adaptor, 3);
195  checkGraphArcList(adaptor, 3);
196  checkGraphConArcList(adaptor, 3);
197
198  checkGraphOutArcList(adaptor, n1, 2);
199  checkGraphOutArcList(adaptor, n2, 1);
200  checkGraphOutArcList(adaptor, n3, 0);
201
202  checkGraphInArcList(adaptor, n1, 0);
203  checkGraphInArcList(adaptor, n2, 1);
204  checkGraphInArcList(adaptor, n3, 2);
205
206  checkNodeIds(adaptor);
207  checkArcIds(adaptor);
208
209  checkGraphNodeMap(adaptor);
210  checkGraphArcMap(adaptor);
211
212  // Hide an arc
213  adaptor.status(a2, false);
214  adaptor.disable(a3);
215  if (!adaptor.status(a3)) adaptor.enable(a3);
216
217  checkGraphNodeList(adaptor, 3);
218  checkGraphArcList(adaptor, 2);
219  checkGraphConArcList(adaptor, 2);
220
221  checkGraphOutArcList(adaptor, n1, 1);
222  checkGraphOutArcList(adaptor, n2, 1);
223  checkGraphOutArcList(adaptor, n3, 0);
224
225  checkGraphInArcList(adaptor, n1, 0);
226  checkGraphInArcList(adaptor, n2, 1);
227  checkGraphInArcList(adaptor, n3, 1);
228
229  checkNodeIds(adaptor);
230  checkArcIds(adaptor);
231
232  checkGraphNodeMap(adaptor);
233  checkGraphArcMap(adaptor);
234
235  // Hide a node
236  adaptor.status(n1, false);
237  adaptor.disable(n3);
238  if (!adaptor.status(n3)) adaptor.enable(n3);
239
240  checkGraphNodeList(adaptor, 2);
241  checkGraphArcList(adaptor, 1);
242  checkGraphConArcList(adaptor, 1);
243
244  checkGraphOutArcList(adaptor, n2, 1);
245  checkGraphOutArcList(adaptor, n3, 0);
246
247  checkGraphInArcList(adaptor, n2, 0);
248  checkGraphInArcList(adaptor, n3, 1);
249
250  checkNodeIds(adaptor);
251  checkArcIds(adaptor);
252
253  checkGraphNodeMap(adaptor);
254  checkGraphArcMap(adaptor);
255
256  // Hide all nodes and arcs
257  node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
258  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
259
260  checkGraphNodeList(adaptor, 0);
261  checkGraphArcList(adaptor, 0);
262  checkGraphConArcList(adaptor, 0);
263
264  checkNodeIds(adaptor);
265  checkArcIds(adaptor);
266
267  checkGraphNodeMap(adaptor);
268  checkGraphArcMap(adaptor);
269
270  // Check the conversion of nodes and arcs
271  Digraph::Node nd = n3;
272  nd = n3;
273  Adaptor::Node na = n1;
274  na = n2;
275  Digraph::Arc ad = a3;
276  ad = a3;
277  Adaptor::Arc aa = a1;
278  aa = a2;
279}
280
281void checkFilterNodes1() {
282  // Check concepts
283  checkConcept<concepts::Digraph, FilterNodes<concepts::Digraph> >();
284  checkConcept<concepts::Digraph, FilterNodes<ListDigraph> >();
285  checkConcept<concepts::AlterableDigraphComponent<>,
286               FilterNodes<ListDigraph> >();
287  checkConcept<concepts::ExtendableDigraphComponent<>,
288               FilterNodes<ListDigraph> >();
289  checkConcept<concepts::ErasableDigraphComponent<>,
290               FilterNodes<ListDigraph> >();
291  checkConcept<concepts::ClearableDigraphComponent<>,
292               FilterNodes<ListDigraph> >();
293
294  // Create a digraph and an adaptor
295  typedef ListDigraph Digraph;
296  typedef Digraph::NodeMap<bool> NodeFilter;
297  typedef FilterNodes<Digraph, NodeFilter> Adaptor;
298
299  Digraph digraph;
300  NodeFilter node_filter(digraph);
301  Adaptor adaptor(digraph, node_filter);
302
303  // Add nodes and arcs to the original digraph and the adaptor
304  Digraph::Node n1 = digraph.addNode();
305  Digraph::Node n2 = digraph.addNode();
306  Adaptor::Node n3 = adaptor.addNode();
307
308  node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
309
310  Digraph::Arc a1 = digraph.addArc(n1, n2);
311  Digraph::Arc a2 = digraph.addArc(n1, n3);
312  Adaptor::Arc a3 = adaptor.addArc(n2, n3);
313
314  checkGraphNodeList(adaptor, 3);
315  checkGraphArcList(adaptor, 3);
316  checkGraphConArcList(adaptor, 3);
317
318  checkGraphOutArcList(adaptor, n1, 2);
319  checkGraphOutArcList(adaptor, n2, 1);
320  checkGraphOutArcList(adaptor, n3, 0);
321
322  checkGraphInArcList(adaptor, n1, 0);
323  checkGraphInArcList(adaptor, n2, 1);
324  checkGraphInArcList(adaptor, n3, 2);
325
326  checkNodeIds(adaptor);
327  checkArcIds(adaptor);
328
329  checkGraphNodeMap(adaptor);
330  checkGraphArcMap(adaptor);
331
332  // Hide a node
333  adaptor.status(n1, false);
334  adaptor.disable(n3);
335  if (!adaptor.status(n3)) adaptor.enable(n3);
336
337  checkGraphNodeList(adaptor, 2);
338  checkGraphArcList(adaptor, 1);
339  checkGraphConArcList(adaptor, 1);
340
341  checkGraphOutArcList(adaptor, n2, 1);
342  checkGraphOutArcList(adaptor, n3, 0);
343
344  checkGraphInArcList(adaptor, n2, 0);
345  checkGraphInArcList(adaptor, n3, 1);
346
347  checkNodeIds(adaptor);
348  checkArcIds(adaptor);
349
350  checkGraphNodeMap(adaptor);
351  checkGraphArcMap(adaptor);
352
353  // Hide all nodes
354  node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
355
356  checkGraphNodeList(adaptor, 0);
357  checkGraphArcList(adaptor, 0);
358  checkGraphConArcList(adaptor, 0);
359
360  checkNodeIds(adaptor);
361  checkArcIds(adaptor);
362
363  checkGraphNodeMap(adaptor);
364  checkGraphArcMap(adaptor);
365
366  // Check the conversion of nodes and arcs
367  Digraph::Node nd = n3;
368  nd = n3;
369  Adaptor::Node na = n1;
370  na = n2;
371  Digraph::Arc ad = a3;
372  ad = a3;
373  Adaptor::Arc aa = a1;
374  aa = a2;
375}
376
377void checkFilterArcs() {
378  // Check concepts
379  checkConcept<concepts::Digraph, FilterArcs<concepts::Digraph> >();
380  checkConcept<concepts::Digraph, FilterArcs<ListDigraph> >();
381  checkConcept<concepts::AlterableDigraphComponent<>,
382               FilterArcs<ListDigraph> >();
383  checkConcept<concepts::ExtendableDigraphComponent<>,
384               FilterArcs<ListDigraph> >();
385  checkConcept<concepts::ErasableDigraphComponent<>,
386               FilterArcs<ListDigraph> >();
387  checkConcept<concepts::ClearableDigraphComponent<>,
388               FilterArcs<ListDigraph> >();
389
390  // Create a digraph and an adaptor
391  typedef ListDigraph Digraph;
392  typedef Digraph::ArcMap<bool> ArcFilter;
393  typedef FilterArcs<Digraph, ArcFilter> Adaptor;
394
395  Digraph digraph;
396  ArcFilter arc_filter(digraph);
397  Adaptor adaptor(digraph, arc_filter);
398
399  // Add nodes and arcs to the original digraph and the adaptor
400  Digraph::Node n1 = digraph.addNode();
401  Digraph::Node n2 = digraph.addNode();
402  Adaptor::Node n3 = adaptor.addNode();
403
404  Digraph::Arc a1 = digraph.addArc(n1, n2);
405  Digraph::Arc a2 = digraph.addArc(n1, n3);
406  Adaptor::Arc a3 = adaptor.addArc(n2, n3);
407
408  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
409
410  checkGraphNodeList(adaptor, 3);
411  checkGraphArcList(adaptor, 3);
412  checkGraphConArcList(adaptor, 3);
413
414  checkGraphOutArcList(adaptor, n1, 2);
415  checkGraphOutArcList(adaptor, n2, 1);
416  checkGraphOutArcList(adaptor, n3, 0);
417
418  checkGraphInArcList(adaptor, n1, 0);
419  checkGraphInArcList(adaptor, n2, 1);
420  checkGraphInArcList(adaptor, n3, 2);
421
422  checkNodeIds(adaptor);
423  checkArcIds(adaptor);
424
425  checkGraphNodeMap(adaptor);
426  checkGraphArcMap(adaptor);
427
428  // Hide an arc
429  adaptor.status(a2, false);
430  adaptor.disable(a3);
431  if (!adaptor.status(a3)) adaptor.enable(a3);
432
433  checkGraphNodeList(adaptor, 3);
434  checkGraphArcList(adaptor, 2);
435  checkGraphConArcList(adaptor, 2);
436
437  checkGraphOutArcList(adaptor, n1, 1);
438  checkGraphOutArcList(adaptor, n2, 1);
439  checkGraphOutArcList(adaptor, n3, 0);
440
441  checkGraphInArcList(adaptor, n1, 0);
442  checkGraphInArcList(adaptor, n2, 1);
443  checkGraphInArcList(adaptor, n3, 1);
444
445  checkNodeIds(adaptor);
446  checkArcIds(adaptor);
447
448  checkGraphNodeMap(adaptor);
449  checkGraphArcMap(adaptor);
450
451  // Hide all arcs
452  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
453
454  checkGraphNodeList(adaptor, 3);
455  checkGraphArcList(adaptor, 0);
456  checkGraphConArcList(adaptor, 0);
457
458  checkNodeIds(adaptor);
459  checkArcIds(adaptor);
460
461  checkGraphNodeMap(adaptor);
462  checkGraphArcMap(adaptor);
463
464  // Check the conversion of nodes and arcs
465  Digraph::Node nd = n3;
466  nd = n3;
467  Adaptor::Node na = n1;
468  na = n2;
469  Digraph::Arc ad = a3;
470  ad = a3;
471  Adaptor::Arc aa = a1;
472  aa = a2;
473}
474
475void checkUndirector() {
476  // Check concepts
477  checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
478  checkConcept<concepts::Graph, Undirector<ListDigraph> >();
479  checkConcept<concepts::AlterableGraphComponent<>,
480               Undirector<ListDigraph> >();
481  checkConcept<concepts::ExtendableGraphComponent<>,
482               Undirector<ListDigraph> >();
483  checkConcept<concepts::ErasableGraphComponent<>,
484               Undirector<ListDigraph> >();
485  checkConcept<concepts::ClearableGraphComponent<>,
486               Undirector<ListDigraph> >();
487
488
489  // Create a digraph and an adaptor
490  typedef ListDigraph Digraph;
491  typedef Undirector<Digraph> Adaptor;
492
493  Digraph digraph;
494  Adaptor adaptor(digraph);
495
496  // Add nodes and arcs/edges to the original digraph and the adaptor
497  Digraph::Node n1 = digraph.addNode();
498  Digraph::Node n2 = digraph.addNode();
499  Adaptor::Node n3 = adaptor.addNode();
500
501  Digraph::Arc a1 = digraph.addArc(n1, n2);
502  Digraph::Arc a2 = digraph.addArc(n1, n3);
503  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
504
505  // Check the original digraph
506  checkGraphNodeList(digraph, 3);
507  checkGraphArcList(digraph, 3);
508  checkGraphConArcList(digraph, 3);
509
510  checkGraphOutArcList(digraph, n1, 2);
511  checkGraphOutArcList(digraph, n2, 1);
512  checkGraphOutArcList(digraph, n3, 0);
513
514  checkGraphInArcList(digraph, n1, 0);
515  checkGraphInArcList(digraph, n2, 1);
516  checkGraphInArcList(digraph, n3, 2);
517
518  checkNodeIds(digraph);
519  checkArcIds(digraph);
520
521  checkGraphNodeMap(digraph);
522  checkGraphArcMap(digraph);
523
524  // Check the adaptor
525  checkGraphNodeList(adaptor, 3);
526  checkGraphArcList(adaptor, 6);
527  checkGraphEdgeList(adaptor, 3);
528  checkGraphConArcList(adaptor, 6);
529  checkGraphConEdgeList(adaptor, 3);
530
531  checkGraphIncEdgeArcLists(adaptor, n1, 2);
532  checkGraphIncEdgeArcLists(adaptor, n2, 2);
533  checkGraphIncEdgeArcLists(adaptor, n3, 2);
534
535  checkNodeIds(adaptor);
536  checkArcIds(adaptor);
537  checkEdgeIds(adaptor);
538
539  checkGraphNodeMap(adaptor);
540  checkGraphArcMap(adaptor);
541  checkGraphEdgeMap(adaptor);
542
543  // Check the edges of the adaptor
544  for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {
545    check(adaptor.u(e) == digraph.source(e), "Wrong undir");
546    check(adaptor.v(e) == digraph.target(e), "Wrong undir");
547  }
548
549  // Check CombinedArcMap
550  typedef Adaptor::CombinedArcMap
551    <Digraph::ArcMap<int>, Digraph::ArcMap<int> > IntCombinedMap;
552  typedef Adaptor::CombinedArcMap
553    <Digraph::ArcMap<bool>, Digraph::ArcMap<bool> > BoolCombinedMap;
554  checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,
555    IntCombinedMap>();
556  checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,
557    BoolCombinedMap>();
558
559  Digraph::ArcMap<int> fw_map(digraph), bk_map(digraph);
560  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
561    fw_map[a] = digraph.id(a);
562    bk_map[a] = -digraph.id(a);
563  }
564
565  Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::ArcMap<int> >
566    comb_map(fw_map, bk_map);
567  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
568    if (adaptor.source(a) == digraph.source(a)) {
569      check(comb_map[a] == fw_map[a], "Wrong combined map");
570    } else {
571      check(comb_map[a] == bk_map[a], "Wrong combined map");
572    }
573  }
574
575  // Check the conversion of nodes and arcs/edges
576  Digraph::Node nd = n3;
577  nd = n3;
578  Adaptor::Node na = n1;
579  na = n2;
580  Digraph::Arc ad = e3;
581  ad = e3;
582  Adaptor::Edge ea = a1;
583  ea = a2;
584}
585
586void checkResidualDigraph() {
587  // Check concepts
588  checkConcept<concepts::Digraph, ResidualDigraph<concepts::Digraph> >();
589  checkConcept<concepts::Digraph, ResidualDigraph<ListDigraph> >();
590
591  // Create a digraph and an adaptor
592  typedef ListDigraph Digraph;
593  typedef Digraph::ArcMap<int> IntArcMap;
594  typedef ResidualDigraph<Digraph, IntArcMap> Adaptor;
595
596  Digraph digraph;
597  IntArcMap capacity(digraph), flow(digraph);
598  Adaptor adaptor(digraph, capacity, flow);
599
600  Digraph::Node n1 = digraph.addNode();
601  Digraph::Node n2 = digraph.addNode();
602  Digraph::Node n3 = digraph.addNode();
603  Digraph::Node n4 = digraph.addNode();
604
605  Digraph::Arc a1 = digraph.addArc(n1, n2);
606  Digraph::Arc a2 = digraph.addArc(n1, n3);
607  Digraph::Arc a3 = digraph.addArc(n1, n4);
608  Digraph::Arc a4 = digraph.addArc(n2, n3);
609  Digraph::Arc a5 = digraph.addArc(n2, n4);
610  Digraph::Arc a6 = digraph.addArc(n3, n4);
611
612  capacity[a1] = 8;
613  capacity[a2] = 6;
614  capacity[a3] = 4;
615  capacity[a4] = 4;
616  capacity[a5] = 6;
617  capacity[a6] = 10;
618
619  // Check the adaptor with various flow values
620  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
621    flow[a] = 0;
622  }
623
624  checkGraphNodeList(adaptor, 4);
625  checkGraphArcList(adaptor, 6);
626  checkGraphConArcList(adaptor, 6);
627
628  checkGraphOutArcList(adaptor, n1, 3);
629  checkGraphOutArcList(adaptor, n2, 2);
630  checkGraphOutArcList(adaptor, n3, 1);
631  checkGraphOutArcList(adaptor, n4, 0);
632
633  checkGraphInArcList(adaptor, n1, 0);
634  checkGraphInArcList(adaptor, n2, 1);
635  checkGraphInArcList(adaptor, n3, 2);
636  checkGraphInArcList(adaptor, n4, 3);
637
638  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
639    flow[a] = capacity[a] / 2;
640  }
641
642  checkGraphNodeList(adaptor, 4);
643  checkGraphArcList(adaptor, 12);
644  checkGraphConArcList(adaptor, 12);
645
646  checkGraphOutArcList(adaptor, n1, 3);
647  checkGraphOutArcList(adaptor, n2, 3);
648  checkGraphOutArcList(adaptor, n3, 3);
649  checkGraphOutArcList(adaptor, n4, 3);
650
651  checkGraphInArcList(adaptor, n1, 3);
652  checkGraphInArcList(adaptor, n2, 3);
653  checkGraphInArcList(adaptor, n3, 3);
654  checkGraphInArcList(adaptor, n4, 3);
655
656  checkNodeIds(adaptor);
657  checkArcIds(adaptor);
658
659  checkGraphNodeMap(adaptor);
660  checkGraphArcMap(adaptor);
661
662  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
663    flow[a] = capacity[a];
664  }
665
666  checkGraphNodeList(adaptor, 4);
667  checkGraphArcList(adaptor, 6);
668  checkGraphConArcList(adaptor, 6);
669
670  checkGraphOutArcList(adaptor, n1, 0);
671  checkGraphOutArcList(adaptor, n2, 1);
672  checkGraphOutArcList(adaptor, n3, 2);
673  checkGraphOutArcList(adaptor, n4, 3);
674
675  checkGraphInArcList(adaptor, n1, 3);
676  checkGraphInArcList(adaptor, n2, 2);
677  checkGraphInArcList(adaptor, n3, 1);
678  checkGraphInArcList(adaptor, n4, 0);
679
680  // Saturate all backward arcs
681  // (set the flow to zero on all forward arcs)
682  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
683    if (adaptor.backward(a))
684      adaptor.augment(a, adaptor.residualCapacity(a));
685  }
686
687  checkGraphNodeList(adaptor, 4);
688  checkGraphArcList(adaptor, 6);
689  checkGraphConArcList(adaptor, 6);
690
691  checkGraphOutArcList(adaptor, n1, 3);
692  checkGraphOutArcList(adaptor, n2, 2);
693  checkGraphOutArcList(adaptor, n3, 1);
694  checkGraphOutArcList(adaptor, n4, 0);
695
696  checkGraphInArcList(adaptor, n1, 0);
697  checkGraphInArcList(adaptor, n2, 1);
698  checkGraphInArcList(adaptor, n3, 2);
699  checkGraphInArcList(adaptor, n4, 3);
700
701  // Find maximum flow by augmenting along shortest paths
702  int flow_value = 0;
703  Adaptor::ResidualCapacity res_cap(adaptor);
704  while (true) {
705
706    Bfs<Adaptor> bfs(adaptor);
707    bfs.run(n1, n4);
708
709    if (!bfs.reached(n4)) break;
710
711    Path<Adaptor> p = bfs.path(n4);
712
713    int min = std::numeric_limits<int>::max();
714    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
715      if (res_cap[a] < min) min = res_cap[a];
716    }
717
718    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
719      adaptor.augment(a, min);
720    }
721    flow_value += min;
722  }
723
724  check(flow_value == 18, "Wrong flow with res graph adaptor");
725
726  // Check forward() and backward()
727  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
728    check(adaptor.forward(a) != adaptor.backward(a),
729          "Wrong forward() or backward()");
730    check((adaptor.forward(a) && adaptor.forward(Digraph::Arc(a)) == a) ||
731          (adaptor.backward(a) && adaptor.backward(Digraph::Arc(a)) == a),
732          "Wrong forward() or backward()");
733  }
734
735  // Check the conversion of nodes and arcs
736  Digraph::Node nd = Adaptor::NodeIt(adaptor);
737  nd = ++Adaptor::NodeIt(adaptor);
738  Adaptor::Node na = n1;
739  na = n2;
740  Digraph::Arc ad = Adaptor::ArcIt(adaptor);
741  ad = ++Adaptor::ArcIt(adaptor);
742}
743
744void checkSplitNodes() {
745  // Check concepts
746  checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
747  checkConcept<concepts::Digraph, SplitNodes<ListDigraph> >();
748
749  // Create a digraph and an adaptor
750  typedef ListDigraph Digraph;
751  typedef SplitNodes<Digraph> Adaptor;
752
753  Digraph digraph;
754  Adaptor adaptor(digraph);
755
756  Digraph::Node n1 = digraph.addNode();
757  Digraph::Node n2 = digraph.addNode();
758  Digraph::Node n3 = digraph.addNode();
759
760  Digraph::Arc a1 = digraph.addArc(n1, n2);
761  Digraph::Arc a2 = digraph.addArc(n1, n3);
762  Digraph::Arc a3 = digraph.addArc(n2, n3);
763  ::lemon::ignore_unused_variable_warning(a1,a2,a3);
764
765  checkGraphNodeList(adaptor, 6);
766  checkGraphArcList(adaptor, 6);
767  checkGraphConArcList(adaptor, 6);
768
769  checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
770  checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2);
771  checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
772  checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1);
773  checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
774  checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0);
775
776  checkGraphInArcList(adaptor, adaptor.inNode(n1), 0);
777  checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
778  checkGraphInArcList(adaptor, adaptor.inNode(n2), 1);
779  checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
780  checkGraphInArcList(adaptor, adaptor.inNode(n3), 2);
781  checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
782
783  checkNodeIds(adaptor);
784  checkArcIds(adaptor);
785
786  checkGraphNodeMap(adaptor);
787  checkGraphArcMap(adaptor);
788
789  // Check split
790  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
791    if (adaptor.origArc(a)) {
792      Digraph::Arc oa = a;
793      check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),
794            "Wrong split");
795      check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),
796            "Wrong split");
797    } else {
798      Digraph::Node on = a;
799      check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");
800      check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");
801    }
802  }
803
804  // Check combined node map
805  typedef Adaptor::CombinedNodeMap
806    <Digraph::NodeMap<int>, Digraph::NodeMap<int> > IntCombinedNodeMap;
807  typedef Adaptor::CombinedNodeMap
808    <Digraph::NodeMap<bool>, Digraph::NodeMap<bool> > BoolCombinedNodeMap;
809  checkConcept<concepts::ReferenceMap<Adaptor::Node, int, int&, const int&>,
810    IntCombinedNodeMap>();
811//checkConcept<concepts::ReferenceMap<Adaptor::Node, bool, bool&, const bool&>,
812//  BoolCombinedNodeMap>();
813  checkConcept<concepts::ReadWriteMap<Adaptor::Node, bool>,
814    BoolCombinedNodeMap>();
815
816  Digraph::NodeMap<int> in_map(digraph), out_map(digraph);
817  for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {
818    in_map[n] = digraph.id(n);
819    out_map[n] = -digraph.id(n);
820  }
821
822  Adaptor::CombinedNodeMap<Digraph::NodeMap<int>, Digraph::NodeMap<int> >
823    node_map(in_map, out_map);
824  for (Adaptor::NodeIt n(adaptor); n != INVALID; ++n) {
825    if (adaptor.inNode(n)) {
826      check(node_map[n] == in_map[n], "Wrong combined node map");
827    } else {
828      check(node_map[n] == out_map[n], "Wrong combined node map");
829    }
830  }
831
832  // Check combined arc map
833  typedef Adaptor::CombinedArcMap
834    <Digraph::ArcMap<int>, Digraph::NodeMap<int> > IntCombinedArcMap;
835  typedef Adaptor::CombinedArcMap
836    <Digraph::ArcMap<bool>, Digraph::NodeMap<bool> > BoolCombinedArcMap;
837  checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,
838    IntCombinedArcMap>();
839//checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,
840//  BoolCombinedArcMap>();
841  checkConcept<concepts::ReadWriteMap<Adaptor::Arc, bool>,
842    BoolCombinedArcMap>();
843
844  Digraph::ArcMap<int> a_map(digraph);
845  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
846    a_map[a] = digraph.id(a);
847  }
848
849  Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::NodeMap<int> >
850    arc_map(a_map, out_map);
851  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
852    check(arc_map[adaptor.arc(a)] == a_map[a],  "Wrong combined arc map");
853  }
854  for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {
855    check(arc_map[adaptor.arc(n)] == out_map[n],  "Wrong combined arc map");
856  }
857
858  // Check the conversion of nodes
859  Digraph::Node nd = adaptor.inNode(n1);
860  check (nd == n1, "Wrong node conversion");
861  nd = adaptor.outNode(n2);
862  check (nd == n2, "Wrong node conversion");
863}
864
865void checkSubGraph() {
866  // Check concepts
867  checkConcept<concepts::Graph, SubGraph<concepts::Graph> >();
868  checkConcept<concepts::Graph, SubGraph<ListGraph> >();
869  checkConcept<concepts::AlterableGraphComponent<>,
870               SubGraph<ListGraph> >();
871  checkConcept<concepts::ExtendableGraphComponent<>,
872               SubGraph<ListGraph> >();
873  checkConcept<concepts::ErasableGraphComponent<>,
874               SubGraph<ListGraph> >();
875  checkConcept<concepts::ClearableGraphComponent<>,
876               SubGraph<ListGraph> >();
877
878  // Create a graph and an adaptor
879  typedef ListGraph Graph;
880  typedef Graph::NodeMap<bool> NodeFilter;
881  typedef Graph::EdgeMap<bool> EdgeFilter;
882  typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;
883
884  Graph graph;
885  NodeFilter node_filter(graph);
886  EdgeFilter edge_filter(graph);
887  Adaptor adaptor(graph, node_filter, edge_filter);
888
889  // Add nodes and edges to the original graph and the adaptor
890  Graph::Node n1 = graph.addNode();
891  Graph::Node n2 = graph.addNode();
892  Adaptor::Node n3 = adaptor.addNode();
893  Adaptor::Node n4 = adaptor.addNode();
894
895  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
896
897  Graph::Edge e1 = graph.addEdge(n1, n2);
898  Graph::Edge e2 = graph.addEdge(n1, n3);
899  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
900  Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
901
902  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
903
904  checkGraphNodeList(adaptor, 4);
905  checkGraphArcList(adaptor, 8);
906  checkGraphEdgeList(adaptor, 4);
907  checkGraphConArcList(adaptor, 8);
908  checkGraphConEdgeList(adaptor, 4);
909
910  checkGraphIncEdgeArcLists(adaptor, n1, 2);
911  checkGraphIncEdgeArcLists(adaptor, n2, 2);
912  checkGraphIncEdgeArcLists(adaptor, n3, 3);
913  checkGraphIncEdgeArcLists(adaptor, n4, 1);
914
915  checkNodeIds(adaptor);
916  checkArcIds(adaptor);
917  checkEdgeIds(adaptor);
918
919  checkGraphNodeMap(adaptor);
920  checkGraphArcMap(adaptor);
921  checkGraphEdgeMap(adaptor);
922
923  // Hide an edge
924  adaptor.status(e2, false);
925  adaptor.disable(e3);
926  if (!adaptor.status(e3)) adaptor.enable(e3);
927
928  checkGraphNodeList(adaptor, 4);
929  checkGraphArcList(adaptor, 6);
930  checkGraphEdgeList(adaptor, 3);
931  checkGraphConArcList(adaptor, 6);
932  checkGraphConEdgeList(adaptor, 3);
933
934  checkGraphIncEdgeArcLists(adaptor, n1, 1);
935  checkGraphIncEdgeArcLists(adaptor, n2, 2);
936  checkGraphIncEdgeArcLists(adaptor, n3, 2);
937  checkGraphIncEdgeArcLists(adaptor, n4, 1);
938
939  checkNodeIds(adaptor);
940  checkArcIds(adaptor);
941  checkEdgeIds(adaptor);
942
943  checkGraphNodeMap(adaptor);
944  checkGraphArcMap(adaptor);
945  checkGraphEdgeMap(adaptor);
946
947  // Hide a node
948  adaptor.status(n1, false);
949  adaptor.disable(n3);
950  if (!adaptor.status(n3)) adaptor.enable(n3);
951
952  checkGraphNodeList(adaptor, 3);
953  checkGraphArcList(adaptor, 4);
954  checkGraphEdgeList(adaptor, 2);
955  checkGraphConArcList(adaptor, 4);
956  checkGraphConEdgeList(adaptor, 2);
957
958  checkGraphIncEdgeArcLists(adaptor, n2, 1);
959  checkGraphIncEdgeArcLists(adaptor, n3, 2);
960  checkGraphIncEdgeArcLists(adaptor, n4, 1);
961
962  checkNodeIds(adaptor);
963  checkArcIds(adaptor);
964  checkEdgeIds(adaptor);
965
966  checkGraphNodeMap(adaptor);
967  checkGraphArcMap(adaptor);
968  checkGraphEdgeMap(adaptor);
969
970  // Hide all nodes and edges
971  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
972  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
973
974  checkGraphNodeList(adaptor, 0);
975  checkGraphArcList(adaptor, 0);
976  checkGraphEdgeList(adaptor, 0);
977  checkGraphConArcList(adaptor, 0);
978  checkGraphConEdgeList(adaptor, 0);
979
980  checkNodeIds(adaptor);
981  checkArcIds(adaptor);
982  checkEdgeIds(adaptor);
983
984  checkGraphNodeMap(adaptor);
985  checkGraphArcMap(adaptor);
986  checkGraphEdgeMap(adaptor);
987
988  // Check the conversion of nodes and edges
989  Graph::Node ng = n3;
990  ng = n4;
991  Adaptor::Node na = n1;
992  na = n2;
993  Graph::Edge eg = e3;
994  eg = e4;
995  Adaptor::Edge ea = e1;
996  ea = e2;
997}
998
999void checkFilterNodes2() {
1000  // Check concepts
1001  checkConcept<concepts::Graph, FilterNodes<concepts::Graph> >();
1002  checkConcept<concepts::Graph, FilterNodes<ListGraph> >();
1003  checkConcept<concepts::AlterableGraphComponent<>,
1004               FilterNodes<ListGraph> >();
1005  checkConcept<concepts::ExtendableGraphComponent<>,
1006               FilterNodes<ListGraph> >();
1007  checkConcept<concepts::ErasableGraphComponent<>,
1008               FilterNodes<ListGraph> >();
1009  checkConcept<concepts::ClearableGraphComponent<>,
1010               FilterNodes<ListGraph> >();
1011
1012  // Create a graph and an adaptor
1013  typedef ListGraph Graph;
1014  typedef Graph::NodeMap<bool> NodeFilter;
1015  typedef FilterNodes<Graph, NodeFilter> Adaptor;
1016
1017  // Add nodes and edges to the original graph and the adaptor
1018  Graph graph;
1019  NodeFilter node_filter(graph);
1020  Adaptor adaptor(graph, node_filter);
1021
1022  Graph::Node n1 = graph.addNode();
1023  Graph::Node n2 = graph.addNode();
1024  Adaptor::Node n3 = adaptor.addNode();
1025  Adaptor::Node n4 = adaptor.addNode();
1026
1027  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
1028
1029  Graph::Edge e1 = graph.addEdge(n1, n2);
1030  Graph::Edge e2 = graph.addEdge(n1, n3);
1031  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
1032  Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
1033
1034  checkGraphNodeList(adaptor, 4);
1035  checkGraphArcList(adaptor, 8);
1036  checkGraphEdgeList(adaptor, 4);
1037  checkGraphConArcList(adaptor, 8);
1038  checkGraphConEdgeList(adaptor, 4);
1039
1040  checkGraphIncEdgeArcLists(adaptor, n1, 2);
1041  checkGraphIncEdgeArcLists(adaptor, n2, 2);
1042  checkGraphIncEdgeArcLists(adaptor, n3, 3);
1043  checkGraphIncEdgeArcLists(adaptor, n4, 1);
1044
1045  checkNodeIds(adaptor);
1046  checkArcIds(adaptor);
1047  checkEdgeIds(adaptor);
1048
1049  checkGraphNodeMap(adaptor);
1050  checkGraphArcMap(adaptor);
1051  checkGraphEdgeMap(adaptor);
1052
1053  // Hide a node
1054  adaptor.status(n1, false);
1055  adaptor.disable(n3);
1056  if (!adaptor.status(n3)) adaptor.enable(n3);
1057
1058  checkGraphNodeList(adaptor, 3);
1059  checkGraphArcList(adaptor, 4);
1060  checkGraphEdgeList(adaptor, 2);
1061  checkGraphConArcList(adaptor, 4);
1062  checkGraphConEdgeList(adaptor, 2);
1063
1064  checkGraphIncEdgeArcLists(adaptor, n2, 1);
1065  checkGraphIncEdgeArcLists(adaptor, n3, 2);
1066  checkGraphIncEdgeArcLists(adaptor, n4, 1);
1067
1068  checkNodeIds(adaptor);
1069  checkArcIds(adaptor);
1070  checkEdgeIds(adaptor);
1071
1072  checkGraphNodeMap(adaptor);
1073  checkGraphArcMap(adaptor);
1074  checkGraphEdgeMap(adaptor);
1075
1076  // Hide all nodes
1077  node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
1078
1079  checkGraphNodeList(adaptor, 0);
1080  checkGraphArcList(adaptor, 0);
1081  checkGraphEdgeList(adaptor, 0);
1082  checkGraphConArcList(adaptor, 0);
1083  checkGraphConEdgeList(adaptor, 0);
1084
1085  checkNodeIds(adaptor);
1086  checkArcIds(adaptor);
1087  checkEdgeIds(adaptor);
1088
1089  checkGraphNodeMap(adaptor);
1090  checkGraphArcMap(adaptor);
1091  checkGraphEdgeMap(adaptor);
1092
1093  // Check the conversion of nodes and edges
1094  Graph::Node ng = n3;
1095  ng = n4;
1096  Adaptor::Node na = n1;
1097  na = n2;
1098  Graph::Edge eg = e3;
1099  eg = e4;
1100  Adaptor::Edge ea = e1;
1101  ea = e2;
1102}
1103
1104void checkFilterEdges() {
1105  // Check concepts
1106  checkConcept<concepts::Graph, FilterEdges<concepts::Graph> >();
1107  checkConcept<concepts::Graph, FilterEdges<ListGraph> >();
1108  checkConcept<concepts::AlterableGraphComponent<>,
1109               FilterEdges<ListGraph> >();
1110  checkConcept<concepts::ExtendableGraphComponent<>,
1111               FilterEdges<ListGraph> >();
1112  checkConcept<concepts::ErasableGraphComponent<>,
1113               FilterEdges<ListGraph> >();
1114  checkConcept<concepts::ClearableGraphComponent<>,
1115               FilterEdges<ListGraph> >();
1116
1117  // Create a graph and an adaptor
1118  typedef ListGraph Graph;
1119  typedef Graph::EdgeMap<bool> EdgeFilter;
1120  typedef FilterEdges<Graph, EdgeFilter> Adaptor;
1121
1122  Graph graph;
1123  EdgeFilter edge_filter(graph);
1124  Adaptor adaptor(graph, edge_filter);
1125
1126  // Add nodes and edges to the original graph and the adaptor
1127  Graph::Node n1 = graph.addNode();
1128  Graph::Node n2 = graph.addNode();
1129  Adaptor::Node n3 = adaptor.addNode();
1130  Adaptor::Node n4 = adaptor.addNode();
1131
1132  Graph::Edge e1 = graph.addEdge(n1, n2);
1133  Graph::Edge e2 = graph.addEdge(n1, n3);
1134  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
1135  Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
1136
1137  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
1138
1139  checkGraphNodeList(adaptor, 4);
1140  checkGraphArcList(adaptor, 8);
1141  checkGraphEdgeList(adaptor, 4);
1142  checkGraphConArcList(adaptor, 8);
1143  checkGraphConEdgeList(adaptor, 4);
1144
1145  checkGraphIncEdgeArcLists(adaptor, n1, 2);
1146  checkGraphIncEdgeArcLists(adaptor, n2, 2);
1147  checkGraphIncEdgeArcLists(adaptor, n3, 3);
1148  checkGraphIncEdgeArcLists(adaptor, n4, 1);
1149
1150  checkNodeIds(adaptor);
1151  checkArcIds(adaptor);
1152  checkEdgeIds(adaptor);
1153
1154  checkGraphNodeMap(adaptor);
1155  checkGraphArcMap(adaptor);
1156  checkGraphEdgeMap(adaptor);
1157
1158  // Hide an edge
1159  adaptor.status(e2, false);
1160  adaptor.disable(e3);
1161  if (!adaptor.status(e3)) adaptor.enable(e3);
1162
1163  checkGraphNodeList(adaptor, 4);
1164  checkGraphArcList(adaptor, 6);
1165  checkGraphEdgeList(adaptor, 3);
1166  checkGraphConArcList(adaptor, 6);
1167  checkGraphConEdgeList(adaptor, 3);
1168
1169  checkGraphIncEdgeArcLists(adaptor, n1, 1);
1170  checkGraphIncEdgeArcLists(adaptor, n2, 2);
1171  checkGraphIncEdgeArcLists(adaptor, n3, 2);
1172  checkGraphIncEdgeArcLists(adaptor, n4, 1);
1173
1174  checkNodeIds(adaptor);
1175  checkArcIds(adaptor);
1176  checkEdgeIds(adaptor);
1177
1178  checkGraphNodeMap(adaptor);
1179  checkGraphArcMap(adaptor);
1180  checkGraphEdgeMap(adaptor);
1181
1182  // Hide all edges
1183  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
1184
1185  checkGraphNodeList(adaptor, 4);
1186  checkGraphArcList(adaptor, 0);
1187  checkGraphEdgeList(adaptor, 0);
1188  checkGraphConArcList(adaptor, 0);
1189  checkGraphConEdgeList(adaptor, 0);
1190
1191  checkNodeIds(adaptor);
1192  checkArcIds(adaptor);
1193  checkEdgeIds(adaptor);
1194
1195  checkGraphNodeMap(adaptor);
1196  checkGraphArcMap(adaptor);
1197  checkGraphEdgeMap(adaptor);
1198
1199  // Check the conversion of nodes and edges
1200  Graph::Node ng = n3;
1201  ng = n4;
1202  Adaptor::Node na = n1;
1203  na = n2;
1204  Graph::Edge eg = e3;
1205  eg = e4;
1206  Adaptor::Edge ea = e1;
1207  ea = e2;
1208}
1209
1210void checkOrienter() {
1211  // Check concepts
1212  checkConcept<concepts::Digraph, Orienter<concepts::Graph> >();
1213  checkConcept<concepts::Digraph, Orienter<ListGraph> >();
1214  checkConcept<concepts::AlterableDigraphComponent<>,
1215               Orienter<ListGraph> >();
1216  checkConcept<concepts::ExtendableDigraphComponent<>,
1217               Orienter<ListGraph> >();
1218  checkConcept<concepts::ErasableDigraphComponent<>,
1219               Orienter<ListGraph> >();
1220  checkConcept<concepts::ClearableDigraphComponent<>,
1221               Orienter<ListGraph> >();
1222
1223  // Create a graph and an adaptor
1224  typedef ListGraph Graph;
1225  typedef ListGraph::EdgeMap<bool> DirMap;
1226  typedef Orienter<Graph> Adaptor;
1227
1228  Graph graph;
1229  DirMap dir(graph);
1230  Adaptor adaptor(graph, dir);
1231
1232  // Add nodes and edges to the original graph and the adaptor
1233  Graph::Node n1 = graph.addNode();
1234  Graph::Node n2 = graph.addNode();
1235  Adaptor::Node n3 = adaptor.addNode();
1236
1237  Graph::Edge e1 = graph.addEdge(n1, n2);
1238  Graph::Edge e2 = graph.addEdge(n1, n3);
1239  Adaptor::Arc e3 = adaptor.addArc(n2, n3);
1240
1241  dir[e1] = dir[e2] = dir[e3] = true;
1242
1243  // Check the original graph
1244  checkGraphNodeList(graph, 3);
1245  checkGraphArcList(graph, 6);
1246  checkGraphConArcList(graph, 6);
1247  checkGraphEdgeList(graph, 3);
1248  checkGraphConEdgeList(graph, 3);
1249
1250  checkGraphIncEdgeArcLists(graph, n1, 2);
1251  checkGraphIncEdgeArcLists(graph, n2, 2);
1252  checkGraphIncEdgeArcLists(graph, n3, 2);
1253
1254  checkNodeIds(graph);
1255  checkArcIds(graph);
1256  checkEdgeIds(graph);
1257
1258  checkGraphNodeMap(graph);
1259  checkGraphArcMap(graph);
1260  checkGraphEdgeMap(graph);
1261
1262  // Check the adaptor
1263  checkGraphNodeList(adaptor, 3);
1264  checkGraphArcList(adaptor, 3);
1265  checkGraphConArcList(adaptor, 3);
1266
1267  checkGraphOutArcList(adaptor, n1, 2);
1268  checkGraphOutArcList(adaptor, n2, 1);
1269  checkGraphOutArcList(adaptor, n3, 0);
1270
1271  checkGraphInArcList(adaptor, n1, 0);
1272  checkGraphInArcList(adaptor, n2, 1);
1273  checkGraphInArcList(adaptor, n3, 2);
1274
1275  checkNodeIds(adaptor);
1276  checkArcIds(adaptor);
1277
1278  checkGraphNodeMap(adaptor);
1279  checkGraphArcMap(adaptor);
1280
1281  // Check direction changing
1282  {
1283    dir[e1] = true;
1284    Adaptor::Node u = adaptor.source(e1);
1285    Adaptor::Node v = adaptor.target(e1);
1286
1287    dir[e1] = false;
1288    check (u == adaptor.target(e1), "Wrong dir");
1289    check (v == adaptor.source(e1), "Wrong dir");
1290
1291    check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");
1292    dir[e1] = n1 == u;
1293  }
1294
1295  {
1296    dir[e2] = true;
1297    Adaptor::Node u = adaptor.source(e2);
1298    Adaptor::Node v = adaptor.target(e2);
1299
1300    dir[e2] = false;
1301    check (u == adaptor.target(e2), "Wrong dir");
1302    check (v == adaptor.source(e2), "Wrong dir");
1303
1304    check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");
1305    dir[e2] = n3 == u;
1306  }
1307
1308  {
1309    dir[e3] = true;
1310    Adaptor::Node u = adaptor.source(e3);
1311    Adaptor::Node v = adaptor.target(e3);
1312
1313    dir[e3] = false;
1314    check (u == adaptor.target(e3), "Wrong dir");
1315    check (v == adaptor.source(e3), "Wrong dir");
1316
1317    check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
1318    dir[e3] = n2 == u;
1319  }
1320
1321  // Check the adaptor again
1322  checkGraphNodeList(adaptor, 3);
1323  checkGraphArcList(adaptor, 3);
1324  checkGraphConArcList(adaptor, 3);
1325
1326  checkGraphOutArcList(adaptor, n1, 1);
1327  checkGraphOutArcList(adaptor, n2, 1);
1328  checkGraphOutArcList(adaptor, n3, 1);
1329
1330  checkGraphInArcList(adaptor, n1, 1);
1331  checkGraphInArcList(adaptor, n2, 1);
1332  checkGraphInArcList(adaptor, n3, 1);
1333
1334  checkNodeIds(adaptor);
1335  checkArcIds(adaptor);
1336
1337  checkGraphNodeMap(adaptor);
1338  checkGraphArcMap(adaptor);
1339
1340  // Check reverseArc()
1341  adaptor.reverseArc(e2);
1342  adaptor.reverseArc(e3);
1343  adaptor.reverseArc(e2);
1344
1345  checkGraphNodeList(adaptor, 3);
1346  checkGraphArcList(adaptor, 3);
1347  checkGraphConArcList(adaptor, 3);
1348
1349  checkGraphOutArcList(adaptor, n1, 1);
1350  checkGraphOutArcList(adaptor, n2, 0);
1351  checkGraphOutArcList(adaptor, n3, 2);
1352
1353  checkGraphInArcList(adaptor, n1, 1);
1354  checkGraphInArcList(adaptor, n2, 2);
1355  checkGraphInArcList(adaptor, n3, 0);
1356
1357  // Check the conversion of nodes and arcs/edges
1358  Graph::Node ng = n3;
1359  ng = n3;
1360  Adaptor::Node na = n1;
1361  na = n2;
1362  Graph::Edge eg = e3;
1363  eg = e3;
1364  Adaptor::Arc aa = e1;
1365  aa = e2;
1366}
1367
1368void checkCombiningAdaptors() {
1369  // Create a grid graph
1370  GridGraph graph(2,2);
1371  GridGraph::Node n1 = graph(0,0);
1372  GridGraph::Node n2 = graph(0,1);
1373  GridGraph::Node n3 = graph(1,0);
1374  GridGraph::Node n4 = graph(1,1);
1375
1376  GridGraph::EdgeMap<bool> dir_map(graph);
1377  dir_map[graph.right(n1)] = graph.u(graph.right(n1)) == n1;
1378  dir_map[graph.up(n1)] = graph.u(graph.up(n1)) != n1;
1379  dir_map[graph.left(n4)] = graph.u(graph.left(n4)) != n4;
1380  dir_map[graph.down(n4)] = graph.u(graph.down(n4)) != n4;
1381
1382  // Apply several adaptors on the grid graph
1383  typedef SplitNodes< ReverseDigraph< const Orienter<
1384            const GridGraph, GridGraph::EdgeMap<bool> > > >
1385    RevSplitGridGraph;
1386  typedef ReverseDigraph<const RevSplitGridGraph> SplitGridGraph;
1387  typedef Undirector<const SplitGridGraph> USplitGridGraph;
1388  typedef Undirector<const USplitGridGraph> UUSplitGridGraph;
1389  checkConcept<concepts::Digraph, RevSplitGridGraph>();
1390  checkConcept<concepts::Digraph, SplitGridGraph>();
1391  checkConcept<concepts::Graph, USplitGridGraph>();
1392  checkConcept<concepts::Graph, UUSplitGridGraph>();
1393
1394  RevSplitGridGraph rev_adaptor =
1395    splitNodes(reverseDigraph(orienter(graph, dir_map)));
1396  SplitGridGraph adaptor = reverseDigraph(rev_adaptor);
1397  USplitGridGraph uadaptor = undirector(adaptor);
1398  UUSplitGridGraph uuadaptor = undirector(uadaptor);
1399
1400  // Check adaptor
1401  checkGraphNodeList(adaptor, 8);
1402  checkGraphArcList(adaptor, 8);
1403  checkGraphConArcList(adaptor, 8);
1404
1405  checkGraphOutArcList(adaptor, rev_adaptor.inNode(n1), 1);
1406  checkGraphOutArcList(adaptor, rev_adaptor.outNode(n1), 1);
1407  checkGraphOutArcList(adaptor, rev_adaptor.inNode(n2), 2);
1408  checkGraphOutArcList(adaptor, rev_adaptor.outNode(n2), 1);
1409  checkGraphOutArcList(adaptor, rev_adaptor.inNode(n3), 1);
1410  checkGraphOutArcList(adaptor, rev_adaptor.outNode(n3), 1);
1411  checkGraphOutArcList(adaptor, rev_adaptor.inNode(n4), 0);
1412  checkGraphOutArcList(adaptor, rev_adaptor.outNode(n4), 1);
1413
1414  checkGraphInArcList(adaptor, rev_adaptor.inNode(n1), 1);
1415  checkGraphInArcList(adaptor, rev_adaptor.outNode(n1), 1);
1416  checkGraphInArcList(adaptor, rev_adaptor.inNode(n2), 1);
1417  checkGraphInArcList(adaptor, rev_adaptor.outNode(n2), 0);
1418  checkGraphInArcList(adaptor, rev_adaptor.inNode(n3), 1);
1419  checkGraphInArcList(adaptor, rev_adaptor.outNode(n3), 1);
1420  checkGraphInArcList(adaptor, rev_adaptor.inNode(n4), 1);
1421  checkGraphInArcList(adaptor, rev_adaptor.outNode(n4), 2);
1422
1423  checkNodeIds(adaptor);
1424  checkArcIds(adaptor);
1425
1426  checkGraphNodeMap(adaptor);
1427  checkGraphArcMap(adaptor);
1428
1429  // Check uadaptor
1430  checkGraphNodeList(uadaptor, 8);
1431  checkGraphEdgeList(uadaptor, 8);
1432  checkGraphArcList(uadaptor, 16);
1433  checkGraphConEdgeList(uadaptor, 8);
1434  checkGraphConArcList(uadaptor, 16);
1435
1436  checkNodeIds(uadaptor);
1437  checkEdgeIds(uadaptor);
1438  checkArcIds(uadaptor);
1439
1440  checkGraphNodeMap(uadaptor);
1441  checkGraphEdgeMap(uadaptor);
1442  checkGraphArcMap(uadaptor);
1443
1444  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n1), 2);
1445  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n1), 2);
1446  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n2), 3);
1447  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n2), 1);
1448  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n3), 2);
1449  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n3), 2);
1450  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n4), 1);
1451  checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n4), 3);
1452
1453  // Check uuadaptor
1454  checkGraphNodeList(uuadaptor, 8);
1455  checkGraphEdgeList(uuadaptor, 16);
1456  checkGraphArcList(uuadaptor, 32);
1457  checkGraphConEdgeList(uuadaptor, 16);
1458  checkGraphConArcList(uuadaptor, 32);
1459
1460  checkNodeIds(uuadaptor);
1461  checkEdgeIds(uuadaptor);
1462  checkArcIds(uuadaptor);
1463
1464  checkGraphNodeMap(uuadaptor);
1465  checkGraphEdgeMap(uuadaptor);
1466  checkGraphArcMap(uuadaptor);
1467}
1468
1469int main(int, const char **) {
1470  // Check the digraph adaptors (using ListDigraph)
1471  checkReverseDigraph();
1472  checkSubDigraph();
1473  checkFilterNodes1();
1474  checkFilterArcs();
1475  checkUndirector();
1476  checkResidualDigraph();
1477  checkSplitNodes();
1478
1479  // Check the graph adaptors (using ListGraph)
1480  checkSubGraph();
1481  checkFilterNodes2();
1482  checkFilterEdges();
1483  checkOrienter();
1484
1485  // Combine adaptors (using GridGraph)
1486  checkCombiningAdaptors();
1487
1488  return 0;
1489}
Note: See TracBrowser for help on using the repository browser.