1.1 --- a/test/CMakeLists.txt Mon Jan 12 08:05:30 2009 +0100
1.2 +++ b/test/CMakeLists.txt Mon Jan 12 08:18:04 2009 +0100
1.3 @@ -3,6 +3,7 @@
1.4 LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
1.5
1.6 SET(TESTS
1.7 + adaptors_test
1.8 bfs_test
1.9 circulation_test
1.10 counter_test
1.11 @@ -11,7 +12,6 @@
1.12 dijkstra_test
1.13 dim_test
1.14 error_test
1.15 - graph_adaptor_test
1.16 graph_copy_test
1.17 graph_test
1.18 graph_utils_test
2.1 --- a/test/Makefile.am Mon Jan 12 08:05:30 2009 +0100
2.2 +++ b/test/Makefile.am Mon Jan 12 08:18:04 2009 +0100
2.3 @@ -6,6 +6,7 @@
2.4 test/test_tools.h
2.5
2.6 check_PROGRAMS += \
2.7 + test/adaptors_test \
2.8 test/bfs_test \
2.9 test/circulation_test \
2.10 test/counter_test \
2.11 @@ -14,7 +15,6 @@
2.12 test/dijkstra_test \
2.13 test/dim_test \
2.14 test/error_test \
2.15 - test/graph_adaptor_test \
2.16 test/graph_copy_test \
2.17 test/graph_test \
2.18 test/graph_utils_test \
2.19 @@ -36,6 +36,7 @@
2.20 TESTS += $(check_PROGRAMS)
2.21 XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
2.22
2.23 +test_adaptors_test_SOURCES = test/adaptors_test.cc
2.24 test_bfs_test_SOURCES = test/bfs_test.cc
2.25 test_circulation_test_SOURCES = test/circulation_test.cc
2.26 test_counter_test_SOURCES = test/counter_test.cc
2.27 @@ -44,7 +45,6 @@
2.28 test_dijkstra_test_SOURCES = test/dijkstra_test.cc
2.29 test_dim_test_SOURCES = test/dim_test.cc
2.30 test_error_test_SOURCES = test/error_test.cc
2.31 -test_graph_adaptor_test_SOURCES = test/graph_adaptor_test.cc
2.32 test_graph_copy_test_SOURCES = test/graph_copy_test.cc
2.33 test_graph_test_SOURCES = test/graph_test.cc
2.34 test_graph_utils_test_SOURCES = test/graph_utils_test.cc
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/test/adaptors_test.cc Mon Jan 12 08:18:04 2009 +0100
3.3 @@ -0,0 +1,1486 @@
3.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
3.5 + *
3.6 + * This file is a part of LEMON, a generic C++ optimization library.
3.7 + *
3.8 + * Copyright (C) 2003-2009
3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 + *
3.12 + * Permission to use, modify and distribute this software is granted
3.13 + * provided that this copyright notice appears in all copies. For
3.14 + * precise terms see the accompanying LICENSE file.
3.15 + *
3.16 + * This software is provided "AS IS" with no warranty of any kind,
3.17 + * express or implied, and with no claim as to its suitability for any
3.18 + * purpose.
3.19 + *
3.20 + */
3.21 +
3.22 +#include <iostream>
3.23 +#include <limits>
3.24 +
3.25 +#include <lemon/list_graph.h>
3.26 +#include <lemon/grid_graph.h>
3.27 +#include <lemon/bfs.h>
3.28 +#include <lemon/path.h>
3.29 +
3.30 +#include <lemon/concepts/digraph.h>
3.31 +#include <lemon/concepts/graph.h>
3.32 +#include <lemon/concepts/graph_components.h>
3.33 +#include <lemon/concepts/maps.h>
3.34 +#include <lemon/concept_check.h>
3.35 +
3.36 +#include <lemon/adaptors.h>
3.37 +
3.38 +#include "test/test_tools.h"
3.39 +#include "test/graph_test.h"
3.40 +
3.41 +using namespace lemon;
3.42 +
3.43 +void checkReverseDigraph() {
3.44 + // Check concepts
3.45 + checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
3.46 + checkConcept<concepts::Digraph, ReverseDigraph<ListDigraph> >();
3.47 + checkConcept<concepts::AlterableDigraphComponent<>,
3.48 + ReverseDigraph<ListDigraph> >();
3.49 + checkConcept<concepts::ExtendableDigraphComponent<>,
3.50 + ReverseDigraph<ListDigraph> >();
3.51 + checkConcept<concepts::ErasableDigraphComponent<>,
3.52 + ReverseDigraph<ListDigraph> >();
3.53 + checkConcept<concepts::ClearableDigraphComponent<>,
3.54 + ReverseDigraph<ListDigraph> >();
3.55 +
3.56 + // Create a digraph and an adaptor
3.57 + typedef ListDigraph Digraph;
3.58 + typedef ReverseDigraph<Digraph> Adaptor;
3.59 +
3.60 + Digraph digraph;
3.61 + Adaptor adaptor(digraph);
3.62 +
3.63 + // Add nodes and arcs to the original digraph
3.64 + Digraph::Node n1 = digraph.addNode();
3.65 + Digraph::Node n2 = digraph.addNode();
3.66 + Digraph::Node n3 = digraph.addNode();
3.67 +
3.68 + Digraph::Arc a1 = digraph.addArc(n1, n2);
3.69 + Digraph::Arc a2 = digraph.addArc(n1, n3);
3.70 + Digraph::Arc a3 = digraph.addArc(n2, n3);
3.71 +
3.72 + // Check the adaptor
3.73 + checkGraphNodeList(adaptor, 3);
3.74 + checkGraphArcList(adaptor, 3);
3.75 + checkGraphConArcList(adaptor, 3);
3.76 +
3.77 + checkGraphOutArcList(adaptor, n1, 0);
3.78 + checkGraphOutArcList(adaptor, n2, 1);
3.79 + checkGraphOutArcList(adaptor, n3, 2);
3.80 +
3.81 + checkGraphInArcList(adaptor, n1, 2);
3.82 + checkGraphInArcList(adaptor, n2, 1);
3.83 + checkGraphInArcList(adaptor, n3, 0);
3.84 +
3.85 + checkNodeIds(adaptor);
3.86 + checkArcIds(adaptor);
3.87 +
3.88 + checkGraphNodeMap(adaptor);
3.89 + checkGraphArcMap(adaptor);
3.90 +
3.91 + // Check the orientation of the arcs
3.92 + for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
3.93 + check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
3.94 + check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
3.95 + }
3.96 +
3.97 + // Add and erase nodes and arcs in the digraph through the adaptor
3.98 + Adaptor::Node n4 = adaptor.addNode();
3.99 +
3.100 + Adaptor::Arc a4 = adaptor.addArc(n4, n3);
3.101 + Adaptor::Arc a5 = adaptor.addArc(n2, n4);
3.102 + Adaptor::Arc a6 = adaptor.addArc(n2, n4);
3.103 + Adaptor::Arc a7 = adaptor.addArc(n1, n4);
3.104 + Adaptor::Arc a8 = adaptor.addArc(n1, n2);
3.105 +
3.106 + adaptor.erase(a1);
3.107 + adaptor.erase(n3);
3.108 +
3.109 + // Check the adaptor
3.110 + checkGraphNodeList(adaptor, 3);
3.111 + checkGraphArcList(adaptor, 4);
3.112 + checkGraphConArcList(adaptor, 4);
3.113 +
3.114 + checkGraphOutArcList(adaptor, n1, 2);
3.115 + checkGraphOutArcList(adaptor, n2, 2);
3.116 + checkGraphOutArcList(adaptor, n4, 0);
3.117 +
3.118 + checkGraphInArcList(adaptor, n1, 0);
3.119 + checkGraphInArcList(adaptor, n2, 1);
3.120 + checkGraphInArcList(adaptor, n4, 3);
3.121 +
3.122 + checkNodeIds(adaptor);
3.123 + checkArcIds(adaptor);
3.124 +
3.125 + checkGraphNodeMap(adaptor);
3.126 + checkGraphArcMap(adaptor);
3.127 +
3.128 + // Check the digraph
3.129 + checkGraphNodeList(digraph, 3);
3.130 + checkGraphArcList(digraph, 4);
3.131 + checkGraphConArcList(digraph, 4);
3.132 +
3.133 + checkGraphOutArcList(digraph, n1, 0);
3.134 + checkGraphOutArcList(digraph, n2, 1);
3.135 + checkGraphOutArcList(digraph, n4, 3);
3.136 +
3.137 + checkGraphInArcList(digraph, n1, 2);
3.138 + checkGraphInArcList(digraph, n2, 2);
3.139 + checkGraphInArcList(digraph, n4, 0);
3.140 +
3.141 + checkNodeIds(digraph);
3.142 + checkArcIds(digraph);
3.143 +
3.144 + checkGraphNodeMap(digraph);
3.145 + checkGraphArcMap(digraph);
3.146 +
3.147 + // Check the conversion of nodes and arcs
3.148 + Digraph::Node nd = n4;
3.149 + nd = n4;
3.150 + Adaptor::Node na = n1;
3.151 + na = n2;
3.152 + Digraph::Arc ad = a4;
3.153 + ad = a5;
3.154 + Adaptor::Arc aa = a1;
3.155 + aa = a2;
3.156 +}
3.157 +
3.158 +void checkSubDigraph() {
3.159 + // Check concepts
3.160 + checkConcept<concepts::Digraph, SubDigraph<concepts::Digraph> >();
3.161 + checkConcept<concepts::Digraph, SubDigraph<ListDigraph> >();
3.162 + checkConcept<concepts::AlterableDigraphComponent<>,
3.163 + SubDigraph<ListDigraph> >();
3.164 + checkConcept<concepts::ExtendableDigraphComponent<>,
3.165 + SubDigraph<ListDigraph> >();
3.166 + checkConcept<concepts::ErasableDigraphComponent<>,
3.167 + SubDigraph<ListDigraph> >();
3.168 + checkConcept<concepts::ClearableDigraphComponent<>,
3.169 + SubDigraph<ListDigraph> >();
3.170 +
3.171 + // Create a digraph and an adaptor
3.172 + typedef ListDigraph Digraph;
3.173 + typedef Digraph::NodeMap<bool> NodeFilter;
3.174 + typedef Digraph::ArcMap<bool> ArcFilter;
3.175 + typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
3.176 +
3.177 + Digraph digraph;
3.178 + NodeFilter node_filter(digraph);
3.179 + ArcFilter arc_filter(digraph);
3.180 + Adaptor adaptor(digraph, node_filter, arc_filter);
3.181 +
3.182 + // Add nodes and arcs to the original digraph and the adaptor
3.183 + Digraph::Node n1 = digraph.addNode();
3.184 + Digraph::Node n2 = digraph.addNode();
3.185 + Adaptor::Node n3 = adaptor.addNode();
3.186 +
3.187 + node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
3.188 +
3.189 + Digraph::Arc a1 = digraph.addArc(n1, n2);
3.190 + Digraph::Arc a2 = digraph.addArc(n1, n3);
3.191 + Adaptor::Arc a3 = adaptor.addArc(n2, n3);
3.192 +
3.193 + arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
3.194 +
3.195 + checkGraphNodeList(adaptor, 3);
3.196 + checkGraphArcList(adaptor, 3);
3.197 + checkGraphConArcList(adaptor, 3);
3.198 +
3.199 + checkGraphOutArcList(adaptor, n1, 2);
3.200 + checkGraphOutArcList(adaptor, n2, 1);
3.201 + checkGraphOutArcList(adaptor, n3, 0);
3.202 +
3.203 + checkGraphInArcList(adaptor, n1, 0);
3.204 + checkGraphInArcList(adaptor, n2, 1);
3.205 + checkGraphInArcList(adaptor, n3, 2);
3.206 +
3.207 + checkNodeIds(adaptor);
3.208 + checkArcIds(adaptor);
3.209 +
3.210 + checkGraphNodeMap(adaptor);
3.211 + checkGraphArcMap(adaptor);
3.212 +
3.213 + // Hide an arc
3.214 + adaptor.status(a2, false);
3.215 + adaptor.disable(a3);
3.216 + if (!adaptor.status(a3)) adaptor.enable(a3);
3.217 +
3.218 + checkGraphNodeList(adaptor, 3);
3.219 + checkGraphArcList(adaptor, 2);
3.220 + checkGraphConArcList(adaptor, 2);
3.221 +
3.222 + checkGraphOutArcList(adaptor, n1, 1);
3.223 + checkGraphOutArcList(adaptor, n2, 1);
3.224 + checkGraphOutArcList(adaptor, n3, 0);
3.225 +
3.226 + checkGraphInArcList(adaptor, n1, 0);
3.227 + checkGraphInArcList(adaptor, n2, 1);
3.228 + checkGraphInArcList(adaptor, n3, 1);
3.229 +
3.230 + checkNodeIds(adaptor);
3.231 + checkArcIds(adaptor);
3.232 +
3.233 + checkGraphNodeMap(adaptor);
3.234 + checkGraphArcMap(adaptor);
3.235 +
3.236 + // Hide a node
3.237 + adaptor.status(n1, false);
3.238 + adaptor.disable(n3);
3.239 + if (!adaptor.status(n3)) adaptor.enable(n3);
3.240 +
3.241 + checkGraphNodeList(adaptor, 2);
3.242 + checkGraphArcList(adaptor, 1);
3.243 + checkGraphConArcList(adaptor, 1);
3.244 +
3.245 + checkGraphOutArcList(adaptor, n2, 1);
3.246 + checkGraphOutArcList(adaptor, n3, 0);
3.247 +
3.248 + checkGraphInArcList(adaptor, n2, 0);
3.249 + checkGraphInArcList(adaptor, n3, 1);
3.250 +
3.251 + checkNodeIds(adaptor);
3.252 + checkArcIds(adaptor);
3.253 +
3.254 + checkGraphNodeMap(adaptor);
3.255 + checkGraphArcMap(adaptor);
3.256 +
3.257 + // Hide all nodes and arcs
3.258 + node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
3.259 + arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
3.260 +
3.261 + checkGraphNodeList(adaptor, 0);
3.262 + checkGraphArcList(adaptor, 0);
3.263 + checkGraphConArcList(adaptor, 0);
3.264 +
3.265 + checkNodeIds(adaptor);
3.266 + checkArcIds(adaptor);
3.267 +
3.268 + checkGraphNodeMap(adaptor);
3.269 + checkGraphArcMap(adaptor);
3.270 +
3.271 + // Check the conversion of nodes and arcs
3.272 + Digraph::Node nd = n3;
3.273 + nd = n3;
3.274 + Adaptor::Node na = n1;
3.275 + na = n2;
3.276 + Digraph::Arc ad = a3;
3.277 + ad = a3;
3.278 + Adaptor::Arc aa = a1;
3.279 + aa = a2;
3.280 +}
3.281 +
3.282 +void checkFilterNodes1() {
3.283 + // Check concepts
3.284 + checkConcept<concepts::Digraph, FilterNodes<concepts::Digraph> >();
3.285 + checkConcept<concepts::Digraph, FilterNodes<ListDigraph> >();
3.286 + checkConcept<concepts::AlterableDigraphComponent<>,
3.287 + FilterNodes<ListDigraph> >();
3.288 + checkConcept<concepts::ExtendableDigraphComponent<>,
3.289 + FilterNodes<ListDigraph> >();
3.290 + checkConcept<concepts::ErasableDigraphComponent<>,
3.291 + FilterNodes<ListDigraph> >();
3.292 + checkConcept<concepts::ClearableDigraphComponent<>,
3.293 + FilterNodes<ListDigraph> >();
3.294 +
3.295 + // Create a digraph and an adaptor
3.296 + typedef ListDigraph Digraph;
3.297 + typedef Digraph::NodeMap<bool> NodeFilter;
3.298 + typedef FilterNodes<Digraph, NodeFilter> Adaptor;
3.299 +
3.300 + Digraph digraph;
3.301 + NodeFilter node_filter(digraph);
3.302 + Adaptor adaptor(digraph, node_filter);
3.303 +
3.304 + // Add nodes and arcs to the original digraph and the adaptor
3.305 + Digraph::Node n1 = digraph.addNode();
3.306 + Digraph::Node n2 = digraph.addNode();
3.307 + Adaptor::Node n3 = adaptor.addNode();
3.308 +
3.309 + node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
3.310 +
3.311 + Digraph::Arc a1 = digraph.addArc(n1, n2);
3.312 + Digraph::Arc a2 = digraph.addArc(n1, n3);
3.313 + Adaptor::Arc a3 = adaptor.addArc(n2, n3);
3.314 +
3.315 + checkGraphNodeList(adaptor, 3);
3.316 + checkGraphArcList(adaptor, 3);
3.317 + checkGraphConArcList(adaptor, 3);
3.318 +
3.319 + checkGraphOutArcList(adaptor, n1, 2);
3.320 + checkGraphOutArcList(adaptor, n2, 1);
3.321 + checkGraphOutArcList(adaptor, n3, 0);
3.322 +
3.323 + checkGraphInArcList(adaptor, n1, 0);
3.324 + checkGraphInArcList(adaptor, n2, 1);
3.325 + checkGraphInArcList(adaptor, n3, 2);
3.326 +
3.327 + checkNodeIds(adaptor);
3.328 + checkArcIds(adaptor);
3.329 +
3.330 + checkGraphNodeMap(adaptor);
3.331 + checkGraphArcMap(adaptor);
3.332 +
3.333 + // Hide a node
3.334 + adaptor.status(n1, false);
3.335 + adaptor.disable(n3);
3.336 + if (!adaptor.status(n3)) adaptor.enable(n3);
3.337 +
3.338 + checkGraphNodeList(adaptor, 2);
3.339 + checkGraphArcList(adaptor, 1);
3.340 + checkGraphConArcList(adaptor, 1);
3.341 +
3.342 + checkGraphOutArcList(adaptor, n2, 1);
3.343 + checkGraphOutArcList(adaptor, n3, 0);
3.344 +
3.345 + checkGraphInArcList(adaptor, n2, 0);
3.346 + checkGraphInArcList(adaptor, n3, 1);
3.347 +
3.348 + checkNodeIds(adaptor);
3.349 + checkArcIds(adaptor);
3.350 +
3.351 + checkGraphNodeMap(adaptor);
3.352 + checkGraphArcMap(adaptor);
3.353 +
3.354 + // Hide all nodes
3.355 + node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
3.356 +
3.357 + checkGraphNodeList(adaptor, 0);
3.358 + checkGraphArcList(adaptor, 0);
3.359 + checkGraphConArcList(adaptor, 0);
3.360 +
3.361 + checkNodeIds(adaptor);
3.362 + checkArcIds(adaptor);
3.363 +
3.364 + checkGraphNodeMap(adaptor);
3.365 + checkGraphArcMap(adaptor);
3.366 +
3.367 + // Check the conversion of nodes and arcs
3.368 + Digraph::Node nd = n3;
3.369 + nd = n3;
3.370 + Adaptor::Node na = n1;
3.371 + na = n2;
3.372 + Digraph::Arc ad = a3;
3.373 + ad = a3;
3.374 + Adaptor::Arc aa = a1;
3.375 + aa = a2;
3.376 +}
3.377 +
3.378 +void checkFilterArcs() {
3.379 + // Check concepts
3.380 + checkConcept<concepts::Digraph, FilterArcs<concepts::Digraph> >();
3.381 + checkConcept<concepts::Digraph, FilterArcs<ListDigraph> >();
3.382 + checkConcept<concepts::AlterableDigraphComponent<>,
3.383 + FilterArcs<ListDigraph> >();
3.384 + checkConcept<concepts::ExtendableDigraphComponent<>,
3.385 + FilterArcs<ListDigraph> >();
3.386 + checkConcept<concepts::ErasableDigraphComponent<>,
3.387 + FilterArcs<ListDigraph> >();
3.388 + checkConcept<concepts::ClearableDigraphComponent<>,
3.389 + FilterArcs<ListDigraph> >();
3.390 +
3.391 + // Create a digraph and an adaptor
3.392 + typedef ListDigraph Digraph;
3.393 + typedef Digraph::ArcMap<bool> ArcFilter;
3.394 + typedef FilterArcs<Digraph, ArcFilter> Adaptor;
3.395 +
3.396 + Digraph digraph;
3.397 + ArcFilter arc_filter(digraph);
3.398 + Adaptor adaptor(digraph, arc_filter);
3.399 +
3.400 + // Add nodes and arcs to the original digraph and the adaptor
3.401 + Digraph::Node n1 = digraph.addNode();
3.402 + Digraph::Node n2 = digraph.addNode();
3.403 + Adaptor::Node n3 = adaptor.addNode();
3.404 +
3.405 + Digraph::Arc a1 = digraph.addArc(n1, n2);
3.406 + Digraph::Arc a2 = digraph.addArc(n1, n3);
3.407 + Adaptor::Arc a3 = adaptor.addArc(n2, n3);
3.408 +
3.409 + arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
3.410 +
3.411 + checkGraphNodeList(adaptor, 3);
3.412 + checkGraphArcList(adaptor, 3);
3.413 + checkGraphConArcList(adaptor, 3);
3.414 +
3.415 + checkGraphOutArcList(adaptor, n1, 2);
3.416 + checkGraphOutArcList(adaptor, n2, 1);
3.417 + checkGraphOutArcList(adaptor, n3, 0);
3.418 +
3.419 + checkGraphInArcList(adaptor, n1, 0);
3.420 + checkGraphInArcList(adaptor, n2, 1);
3.421 + checkGraphInArcList(adaptor, n3, 2);
3.422 +
3.423 + checkNodeIds(adaptor);
3.424 + checkArcIds(adaptor);
3.425 +
3.426 + checkGraphNodeMap(adaptor);
3.427 + checkGraphArcMap(adaptor);
3.428 +
3.429 + // Hide an arc
3.430 + adaptor.status(a2, false);
3.431 + adaptor.disable(a3);
3.432 + if (!adaptor.status(a3)) adaptor.enable(a3);
3.433 +
3.434 + checkGraphNodeList(adaptor, 3);
3.435 + checkGraphArcList(adaptor, 2);
3.436 + checkGraphConArcList(adaptor, 2);
3.437 +
3.438 + checkGraphOutArcList(adaptor, n1, 1);
3.439 + checkGraphOutArcList(adaptor, n2, 1);
3.440 + checkGraphOutArcList(adaptor, n3, 0);
3.441 +
3.442 + checkGraphInArcList(adaptor, n1, 0);
3.443 + checkGraphInArcList(adaptor, n2, 1);
3.444 + checkGraphInArcList(adaptor, n3, 1);
3.445 +
3.446 + checkNodeIds(adaptor);
3.447 + checkArcIds(adaptor);
3.448 +
3.449 + checkGraphNodeMap(adaptor);
3.450 + checkGraphArcMap(adaptor);
3.451 +
3.452 + // Hide all arcs
3.453 + arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
3.454 +
3.455 + checkGraphNodeList(adaptor, 3);
3.456 + checkGraphArcList(adaptor, 0);
3.457 + checkGraphConArcList(adaptor, 0);
3.458 +
3.459 + checkNodeIds(adaptor);
3.460 + checkArcIds(adaptor);
3.461 +
3.462 + checkGraphNodeMap(adaptor);
3.463 + checkGraphArcMap(adaptor);
3.464 +
3.465 + // Check the conversion of nodes and arcs
3.466 + Digraph::Node nd = n3;
3.467 + nd = n3;
3.468 + Adaptor::Node na = n1;
3.469 + na = n2;
3.470 + Digraph::Arc ad = a3;
3.471 + ad = a3;
3.472 + Adaptor::Arc aa = a1;
3.473 + aa = a2;
3.474 +}
3.475 +
3.476 +void checkUndirector() {
3.477 + // Check concepts
3.478 + checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
3.479 + checkConcept<concepts::Graph, Undirector<ListDigraph> >();
3.480 + checkConcept<concepts::AlterableGraphComponent<>,
3.481 + Undirector<ListDigraph> >();
3.482 + checkConcept<concepts::ExtendableGraphComponent<>,
3.483 + Undirector<ListDigraph> >();
3.484 + checkConcept<concepts::ErasableGraphComponent<>,
3.485 + Undirector<ListDigraph> >();
3.486 + checkConcept<concepts::ClearableGraphComponent<>,
3.487 + Undirector<ListDigraph> >();
3.488 +
3.489 +
3.490 + // Create a digraph and an adaptor
3.491 + typedef ListDigraph Digraph;
3.492 + typedef Undirector<Digraph> Adaptor;
3.493 +
3.494 + Digraph digraph;
3.495 + Adaptor adaptor(digraph);
3.496 +
3.497 + // Add nodes and arcs/edges to the original digraph and the adaptor
3.498 + Digraph::Node n1 = digraph.addNode();
3.499 + Digraph::Node n2 = digraph.addNode();
3.500 + Adaptor::Node n3 = adaptor.addNode();
3.501 +
3.502 + Digraph::Arc a1 = digraph.addArc(n1, n2);
3.503 + Digraph::Arc a2 = digraph.addArc(n1, n3);
3.504 + Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
3.505 +
3.506 + // Check the original digraph
3.507 + checkGraphNodeList(digraph, 3);
3.508 + checkGraphArcList(digraph, 3);
3.509 + checkGraphConArcList(digraph, 3);
3.510 +
3.511 + checkGraphOutArcList(digraph, n1, 2);
3.512 + checkGraphOutArcList(digraph, n2, 1);
3.513 + checkGraphOutArcList(digraph, n3, 0);
3.514 +
3.515 + checkGraphInArcList(digraph, n1, 0);
3.516 + checkGraphInArcList(digraph, n2, 1);
3.517 + checkGraphInArcList(digraph, n3, 2);
3.518 +
3.519 + checkNodeIds(digraph);
3.520 + checkArcIds(digraph);
3.521 +
3.522 + checkGraphNodeMap(digraph);
3.523 + checkGraphArcMap(digraph);
3.524 +
3.525 + // Check the adaptor
3.526 + checkGraphNodeList(adaptor, 3);
3.527 + checkGraphArcList(adaptor, 6);
3.528 + checkGraphEdgeList(adaptor, 3);
3.529 + checkGraphConArcList(adaptor, 6);
3.530 + checkGraphConEdgeList(adaptor, 3);
3.531 +
3.532 + checkGraphIncEdgeArcLists(adaptor, n1, 2);
3.533 + checkGraphIncEdgeArcLists(adaptor, n2, 2);
3.534 + checkGraphIncEdgeArcLists(adaptor, n3, 2);
3.535 +
3.536 + checkNodeIds(adaptor);
3.537 + checkArcIds(adaptor);
3.538 + checkEdgeIds(adaptor);
3.539 +
3.540 + checkGraphNodeMap(adaptor);
3.541 + checkGraphArcMap(adaptor);
3.542 + checkGraphEdgeMap(adaptor);
3.543 +
3.544 + // Check the edges of the adaptor
3.545 + for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {
3.546 + check(adaptor.u(e) == digraph.source(e), "Wrong undir");
3.547 + check(adaptor.v(e) == digraph.target(e), "Wrong undir");
3.548 + }
3.549 +
3.550 + // Check CombinedArcMap
3.551 + typedef Adaptor::CombinedArcMap
3.552 + <Digraph::ArcMap<int>, Digraph::ArcMap<int> > IntCombinedMap;
3.553 + typedef Adaptor::CombinedArcMap
3.554 + <Digraph::ArcMap<bool>, Digraph::ArcMap<bool> > BoolCombinedMap;
3.555 + checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,
3.556 + IntCombinedMap>();
3.557 + checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,
3.558 + BoolCombinedMap>();
3.559 +
3.560 + Digraph::ArcMap<int> fw_map(digraph), bk_map(digraph);
3.561 + for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
3.562 + fw_map[a] = digraph.id(a);
3.563 + bk_map[a] = -digraph.id(a);
3.564 + }
3.565 +
3.566 + Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::ArcMap<int> >
3.567 + comb_map(fw_map, bk_map);
3.568 + for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
3.569 + if (adaptor.source(a) == digraph.source(a)) {
3.570 + check(comb_map[a] == fw_map[a], "Wrong combined map");
3.571 + } else {
3.572 + check(comb_map[a] == bk_map[a], "Wrong combined map");
3.573 + }
3.574 + }
3.575 +
3.576 + // Check the conversion of nodes and arcs/edges
3.577 + Digraph::Node nd = n3;
3.578 + nd = n3;
3.579 + Adaptor::Node na = n1;
3.580 + na = n2;
3.581 + Digraph::Arc ad = e3;
3.582 + ad = e3;
3.583 + Adaptor::Edge ea = a1;
3.584 + ea = a2;
3.585 +}
3.586 +
3.587 +void checkResidualDigraph() {
3.588 + // Check concepts
3.589 + checkConcept<concepts::Digraph, ResidualDigraph<concepts::Digraph> >();
3.590 + checkConcept<concepts::Digraph, ResidualDigraph<ListDigraph> >();
3.591 +
3.592 + // Create a digraph and an adaptor
3.593 + typedef ListDigraph Digraph;
3.594 + typedef Digraph::ArcMap<int> IntArcMap;
3.595 + typedef ResidualDigraph<Digraph, IntArcMap> Adaptor;
3.596 +
3.597 + Digraph digraph;
3.598 + IntArcMap capacity(digraph), flow(digraph);
3.599 + Adaptor adaptor(digraph, capacity, flow);
3.600 +
3.601 + Digraph::Node n1 = digraph.addNode();
3.602 + Digraph::Node n2 = digraph.addNode();
3.603 + Digraph::Node n3 = digraph.addNode();
3.604 + Digraph::Node n4 = digraph.addNode();
3.605 +
3.606 + Digraph::Arc a1 = digraph.addArc(n1, n2);
3.607 + Digraph::Arc a2 = digraph.addArc(n1, n3);
3.608 + Digraph::Arc a3 = digraph.addArc(n1, n4);
3.609 + Digraph::Arc a4 = digraph.addArc(n2, n3);
3.610 + Digraph::Arc a5 = digraph.addArc(n2, n4);
3.611 + Digraph::Arc a6 = digraph.addArc(n3, n4);
3.612 +
3.613 + capacity[a1] = 8;
3.614 + capacity[a2] = 6;
3.615 + capacity[a3] = 4;
3.616 + capacity[a4] = 4;
3.617 + capacity[a5] = 6;
3.618 + capacity[a6] = 10;
3.619 +
3.620 + // Check the adaptor with various flow values
3.621 + for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
3.622 + flow[a] = 0;
3.623 + }
3.624 +
3.625 + checkGraphNodeList(adaptor, 4);
3.626 + checkGraphArcList(adaptor, 6);
3.627 + checkGraphConArcList(adaptor, 6);
3.628 +
3.629 + checkGraphOutArcList(adaptor, n1, 3);
3.630 + checkGraphOutArcList(adaptor, n2, 2);
3.631 + checkGraphOutArcList(adaptor, n3, 1);
3.632 + checkGraphOutArcList(adaptor, n4, 0);
3.633 +
3.634 + checkGraphInArcList(adaptor, n1, 0);
3.635 + checkGraphInArcList(adaptor, n2, 1);
3.636 + checkGraphInArcList(adaptor, n3, 2);
3.637 + checkGraphInArcList(adaptor, n4, 3);
3.638 +
3.639 + for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
3.640 + flow[a] = capacity[a] / 2;
3.641 + }
3.642 +
3.643 + checkGraphNodeList(adaptor, 4);
3.644 + checkGraphArcList(adaptor, 12);
3.645 + checkGraphConArcList(adaptor, 12);
3.646 +
3.647 + checkGraphOutArcList(adaptor, n1, 3);
3.648 + checkGraphOutArcList(adaptor, n2, 3);
3.649 + checkGraphOutArcList(adaptor, n3, 3);
3.650 + checkGraphOutArcList(adaptor, n4, 3);
3.651 +
3.652 + checkGraphInArcList(adaptor, n1, 3);
3.653 + checkGraphInArcList(adaptor, n2, 3);
3.654 + checkGraphInArcList(adaptor, n3, 3);
3.655 + checkGraphInArcList(adaptor, n4, 3);
3.656 +
3.657 + checkNodeIds(adaptor);
3.658 + checkArcIds(adaptor);
3.659 +
3.660 + checkGraphNodeMap(adaptor);
3.661 + checkGraphArcMap(adaptor);
3.662 +
3.663 + for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
3.664 + flow[a] = capacity[a];
3.665 + }
3.666 +
3.667 + checkGraphNodeList(adaptor, 4);
3.668 + checkGraphArcList(adaptor, 6);
3.669 + checkGraphConArcList(adaptor, 6);
3.670 +
3.671 + checkGraphOutArcList(adaptor, n1, 0);
3.672 + checkGraphOutArcList(adaptor, n2, 1);
3.673 + checkGraphOutArcList(adaptor, n3, 2);
3.674 + checkGraphOutArcList(adaptor, n4, 3);
3.675 +
3.676 + checkGraphInArcList(adaptor, n1, 3);
3.677 + checkGraphInArcList(adaptor, n2, 2);
3.678 + checkGraphInArcList(adaptor, n3, 1);
3.679 + checkGraphInArcList(adaptor, n4, 0);
3.680 +
3.681 + // Saturate all backward arcs
3.682 + // (set the flow to zero on all forward arcs)
3.683 + for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
3.684 + if (adaptor.backward(a))
3.685 + adaptor.augment(a, adaptor.residualCapacity(a));
3.686 + }
3.687 +
3.688 + checkGraphNodeList(adaptor, 4);
3.689 + checkGraphArcList(adaptor, 6);
3.690 + checkGraphConArcList(adaptor, 6);
3.691 +
3.692 + checkGraphOutArcList(adaptor, n1, 3);
3.693 + checkGraphOutArcList(adaptor, n2, 2);
3.694 + checkGraphOutArcList(adaptor, n3, 1);
3.695 + checkGraphOutArcList(adaptor, n4, 0);
3.696 +
3.697 + checkGraphInArcList(adaptor, n1, 0);
3.698 + checkGraphInArcList(adaptor, n2, 1);
3.699 + checkGraphInArcList(adaptor, n3, 2);
3.700 + checkGraphInArcList(adaptor, n4, 3);
3.701 +
3.702 + // Find maximum flow by augmenting along shortest paths
3.703 + int flow_value = 0;
3.704 + Adaptor::ResidualCapacity res_cap(adaptor);
3.705 + while (true) {
3.706 +
3.707 + Bfs<Adaptor> bfs(adaptor);
3.708 + bfs.run(n1, n4);
3.709 +
3.710 + if (!bfs.reached(n4)) break;
3.711 +
3.712 + Path<Adaptor> p = bfs.path(n4);
3.713 +
3.714 + int min = std::numeric_limits<int>::max();
3.715 + for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
3.716 + if (res_cap[a] < min) min = res_cap[a];
3.717 + }
3.718 +
3.719 + for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
3.720 + adaptor.augment(a, min);
3.721 + }
3.722 + flow_value += min;
3.723 + }
3.724 +
3.725 + check(flow_value == 18, "Wrong flow with res graph adaptor");
3.726 +
3.727 + // Check forward() and backward()
3.728 + for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
3.729 + check(adaptor.forward(a) != adaptor.backward(a),
3.730 + "Wrong forward() or backward()");
3.731 + check((adaptor.forward(a) && adaptor.forward(Digraph::Arc(a)) == a) ||
3.732 + (adaptor.backward(a) && adaptor.backward(Digraph::Arc(a)) == a),
3.733 + "Wrong forward() or backward()");
3.734 + }
3.735 +
3.736 + // Check the conversion of nodes and arcs
3.737 + Digraph::Node nd = Adaptor::NodeIt(adaptor);
3.738 + nd = ++Adaptor::NodeIt(adaptor);
3.739 + Adaptor::Node na = n1;
3.740 + na = n2;
3.741 + Digraph::Arc ad = Adaptor::ArcIt(adaptor);
3.742 + ad = ++Adaptor::ArcIt(adaptor);
3.743 +}
3.744 +
3.745 +void checkSplitNodes() {
3.746 + // Check concepts
3.747 + checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
3.748 + checkConcept<concepts::Digraph, SplitNodes<ListDigraph> >();
3.749 +
3.750 + // Create a digraph and an adaptor
3.751 + typedef ListDigraph Digraph;
3.752 + typedef SplitNodes<Digraph> Adaptor;
3.753 +
3.754 + Digraph digraph;
3.755 + Adaptor adaptor(digraph);
3.756 +
3.757 + Digraph::Node n1 = digraph.addNode();
3.758 + Digraph::Node n2 = digraph.addNode();
3.759 + Digraph::Node n3 = digraph.addNode();
3.760 +
3.761 + Digraph::Arc a1 = digraph.addArc(n1, n2);
3.762 + Digraph::Arc a2 = digraph.addArc(n1, n3);
3.763 + Digraph::Arc a3 = digraph.addArc(n2, n3);
3.764 +
3.765 + checkGraphNodeList(adaptor, 6);
3.766 + checkGraphArcList(adaptor, 6);
3.767 + checkGraphConArcList(adaptor, 6);
3.768 +
3.769 + checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
3.770 + checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2);
3.771 + checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
3.772 + checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1);
3.773 + checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
3.774 + checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0);
3.775 +
3.776 + checkGraphInArcList(adaptor, adaptor.inNode(n1), 0);
3.777 + checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
3.778 + checkGraphInArcList(adaptor, adaptor.inNode(n2), 1);
3.779 + checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
3.780 + checkGraphInArcList(adaptor, adaptor.inNode(n3), 2);
3.781 + checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
3.782 +
3.783 + checkNodeIds(adaptor);
3.784 + checkArcIds(adaptor);
3.785 +
3.786 + checkGraphNodeMap(adaptor);
3.787 + checkGraphArcMap(adaptor);
3.788 +
3.789 + // Check split
3.790 + for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
3.791 + if (adaptor.origArc(a)) {
3.792 + Digraph::Arc oa = a;
3.793 + check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),
3.794 + "Wrong split");
3.795 + check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),
3.796 + "Wrong split");
3.797 + } else {
3.798 + Digraph::Node on = a;
3.799 + check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");
3.800 + check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");
3.801 + }
3.802 + }
3.803 +
3.804 + // Check combined node map
3.805 + typedef Adaptor::CombinedNodeMap
3.806 + <Digraph::NodeMap<int>, Digraph::NodeMap<int> > IntCombinedNodeMap;
3.807 + typedef Adaptor::CombinedNodeMap
3.808 + <Digraph::NodeMap<bool>, Digraph::NodeMap<bool> > BoolCombinedNodeMap;
3.809 + checkConcept<concepts::ReferenceMap<Adaptor::Node, int, int&, const int&>,
3.810 + IntCombinedNodeMap>();
3.811 +//checkConcept<concepts::ReferenceMap<Adaptor::Node, bool, bool&, const bool&>,
3.812 +// BoolCombinedNodeMap>();
3.813 + checkConcept<concepts::ReadWriteMap<Adaptor::Node, bool>,
3.814 + BoolCombinedNodeMap>();
3.815 +
3.816 + Digraph::NodeMap<int> in_map(digraph), out_map(digraph);
3.817 + for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {
3.818 + in_map[n] = digraph.id(n);
3.819 + out_map[n] = -digraph.id(n);
3.820 + }
3.821 +
3.822 + Adaptor::CombinedNodeMap<Digraph::NodeMap<int>, Digraph::NodeMap<int> >
3.823 + node_map(in_map, out_map);
3.824 + for (Adaptor::NodeIt n(adaptor); n != INVALID; ++n) {
3.825 + if (adaptor.inNode(n)) {
3.826 + check(node_map[n] == in_map[n], "Wrong combined node map");
3.827 + } else {
3.828 + check(node_map[n] == out_map[n], "Wrong combined node map");
3.829 + }
3.830 + }
3.831 +
3.832 + // Check combined arc map
3.833 + typedef Adaptor::CombinedArcMap
3.834 + <Digraph::ArcMap<int>, Digraph::NodeMap<int> > IntCombinedArcMap;
3.835 + typedef Adaptor::CombinedArcMap
3.836 + <Digraph::ArcMap<bool>, Digraph::NodeMap<bool> > BoolCombinedArcMap;
3.837 + checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,
3.838 + IntCombinedArcMap>();
3.839 +//checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,
3.840 +// BoolCombinedArcMap>();
3.841 + checkConcept<concepts::ReadWriteMap<Adaptor::Arc, bool>,
3.842 + BoolCombinedArcMap>();
3.843 +
3.844 + Digraph::ArcMap<int> a_map(digraph);
3.845 + for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
3.846 + a_map[a] = digraph.id(a);
3.847 + }
3.848 +
3.849 + Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::NodeMap<int> >
3.850 + arc_map(a_map, out_map);
3.851 + for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
3.852 + check(arc_map[adaptor.arc(a)] == a_map[a], "Wrong combined arc map");
3.853 + }
3.854 + for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {
3.855 + check(arc_map[adaptor.arc(n)] == out_map[n], "Wrong combined arc map");
3.856 + }
3.857 +
3.858 + // Check the conversion of nodes
3.859 + Digraph::Node nd = adaptor.inNode(n1);
3.860 + check (nd == n1, "Wrong node conversion");
3.861 + nd = adaptor.outNode(n2);
3.862 + check (nd == n2, "Wrong node conversion");
3.863 +}
3.864 +
3.865 +void checkSubGraph() {
3.866 + // Check concepts
3.867 + checkConcept<concepts::Graph, SubGraph<concepts::Graph> >();
3.868 + checkConcept<concepts::Graph, SubGraph<ListGraph> >();
3.869 + checkConcept<concepts::AlterableGraphComponent<>,
3.870 + SubGraph<ListGraph> >();
3.871 + checkConcept<concepts::ExtendableGraphComponent<>,
3.872 + SubGraph<ListGraph> >();
3.873 + checkConcept<concepts::ErasableGraphComponent<>,
3.874 + SubGraph<ListGraph> >();
3.875 + checkConcept<concepts::ClearableGraphComponent<>,
3.876 + SubGraph<ListGraph> >();
3.877 +
3.878 + // Create a graph and an adaptor
3.879 + typedef ListGraph Graph;
3.880 + typedef Graph::NodeMap<bool> NodeFilter;
3.881 + typedef Graph::EdgeMap<bool> EdgeFilter;
3.882 + typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;
3.883 +
3.884 + Graph graph;
3.885 + NodeFilter node_filter(graph);
3.886 + EdgeFilter edge_filter(graph);
3.887 + Adaptor adaptor(graph, node_filter, edge_filter);
3.888 +
3.889 + // Add nodes and edges to the original graph and the adaptor
3.890 + Graph::Node n1 = graph.addNode();
3.891 + Graph::Node n2 = graph.addNode();
3.892 + Adaptor::Node n3 = adaptor.addNode();
3.893 + Adaptor::Node n4 = adaptor.addNode();
3.894 +
3.895 + node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
3.896 +
3.897 + Graph::Edge e1 = graph.addEdge(n1, n2);
3.898 + Graph::Edge e2 = graph.addEdge(n1, n3);
3.899 + Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
3.900 + Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
3.901 +
3.902 + edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
3.903 +
3.904 + checkGraphNodeList(adaptor, 4);
3.905 + checkGraphArcList(adaptor, 8);
3.906 + checkGraphEdgeList(adaptor, 4);
3.907 + checkGraphConArcList(adaptor, 8);
3.908 + checkGraphConEdgeList(adaptor, 4);
3.909 +
3.910 + checkGraphIncEdgeArcLists(adaptor, n1, 2);
3.911 + checkGraphIncEdgeArcLists(adaptor, n2, 2);
3.912 + checkGraphIncEdgeArcLists(adaptor, n3, 3);
3.913 + checkGraphIncEdgeArcLists(adaptor, n4, 1);
3.914 +
3.915 + checkNodeIds(adaptor);
3.916 + checkArcIds(adaptor);
3.917 + checkEdgeIds(adaptor);
3.918 +
3.919 + checkGraphNodeMap(adaptor);
3.920 + checkGraphArcMap(adaptor);
3.921 + checkGraphEdgeMap(adaptor);
3.922 +
3.923 + // Hide an edge
3.924 + adaptor.status(e2, false);
3.925 + adaptor.disable(e3);
3.926 + if (!adaptor.status(e3)) adaptor.enable(e3);
3.927 +
3.928 + checkGraphNodeList(adaptor, 4);
3.929 + checkGraphArcList(adaptor, 6);
3.930 + checkGraphEdgeList(adaptor, 3);
3.931 + checkGraphConArcList(adaptor, 6);
3.932 + checkGraphConEdgeList(adaptor, 3);
3.933 +
3.934 + checkGraphIncEdgeArcLists(adaptor, n1, 1);
3.935 + checkGraphIncEdgeArcLists(adaptor, n2, 2);
3.936 + checkGraphIncEdgeArcLists(adaptor, n3, 2);
3.937 + checkGraphIncEdgeArcLists(adaptor, n4, 1);
3.938 +
3.939 + checkNodeIds(adaptor);
3.940 + checkArcIds(adaptor);
3.941 + checkEdgeIds(adaptor);
3.942 +
3.943 + checkGraphNodeMap(adaptor);
3.944 + checkGraphArcMap(adaptor);
3.945 + checkGraphEdgeMap(adaptor);
3.946 +
3.947 + // Hide a node
3.948 + adaptor.status(n1, false);
3.949 + adaptor.disable(n3);
3.950 + if (!adaptor.status(n3)) adaptor.enable(n3);
3.951 +
3.952 + checkGraphNodeList(adaptor, 3);
3.953 + checkGraphArcList(adaptor, 4);
3.954 + checkGraphEdgeList(adaptor, 2);
3.955 + checkGraphConArcList(adaptor, 4);
3.956 + checkGraphConEdgeList(adaptor, 2);
3.957 +
3.958 + checkGraphIncEdgeArcLists(adaptor, n2, 1);
3.959 + checkGraphIncEdgeArcLists(adaptor, n3, 2);
3.960 + checkGraphIncEdgeArcLists(adaptor, n4, 1);
3.961 +
3.962 + checkNodeIds(adaptor);
3.963 + checkArcIds(adaptor);
3.964 + checkEdgeIds(adaptor);
3.965 +
3.966 + checkGraphNodeMap(adaptor);
3.967 + checkGraphArcMap(adaptor);
3.968 + checkGraphEdgeMap(adaptor);
3.969 +
3.970 + // Hide all nodes and edges
3.971 + node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
3.972 + edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
3.973 +
3.974 + checkGraphNodeList(adaptor, 0);
3.975 + checkGraphArcList(adaptor, 0);
3.976 + checkGraphEdgeList(adaptor, 0);
3.977 + checkGraphConArcList(adaptor, 0);
3.978 + checkGraphConEdgeList(adaptor, 0);
3.979 +
3.980 + checkNodeIds(adaptor);
3.981 + checkArcIds(adaptor);
3.982 + checkEdgeIds(adaptor);
3.983 +
3.984 + checkGraphNodeMap(adaptor);
3.985 + checkGraphArcMap(adaptor);
3.986 + checkGraphEdgeMap(adaptor);
3.987 +
3.988 + // Check the conversion of nodes and edges
3.989 + Graph::Node ng = n3;
3.990 + ng = n4;
3.991 + Adaptor::Node na = n1;
3.992 + na = n2;
3.993 + Graph::Edge eg = e3;
3.994 + eg = e4;
3.995 + Adaptor::Edge ea = e1;
3.996 + ea = e2;
3.997 +}
3.998 +
3.999 +void checkFilterNodes2() {
3.1000 + // Check concepts
3.1001 + checkConcept<concepts::Graph, FilterNodes<concepts::Graph> >();
3.1002 + checkConcept<concepts::Graph, FilterNodes<ListGraph> >();
3.1003 + checkConcept<concepts::AlterableGraphComponent<>,
3.1004 + FilterNodes<ListGraph> >();
3.1005 + checkConcept<concepts::ExtendableGraphComponent<>,
3.1006 + FilterNodes<ListGraph> >();
3.1007 + checkConcept<concepts::ErasableGraphComponent<>,
3.1008 + FilterNodes<ListGraph> >();
3.1009 + checkConcept<concepts::ClearableGraphComponent<>,
3.1010 + FilterNodes<ListGraph> >();
3.1011 +
3.1012 + // Create a graph and an adaptor
3.1013 + typedef ListGraph Graph;
3.1014 + typedef Graph::NodeMap<bool> NodeFilter;
3.1015 + typedef FilterNodes<Graph, NodeFilter> Adaptor;
3.1016 +
3.1017 + // Add nodes and edges to the original graph and the adaptor
3.1018 + Graph graph;
3.1019 + NodeFilter node_filter(graph);
3.1020 + Adaptor adaptor(graph, node_filter);
3.1021 +
3.1022 + Graph::Node n1 = graph.addNode();
3.1023 + Graph::Node n2 = graph.addNode();
3.1024 + Adaptor::Node n3 = adaptor.addNode();
3.1025 + Adaptor::Node n4 = adaptor.addNode();
3.1026 +
3.1027 + node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
3.1028 +
3.1029 + Graph::Edge e1 = graph.addEdge(n1, n2);
3.1030 + Graph::Edge e2 = graph.addEdge(n1, n3);
3.1031 + Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
3.1032 + Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
3.1033 +
3.1034 + checkGraphNodeList(adaptor, 4);
3.1035 + checkGraphArcList(adaptor, 8);
3.1036 + checkGraphEdgeList(adaptor, 4);
3.1037 + checkGraphConArcList(adaptor, 8);
3.1038 + checkGraphConEdgeList(adaptor, 4);
3.1039 +
3.1040 + checkGraphIncEdgeArcLists(adaptor, n1, 2);
3.1041 + checkGraphIncEdgeArcLists(adaptor, n2, 2);
3.1042 + checkGraphIncEdgeArcLists(adaptor, n3, 3);
3.1043 + checkGraphIncEdgeArcLists(adaptor, n4, 1);
3.1044 +
3.1045 + checkNodeIds(adaptor);
3.1046 + checkArcIds(adaptor);
3.1047 + checkEdgeIds(adaptor);
3.1048 +
3.1049 + checkGraphNodeMap(adaptor);
3.1050 + checkGraphArcMap(adaptor);
3.1051 + checkGraphEdgeMap(adaptor);
3.1052 +
3.1053 + // Hide a node
3.1054 + adaptor.status(n1, false);
3.1055 + adaptor.disable(n3);
3.1056 + if (!adaptor.status(n3)) adaptor.enable(n3);
3.1057 +
3.1058 + checkGraphNodeList(adaptor, 3);
3.1059 + checkGraphArcList(adaptor, 4);
3.1060 + checkGraphEdgeList(adaptor, 2);
3.1061 + checkGraphConArcList(adaptor, 4);
3.1062 + checkGraphConEdgeList(adaptor, 2);
3.1063 +
3.1064 + checkGraphIncEdgeArcLists(adaptor, n2, 1);
3.1065 + checkGraphIncEdgeArcLists(adaptor, n3, 2);
3.1066 + checkGraphIncEdgeArcLists(adaptor, n4, 1);
3.1067 +
3.1068 + checkNodeIds(adaptor);
3.1069 + checkArcIds(adaptor);
3.1070 + checkEdgeIds(adaptor);
3.1071 +
3.1072 + checkGraphNodeMap(adaptor);
3.1073 + checkGraphArcMap(adaptor);
3.1074 + checkGraphEdgeMap(adaptor);
3.1075 +
3.1076 + // Hide all nodes
3.1077 + node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
3.1078 +
3.1079 + checkGraphNodeList(adaptor, 0);
3.1080 + checkGraphArcList(adaptor, 0);
3.1081 + checkGraphEdgeList(adaptor, 0);
3.1082 + checkGraphConArcList(adaptor, 0);
3.1083 + checkGraphConEdgeList(adaptor, 0);
3.1084 +
3.1085 + checkNodeIds(adaptor);
3.1086 + checkArcIds(adaptor);
3.1087 + checkEdgeIds(adaptor);
3.1088 +
3.1089 + checkGraphNodeMap(adaptor);
3.1090 + checkGraphArcMap(adaptor);
3.1091 + checkGraphEdgeMap(adaptor);
3.1092 +
3.1093 + // Check the conversion of nodes and edges
3.1094 + Graph::Node ng = n3;
3.1095 + ng = n4;
3.1096 + Adaptor::Node na = n1;
3.1097 + na = n2;
3.1098 + Graph::Edge eg = e3;
3.1099 + eg = e4;
3.1100 + Adaptor::Edge ea = e1;
3.1101 + ea = e2;
3.1102 +}
3.1103 +
3.1104 +void checkFilterEdges() {
3.1105 + // Check concepts
3.1106 + checkConcept<concepts::Graph, FilterEdges<concepts::Graph> >();
3.1107 + checkConcept<concepts::Graph, FilterEdges<ListGraph> >();
3.1108 + checkConcept<concepts::AlterableGraphComponent<>,
3.1109 + FilterEdges<ListGraph> >();
3.1110 + checkConcept<concepts::ExtendableGraphComponent<>,
3.1111 + FilterEdges<ListGraph> >();
3.1112 + checkConcept<concepts::ErasableGraphComponent<>,
3.1113 + FilterEdges<ListGraph> >();
3.1114 + checkConcept<concepts::ClearableGraphComponent<>,
3.1115 + FilterEdges<ListGraph> >();
3.1116 +
3.1117 + // Create a graph and an adaptor
3.1118 + typedef ListGraph Graph;
3.1119 + typedef Graph::EdgeMap<bool> EdgeFilter;
3.1120 + typedef FilterEdges<Graph, EdgeFilter> Adaptor;
3.1121 +
3.1122 + Graph graph;
3.1123 + EdgeFilter edge_filter(graph);
3.1124 + Adaptor adaptor(graph, edge_filter);
3.1125 +
3.1126 + // Add nodes and edges to the original graph and the adaptor
3.1127 + Graph::Node n1 = graph.addNode();
3.1128 + Graph::Node n2 = graph.addNode();
3.1129 + Adaptor::Node n3 = adaptor.addNode();
3.1130 + Adaptor::Node n4 = adaptor.addNode();
3.1131 +
3.1132 + Graph::Edge e1 = graph.addEdge(n1, n2);
3.1133 + Graph::Edge e2 = graph.addEdge(n1, n3);
3.1134 + Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
3.1135 + Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
3.1136 +
3.1137 + edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
3.1138 +
3.1139 + checkGraphNodeList(adaptor, 4);
3.1140 + checkGraphArcList(adaptor, 8);
3.1141 + checkGraphEdgeList(adaptor, 4);
3.1142 + checkGraphConArcList(adaptor, 8);
3.1143 + checkGraphConEdgeList(adaptor, 4);
3.1144 +
3.1145 + checkGraphIncEdgeArcLists(adaptor, n1, 2);
3.1146 + checkGraphIncEdgeArcLists(adaptor, n2, 2);
3.1147 + checkGraphIncEdgeArcLists(adaptor, n3, 3);
3.1148 + checkGraphIncEdgeArcLists(adaptor, n4, 1);
3.1149 +
3.1150 + checkNodeIds(adaptor);
3.1151 + checkArcIds(adaptor);
3.1152 + checkEdgeIds(adaptor);
3.1153 +
3.1154 + checkGraphNodeMap(adaptor);
3.1155 + checkGraphArcMap(adaptor);
3.1156 + checkGraphEdgeMap(adaptor);
3.1157 +
3.1158 + // Hide an edge
3.1159 + adaptor.status(e2, false);
3.1160 + adaptor.disable(e3);
3.1161 + if (!adaptor.status(e3)) adaptor.enable(e3);
3.1162 +
3.1163 + checkGraphNodeList(adaptor, 4);
3.1164 + checkGraphArcList(adaptor, 6);
3.1165 + checkGraphEdgeList(adaptor, 3);
3.1166 + checkGraphConArcList(adaptor, 6);
3.1167 + checkGraphConEdgeList(adaptor, 3);
3.1168 +
3.1169 + checkGraphIncEdgeArcLists(adaptor, n1, 1);
3.1170 + checkGraphIncEdgeArcLists(adaptor, n2, 2);
3.1171 + checkGraphIncEdgeArcLists(adaptor, n3, 2);
3.1172 + checkGraphIncEdgeArcLists(adaptor, n4, 1);
3.1173 +
3.1174 + checkNodeIds(adaptor);
3.1175 + checkArcIds(adaptor);
3.1176 + checkEdgeIds(adaptor);
3.1177 +
3.1178 + checkGraphNodeMap(adaptor);
3.1179 + checkGraphArcMap(adaptor);
3.1180 + checkGraphEdgeMap(adaptor);
3.1181 +
3.1182 + // Hide all edges
3.1183 + edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
3.1184 +
3.1185 + checkGraphNodeList(adaptor, 4);
3.1186 + checkGraphArcList(adaptor, 0);
3.1187 + checkGraphEdgeList(adaptor, 0);
3.1188 + checkGraphConArcList(adaptor, 0);
3.1189 + checkGraphConEdgeList(adaptor, 0);
3.1190 +
3.1191 + checkNodeIds(adaptor);
3.1192 + checkArcIds(adaptor);
3.1193 + checkEdgeIds(adaptor);
3.1194 +
3.1195 + checkGraphNodeMap(adaptor);
3.1196 + checkGraphArcMap(adaptor);
3.1197 + checkGraphEdgeMap(adaptor);
3.1198 +
3.1199 + // Check the conversion of nodes and edges
3.1200 + Graph::Node ng = n3;
3.1201 + ng = n4;
3.1202 + Adaptor::Node na = n1;
3.1203 + na = n2;
3.1204 + Graph::Edge eg = e3;
3.1205 + eg = e4;
3.1206 + Adaptor::Edge ea = e1;
3.1207 + ea = e2;
3.1208 +}
3.1209 +
3.1210 +void checkOrienter() {
3.1211 + // Check concepts
3.1212 + checkConcept<concepts::Digraph, Orienter<concepts::Graph> >();
3.1213 + checkConcept<concepts::Digraph, Orienter<ListGraph> >();
3.1214 + checkConcept<concepts::AlterableDigraphComponent<>,
3.1215 + Orienter<ListGraph> >();
3.1216 + checkConcept<concepts::ExtendableDigraphComponent<>,
3.1217 + Orienter<ListGraph> >();
3.1218 + checkConcept<concepts::ErasableDigraphComponent<>,
3.1219 + Orienter<ListGraph> >();
3.1220 + checkConcept<concepts::ClearableDigraphComponent<>,
3.1221 + Orienter<ListGraph> >();
3.1222 +
3.1223 + // Create a graph and an adaptor
3.1224 + typedef ListGraph Graph;
3.1225 + typedef ListGraph::EdgeMap<bool> DirMap;
3.1226 + typedef Orienter<Graph> Adaptor;
3.1227 +
3.1228 + Graph graph;
3.1229 + DirMap dir(graph);
3.1230 + Adaptor adaptor(graph, dir);
3.1231 +
3.1232 + // Add nodes and edges to the original graph and the adaptor
3.1233 + Graph::Node n1 = graph.addNode();
3.1234 + Graph::Node n2 = graph.addNode();
3.1235 + Adaptor::Node n3 = adaptor.addNode();
3.1236 +
3.1237 + Graph::Edge e1 = graph.addEdge(n1, n2);
3.1238 + Graph::Edge e2 = graph.addEdge(n1, n3);
3.1239 + Adaptor::Arc e3 = adaptor.addArc(n2, n3);
3.1240 +
3.1241 + dir[e1] = dir[e2] = dir[e3] = true;
3.1242 +
3.1243 + // Check the original graph
3.1244 + checkGraphNodeList(graph, 3);
3.1245 + checkGraphArcList(graph, 6);
3.1246 + checkGraphConArcList(graph, 6);
3.1247 + checkGraphEdgeList(graph, 3);
3.1248 + checkGraphConEdgeList(graph, 3);
3.1249 +
3.1250 + checkGraphIncEdgeArcLists(graph, n1, 2);
3.1251 + checkGraphIncEdgeArcLists(graph, n2, 2);
3.1252 + checkGraphIncEdgeArcLists(graph, n3, 2);
3.1253 +
3.1254 + checkNodeIds(graph);
3.1255 + checkArcIds(graph);
3.1256 + checkEdgeIds(graph);
3.1257 +
3.1258 + checkGraphNodeMap(graph);
3.1259 + checkGraphArcMap(graph);
3.1260 + checkGraphEdgeMap(graph);
3.1261 +
3.1262 + // Check the adaptor
3.1263 + checkGraphNodeList(adaptor, 3);
3.1264 + checkGraphArcList(adaptor, 3);
3.1265 + checkGraphConArcList(adaptor, 3);
3.1266 +
3.1267 + checkGraphOutArcList(adaptor, n1, 2);
3.1268 + checkGraphOutArcList(adaptor, n2, 1);
3.1269 + checkGraphOutArcList(adaptor, n3, 0);
3.1270 +
3.1271 + checkGraphInArcList(adaptor, n1, 0);
3.1272 + checkGraphInArcList(adaptor, n2, 1);
3.1273 + checkGraphInArcList(adaptor, n3, 2);
3.1274 +
3.1275 + checkNodeIds(adaptor);
3.1276 + checkArcIds(adaptor);
3.1277 +
3.1278 + checkGraphNodeMap(adaptor);
3.1279 + checkGraphArcMap(adaptor);
3.1280 +
3.1281 + // Check direction changing
3.1282 + {
3.1283 + dir[e1] = true;
3.1284 + Adaptor::Node u = adaptor.source(e1);
3.1285 + Adaptor::Node v = adaptor.target(e1);
3.1286 +
3.1287 + dir[e1] = false;
3.1288 + check (u == adaptor.target(e1), "Wrong dir");
3.1289 + check (v == adaptor.source(e1), "Wrong dir");
3.1290 +
3.1291 + check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");
3.1292 + dir[e1] = n1 == u;
3.1293 + }
3.1294 +
3.1295 + {
3.1296 + dir[e2] = true;
3.1297 + Adaptor::Node u = adaptor.source(e2);
3.1298 + Adaptor::Node v = adaptor.target(e2);
3.1299 +
3.1300 + dir[e2] = false;
3.1301 + check (u == adaptor.target(e2), "Wrong dir");
3.1302 + check (v == adaptor.source(e2), "Wrong dir");
3.1303 +
3.1304 + check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");
3.1305 + dir[e2] = n3 == u;
3.1306 + }
3.1307 +
3.1308 + {
3.1309 + dir[e3] = true;
3.1310 + Adaptor::Node u = adaptor.source(e3);
3.1311 + Adaptor::Node v = adaptor.target(e3);
3.1312 +
3.1313 + dir[e3] = false;
3.1314 + check (u == adaptor.target(e3), "Wrong dir");
3.1315 + check (v == adaptor.source(e3), "Wrong dir");
3.1316 +
3.1317 + check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
3.1318 + dir[e3] = n2 == u;
3.1319 + }
3.1320 +
3.1321 + // Check the adaptor again
3.1322 + checkGraphNodeList(adaptor, 3);
3.1323 + checkGraphArcList(adaptor, 3);
3.1324 + checkGraphConArcList(adaptor, 3);
3.1325 +
3.1326 + checkGraphOutArcList(adaptor, n1, 1);
3.1327 + checkGraphOutArcList(adaptor, n2, 1);
3.1328 + checkGraphOutArcList(adaptor, n3, 1);
3.1329 +
3.1330 + checkGraphInArcList(adaptor, n1, 1);
3.1331 + checkGraphInArcList(adaptor, n2, 1);
3.1332 + checkGraphInArcList(adaptor, n3, 1);
3.1333 +
3.1334 + checkNodeIds(adaptor);
3.1335 + checkArcIds(adaptor);
3.1336 +
3.1337 + checkGraphNodeMap(adaptor);
3.1338 + checkGraphArcMap(adaptor);
3.1339 +
3.1340 + // Check reverseArc()
3.1341 + adaptor.reverseArc(e2);
3.1342 + adaptor.reverseArc(e3);
3.1343 + adaptor.reverseArc(e2);
3.1344 +
3.1345 + checkGraphNodeList(adaptor, 3);
3.1346 + checkGraphArcList(adaptor, 3);
3.1347 + checkGraphConArcList(adaptor, 3);
3.1348 +
3.1349 + checkGraphOutArcList(adaptor, n1, 1);
3.1350 + checkGraphOutArcList(adaptor, n2, 0);
3.1351 + checkGraphOutArcList(adaptor, n3, 2);
3.1352 +
3.1353 + checkGraphInArcList(adaptor, n1, 1);
3.1354 + checkGraphInArcList(adaptor, n2, 2);
3.1355 + checkGraphInArcList(adaptor, n3, 0);
3.1356 +
3.1357 + // Check the conversion of nodes and arcs/edges
3.1358 + Graph::Node ng = n3;
3.1359 + ng = n3;
3.1360 + Adaptor::Node na = n1;
3.1361 + na = n2;
3.1362 + Graph::Edge eg = e3;
3.1363 + eg = e3;
3.1364 + Adaptor::Arc aa = e1;
3.1365 + aa = e2;
3.1366 +}
3.1367 +
3.1368 +void checkCombiningAdaptors() {
3.1369 + // Create a grid graph
3.1370 + GridGraph graph(2,2);
3.1371 + GridGraph::Node n1 = graph(0,0);
3.1372 + GridGraph::Node n2 = graph(0,1);
3.1373 + GridGraph::Node n3 = graph(1,0);
3.1374 + GridGraph::Node n4 = graph(1,1);
3.1375 +
3.1376 + GridGraph::EdgeMap<bool> dir_map(graph);
3.1377 + dir_map[graph.right(n1)] = graph.u(graph.right(n1)) == n1;
3.1378 + dir_map[graph.up(n1)] = graph.u(graph.up(n1)) != n1;
3.1379 + dir_map[graph.left(n4)] = graph.u(graph.left(n4)) != n4;
3.1380 + dir_map[graph.down(n4)] = graph.u(graph.down(n4)) != n4;
3.1381 +
3.1382 + // Apply several adaptors on the grid graph
3.1383 + typedef SplitNodes< ReverseDigraph< const Orienter<
3.1384 + const GridGraph, GridGraph::EdgeMap<bool> > > >
3.1385 + RevSplitGridGraph;
3.1386 + typedef ReverseDigraph<const RevSplitGridGraph> SplitGridGraph;
3.1387 + typedef Undirector<const SplitGridGraph> USplitGridGraph;
3.1388 + typedef Undirector<const USplitGridGraph> UUSplitGridGraph;
3.1389 + checkConcept<concepts::Digraph, RevSplitGridGraph>();
3.1390 + checkConcept<concepts::Digraph, SplitGridGraph>();
3.1391 + checkConcept<concepts::Graph, USplitGridGraph>();
3.1392 + checkConcept<concepts::Graph, UUSplitGridGraph>();
3.1393 +
3.1394 + RevSplitGridGraph rev_adaptor =
3.1395 + splitNodes(reverseDigraph(orienter(graph, dir_map)));
3.1396 + SplitGridGraph adaptor = reverseDigraph(rev_adaptor);
3.1397 + USplitGridGraph uadaptor = undirector(adaptor);
3.1398 + UUSplitGridGraph uuadaptor = undirector(uadaptor);
3.1399 +
3.1400 + // Check adaptor
3.1401 + checkGraphNodeList(adaptor, 8);
3.1402 + checkGraphArcList(adaptor, 8);
3.1403 + checkGraphConArcList(adaptor, 8);
3.1404 +
3.1405 + checkGraphOutArcList(adaptor, rev_adaptor.inNode(n1), 1);
3.1406 + checkGraphOutArcList(adaptor, rev_adaptor.outNode(n1), 1);
3.1407 + checkGraphOutArcList(adaptor, rev_adaptor.inNode(n2), 2);
3.1408 + checkGraphOutArcList(adaptor, rev_adaptor.outNode(n2), 1);
3.1409 + checkGraphOutArcList(adaptor, rev_adaptor.inNode(n3), 1);
3.1410 + checkGraphOutArcList(adaptor, rev_adaptor.outNode(n3), 1);
3.1411 + checkGraphOutArcList(adaptor, rev_adaptor.inNode(n4), 0);
3.1412 + checkGraphOutArcList(adaptor, rev_adaptor.outNode(n4), 1);
3.1413 +
3.1414 + checkGraphInArcList(adaptor, rev_adaptor.inNode(n1), 1);
3.1415 + checkGraphInArcList(adaptor, rev_adaptor.outNode(n1), 1);
3.1416 + checkGraphInArcList(adaptor, rev_adaptor.inNode(n2), 1);
3.1417 + checkGraphInArcList(adaptor, rev_adaptor.outNode(n2), 0);
3.1418 + checkGraphInArcList(adaptor, rev_adaptor.inNode(n3), 1);
3.1419 + checkGraphInArcList(adaptor, rev_adaptor.outNode(n3), 1);
3.1420 + checkGraphInArcList(adaptor, rev_adaptor.inNode(n4), 1);
3.1421 + checkGraphInArcList(adaptor, rev_adaptor.outNode(n4), 2);
3.1422 +
3.1423 + checkNodeIds(adaptor);
3.1424 + checkArcIds(adaptor);
3.1425 +
3.1426 + checkGraphNodeMap(adaptor);
3.1427 + checkGraphArcMap(adaptor);
3.1428 +
3.1429 + // Check uadaptor
3.1430 + checkGraphNodeList(uadaptor, 8);
3.1431 + checkGraphEdgeList(uadaptor, 8);
3.1432 + checkGraphArcList(uadaptor, 16);
3.1433 + checkGraphConEdgeList(uadaptor, 8);
3.1434 + checkGraphConArcList(uadaptor, 16);
3.1435 +
3.1436 + checkNodeIds(uadaptor);
3.1437 + checkEdgeIds(uadaptor);
3.1438 + checkArcIds(uadaptor);
3.1439 +
3.1440 + checkGraphNodeMap(uadaptor);
3.1441 + checkGraphEdgeMap(uadaptor);
3.1442 + checkGraphArcMap(uadaptor);
3.1443 +
3.1444 + checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n1), 2);
3.1445 + checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n1), 2);
3.1446 + checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n2), 3);
3.1447 + checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n2), 1);
3.1448 + checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n3), 2);
3.1449 + checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n3), 2);
3.1450 + checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n4), 1);
3.1451 + checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n4), 3);
3.1452 +
3.1453 + // Check uuadaptor
3.1454 + checkGraphNodeList(uuadaptor, 8);
3.1455 + checkGraphEdgeList(uuadaptor, 16);
3.1456 + checkGraphArcList(uuadaptor, 32);
3.1457 + checkGraphConEdgeList(uuadaptor, 16);
3.1458 + checkGraphConArcList(uuadaptor, 32);
3.1459 +
3.1460 + checkNodeIds(uuadaptor);
3.1461 + checkEdgeIds(uuadaptor);
3.1462 + checkArcIds(uuadaptor);
3.1463 +
3.1464 + checkGraphNodeMap(uuadaptor);
3.1465 + checkGraphEdgeMap(uuadaptor);
3.1466 + checkGraphArcMap(uuadaptor);
3.1467 +}
3.1468 +
3.1469 +int main(int, const char **) {
3.1470 + // Check the digraph adaptors (using ListDigraph)
3.1471 + checkReverseDigraph();
3.1472 + checkSubDigraph();
3.1473 + checkFilterNodes1();
3.1474 + checkFilterArcs();
3.1475 + checkUndirector();
3.1476 + checkResidualDigraph();
3.1477 + checkSplitNodes();
3.1478 +
3.1479 + // Check the graph adaptors (using ListGraph)
3.1480 + checkSubGraph();
3.1481 + checkFilterNodes2();
3.1482 + checkFilterEdges();
3.1483 + checkOrienter();
3.1484 +
3.1485 + // Combine adaptors (using GridGraph)
3.1486 + checkCombiningAdaptors();
3.1487 +
3.1488 + return 0;
3.1489 +}
4.1 --- a/test/graph_adaptor_test.cc Mon Jan 12 08:05:30 2009 +0100
4.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
4.3 @@ -1,1486 +0,0 @@
4.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
4.5 - *
4.6 - * This file is a part of LEMON, a generic C++ optimization library.
4.7 - *
4.8 - * Copyright (C) 2003-2009
4.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.11 - *
4.12 - * Permission to use, modify and distribute this software is granted
4.13 - * provided that this copyright notice appears in all copies. For
4.14 - * precise terms see the accompanying LICENSE file.
4.15 - *
4.16 - * This software is provided "AS IS" with no warranty of any kind,
4.17 - * express or implied, and with no claim as to its suitability for any
4.18 - * purpose.
4.19 - *
4.20 - */
4.21 -
4.22 -#include <iostream>
4.23 -#include <limits>
4.24 -
4.25 -#include <lemon/list_graph.h>
4.26 -#include <lemon/grid_graph.h>
4.27 -#include <lemon/bfs.h>
4.28 -#include <lemon/path.h>
4.29 -
4.30 -#include <lemon/concepts/digraph.h>
4.31 -#include <lemon/concepts/graph.h>
4.32 -#include <lemon/concepts/graph_components.h>
4.33 -#include <lemon/concepts/maps.h>
4.34 -#include <lemon/concept_check.h>
4.35 -
4.36 -#include <lemon/adaptors.h>
4.37 -
4.38 -#include "test/test_tools.h"
4.39 -#include "test/graph_test.h"
4.40 -
4.41 -using namespace lemon;
4.42 -
4.43 -void checkReverseDigraph() {
4.44 - // Check concepts
4.45 - checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
4.46 - checkConcept<concepts::Digraph, ReverseDigraph<ListDigraph> >();
4.47 - checkConcept<concepts::AlterableDigraphComponent<>,
4.48 - ReverseDigraph<ListDigraph> >();
4.49 - checkConcept<concepts::ExtendableDigraphComponent<>,
4.50 - ReverseDigraph<ListDigraph> >();
4.51 - checkConcept<concepts::ErasableDigraphComponent<>,
4.52 - ReverseDigraph<ListDigraph> >();
4.53 - checkConcept<concepts::ClearableDigraphComponent<>,
4.54 - ReverseDigraph<ListDigraph> >();
4.55 -
4.56 - // Create a digraph and an adaptor
4.57 - typedef ListDigraph Digraph;
4.58 - typedef ReverseDigraph<Digraph> Adaptor;
4.59 -
4.60 - Digraph digraph;
4.61 - Adaptor adaptor(digraph);
4.62 -
4.63 - // Add nodes and arcs to the original digraph
4.64 - Digraph::Node n1 = digraph.addNode();
4.65 - Digraph::Node n2 = digraph.addNode();
4.66 - Digraph::Node n3 = digraph.addNode();
4.67 -
4.68 - Digraph::Arc a1 = digraph.addArc(n1, n2);
4.69 - Digraph::Arc a2 = digraph.addArc(n1, n3);
4.70 - Digraph::Arc a3 = digraph.addArc(n2, n3);
4.71 -
4.72 - // Check the adaptor
4.73 - checkGraphNodeList(adaptor, 3);
4.74 - checkGraphArcList(adaptor, 3);
4.75 - checkGraphConArcList(adaptor, 3);
4.76 -
4.77 - checkGraphOutArcList(adaptor, n1, 0);
4.78 - checkGraphOutArcList(adaptor, n2, 1);
4.79 - checkGraphOutArcList(adaptor, n3, 2);
4.80 -
4.81 - checkGraphInArcList(adaptor, n1, 2);
4.82 - checkGraphInArcList(adaptor, n2, 1);
4.83 - checkGraphInArcList(adaptor, n3, 0);
4.84 -
4.85 - checkNodeIds(adaptor);
4.86 - checkArcIds(adaptor);
4.87 -
4.88 - checkGraphNodeMap(adaptor);
4.89 - checkGraphArcMap(adaptor);
4.90 -
4.91 - // Check the orientation of the arcs
4.92 - for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
4.93 - check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
4.94 - check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
4.95 - }
4.96 -
4.97 - // Add and erase nodes and arcs in the digraph through the adaptor
4.98 - Adaptor::Node n4 = adaptor.addNode();
4.99 -
4.100 - Adaptor::Arc a4 = adaptor.addArc(n4, n3);
4.101 - Adaptor::Arc a5 = adaptor.addArc(n2, n4);
4.102 - Adaptor::Arc a6 = adaptor.addArc(n2, n4);
4.103 - Adaptor::Arc a7 = adaptor.addArc(n1, n4);
4.104 - Adaptor::Arc a8 = adaptor.addArc(n1, n2);
4.105 -
4.106 - adaptor.erase(a1);
4.107 - adaptor.erase(n3);
4.108 -
4.109 - // Check the adaptor
4.110 - checkGraphNodeList(adaptor, 3);
4.111 - checkGraphArcList(adaptor, 4);
4.112 - checkGraphConArcList(adaptor, 4);
4.113 -
4.114 - checkGraphOutArcList(adaptor, n1, 2);
4.115 - checkGraphOutArcList(adaptor, n2, 2);
4.116 - checkGraphOutArcList(adaptor, n4, 0);
4.117 -
4.118 - checkGraphInArcList(adaptor, n1, 0);
4.119 - checkGraphInArcList(adaptor, n2, 1);
4.120 - checkGraphInArcList(adaptor, n4, 3);
4.121 -
4.122 - checkNodeIds(adaptor);
4.123 - checkArcIds(adaptor);
4.124 -
4.125 - checkGraphNodeMap(adaptor);
4.126 - checkGraphArcMap(adaptor);
4.127 -
4.128 - // Check the digraph
4.129 - checkGraphNodeList(digraph, 3);
4.130 - checkGraphArcList(digraph, 4);
4.131 - checkGraphConArcList(digraph, 4);
4.132 -
4.133 - checkGraphOutArcList(digraph, n1, 0);
4.134 - checkGraphOutArcList(digraph, n2, 1);
4.135 - checkGraphOutArcList(digraph, n4, 3);
4.136 -
4.137 - checkGraphInArcList(digraph, n1, 2);
4.138 - checkGraphInArcList(digraph, n2, 2);
4.139 - checkGraphInArcList(digraph, n4, 0);
4.140 -
4.141 - checkNodeIds(digraph);
4.142 - checkArcIds(digraph);
4.143 -
4.144 - checkGraphNodeMap(digraph);
4.145 - checkGraphArcMap(digraph);
4.146 -
4.147 - // Check the conversion of nodes and arcs
4.148 - Digraph::Node nd = n4;
4.149 - nd = n4;
4.150 - Adaptor::Node na = n1;
4.151 - na = n2;
4.152 - Digraph::Arc ad = a4;
4.153 - ad = a5;
4.154 - Adaptor::Arc aa = a1;
4.155 - aa = a2;
4.156 -}
4.157 -
4.158 -void checkSubDigraph() {
4.159 - // Check concepts
4.160 - checkConcept<concepts::Digraph, SubDigraph<concepts::Digraph> >();
4.161 - checkConcept<concepts::Digraph, SubDigraph<ListDigraph> >();
4.162 - checkConcept<concepts::AlterableDigraphComponent<>,
4.163 - SubDigraph<ListDigraph> >();
4.164 - checkConcept<concepts::ExtendableDigraphComponent<>,
4.165 - SubDigraph<ListDigraph> >();
4.166 - checkConcept<concepts::ErasableDigraphComponent<>,
4.167 - SubDigraph<ListDigraph> >();
4.168 - checkConcept<concepts::ClearableDigraphComponent<>,
4.169 - SubDigraph<ListDigraph> >();
4.170 -
4.171 - // Create a digraph and an adaptor
4.172 - typedef ListDigraph Digraph;
4.173 - typedef Digraph::NodeMap<bool> NodeFilter;
4.174 - typedef Digraph::ArcMap<bool> ArcFilter;
4.175 - typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
4.176 -
4.177 - Digraph digraph;
4.178 - NodeFilter node_filter(digraph);
4.179 - ArcFilter arc_filter(digraph);
4.180 - Adaptor adaptor(digraph, node_filter, arc_filter);
4.181 -
4.182 - // Add nodes and arcs to the original digraph and the adaptor
4.183 - Digraph::Node n1 = digraph.addNode();
4.184 - Digraph::Node n2 = digraph.addNode();
4.185 - Adaptor::Node n3 = adaptor.addNode();
4.186 -
4.187 - node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
4.188 -
4.189 - Digraph::Arc a1 = digraph.addArc(n1, n2);
4.190 - Digraph::Arc a2 = digraph.addArc(n1, n3);
4.191 - Adaptor::Arc a3 = adaptor.addArc(n2, n3);
4.192 -
4.193 - arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
4.194 -
4.195 - checkGraphNodeList(adaptor, 3);
4.196 - checkGraphArcList(adaptor, 3);
4.197 - checkGraphConArcList(adaptor, 3);
4.198 -
4.199 - checkGraphOutArcList(adaptor, n1, 2);
4.200 - checkGraphOutArcList(adaptor, n2, 1);
4.201 - checkGraphOutArcList(adaptor, n3, 0);
4.202 -
4.203 - checkGraphInArcList(adaptor, n1, 0);
4.204 - checkGraphInArcList(adaptor, n2, 1);
4.205 - checkGraphInArcList(adaptor, n3, 2);
4.206 -
4.207 - checkNodeIds(adaptor);
4.208 - checkArcIds(adaptor);
4.209 -
4.210 - checkGraphNodeMap(adaptor);
4.211 - checkGraphArcMap(adaptor);
4.212 -
4.213 - // Hide an arc
4.214 - adaptor.status(a2, false);
4.215 - adaptor.disable(a3);
4.216 - if (!adaptor.status(a3)) adaptor.enable(a3);
4.217 -
4.218 - checkGraphNodeList(adaptor, 3);
4.219 - checkGraphArcList(adaptor, 2);
4.220 - checkGraphConArcList(adaptor, 2);
4.221 -
4.222 - checkGraphOutArcList(adaptor, n1, 1);
4.223 - checkGraphOutArcList(adaptor, n2, 1);
4.224 - checkGraphOutArcList(adaptor, n3, 0);
4.225 -
4.226 - checkGraphInArcList(adaptor, n1, 0);
4.227 - checkGraphInArcList(adaptor, n2, 1);
4.228 - checkGraphInArcList(adaptor, n3, 1);
4.229 -
4.230 - checkNodeIds(adaptor);
4.231 - checkArcIds(adaptor);
4.232 -
4.233 - checkGraphNodeMap(adaptor);
4.234 - checkGraphArcMap(adaptor);
4.235 -
4.236 - // Hide a node
4.237 - adaptor.status(n1, false);
4.238 - adaptor.disable(n3);
4.239 - if (!adaptor.status(n3)) adaptor.enable(n3);
4.240 -
4.241 - checkGraphNodeList(adaptor, 2);
4.242 - checkGraphArcList(adaptor, 1);
4.243 - checkGraphConArcList(adaptor, 1);
4.244 -
4.245 - checkGraphOutArcList(adaptor, n2, 1);
4.246 - checkGraphOutArcList(adaptor, n3, 0);
4.247 -
4.248 - checkGraphInArcList(adaptor, n2, 0);
4.249 - checkGraphInArcList(adaptor, n3, 1);
4.250 -
4.251 - checkNodeIds(adaptor);
4.252 - checkArcIds(adaptor);
4.253 -
4.254 - checkGraphNodeMap(adaptor);
4.255 - checkGraphArcMap(adaptor);
4.256 -
4.257 - // Hide all nodes and arcs
4.258 - node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
4.259 - arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
4.260 -
4.261 - checkGraphNodeList(adaptor, 0);
4.262 - checkGraphArcList(adaptor, 0);
4.263 - checkGraphConArcList(adaptor, 0);
4.264 -
4.265 - checkNodeIds(adaptor);
4.266 - checkArcIds(adaptor);
4.267 -
4.268 - checkGraphNodeMap(adaptor);
4.269 - checkGraphArcMap(adaptor);
4.270 -
4.271 - // Check the conversion of nodes and arcs
4.272 - Digraph::Node nd = n3;
4.273 - nd = n3;
4.274 - Adaptor::Node na = n1;
4.275 - na = n2;
4.276 - Digraph::Arc ad = a3;
4.277 - ad = a3;
4.278 - Adaptor::Arc aa = a1;
4.279 - aa = a2;
4.280 -}
4.281 -
4.282 -void checkFilterNodes1() {
4.283 - // Check concepts
4.284 - checkConcept<concepts::Digraph, FilterNodes<concepts::Digraph> >();
4.285 - checkConcept<concepts::Digraph, FilterNodes<ListDigraph> >();
4.286 - checkConcept<concepts::AlterableDigraphComponent<>,
4.287 - FilterNodes<ListDigraph> >();
4.288 - checkConcept<concepts::ExtendableDigraphComponent<>,
4.289 - FilterNodes<ListDigraph> >();
4.290 - checkConcept<concepts::ErasableDigraphComponent<>,
4.291 - FilterNodes<ListDigraph> >();
4.292 - checkConcept<concepts::ClearableDigraphComponent<>,
4.293 - FilterNodes<ListDigraph> >();
4.294 -
4.295 - // Create a digraph and an adaptor
4.296 - typedef ListDigraph Digraph;
4.297 - typedef Digraph::NodeMap<bool> NodeFilter;
4.298 - typedef FilterNodes<Digraph, NodeFilter> Adaptor;
4.299 -
4.300 - Digraph digraph;
4.301 - NodeFilter node_filter(digraph);
4.302 - Adaptor adaptor(digraph, node_filter);
4.303 -
4.304 - // Add nodes and arcs to the original digraph and the adaptor
4.305 - Digraph::Node n1 = digraph.addNode();
4.306 - Digraph::Node n2 = digraph.addNode();
4.307 - Adaptor::Node n3 = adaptor.addNode();
4.308 -
4.309 - node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
4.310 -
4.311 - Digraph::Arc a1 = digraph.addArc(n1, n2);
4.312 - Digraph::Arc a2 = digraph.addArc(n1, n3);
4.313 - Adaptor::Arc a3 = adaptor.addArc(n2, n3);
4.314 -
4.315 - checkGraphNodeList(adaptor, 3);
4.316 - checkGraphArcList(adaptor, 3);
4.317 - checkGraphConArcList(adaptor, 3);
4.318 -
4.319 - checkGraphOutArcList(adaptor, n1, 2);
4.320 - checkGraphOutArcList(adaptor, n2, 1);
4.321 - checkGraphOutArcList(adaptor, n3, 0);
4.322 -
4.323 - checkGraphInArcList(adaptor, n1, 0);
4.324 - checkGraphInArcList(adaptor, n2, 1);
4.325 - checkGraphInArcList(adaptor, n3, 2);
4.326 -
4.327 - checkNodeIds(adaptor);
4.328 - checkArcIds(adaptor);
4.329 -
4.330 - checkGraphNodeMap(adaptor);
4.331 - checkGraphArcMap(adaptor);
4.332 -
4.333 - // Hide a node
4.334 - adaptor.status(n1, false);
4.335 - adaptor.disable(n3);
4.336 - if (!adaptor.status(n3)) adaptor.enable(n3);
4.337 -
4.338 - checkGraphNodeList(adaptor, 2);
4.339 - checkGraphArcList(adaptor, 1);
4.340 - checkGraphConArcList(adaptor, 1);
4.341 -
4.342 - checkGraphOutArcList(adaptor, n2, 1);
4.343 - checkGraphOutArcList(adaptor, n3, 0);
4.344 -
4.345 - checkGraphInArcList(adaptor, n2, 0);
4.346 - checkGraphInArcList(adaptor, n3, 1);
4.347 -
4.348 - checkNodeIds(adaptor);
4.349 - checkArcIds(adaptor);
4.350 -
4.351 - checkGraphNodeMap(adaptor);
4.352 - checkGraphArcMap(adaptor);
4.353 -
4.354 - // Hide all nodes
4.355 - node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
4.356 -
4.357 - checkGraphNodeList(adaptor, 0);
4.358 - checkGraphArcList(adaptor, 0);
4.359 - checkGraphConArcList(adaptor, 0);
4.360 -
4.361 - checkNodeIds(adaptor);
4.362 - checkArcIds(adaptor);
4.363 -
4.364 - checkGraphNodeMap(adaptor);
4.365 - checkGraphArcMap(adaptor);
4.366 -
4.367 - // Check the conversion of nodes and arcs
4.368 - Digraph::Node nd = n3;
4.369 - nd = n3;
4.370 - Adaptor::Node na = n1;
4.371 - na = n2;
4.372 - Digraph::Arc ad = a3;
4.373 - ad = a3;
4.374 - Adaptor::Arc aa = a1;
4.375 - aa = a2;
4.376 -}
4.377 -
4.378 -void checkFilterArcs() {
4.379 - // Check concepts
4.380 - checkConcept<concepts::Digraph, FilterArcs<concepts::Digraph> >();
4.381 - checkConcept<concepts::Digraph, FilterArcs<ListDigraph> >();
4.382 - checkConcept<concepts::AlterableDigraphComponent<>,
4.383 - FilterArcs<ListDigraph> >();
4.384 - checkConcept<concepts::ExtendableDigraphComponent<>,
4.385 - FilterArcs<ListDigraph> >();
4.386 - checkConcept<concepts::ErasableDigraphComponent<>,
4.387 - FilterArcs<ListDigraph> >();
4.388 - checkConcept<concepts::ClearableDigraphComponent<>,
4.389 - FilterArcs<ListDigraph> >();
4.390 -
4.391 - // Create a digraph and an adaptor
4.392 - typedef ListDigraph Digraph;
4.393 - typedef Digraph::ArcMap<bool> ArcFilter;
4.394 - typedef FilterArcs<Digraph, ArcFilter> Adaptor;
4.395 -
4.396 - Digraph digraph;
4.397 - ArcFilter arc_filter(digraph);
4.398 - Adaptor adaptor(digraph, arc_filter);
4.399 -
4.400 - // Add nodes and arcs to the original digraph and the adaptor
4.401 - Digraph::Node n1 = digraph.addNode();
4.402 - Digraph::Node n2 = digraph.addNode();
4.403 - Adaptor::Node n3 = adaptor.addNode();
4.404 -
4.405 - Digraph::Arc a1 = digraph.addArc(n1, n2);
4.406 - Digraph::Arc a2 = digraph.addArc(n1, n3);
4.407 - Adaptor::Arc a3 = adaptor.addArc(n2, n3);
4.408 -
4.409 - arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
4.410 -
4.411 - checkGraphNodeList(adaptor, 3);
4.412 - checkGraphArcList(adaptor, 3);
4.413 - checkGraphConArcList(adaptor, 3);
4.414 -
4.415 - checkGraphOutArcList(adaptor, n1, 2);
4.416 - checkGraphOutArcList(adaptor, n2, 1);
4.417 - checkGraphOutArcList(adaptor, n3, 0);
4.418 -
4.419 - checkGraphInArcList(adaptor, n1, 0);
4.420 - checkGraphInArcList(adaptor, n2, 1);
4.421 - checkGraphInArcList(adaptor, n3, 2);
4.422 -
4.423 - checkNodeIds(adaptor);
4.424 - checkArcIds(adaptor);
4.425 -
4.426 - checkGraphNodeMap(adaptor);
4.427 - checkGraphArcMap(adaptor);
4.428 -
4.429 - // Hide an arc
4.430 - adaptor.status(a2, false);
4.431 - adaptor.disable(a3);
4.432 - if (!adaptor.status(a3)) adaptor.enable(a3);
4.433 -
4.434 - checkGraphNodeList(adaptor, 3);
4.435 - checkGraphArcList(adaptor, 2);
4.436 - checkGraphConArcList(adaptor, 2);
4.437 -
4.438 - checkGraphOutArcList(adaptor, n1, 1);
4.439 - checkGraphOutArcList(adaptor, n2, 1);
4.440 - checkGraphOutArcList(adaptor, n3, 0);
4.441 -
4.442 - checkGraphInArcList(adaptor, n1, 0);
4.443 - checkGraphInArcList(adaptor, n2, 1);
4.444 - checkGraphInArcList(adaptor, n3, 1);
4.445 -
4.446 - checkNodeIds(adaptor);
4.447 - checkArcIds(adaptor);
4.448 -
4.449 - checkGraphNodeMap(adaptor);
4.450 - checkGraphArcMap(adaptor);
4.451 -
4.452 - // Hide all arcs
4.453 - arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
4.454 -
4.455 - checkGraphNodeList(adaptor, 3);
4.456 - checkGraphArcList(adaptor, 0);
4.457 - checkGraphConArcList(adaptor, 0);
4.458 -
4.459 - checkNodeIds(adaptor);
4.460 - checkArcIds(adaptor);
4.461 -
4.462 - checkGraphNodeMap(adaptor);
4.463 - checkGraphArcMap(adaptor);
4.464 -
4.465 - // Check the conversion of nodes and arcs
4.466 - Digraph::Node nd = n3;
4.467 - nd = n3;
4.468 - Adaptor::Node na = n1;
4.469 - na = n2;
4.470 - Digraph::Arc ad = a3;
4.471 - ad = a3;
4.472 - Adaptor::Arc aa = a1;
4.473 - aa = a2;
4.474 -}
4.475 -
4.476 -void checkUndirector() {
4.477 - // Check concepts
4.478 - checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
4.479 - checkConcept<concepts::Graph, Undirector<ListDigraph> >();
4.480 - checkConcept<concepts::AlterableGraphComponent<>,
4.481 - Undirector<ListDigraph> >();
4.482 - checkConcept<concepts::ExtendableGraphComponent<>,
4.483 - Undirector<ListDigraph> >();
4.484 - checkConcept<concepts::ErasableGraphComponent<>,
4.485 - Undirector<ListDigraph> >();
4.486 - checkConcept<concepts::ClearableGraphComponent<>,
4.487 - Undirector<ListDigraph> >();
4.488 -
4.489 -
4.490 - // Create a digraph and an adaptor
4.491 - typedef ListDigraph Digraph;
4.492 - typedef Undirector<Digraph> Adaptor;
4.493 -
4.494 - Digraph digraph;
4.495 - Adaptor adaptor(digraph);
4.496 -
4.497 - // Add nodes and arcs/edges to the original digraph and the adaptor
4.498 - Digraph::Node n1 = digraph.addNode();
4.499 - Digraph::Node n2 = digraph.addNode();
4.500 - Adaptor::Node n3 = adaptor.addNode();
4.501 -
4.502 - Digraph::Arc a1 = digraph.addArc(n1, n2);
4.503 - Digraph::Arc a2 = digraph.addArc(n1, n3);
4.504 - Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
4.505 -
4.506 - // Check the original digraph
4.507 - checkGraphNodeList(digraph, 3);
4.508 - checkGraphArcList(digraph, 3);
4.509 - checkGraphConArcList(digraph, 3);
4.510 -
4.511 - checkGraphOutArcList(digraph, n1, 2);
4.512 - checkGraphOutArcList(digraph, n2, 1);
4.513 - checkGraphOutArcList(digraph, n3, 0);
4.514 -
4.515 - checkGraphInArcList(digraph, n1, 0);
4.516 - checkGraphInArcList(digraph, n2, 1);
4.517 - checkGraphInArcList(digraph, n3, 2);
4.518 -
4.519 - checkNodeIds(digraph);
4.520 - checkArcIds(digraph);
4.521 -
4.522 - checkGraphNodeMap(digraph);
4.523 - checkGraphArcMap(digraph);
4.524 -
4.525 - // Check the adaptor
4.526 - checkGraphNodeList(adaptor, 3);
4.527 - checkGraphArcList(adaptor, 6);
4.528 - checkGraphEdgeList(adaptor, 3);
4.529 - checkGraphConArcList(adaptor, 6);
4.530 - checkGraphConEdgeList(adaptor, 3);
4.531 -
4.532 - checkGraphIncEdgeArcLists(adaptor, n1, 2);
4.533 - checkGraphIncEdgeArcLists(adaptor, n2, 2);
4.534 - checkGraphIncEdgeArcLists(adaptor, n3, 2);
4.535 -
4.536 - checkNodeIds(adaptor);
4.537 - checkArcIds(adaptor);
4.538 - checkEdgeIds(adaptor);
4.539 -
4.540 - checkGraphNodeMap(adaptor);
4.541 - checkGraphArcMap(adaptor);
4.542 - checkGraphEdgeMap(adaptor);
4.543 -
4.544 - // Check the edges of the adaptor
4.545 - for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {
4.546 - check(adaptor.u(e) == digraph.source(e), "Wrong undir");
4.547 - check(adaptor.v(e) == digraph.target(e), "Wrong undir");
4.548 - }
4.549 -
4.550 - // Check CombinedArcMap
4.551 - typedef Adaptor::CombinedArcMap
4.552 - <Digraph::ArcMap<int>, Digraph::ArcMap<int> > IntCombinedMap;
4.553 - typedef Adaptor::CombinedArcMap
4.554 - <Digraph::ArcMap<bool>, Digraph::ArcMap<bool> > BoolCombinedMap;
4.555 - checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,
4.556 - IntCombinedMap>();
4.557 - checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,
4.558 - BoolCombinedMap>();
4.559 -
4.560 - Digraph::ArcMap<int> fw_map(digraph), bk_map(digraph);
4.561 - for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
4.562 - fw_map[a] = digraph.id(a);
4.563 - bk_map[a] = -digraph.id(a);
4.564 - }
4.565 -
4.566 - Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::ArcMap<int> >
4.567 - comb_map(fw_map, bk_map);
4.568 - for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
4.569 - if (adaptor.source(a) == digraph.source(a)) {
4.570 - check(comb_map[a] == fw_map[a], "Wrong combined map");
4.571 - } else {
4.572 - check(comb_map[a] == bk_map[a], "Wrong combined map");
4.573 - }
4.574 - }
4.575 -
4.576 - // Check the conversion of nodes and arcs/edges
4.577 - Digraph::Node nd = n3;
4.578 - nd = n3;
4.579 - Adaptor::Node na = n1;
4.580 - na = n2;
4.581 - Digraph::Arc ad = e3;
4.582 - ad = e3;
4.583 - Adaptor::Edge ea = a1;
4.584 - ea = a2;
4.585 -}
4.586 -
4.587 -void checkResidualDigraph() {
4.588 - // Check concepts
4.589 - checkConcept<concepts::Digraph, ResidualDigraph<concepts::Digraph> >();
4.590 - checkConcept<concepts::Digraph, ResidualDigraph<ListDigraph> >();
4.591 -
4.592 - // Create a digraph and an adaptor
4.593 - typedef ListDigraph Digraph;
4.594 - typedef Digraph::ArcMap<int> IntArcMap;
4.595 - typedef ResidualDigraph<Digraph, IntArcMap> Adaptor;
4.596 -
4.597 - Digraph digraph;
4.598 - IntArcMap capacity(digraph), flow(digraph);
4.599 - Adaptor adaptor(digraph, capacity, flow);
4.600 -
4.601 - Digraph::Node n1 = digraph.addNode();
4.602 - Digraph::Node n2 = digraph.addNode();
4.603 - Digraph::Node n3 = digraph.addNode();
4.604 - Digraph::Node n4 = digraph.addNode();
4.605 -
4.606 - Digraph::Arc a1 = digraph.addArc(n1, n2);
4.607 - Digraph::Arc a2 = digraph.addArc(n1, n3);
4.608 - Digraph::Arc a3 = digraph.addArc(n1, n4);
4.609 - Digraph::Arc a4 = digraph.addArc(n2, n3);
4.610 - Digraph::Arc a5 = digraph.addArc(n2, n4);
4.611 - Digraph::Arc a6 = digraph.addArc(n3, n4);
4.612 -
4.613 - capacity[a1] = 8;
4.614 - capacity[a2] = 6;
4.615 - capacity[a3] = 4;
4.616 - capacity[a4] = 4;
4.617 - capacity[a5] = 6;
4.618 - capacity[a6] = 10;
4.619 -
4.620 - // Check the adaptor with various flow values
4.621 - for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
4.622 - flow[a] = 0;
4.623 - }
4.624 -
4.625 - checkGraphNodeList(adaptor, 4);
4.626 - checkGraphArcList(adaptor, 6);
4.627 - checkGraphConArcList(adaptor, 6);
4.628 -
4.629 - checkGraphOutArcList(adaptor, n1, 3);
4.630 - checkGraphOutArcList(adaptor, n2, 2);
4.631 - checkGraphOutArcList(adaptor, n3, 1);
4.632 - checkGraphOutArcList(adaptor, n4, 0);
4.633 -
4.634 - checkGraphInArcList(adaptor, n1, 0);
4.635 - checkGraphInArcList(adaptor, n2, 1);
4.636 - checkGraphInArcList(adaptor, n3, 2);
4.637 - checkGraphInArcList(adaptor, n4, 3);
4.638 -
4.639 - for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
4.640 - flow[a] = capacity[a] / 2;
4.641 - }
4.642 -
4.643 - checkGraphNodeList(adaptor, 4);
4.644 - checkGraphArcList(adaptor, 12);
4.645 - checkGraphConArcList(adaptor, 12);
4.646 -
4.647 - checkGraphOutArcList(adaptor, n1, 3);
4.648 - checkGraphOutArcList(adaptor, n2, 3);
4.649 - checkGraphOutArcList(adaptor, n3, 3);
4.650 - checkGraphOutArcList(adaptor, n4, 3);
4.651 -
4.652 - checkGraphInArcList(adaptor, n1, 3);
4.653 - checkGraphInArcList(adaptor, n2, 3);
4.654 - checkGraphInArcList(adaptor, n3, 3);
4.655 - checkGraphInArcList(adaptor, n4, 3);
4.656 -
4.657 - checkNodeIds(adaptor);
4.658 - checkArcIds(adaptor);
4.659 -
4.660 - checkGraphNodeMap(adaptor);
4.661 - checkGraphArcMap(adaptor);
4.662 -
4.663 - for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
4.664 - flow[a] = capacity[a];
4.665 - }
4.666 -
4.667 - checkGraphNodeList(adaptor, 4);
4.668 - checkGraphArcList(adaptor, 6);
4.669 - checkGraphConArcList(adaptor, 6);
4.670 -
4.671 - checkGraphOutArcList(adaptor, n1, 0);
4.672 - checkGraphOutArcList(adaptor, n2, 1);
4.673 - checkGraphOutArcList(adaptor, n3, 2);
4.674 - checkGraphOutArcList(adaptor, n4, 3);
4.675 -
4.676 - checkGraphInArcList(adaptor, n1, 3);
4.677 - checkGraphInArcList(adaptor, n2, 2);
4.678 - checkGraphInArcList(adaptor, n3, 1);
4.679 - checkGraphInArcList(adaptor, n4, 0);
4.680 -
4.681 - // Saturate all backward arcs
4.682 - // (set the flow to zero on all forward arcs)
4.683 - for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
4.684 - if (adaptor.backward(a))
4.685 - adaptor.augment(a, adaptor.residualCapacity(a));
4.686 - }
4.687 -
4.688 - checkGraphNodeList(adaptor, 4);
4.689 - checkGraphArcList(adaptor, 6);
4.690 - checkGraphConArcList(adaptor, 6);
4.691 -
4.692 - checkGraphOutArcList(adaptor, n1, 3);
4.693 - checkGraphOutArcList(adaptor, n2, 2);
4.694 - checkGraphOutArcList(adaptor, n3, 1);
4.695 - checkGraphOutArcList(adaptor, n4, 0);
4.696 -
4.697 - checkGraphInArcList(adaptor, n1, 0);
4.698 - checkGraphInArcList(adaptor, n2, 1);
4.699 - checkGraphInArcList(adaptor, n3, 2);
4.700 - checkGraphInArcList(adaptor, n4, 3);
4.701 -
4.702 - // Find maximum flow by augmenting along shortest paths
4.703 - int flow_value = 0;
4.704 - Adaptor::ResidualCapacity res_cap(adaptor);
4.705 - while (true) {
4.706 -
4.707 - Bfs<Adaptor> bfs(adaptor);
4.708 - bfs.run(n1, n4);
4.709 -
4.710 - if (!bfs.reached(n4)) break;
4.711 -
4.712 - Path<Adaptor> p = bfs.path(n4);
4.713 -
4.714 - int min = std::numeric_limits<int>::max();
4.715 - for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
4.716 - if (res_cap[a] < min) min = res_cap[a];
4.717 - }
4.718 -
4.719 - for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
4.720 - adaptor.augment(a, min);
4.721 - }
4.722 - flow_value += min;
4.723 - }
4.724 -
4.725 - check(flow_value == 18, "Wrong flow with res graph adaptor");
4.726 -
4.727 - // Check forward() and backward()
4.728 - for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
4.729 - check(adaptor.forward(a) != adaptor.backward(a),
4.730 - "Wrong forward() or backward()");
4.731 - check((adaptor.forward(a) && adaptor.forward(Digraph::Arc(a)) == a) ||
4.732 - (adaptor.backward(a) && adaptor.backward(Digraph::Arc(a)) == a),
4.733 - "Wrong forward() or backward()");
4.734 - }
4.735 -
4.736 - // Check the conversion of nodes and arcs
4.737 - Digraph::Node nd = Adaptor::NodeIt(adaptor);
4.738 - nd = ++Adaptor::NodeIt(adaptor);
4.739 - Adaptor::Node na = n1;
4.740 - na = n2;
4.741 - Digraph::Arc ad = Adaptor::ArcIt(adaptor);
4.742 - ad = ++Adaptor::ArcIt(adaptor);
4.743 -}
4.744 -
4.745 -void checkSplitNodes() {
4.746 - // Check concepts
4.747 - checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
4.748 - checkConcept<concepts::Digraph, SplitNodes<ListDigraph> >();
4.749 -
4.750 - // Create a digraph and an adaptor
4.751 - typedef ListDigraph Digraph;
4.752 - typedef SplitNodes<Digraph> Adaptor;
4.753 -
4.754 - Digraph digraph;
4.755 - Adaptor adaptor(digraph);
4.756 -
4.757 - Digraph::Node n1 = digraph.addNode();
4.758 - Digraph::Node n2 = digraph.addNode();
4.759 - Digraph::Node n3 = digraph.addNode();
4.760 -
4.761 - Digraph::Arc a1 = digraph.addArc(n1, n2);
4.762 - Digraph::Arc a2 = digraph.addArc(n1, n3);
4.763 - Digraph::Arc a3 = digraph.addArc(n2, n3);
4.764 -
4.765 - checkGraphNodeList(adaptor, 6);
4.766 - checkGraphArcList(adaptor, 6);
4.767 - checkGraphConArcList(adaptor, 6);
4.768 -
4.769 - checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
4.770 - checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2);
4.771 - checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
4.772 - checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1);
4.773 - checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
4.774 - checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0);
4.775 -
4.776 - checkGraphInArcList(adaptor, adaptor.inNode(n1), 0);
4.777 - checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
4.778 - checkGraphInArcList(adaptor, adaptor.inNode(n2), 1);
4.779 - checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
4.780 - checkGraphInArcList(adaptor, adaptor.inNode(n3), 2);
4.781 - checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
4.782 -
4.783 - checkNodeIds(adaptor);
4.784 - checkArcIds(adaptor);
4.785 -
4.786 - checkGraphNodeMap(adaptor);
4.787 - checkGraphArcMap(adaptor);
4.788 -
4.789 - // Check split
4.790 - for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
4.791 - if (adaptor.origArc(a)) {
4.792 - Digraph::Arc oa = a;
4.793 - check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),
4.794 - "Wrong split");
4.795 - check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),
4.796 - "Wrong split");
4.797 - } else {
4.798 - Digraph::Node on = a;
4.799 - check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");
4.800 - check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");
4.801 - }
4.802 - }
4.803 -
4.804 - // Check combined node map
4.805 - typedef Adaptor::CombinedNodeMap
4.806 - <Digraph::NodeMap<int>, Digraph::NodeMap<int> > IntCombinedNodeMap;
4.807 - typedef Adaptor::CombinedNodeMap
4.808 - <Digraph::NodeMap<bool>, Digraph::NodeMap<bool> > BoolCombinedNodeMap;
4.809 - checkConcept<concepts::ReferenceMap<Adaptor::Node, int, int&, const int&>,
4.810 - IntCombinedNodeMap>();
4.811 -//checkConcept<concepts::ReferenceMap<Adaptor::Node, bool, bool&, const bool&>,
4.812 -// BoolCombinedNodeMap>();
4.813 - checkConcept<concepts::ReadWriteMap<Adaptor::Node, bool>,
4.814 - BoolCombinedNodeMap>();
4.815 -
4.816 - Digraph::NodeMap<int> in_map(digraph), out_map(digraph);
4.817 - for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {
4.818 - in_map[n] = digraph.id(n);
4.819 - out_map[n] = -digraph.id(n);
4.820 - }
4.821 -
4.822 - Adaptor::CombinedNodeMap<Digraph::NodeMap<int>, Digraph::NodeMap<int> >
4.823 - node_map(in_map, out_map);
4.824 - for (Adaptor::NodeIt n(adaptor); n != INVALID; ++n) {
4.825 - if (adaptor.inNode(n)) {
4.826 - check(node_map[n] == in_map[n], "Wrong combined node map");
4.827 - } else {
4.828 - check(node_map[n] == out_map[n], "Wrong combined node map");
4.829 - }
4.830 - }
4.831 -
4.832 - // Check combined arc map
4.833 - typedef Adaptor::CombinedArcMap
4.834 - <Digraph::ArcMap<int>, Digraph::NodeMap<int> > IntCombinedArcMap;
4.835 - typedef Adaptor::CombinedArcMap
4.836 - <Digraph::ArcMap<bool>, Digraph::NodeMap<bool> > BoolCombinedArcMap;
4.837 - checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,
4.838 - IntCombinedArcMap>();
4.839 -//checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,
4.840 -// BoolCombinedArcMap>();
4.841 - checkConcept<concepts::ReadWriteMap<Adaptor::Arc, bool>,
4.842 - BoolCombinedArcMap>();
4.843 -
4.844 - Digraph::ArcMap<int> a_map(digraph);
4.845 - for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
4.846 - a_map[a] = digraph.id(a);
4.847 - }
4.848 -
4.849 - Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::NodeMap<int> >
4.850 - arc_map(a_map, out_map);
4.851 - for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
4.852 - check(arc_map[adaptor.arc(a)] == a_map[a], "Wrong combined arc map");
4.853 - }
4.854 - for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {
4.855 - check(arc_map[adaptor.arc(n)] == out_map[n], "Wrong combined arc map");
4.856 - }
4.857 -
4.858 - // Check the conversion of nodes
4.859 - Digraph::Node nd = adaptor.inNode(n1);
4.860 - check (nd == n1, "Wrong node conversion");
4.861 - nd = adaptor.outNode(n2);
4.862 - check (nd == n2, "Wrong node conversion");
4.863 -}
4.864 -
4.865 -void checkSubGraph() {
4.866 - // Check concepts
4.867 - checkConcept<concepts::Graph, SubGraph<concepts::Graph> >();
4.868 - checkConcept<concepts::Graph, SubGraph<ListGraph> >();
4.869 - checkConcept<concepts::AlterableGraphComponent<>,
4.870 - SubGraph<ListGraph> >();
4.871 - checkConcept<concepts::ExtendableGraphComponent<>,
4.872 - SubGraph<ListGraph> >();
4.873 - checkConcept<concepts::ErasableGraphComponent<>,
4.874 - SubGraph<ListGraph> >();
4.875 - checkConcept<concepts::ClearableGraphComponent<>,
4.876 - SubGraph<ListGraph> >();
4.877 -
4.878 - // Create a graph and an adaptor
4.879 - typedef ListGraph Graph;
4.880 - typedef Graph::NodeMap<bool> NodeFilter;
4.881 - typedef Graph::EdgeMap<bool> EdgeFilter;
4.882 - typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;
4.883 -
4.884 - Graph graph;
4.885 - NodeFilter node_filter(graph);
4.886 - EdgeFilter edge_filter(graph);
4.887 - Adaptor adaptor(graph, node_filter, edge_filter);
4.888 -
4.889 - // Add nodes and edges to the original graph and the adaptor
4.890 - Graph::Node n1 = graph.addNode();
4.891 - Graph::Node n2 = graph.addNode();
4.892 - Adaptor::Node n3 = adaptor.addNode();
4.893 - Adaptor::Node n4 = adaptor.addNode();
4.894 -
4.895 - node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
4.896 -
4.897 - Graph::Edge e1 = graph.addEdge(n1, n2);
4.898 - Graph::Edge e2 = graph.addEdge(n1, n3);
4.899 - Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
4.900 - Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
4.901 -
4.902 - edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
4.903 -
4.904 - checkGraphNodeList(adaptor, 4);
4.905 - checkGraphArcList(adaptor, 8);
4.906 - checkGraphEdgeList(adaptor, 4);
4.907 - checkGraphConArcList(adaptor, 8);
4.908 - checkGraphConEdgeList(adaptor, 4);
4.909 -
4.910 - checkGraphIncEdgeArcLists(adaptor, n1, 2);
4.911 - checkGraphIncEdgeArcLists(adaptor, n2, 2);
4.912 - checkGraphIncEdgeArcLists(adaptor, n3, 3);
4.913 - checkGraphIncEdgeArcLists(adaptor, n4, 1);
4.914 -
4.915 - checkNodeIds(adaptor);
4.916 - checkArcIds(adaptor);
4.917 - checkEdgeIds(adaptor);
4.918 -
4.919 - checkGraphNodeMap(adaptor);
4.920 - checkGraphArcMap(adaptor);
4.921 - checkGraphEdgeMap(adaptor);
4.922 -
4.923 - // Hide an edge
4.924 - adaptor.status(e2, false);
4.925 - adaptor.disable(e3);
4.926 - if (!adaptor.status(e3)) adaptor.enable(e3);
4.927 -
4.928 - checkGraphNodeList(adaptor, 4);
4.929 - checkGraphArcList(adaptor, 6);
4.930 - checkGraphEdgeList(adaptor, 3);
4.931 - checkGraphConArcList(adaptor, 6);
4.932 - checkGraphConEdgeList(adaptor, 3);
4.933 -
4.934 - checkGraphIncEdgeArcLists(adaptor, n1, 1);
4.935 - checkGraphIncEdgeArcLists(adaptor, n2, 2);
4.936 - checkGraphIncEdgeArcLists(adaptor, n3, 2);
4.937 - checkGraphIncEdgeArcLists(adaptor, n4, 1);
4.938 -
4.939 - checkNodeIds(adaptor);
4.940 - checkArcIds(adaptor);
4.941 - checkEdgeIds(adaptor);
4.942 -
4.943 - checkGraphNodeMap(adaptor);
4.944 - checkGraphArcMap(adaptor);
4.945 - checkGraphEdgeMap(adaptor);
4.946 -
4.947 - // Hide a node
4.948 - adaptor.status(n1, false);
4.949 - adaptor.disable(n3);
4.950 - if (!adaptor.status(n3)) adaptor.enable(n3);
4.951 -
4.952 - checkGraphNodeList(adaptor, 3);
4.953 - checkGraphArcList(adaptor, 4);
4.954 - checkGraphEdgeList(adaptor, 2);
4.955 - checkGraphConArcList(adaptor, 4);
4.956 - checkGraphConEdgeList(adaptor, 2);
4.957 -
4.958 - checkGraphIncEdgeArcLists(adaptor, n2, 1);
4.959 - checkGraphIncEdgeArcLists(adaptor, n3, 2);
4.960 - checkGraphIncEdgeArcLists(adaptor, n4, 1);
4.961 -
4.962 - checkNodeIds(adaptor);
4.963 - checkArcIds(adaptor);
4.964 - checkEdgeIds(adaptor);
4.965 -
4.966 - checkGraphNodeMap(adaptor);
4.967 - checkGraphArcMap(adaptor);
4.968 - checkGraphEdgeMap(adaptor);
4.969 -
4.970 - // Hide all nodes and edges
4.971 - node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
4.972 - edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
4.973 -
4.974 - checkGraphNodeList(adaptor, 0);
4.975 - checkGraphArcList(adaptor, 0);
4.976 - checkGraphEdgeList(adaptor, 0);
4.977 - checkGraphConArcList(adaptor, 0);
4.978 - checkGraphConEdgeList(adaptor, 0);
4.979 -
4.980 - checkNodeIds(adaptor);
4.981 - checkArcIds(adaptor);
4.982 - checkEdgeIds(adaptor);
4.983 -
4.984 - checkGraphNodeMap(adaptor);
4.985 - checkGraphArcMap(adaptor);
4.986 - checkGraphEdgeMap(adaptor);
4.987 -
4.988 - // Check the conversion of nodes and edges
4.989 - Graph::Node ng = n3;
4.990 - ng = n4;
4.991 - Adaptor::Node na = n1;
4.992 - na = n2;
4.993 - Graph::Edge eg = e3;
4.994 - eg = e4;
4.995 - Adaptor::Edge ea = e1;
4.996 - ea = e2;
4.997 -}
4.998 -
4.999 -void checkFilterNodes2() {
4.1000 - // Check concepts
4.1001 - checkConcept<concepts::Graph, FilterNodes<concepts::Graph> >();
4.1002 - checkConcept<concepts::Graph, FilterNodes<ListGraph> >();
4.1003 - checkConcept<concepts::AlterableGraphComponent<>,
4.1004 - FilterNodes<ListGraph> >();
4.1005 - checkConcept<concepts::ExtendableGraphComponent<>,
4.1006 - FilterNodes<ListGraph> >();
4.1007 - checkConcept<concepts::ErasableGraphComponent<>,
4.1008 - FilterNodes<ListGraph> >();
4.1009 - checkConcept<concepts::ClearableGraphComponent<>,
4.1010 - FilterNodes<ListGraph> >();
4.1011 -
4.1012 - // Create a graph and an adaptor
4.1013 - typedef ListGraph Graph;
4.1014 - typedef Graph::NodeMap<bool> NodeFilter;
4.1015 - typedef FilterNodes<Graph, NodeFilter> Adaptor;
4.1016 -
4.1017 - // Add nodes and edges to the original graph and the adaptor
4.1018 - Graph graph;
4.1019 - NodeFilter node_filter(graph);
4.1020 - Adaptor adaptor(graph, node_filter);
4.1021 -
4.1022 - Graph::Node n1 = graph.addNode();
4.1023 - Graph::Node n2 = graph.addNode();
4.1024 - Adaptor::Node n3 = adaptor.addNode();
4.1025 - Adaptor::Node n4 = adaptor.addNode();
4.1026 -
4.1027 - node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
4.1028 -
4.1029 - Graph::Edge e1 = graph.addEdge(n1, n2);
4.1030 - Graph::Edge e2 = graph.addEdge(n1, n3);
4.1031 - Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
4.1032 - Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
4.1033 -
4.1034 - checkGraphNodeList(adaptor, 4);
4.1035 - checkGraphArcList(adaptor, 8);
4.1036 - checkGraphEdgeList(adaptor, 4);
4.1037 - checkGraphConArcList(adaptor, 8);
4.1038 - checkGraphConEdgeList(adaptor, 4);
4.1039 -
4.1040 - checkGraphIncEdgeArcLists(adaptor, n1, 2);
4.1041 - checkGraphIncEdgeArcLists(adaptor, n2, 2);
4.1042 - checkGraphIncEdgeArcLists(adaptor, n3, 3);
4.1043 - checkGraphIncEdgeArcLists(adaptor, n4, 1);
4.1044 -
4.1045 - checkNodeIds(adaptor);
4.1046 - checkArcIds(adaptor);
4.1047 - checkEdgeIds(adaptor);
4.1048 -
4.1049 - checkGraphNodeMap(adaptor);
4.1050 - checkGraphArcMap(adaptor);
4.1051 - checkGraphEdgeMap(adaptor);
4.1052 -
4.1053 - // Hide a node
4.1054 - adaptor.status(n1, false);
4.1055 - adaptor.disable(n3);
4.1056 - if (!adaptor.status(n3)) adaptor.enable(n3);
4.1057 -
4.1058 - checkGraphNodeList(adaptor, 3);
4.1059 - checkGraphArcList(adaptor, 4);
4.1060 - checkGraphEdgeList(adaptor, 2);
4.1061 - checkGraphConArcList(adaptor, 4);
4.1062 - checkGraphConEdgeList(adaptor, 2);
4.1063 -
4.1064 - checkGraphIncEdgeArcLists(adaptor, n2, 1);
4.1065 - checkGraphIncEdgeArcLists(adaptor, n3, 2);
4.1066 - checkGraphIncEdgeArcLists(adaptor, n4, 1);
4.1067 -
4.1068 - checkNodeIds(adaptor);
4.1069 - checkArcIds(adaptor);
4.1070 - checkEdgeIds(adaptor);
4.1071 -
4.1072 - checkGraphNodeMap(adaptor);
4.1073 - checkGraphArcMap(adaptor);
4.1074 - checkGraphEdgeMap(adaptor);
4.1075 -
4.1076 - // Hide all nodes
4.1077 - node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
4.1078 -
4.1079 - checkGraphNodeList(adaptor, 0);
4.1080 - checkGraphArcList(adaptor, 0);
4.1081 - checkGraphEdgeList(adaptor, 0);
4.1082 - checkGraphConArcList(adaptor, 0);
4.1083 - checkGraphConEdgeList(adaptor, 0);
4.1084 -
4.1085 - checkNodeIds(adaptor);
4.1086 - checkArcIds(adaptor);
4.1087 - checkEdgeIds(adaptor);
4.1088 -
4.1089 - checkGraphNodeMap(adaptor);
4.1090 - checkGraphArcMap(adaptor);
4.1091 - checkGraphEdgeMap(adaptor);
4.1092 -
4.1093 - // Check the conversion of nodes and edges
4.1094 - Graph::Node ng = n3;
4.1095 - ng = n4;
4.1096 - Adaptor::Node na = n1;
4.1097 - na = n2;
4.1098 - Graph::Edge eg = e3;
4.1099 - eg = e4;
4.1100 - Adaptor::Edge ea = e1;
4.1101 - ea = e2;
4.1102 -}
4.1103 -
4.1104 -void checkFilterEdges() {
4.1105 - // Check concepts
4.1106 - checkConcept<concepts::Graph, FilterEdges<concepts::Graph> >();
4.1107 - checkConcept<concepts::Graph, FilterEdges<ListGraph> >();
4.1108 - checkConcept<concepts::AlterableGraphComponent<>,
4.1109 - FilterEdges<ListGraph> >();
4.1110 - checkConcept<concepts::ExtendableGraphComponent<>,
4.1111 - FilterEdges<ListGraph> >();
4.1112 - checkConcept<concepts::ErasableGraphComponent<>,
4.1113 - FilterEdges<ListGraph> >();
4.1114 - checkConcept<concepts::ClearableGraphComponent<>,
4.1115 - FilterEdges<ListGraph> >();
4.1116 -
4.1117 - // Create a graph and an adaptor
4.1118 - typedef ListGraph Graph;
4.1119 - typedef Graph::EdgeMap<bool> EdgeFilter;
4.1120 - typedef FilterEdges<Graph, EdgeFilter> Adaptor;
4.1121 -
4.1122 - Graph graph;
4.1123 - EdgeFilter edge_filter(graph);
4.1124 - Adaptor adaptor(graph, edge_filter);
4.1125 -
4.1126 - // Add nodes and edges to the original graph and the adaptor
4.1127 - Graph::Node n1 = graph.addNode();
4.1128 - Graph::Node n2 = graph.addNode();
4.1129 - Adaptor::Node n3 = adaptor.addNode();
4.1130 - Adaptor::Node n4 = adaptor.addNode();
4.1131 -
4.1132 - Graph::Edge e1 = graph.addEdge(n1, n2);
4.1133 - Graph::Edge e2 = graph.addEdge(n1, n3);
4.1134 - Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
4.1135 - Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
4.1136 -
4.1137 - edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
4.1138 -
4.1139 - checkGraphNodeList(adaptor, 4);
4.1140 - checkGraphArcList(adaptor, 8);
4.1141 - checkGraphEdgeList(adaptor, 4);
4.1142 - checkGraphConArcList(adaptor, 8);
4.1143 - checkGraphConEdgeList(adaptor, 4);
4.1144 -
4.1145 - checkGraphIncEdgeArcLists(adaptor, n1, 2);
4.1146 - checkGraphIncEdgeArcLists(adaptor, n2, 2);
4.1147 - checkGraphIncEdgeArcLists(adaptor, n3, 3);
4.1148 - checkGraphIncEdgeArcLists(adaptor, n4, 1);
4.1149 -
4.1150 - checkNodeIds(adaptor);
4.1151 - checkArcIds(adaptor);
4.1152 - checkEdgeIds(adaptor);
4.1153 -
4.1154 - checkGraphNodeMap(adaptor);
4.1155 - checkGraphArcMap(adaptor);
4.1156 - checkGraphEdgeMap(adaptor);
4.1157 -
4.1158 - // Hide an edge
4.1159 - adaptor.status(e2, false);
4.1160 - adaptor.disable(e3);
4.1161 - if (!adaptor.status(e3)) adaptor.enable(e3);
4.1162 -
4.1163 - checkGraphNodeList(adaptor, 4);
4.1164 - checkGraphArcList(adaptor, 6);
4.1165 - checkGraphEdgeList(adaptor, 3);
4.1166 - checkGraphConArcList(adaptor, 6);
4.1167 - checkGraphConEdgeList(adaptor, 3);
4.1168 -
4.1169 - checkGraphIncEdgeArcLists(adaptor, n1, 1);
4.1170 - checkGraphIncEdgeArcLists(adaptor, n2, 2);
4.1171 - checkGraphIncEdgeArcLists(adaptor, n3, 2);
4.1172 - checkGraphIncEdgeArcLists(adaptor, n4, 1);
4.1173 -
4.1174 - checkNodeIds(adaptor);
4.1175 - checkArcIds(adaptor);
4.1176 - checkEdgeIds(adaptor);
4.1177 -
4.1178 - checkGraphNodeMap(adaptor);
4.1179 - checkGraphArcMap(adaptor);
4.1180 - checkGraphEdgeMap(adaptor);
4.1181 -
4.1182 - // Hide all edges
4.1183 - edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
4.1184 -
4.1185 - checkGraphNodeList(adaptor, 4);
4.1186 - checkGraphArcList(adaptor, 0);
4.1187 - checkGraphEdgeList(adaptor, 0);
4.1188 - checkGraphConArcList(adaptor, 0);
4.1189 - checkGraphConEdgeList(adaptor, 0);
4.1190 -
4.1191 - checkNodeIds(adaptor);
4.1192 - checkArcIds(adaptor);
4.1193 - checkEdgeIds(adaptor);
4.1194 -
4.1195 - checkGraphNodeMap(adaptor);
4.1196 - checkGraphArcMap(adaptor);
4.1197 - checkGraphEdgeMap(adaptor);
4.1198 -
4.1199 - // Check the conversion of nodes and edges
4.1200 - Graph::Node ng = n3;
4.1201 - ng = n4;
4.1202 - Adaptor::Node na = n1;
4.1203 - na = n2;
4.1204 - Graph::Edge eg = e3;
4.1205 - eg = e4;
4.1206 - Adaptor::Edge ea = e1;
4.1207 - ea = e2;
4.1208 -}
4.1209 -
4.1210 -void checkOrienter() {
4.1211 - // Check concepts
4.1212 - checkConcept<concepts::Digraph, Orienter<concepts::Graph> >();
4.1213 - checkConcept<concepts::Digraph, Orienter<ListGraph> >();
4.1214 - checkConcept<concepts::AlterableDigraphComponent<>,
4.1215 - Orienter<ListGraph> >();
4.1216 - checkConcept<concepts::ExtendableDigraphComponent<>,
4.1217 - Orienter<ListGraph> >();
4.1218 - checkConcept<concepts::ErasableDigraphComponent<>,
4.1219 - Orienter<ListGraph> >();
4.1220 - checkConcept<concepts::ClearableDigraphComponent<>,
4.1221 - Orienter<ListGraph> >();
4.1222 -
4.1223 - // Create a graph and an adaptor
4.1224 - typedef ListGraph Graph;
4.1225 - typedef ListGraph::EdgeMap<bool> DirMap;
4.1226 - typedef Orienter<Graph> Adaptor;
4.1227 -
4.1228 - Graph graph;
4.1229 - DirMap dir(graph);
4.1230 - Adaptor adaptor(graph, dir);
4.1231 -
4.1232 - // Add nodes and edges to the original graph and the adaptor
4.1233 - Graph::Node n1 = graph.addNode();
4.1234 - Graph::Node n2 = graph.addNode();
4.1235 - Adaptor::Node n3 = adaptor.addNode();
4.1236 -
4.1237 - Graph::Edge e1 = graph.addEdge(n1, n2);
4.1238 - Graph::Edge e2 = graph.addEdge(n1, n3);
4.1239 - Adaptor::Arc e3 = adaptor.addArc(n2, n3);
4.1240 -
4.1241 - dir[e1] = dir[e2] = dir[e3] = true;
4.1242 -
4.1243 - // Check the original graph
4.1244 - checkGraphNodeList(graph, 3);
4.1245 - checkGraphArcList(graph, 6);
4.1246 - checkGraphConArcList(graph, 6);
4.1247 - checkGraphEdgeList(graph, 3);
4.1248 - checkGraphConEdgeList(graph, 3);
4.1249 -
4.1250 - checkGraphIncEdgeArcLists(graph, n1, 2);
4.1251 - checkGraphIncEdgeArcLists(graph, n2, 2);
4.1252 - checkGraphIncEdgeArcLists(graph, n3, 2);
4.1253 -
4.1254 - checkNodeIds(graph);
4.1255 - checkArcIds(graph);
4.1256 - checkEdgeIds(graph);
4.1257 -
4.1258 - checkGraphNodeMap(graph);
4.1259 - checkGraphArcMap(graph);
4.1260 - checkGraphEdgeMap(graph);
4.1261 -
4.1262 - // Check the adaptor
4.1263 - checkGraphNodeList(adaptor, 3);
4.1264 - checkGraphArcList(adaptor, 3);
4.1265 - checkGraphConArcList(adaptor, 3);
4.1266 -
4.1267 - checkGraphOutArcList(adaptor, n1, 2);
4.1268 - checkGraphOutArcList(adaptor, n2, 1);
4.1269 - checkGraphOutArcList(adaptor, n3, 0);
4.1270 -
4.1271 - checkGraphInArcList(adaptor, n1, 0);
4.1272 - checkGraphInArcList(adaptor, n2, 1);
4.1273 - checkGraphInArcList(adaptor, n3, 2);
4.1274 -
4.1275 - checkNodeIds(adaptor);
4.1276 - checkArcIds(adaptor);
4.1277 -
4.1278 - checkGraphNodeMap(adaptor);
4.1279 - checkGraphArcMap(adaptor);
4.1280 -
4.1281 - // Check direction changing
4.1282 - {
4.1283 - dir[e1] = true;
4.1284 - Adaptor::Node u = adaptor.source(e1);
4.1285 - Adaptor::Node v = adaptor.target(e1);
4.1286 -
4.1287 - dir[e1] = false;
4.1288 - check (u == adaptor.target(e1), "Wrong dir");
4.1289 - check (v == adaptor.source(e1), "Wrong dir");
4.1290 -
4.1291 - check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");
4.1292 - dir[e1] = n1 == u;
4.1293 - }
4.1294 -
4.1295 - {
4.1296 - dir[e2] = true;
4.1297 - Adaptor::Node u = adaptor.source(e2);
4.1298 - Adaptor::Node v = adaptor.target(e2);
4.1299 -
4.1300 - dir[e2] = false;
4.1301 - check (u == adaptor.target(e2), "Wrong dir");
4.1302 - check (v == adaptor.source(e2), "Wrong dir");
4.1303 -
4.1304 - check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");
4.1305 - dir[e2] = n3 == u;
4.1306 - }
4.1307 -
4.1308 - {
4.1309 - dir[e3] = true;
4.1310 - Adaptor::Node u = adaptor.source(e3);
4.1311 - Adaptor::Node v = adaptor.target(e3);
4.1312 -
4.1313 - dir[e3] = false;
4.1314 - check (u == adaptor.target(e3), "Wrong dir");
4.1315 - check (v == adaptor.source(e3), "Wrong dir");
4.1316 -
4.1317 - check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
4.1318 - dir[e3] = n2 == u;
4.1319 - }
4.1320 -
4.1321 - // Check the adaptor again
4.1322 - checkGraphNodeList(adaptor, 3);
4.1323 - checkGraphArcList(adaptor, 3);
4.1324 - checkGraphConArcList(adaptor, 3);
4.1325 -
4.1326 - checkGraphOutArcList(adaptor, n1, 1);
4.1327 - checkGraphOutArcList(adaptor, n2, 1);
4.1328 - checkGraphOutArcList(adaptor, n3, 1);
4.1329 -
4.1330 - checkGraphInArcList(adaptor, n1, 1);
4.1331 - checkGraphInArcList(adaptor, n2, 1);
4.1332 - checkGraphInArcList(adaptor, n3, 1);
4.1333 -
4.1334 - checkNodeIds(adaptor);
4.1335 - checkArcIds(adaptor);
4.1336 -
4.1337 - checkGraphNodeMap(adaptor);
4.1338 - checkGraphArcMap(adaptor);
4.1339 -
4.1340 - // Check reverseArc()
4.1341 - adaptor.reverseArc(e2);
4.1342 - adaptor.reverseArc(e3);
4.1343 - adaptor.reverseArc(e2);
4.1344 -
4.1345 - checkGraphNodeList(adaptor, 3);
4.1346 - checkGraphArcList(adaptor, 3);
4.1347 - checkGraphConArcList(adaptor, 3);
4.1348 -
4.1349 - checkGraphOutArcList(adaptor, n1, 1);
4.1350 - checkGraphOutArcList(adaptor, n2, 0);
4.1351 - checkGraphOutArcList(adaptor, n3, 2);
4.1352 -
4.1353 - checkGraphInArcList(adaptor, n1, 1);
4.1354 - checkGraphInArcList(adaptor, n2, 2);
4.1355 - checkGraphInArcList(adaptor, n3, 0);
4.1356 -
4.1357 - // Check the conversion of nodes and arcs/edges
4.1358 - Graph::Node ng = n3;
4.1359 - ng = n3;
4.1360 - Adaptor::Node na = n1;
4.1361 - na = n2;
4.1362 - Graph::Edge eg = e3;
4.1363 - eg = e3;
4.1364 - Adaptor::Arc aa = e1;
4.1365 - aa = e2;
4.1366 -}
4.1367 -
4.1368 -void checkCombiningAdaptors() {
4.1369 - // Create a grid graph
4.1370 - GridGraph graph(2,2);
4.1371 - GridGraph::Node n1 = graph(0,0);
4.1372 - GridGraph::Node n2 = graph(0,1);
4.1373 - GridGraph::Node n3 = graph(1,0);
4.1374 - GridGraph::Node n4 = graph(1,1);
4.1375 -
4.1376 - GridGraph::EdgeMap<bool> dir_map(graph);
4.1377 - dir_map[graph.right(n1)] = graph.u(graph.right(n1)) == n1;
4.1378 - dir_map[graph.up(n1)] = graph.u(graph.up(n1)) != n1;
4.1379 - dir_map[graph.left(n4)] = graph.u(graph.left(n4)) != n4;
4.1380 - dir_map[graph.down(n4)] = graph.u(graph.down(n4)) != n4;
4.1381 -
4.1382 - // Apply several adaptors on the grid graph
4.1383 - typedef SplitNodes< ReverseDigraph< const Orienter<
4.1384 - const GridGraph, GridGraph::EdgeMap<bool> > > >
4.1385 - RevSplitGridGraph;
4.1386 - typedef ReverseDigraph<const RevSplitGridGraph> SplitGridGraph;
4.1387 - typedef Undirector<const SplitGridGraph> USplitGridGraph;
4.1388 - typedef Undirector<const USplitGridGraph> UUSplitGridGraph;
4.1389 - checkConcept<concepts::Digraph, RevSplitGridGraph>();
4.1390 - checkConcept<concepts::Digraph, SplitGridGraph>();
4.1391 - checkConcept<concepts::Graph, USplitGridGraph>();
4.1392 - checkConcept<concepts::Graph, UUSplitGridGraph>();
4.1393 -
4.1394 - RevSplitGridGraph rev_adaptor =
4.1395 - splitNodes(reverseDigraph(orienter(graph, dir_map)));
4.1396 - SplitGridGraph adaptor = reverseDigraph(rev_adaptor);
4.1397 - USplitGridGraph uadaptor = undirector(adaptor);
4.1398 - UUSplitGridGraph uuadaptor = undirector(uadaptor);
4.1399 -
4.1400 - // Check adaptor
4.1401 - checkGraphNodeList(adaptor, 8);
4.1402 - checkGraphArcList(adaptor, 8);
4.1403 - checkGraphConArcList(adaptor, 8);
4.1404 -
4.1405 - checkGraphOutArcList(adaptor, rev_adaptor.inNode(n1), 1);
4.1406 - checkGraphOutArcList(adaptor, rev_adaptor.outNode(n1), 1);
4.1407 - checkGraphOutArcList(adaptor, rev_adaptor.inNode(n2), 2);
4.1408 - checkGraphOutArcList(adaptor, rev_adaptor.outNode(n2), 1);
4.1409 - checkGraphOutArcList(adaptor, rev_adaptor.inNode(n3), 1);
4.1410 - checkGraphOutArcList(adaptor, rev_adaptor.outNode(n3), 1);
4.1411 - checkGraphOutArcList(adaptor, rev_adaptor.inNode(n4), 0);
4.1412 - checkGraphOutArcList(adaptor, rev_adaptor.outNode(n4), 1);
4.1413 -
4.1414 - checkGraphInArcList(adaptor, rev_adaptor.inNode(n1), 1);
4.1415 - checkGraphInArcList(adaptor, rev_adaptor.outNode(n1), 1);
4.1416 - checkGraphInArcList(adaptor, rev_adaptor.inNode(n2), 1);
4.1417 - checkGraphInArcList(adaptor, rev_adaptor.outNode(n2), 0);
4.1418 - checkGraphInArcList(adaptor, rev_adaptor.inNode(n3), 1);
4.1419 - checkGraphInArcList(adaptor, rev_adaptor.outNode(n3), 1);
4.1420 - checkGraphInArcList(adaptor, rev_adaptor.inNode(n4), 1);
4.1421 - checkGraphInArcList(adaptor, rev_adaptor.outNode(n4), 2);
4.1422 -
4.1423 - checkNodeIds(adaptor);
4.1424 - checkArcIds(adaptor);
4.1425 -
4.1426 - checkGraphNodeMap(adaptor);
4.1427 - checkGraphArcMap(adaptor);
4.1428 -
4.1429 - // Check uadaptor
4.1430 - checkGraphNodeList(uadaptor, 8);
4.1431 - checkGraphEdgeList(uadaptor, 8);
4.1432 - checkGraphArcList(uadaptor, 16);
4.1433 - checkGraphConEdgeList(uadaptor, 8);
4.1434 - checkGraphConArcList(uadaptor, 16);
4.1435 -
4.1436 - checkNodeIds(uadaptor);
4.1437 - checkEdgeIds(uadaptor);
4.1438 - checkArcIds(uadaptor);
4.1439 -
4.1440 - checkGraphNodeMap(uadaptor);
4.1441 - checkGraphEdgeMap(uadaptor);
4.1442 - checkGraphArcMap(uadaptor);
4.1443 -
4.1444 - checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n1), 2);
4.1445 - checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n1), 2);
4.1446 - checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n2), 3);
4.1447 - checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n2), 1);
4.1448 - checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n3), 2);
4.1449 - checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n3), 2);
4.1450 - checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n4), 1);
4.1451 - checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n4), 3);
4.1452 -
4.1453 - // Check uuadaptor
4.1454 - checkGraphNodeList(uuadaptor, 8);
4.1455 - checkGraphEdgeList(uuadaptor, 16);
4.1456 - checkGraphArcList(uuadaptor, 32);
4.1457 - checkGraphConEdgeList(uuadaptor, 16);
4.1458 - checkGraphConArcList(uuadaptor, 32);
4.1459 -
4.1460 - checkNodeIds(uuadaptor);
4.1461 - checkEdgeIds(uuadaptor);
4.1462 - checkArcIds(uuadaptor);
4.1463 -
4.1464 - checkGraphNodeMap(uuadaptor);
4.1465 - checkGraphEdgeMap(uuadaptor);
4.1466 - checkGraphArcMap(uuadaptor);
4.1467 -}
4.1468 -
4.1469 -int main(int, const char **) {
4.1470 - // Check the digraph adaptors (using ListDigraph)
4.1471 - checkReverseDigraph();
4.1472 - checkSubDigraph();
4.1473 - checkFilterNodes1();
4.1474 - checkFilterArcs();
4.1475 - checkUndirector();
4.1476 - checkResidualDigraph();
4.1477 - checkSplitNodes();
4.1478 -
4.1479 - // Check the graph adaptors (using ListGraph)
4.1480 - checkSubGraph();
4.1481 - checkFilterNodes2();
4.1482 - checkFilterEdges();
4.1483 - checkOrienter();
4.1484 -
4.1485 - // Combine adaptors (using GridGraph)
4.1486 - checkCombiningAdaptors();
4.1487 -
4.1488 - return 0;
4.1489 -}