COIN-OR::LEMON - Graph Library

source: lemon-main/test/adaptors_test.cc @ 1092:dceba191c00d

Last change on this file since 1092:dceba191c00d was 1092:dceba191c00d, checked in by Alpar Juttner <alpar@…>, 11 years ago

Apply unify-sources.sh to the source tree

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