COIN-OR::LEMON - Graph Library

source: lemon/test/adaptors_test.cc

Last change on this file was 1416:f179aa1045a4, checked in by Peter Kovacs <kpeter@…>, 12 months ago

Suppress unused typdef warnings (#615)

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