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 @ 1208:c6aa2cc1af04

Last change on this file since 1208:c6aa2cc1af04 was 1197:f179aa1045a4, checked in by Peter Kovacs <kpeter@…>, 6 years ago

Suppress unused typdef warnings (#615)
File size: 44.0 KB
RevLine 
[416]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
[414]2 *
[416]3 * This file is a part of LEMON, a generic C++ optimization library.
[414]4 *
[1092]5 * Copyright (C) 2003-2013
[414]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
[463]19#include <iostream>
20#include <limits>
[414]21
[463]22#include <lemon/list_graph.h>
23#include <lemon/grid_graph.h>
[414]24#include <lemon/bfs.h>
25#include <lemon/path.h>
26
[463]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"
[414]37
38using namespace lemon;
39
[416]40void checkReverseDigraph() {
[463]41  // Check concepts
[416]42  checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
[463]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> >();
[414]52
[463]53  // Create a digraph and an adaptor
[414]54  typedef ListDigraph Digraph;
[416]55  typedef ReverseDigraph<Digraph> Adaptor;
[414]56
57  Digraph digraph;
58  Adaptor adaptor(digraph);
59
[463]60  // Add nodes and arcs to the original digraph
[414]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);
[1083]68  ::lemon::ignore_unused_variable_warning(a3);
[416]69
[463]70  // Check the adaptor
[414]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
[463]89  // Check the orientation of the arcs
[414]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  }
[463]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);
[1083]103  ::lemon::ignore_unused_variable_warning(a6,a7,a8);
[463]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;
[1197]148  ::lemon::ignore_unused_variable_warning(nd);
[463]149  nd = n4;
150  Adaptor::Node na = n1;
[1197]151  ::lemon::ignore_unused_variable_warning(na);
[463]152  na = n2;
153  Digraph::Arc ad = a4;
[1197]154  ::lemon::ignore_unused_variable_warning(ad);
[463]155  ad = a5;
156  Adaptor::Arc aa = a1;
[1197]157  ::lemon::ignore_unused_variable_warning(aa);
[463]158  aa = a2;
[414]159}
160
[416]161void checkSubDigraph() {
[463]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> >();
[414]173
[463]174  // Create a digraph and an adaptor
[414]175  typedef ListDigraph Digraph;
176  typedef Digraph::NodeMap<bool> NodeFilter;
177  typedef Digraph::ArcMap<bool> ArcFilter;
[416]178  typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
[414]179
180  Digraph digraph;
181  NodeFilter node_filter(digraph);
182  ArcFilter arc_filter(digraph);
183  Adaptor adaptor(digraph, node_filter, arc_filter);
184
[463]185  // Add nodes and arcs to the original digraph and the adaptor
[414]186  Digraph::Node n1 = digraph.addNode();
187  Digraph::Node n2 = digraph.addNode();
[463]188  Adaptor::Node n3 = adaptor.addNode();
189
190  node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
[414]191
192  Digraph::Arc a1 = digraph.addArc(n1, n2);
193  Digraph::Arc a2 = digraph.addArc(n1, n3);
[463]194  Adaptor::Arc a3 = adaptor.addArc(n2, n3);
[414]195
196  arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
[440]197
[414]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
[463]216  // Hide an arc
217  adaptor.status(a2, false);
218  adaptor.disable(a3);
219  if (!adaptor.status(a3)) adaptor.enable(a3);
[414]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
[463]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;
[1197]276  ::lemon::ignore_unused_variable_warning(nd);
[463]277  nd = n3;
278  Adaptor::Node na = n1;
[1197]279  ::lemon::ignore_unused_variable_warning(na);
[463]280  na = n2;
281  Digraph::Arc ad = a3;
[1197]282  ::lemon::ignore_unused_variable_warning(ad);
[463]283  ad = a3;
284  Adaptor::Arc aa = a1;
[1197]285  ::lemon::ignore_unused_variable_warning(aa);
[463]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;
[1197]376  ::lemon::ignore_unused_variable_warning(nd);
[463]377  nd = n3;
378  Adaptor::Node na = n1;
[1197]379  ::lemon::ignore_unused_variable_warning(na);
[463]380  na = n2;
381  Digraph::Arc ad = a3;
[1197]382  ::lemon::ignore_unused_variable_warning(ad);
[463]383  ad = a3;
384  Adaptor::Arc aa = a1;
[1197]385  ::lemon::ignore_unused_variable_warning(aa);
[463]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
[414]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);
[463]475
476  // Check the conversion of nodes and arcs
477  Digraph::Node nd = n3;
[1197]478  ::lemon::ignore_unused_variable_warning(nd);
[463]479  nd = n3;
480  Adaptor::Node na = n1;
[1197]481  ::lemon::ignore_unused_variable_warning(na);
[463]482  na = n2;
483  Digraph::Arc ad = a3;
[1197]484  ::lemon::ignore_unused_variable_warning(ad);
[463]485  ad = a3;
486  Adaptor::Arc aa = a1;
[1197]487  ::lemon::ignore_unused_variable_warning(aa);
[463]488  aa = a2;
[414]489}
490
[416]491void checkUndirector() {
[463]492  // Check concepts
[416]493  checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
[463]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> >();
[414]503
[463]504
505  // Create a digraph and an adaptor
[414]506  typedef ListDigraph Digraph;
[416]507  typedef Undirector<Digraph> Adaptor;
[414]508
509  Digraph digraph;
510  Adaptor adaptor(digraph);
511
[463]512  // Add nodes and arcs/edges to the original digraph and the adaptor
[414]513  Digraph::Node n1 = digraph.addNode();
514  Digraph::Node n2 = digraph.addNode();
[463]515  Adaptor::Node n3 = adaptor.addNode();
[414]516
517  Digraph::Arc a1 = digraph.addArc(n1, n2);
518  Digraph::Arc a2 = digraph.addArc(n1, n3);
[463]519  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
[416]520
[463]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
[414]541  checkGraphNodeList(adaptor, 3);
542  checkGraphArcList(adaptor, 6);
543  checkGraphEdgeList(adaptor, 3);
544  checkGraphConArcList(adaptor, 6);
545  checkGraphConEdgeList(adaptor, 3);
546
[463]547  checkGraphIncEdgeArcLists(adaptor, n1, 2);
548  checkGraphIncEdgeArcLists(adaptor, n2, 2);
549  checkGraphIncEdgeArcLists(adaptor, n3, 2);
[414]550
551  checkNodeIds(adaptor);
552  checkArcIds(adaptor);
553  checkEdgeIds(adaptor);
554
555  checkGraphNodeMap(adaptor);
556  checkGraphArcMap(adaptor);
557  checkGraphEdgeMap(adaptor);
558
[463]559  // Check the edges of the adaptor
[414]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
[463]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;
[1197]593  ::lemon::ignore_unused_variable_warning(nd);
[463]594  nd = n3;
595  Adaptor::Node na = n1;
[1197]596  ::lemon::ignore_unused_variable_warning(na);
[463]597  na = n2;
598  Digraph::Arc ad = e3;
[1197]599  ::lemon::ignore_unused_variable_warning(ad);
[463]600  ad = e3;
601  Adaptor::Edge ea = a1;
[1197]602  ::lemon::ignore_unused_variable_warning(ea);
[463]603  ea = a2;
[414]604}
605
[464]606void checkResidualDigraph() {
[463]607  // Check concepts
[464]608  checkConcept<concepts::Digraph, ResidualDigraph<concepts::Digraph> >();
609  checkConcept<concepts::Digraph, ResidualDigraph<ListDigraph> >();
[414]610
[463]611  // Create a digraph and an adaptor
[414]612  typedef ListDigraph Digraph;
613  typedef Digraph::ArcMap<int> IntArcMap;
[464]614  typedef ResidualDigraph<Digraph, IntArcMap> Adaptor;
[414]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
[463]639  // Check the adaptor with various flow values
640  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
[414]641    flow[a] = 0;
642  }
[416]643
[414]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
[463]658  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
[414]659    flow[a] = capacity[a] / 2;
660  }
[416]661
[414]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
[463]682  for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
[414]683    flow[a] = capacity[a];
684  }
[416]685
[414]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
[463]700  // Saturate all backward arcs
701  // (set the flow to zero on all forward arcs)
[414]702  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
[463]703    if (adaptor.backward(a))
704      adaptor.augment(a, adaptor.residualCapacity(a));
[414]705  }
706
[463]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
[414]722  int flow_value = 0;
[463]723  Adaptor::ResidualCapacity res_cap(adaptor);
[414]724  while (true) {
[416]725
[414]726    Bfs<Adaptor> bfs(adaptor);
727    bfs.run(n1, n4);
[416]728
[414]729    if (!bfs.reached(n4)) break;
730
731    Path<Adaptor> p = bfs.path(n4);
[416]732
[414]733    int min = std::numeric_limits<int>::max();
734    for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
[463]735      if (res_cap[a] < min) min = res_cap[a];
[414]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
[463]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);
[1197]757  ::lemon::ignore_unused_variable_warning(nd);
[463]758  nd = ++Adaptor::NodeIt(adaptor);
759  Adaptor::Node na = n1;
[1197]760  ::lemon::ignore_unused_variable_warning(na);
[463]761  na = n2;
762  Digraph::Arc ad = Adaptor::ArcIt(adaptor);
[1197]763  ::lemon::ignore_unused_variable_warning(ad);
[463]764  ad = ++Adaptor::ArcIt(adaptor);
[414]765}
766
[416]767void checkSplitNodes() {
[463]768  // Check concepts
[416]769  checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
[463]770  checkConcept<concepts::Digraph, SplitNodes<ListDigraph> >();
[414]771
[463]772  // Create a digraph and an adaptor
[414]773  typedef ListDigraph Digraph;
[416]774  typedef SplitNodes<Digraph> Adaptor;
[414]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);
[1083]786  ::lemon::ignore_unused_variable_warning(a1,a2,a3);
[416]787
[414]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);
[416]808
[414]809  checkGraphNodeMap(adaptor);
810  checkGraphArcMap(adaptor);
811
[463]812  // Check split
[414]813  for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
814    if (adaptor.origArc(a)) {
815      Digraph::Arc oa = a;
[416]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");
[414]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  }
[463]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");
[414]886}
887
[416]888void checkSubGraph() {
[463]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> >();
[414]900
[463]901  // Create a graph and an adaptor
[414]902  typedef ListGraph Graph;
903  typedef Graph::NodeMap<bool> NodeFilter;
904  typedef Graph::EdgeMap<bool> EdgeFilter;
[416]905  typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;
[414]906
907  Graph graph;
908  NodeFilter node_filter(graph);
909  EdgeFilter edge_filter(graph);
910  Adaptor adaptor(graph, node_filter, edge_filter);
911
[463]912  // Add nodes and edges to the original graph and the adaptor
[414]913  Graph::Node n1 = graph.addNode();
914  Graph::Node n2 = graph.addNode();
[463]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;
[414]919
920  Graph::Edge e1 = graph.addEdge(n1, n2);
921  Graph::Edge e2 = graph.addEdge(n1, n3);
[463]922  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
923  Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
[414]924
925  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
[440]926
[414]927  checkGraphNodeList(adaptor, 4);
928  checkGraphArcList(adaptor, 8);
929  checkGraphEdgeList(adaptor, 4);
930  checkGraphConArcList(adaptor, 8);
931  checkGraphConEdgeList(adaptor, 4);
932
[463]933  checkGraphIncEdgeArcLists(adaptor, n1, 2);
934  checkGraphIncEdgeArcLists(adaptor, n2, 2);
935  checkGraphIncEdgeArcLists(adaptor, n3, 3);
936  checkGraphIncEdgeArcLists(adaptor, n4, 1);
[414]937
938  checkNodeIds(adaptor);
939  checkArcIds(adaptor);
940  checkEdgeIds(adaptor);
941
942  checkGraphNodeMap(adaptor);
943  checkGraphArcMap(adaptor);
944  checkGraphEdgeMap(adaptor);
945
[463]946  // Hide an edge
947  adaptor.status(e2, false);
948  adaptor.disable(e3);
949  if (!adaptor.status(e3)) adaptor.enable(e3);
[414]950
951  checkGraphNodeList(adaptor, 4);
952  checkGraphArcList(adaptor, 6);
953  checkGraphEdgeList(adaptor, 3);
954  checkGraphConArcList(adaptor, 6);
955  checkGraphConEdgeList(adaptor, 3);
956
[463]957  checkGraphIncEdgeArcLists(adaptor, n1, 1);
958  checkGraphIncEdgeArcLists(adaptor, n2, 2);
959  checkGraphIncEdgeArcLists(adaptor, n3, 2);
960  checkGraphIncEdgeArcLists(adaptor, n4, 1);
[414]961
962  checkNodeIds(adaptor);
963  checkArcIds(adaptor);
964  checkEdgeIds(adaptor);
965
966  checkGraphNodeMap(adaptor);
967  checkGraphArcMap(adaptor);
968  checkGraphEdgeMap(adaptor);
969
[463]970  // Hide a node
971  adaptor.status(n1, false);
972  adaptor.disable(n3);
973  if (!adaptor.status(n3)) adaptor.enable(n3);
[414]974
975  checkGraphNodeList(adaptor, 3);
976  checkGraphArcList(adaptor, 4);
977  checkGraphEdgeList(adaptor, 2);
978  checkGraphConArcList(adaptor, 4);
979  checkGraphConEdgeList(adaptor, 2);
980
[463]981  checkGraphIncEdgeArcLists(adaptor, n2, 1);
982  checkGraphIncEdgeArcLists(adaptor, n3, 2);
983  checkGraphIncEdgeArcLists(adaptor, n4, 1);
[414]984
985  checkNodeIds(adaptor);
986  checkArcIds(adaptor);
987  checkEdgeIds(adaptor);
988
989  checkGraphNodeMap(adaptor);
990  checkGraphArcMap(adaptor);
991  checkGraphEdgeMap(adaptor);
992
[463]993  // Hide all nodes and edges
[414]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);
[463]1010
1011  // Check the conversion of nodes and edges
1012  Graph::Node ng = n3;
[1197]1013  ::lemon::ignore_unused_variable_warning(ng);
[463]1014  ng = n4;
1015  Adaptor::Node na = n1;
[1197]1016  ::lemon::ignore_unused_variable_warning(na);
[463]1017  na = n2;
1018  Graph::Edge eg = e3;
[1197]1019  ::lemon::ignore_unused_variable_warning(eg);
[463]1020  eg = e4;
1021  Adaptor::Edge ea = e1;
[1197]1022  ::lemon::ignore_unused_variable_warning(ea);
[463]1023  ea = e2;
[414]1024}
1025
[416]1026void checkFilterNodes2() {
[463]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> >();
[414]1038
[463]1039  // Create a graph and an adaptor
[414]1040  typedef ListGraph Graph;
1041  typedef Graph::NodeMap<bool> NodeFilter;
[416]1042  typedef FilterNodes<Graph, NodeFilter> Adaptor;
[414]1043
[463]1044  // Add nodes and edges to the original graph and the adaptor
[414]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();
[463]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;
[414]1055
1056  Graph::Edge e1 = graph.addEdge(n1, n2);
1057  Graph::Edge e2 = graph.addEdge(n1, n3);
[463]1058  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
1059  Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
[440]1060
[414]1061  checkGraphNodeList(adaptor, 4);
1062  checkGraphArcList(adaptor, 8);
1063  checkGraphEdgeList(adaptor, 4);
1064  checkGraphConArcList(adaptor, 8);
1065  checkGraphConEdgeList(adaptor, 4);
1066
[463]1067  checkGraphIncEdgeArcLists(adaptor, n1, 2);
1068  checkGraphIncEdgeArcLists(adaptor, n2, 2);
1069  checkGraphIncEdgeArcLists(adaptor, n3, 3);
1070  checkGraphIncEdgeArcLists(adaptor, n4, 1);
[414]1071
1072  checkNodeIds(adaptor);
1073  checkArcIds(adaptor);
1074  checkEdgeIds(adaptor);
1075
1076  checkGraphNodeMap(adaptor);
1077  checkGraphArcMap(adaptor);
1078  checkGraphEdgeMap(adaptor);
1079
[463]1080  // Hide a node
1081  adaptor.status(n1, false);
1082  adaptor.disable(n3);
1083  if (!adaptor.status(n3)) adaptor.enable(n3);
[414]1084
1085  checkGraphNodeList(adaptor, 3);
1086  checkGraphArcList(adaptor, 4);
1087  checkGraphEdgeList(adaptor, 2);
1088  checkGraphConArcList(adaptor, 4);
1089  checkGraphConEdgeList(adaptor, 2);
1090
[463]1091  checkGraphIncEdgeArcLists(adaptor, n2, 1);
1092  checkGraphIncEdgeArcLists(adaptor, n3, 2);
1093  checkGraphIncEdgeArcLists(adaptor, n4, 1);
[414]1094
1095  checkNodeIds(adaptor);
1096  checkArcIds(adaptor);
1097  checkEdgeIds(adaptor);
1098
1099  checkGraphNodeMap(adaptor);
1100  checkGraphArcMap(adaptor);
1101  checkGraphEdgeMap(adaptor);
1102
[463]1103  // Hide all nodes
[414]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);
[463]1119
1120  // Check the conversion of nodes and edges
1121  Graph::Node ng = n3;
[1197]1122  ::lemon::ignore_unused_variable_warning(ng);
[463]1123  ng = n4;
1124  Adaptor::Node na = n1;
[1197]1125  ::lemon::ignore_unused_variable_warning(na);
[463]1126  na = n2;
1127  Graph::Edge eg = e3;
[1197]1128  ::lemon::ignore_unused_variable_warning(eg);
[463]1129  eg = e4;
1130  Adaptor::Edge ea = e1;
[1197]1131  ::lemon::ignore_unused_variable_warning(ea);
[463]1132  ea = e2;
[414]1133}
1134
[416]1135void checkFilterEdges() {
[463]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> >();
[414]1147
[463]1148  // Create a graph and an adaptor
[414]1149  typedef ListGraph Graph;
1150  typedef Graph::EdgeMap<bool> EdgeFilter;
[416]1151  typedef FilterEdges<Graph, EdgeFilter> Adaptor;
[414]1152
1153  Graph graph;
1154  EdgeFilter edge_filter(graph);
1155  Adaptor adaptor(graph, edge_filter);
1156
[463]1157  // Add nodes and edges to the original graph and the adaptor
[414]1158  Graph::Node n1 = graph.addNode();
1159  Graph::Node n2 = graph.addNode();
[463]1160  Adaptor::Node n3 = adaptor.addNode();
1161  Adaptor::Node n4 = adaptor.addNode();
[414]1162
1163  Graph::Edge e1 = graph.addEdge(n1, n2);
1164  Graph::Edge e2 = graph.addEdge(n1, n3);
[463]1165  Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
1166  Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
[414]1167
1168  edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
[440]1169
[414]1170  checkGraphNodeList(adaptor, 4);
1171  checkGraphArcList(adaptor, 8);
1172  checkGraphEdgeList(adaptor, 4);
1173  checkGraphConArcList(adaptor, 8);
1174  checkGraphConEdgeList(adaptor, 4);
1175
[463]1176  checkGraphIncEdgeArcLists(adaptor, n1, 2);
1177  checkGraphIncEdgeArcLists(adaptor, n2, 2);
1178  checkGraphIncEdgeArcLists(adaptor, n3, 3);
1179  checkGraphIncEdgeArcLists(adaptor, n4, 1);
[414]1180
1181  checkNodeIds(adaptor);
1182  checkArcIds(adaptor);
1183  checkEdgeIds(adaptor);
1184
1185  checkGraphNodeMap(adaptor);
1186  checkGraphArcMap(adaptor);
1187  checkGraphEdgeMap(adaptor);
1188
[463]1189  // Hide an edge
1190  adaptor.status(e2, false);
1191  adaptor.disable(e3);
1192  if (!adaptor.status(e3)) adaptor.enable(e3);
[414]1193
1194  checkGraphNodeList(adaptor, 4);
1195  checkGraphArcList(adaptor, 6);
1196  checkGraphEdgeList(adaptor, 3);
1197  checkGraphConArcList(adaptor, 6);
1198  checkGraphConEdgeList(adaptor, 3);
1199
[463]1200  checkGraphIncEdgeArcLists(adaptor, n1, 1);
1201  checkGraphIncEdgeArcLists(adaptor, n2, 2);
1202  checkGraphIncEdgeArcLists(adaptor, n3, 2);
1203  checkGraphIncEdgeArcLists(adaptor, n4, 1);
[414]1204
1205  checkNodeIds(adaptor);
1206  checkArcIds(adaptor);
1207  checkEdgeIds(adaptor);
1208
1209  checkGraphNodeMap(adaptor);
1210  checkGraphArcMap(adaptor);
1211  checkGraphEdgeMap(adaptor);
1212
[463]1213  // Hide all edges
[414]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);
[463]1229
1230  // Check the conversion of nodes and edges
1231  Graph::Node ng = n3;
[1197]1232  ::lemon::ignore_unused_variable_warning(ng);
[463]1233  ng = n4;
1234  Adaptor::Node na = n1;
[1197]1235  ::lemon::ignore_unused_variable_warning(na);
[463]1236  na = n2;
1237  Graph::Edge eg = e3;
[1197]1238  ::lemon::ignore_unused_variable_warning(eg);
[463]1239  eg = e4;
1240  Adaptor::Edge ea = e1;
[1197]1241  ::lemon::ignore_unused_variable_warning(ea);
[463]1242  ea = e2;
[414]1243}
1244
[416]1245void checkOrienter() {
[463]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> >();
[414]1257
[463]1258  // Create a graph and an adaptor
[414]1259  typedef ListGraph Graph;
1260  typedef ListGraph::EdgeMap<bool> DirMap;
[416]1261  typedef Orienter<Graph> Adaptor;
[414]1262
1263  Graph graph;
[463]1264  DirMap dir(graph);
[414]1265  Adaptor adaptor(graph, dir);
1266
[463]1267  // Add nodes and edges to the original graph and the adaptor
[414]1268  Graph::Node n1 = graph.addNode();
1269  Graph::Node n2 = graph.addNode();
[463]1270  Adaptor::Node n3 = adaptor.addNode();
[414]1271
1272  Graph::Edge e1 = graph.addEdge(n1, n2);
1273  Graph::Edge e2 = graph.addEdge(n1, n3);
[463]1274  Adaptor::Arc e3 = adaptor.addArc(n2, n3);
[416]1275
[463]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
[414]1298  checkGraphNodeList(adaptor, 3);
1299  checkGraphArcList(adaptor, 3);
1300  checkGraphConArcList(adaptor, 3);
[416]1301
[463]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
[414]1317  {
1318    dir[e1] = true;
1319    Adaptor::Node u = adaptor.source(e1);
1320    Adaptor::Node v = adaptor.target(e1);
[416]1321
[414]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);
[416]1334
[414]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);
[416]1347
[414]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
[463]1356  // Check the adaptor again
1357  checkGraphNodeList(adaptor, 3);
1358  checkGraphArcList(adaptor, 3);
1359  checkGraphConArcList(adaptor, 3);
1360
[414]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
[463]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;
[1197]1394  ::lemon::ignore_unused_variable_warning(ng);
[463]1395  ng = n3;
1396  Adaptor::Node na = n1;
[1197]1397  ::lemon::ignore_unused_variable_warning(na);
[463]1398  na = n2;
1399  Graph::Edge eg = e3;
[1197]1400  ::lemon::ignore_unused_variable_warning(eg);
[463]1401  eg = e3;
1402  Adaptor::Arc aa = e1;
[1197]1403  ::lemon::ignore_unused_variable_warning(aa);
[463]1404  aa = e2;
[414]1405}
1406
[463]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);
[515]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;
[463]1420
1421  // Apply several adaptors on the grid graph
[995]1422  typedef Orienter< const GridGraph, GridGraph::EdgeMap<bool> >
1423    OrientedGridGraph;
1424  typedef SplitNodes<OrientedGridGraph> SplitGridGraph;
[463]1425  typedef Undirector<const SplitGridGraph> USplitGridGraph;
1426  checkConcept<concepts::Digraph, SplitGridGraph>();
1427  checkConcept<concepts::Graph, USplitGridGraph>();
1428
[995]1429  OrientedGridGraph oadaptor = orienter(graph, dir_map);
1430  SplitGridGraph adaptor = splitNodes(oadaptor);
[463]1431  USplitGridGraph uadaptor = undirector(adaptor);
1432
1433  // Check adaptor
1434  checkGraphNodeList(adaptor, 8);
1435  checkGraphArcList(adaptor, 8);
1436  checkGraphConArcList(adaptor, 8);
1437
[515]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);
[463]1446
[515]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);
[463]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
[515]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);
[463]1485}
[414]1486
1487int main(int, const char **) {
[463]1488  // Check the digraph adaptors (using ListDigraph)
[416]1489  checkReverseDigraph();
1490  checkSubDigraph();
1491  checkFilterNodes1();
1492  checkFilterArcs();
1493  checkUndirector();
[464]1494  checkResidualDigraph();
[416]1495  checkSplitNodes();
[414]1496
[463]1497  // Check the graph adaptors (using ListGraph)
[416]1498  checkSubGraph();
1499  checkFilterNodes2();
1500  checkFilterEdges();
1501  checkOrienter();
[414]1502
[463]1503  // Combine adaptors (using GridGraph)
1504  checkCombiningAdaptors();
1505
[414]1506  return 0;
1507}
Note: See TracBrowser for help on using the repository browser.