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 @ 663:8b0df68370a4

Last change on this file since 663:8b0df68370a4 was 465:2b5496c62ccd, checked in by Peter Kovacs <kpeter@…>, 16 years ago

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