1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/adaptors_test.cc Thu Nov 05 15:50:01 2009 +0100
1.3 @@ -0,0 +1,1463 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2009
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#include <iostream>
1.23 +#include <limits>
1.24 +
1.25 +#include <lemon/list_graph.h>
1.26 +#include <lemon/grid_graph.h>
1.27 +#include <lemon/bfs.h>
1.28 +#include <lemon/path.h>
1.29 +
1.30 +#include <lemon/concepts/digraph.h>
1.31 +#include <lemon/concepts/graph.h>
1.32 +#include <lemon/concepts/graph_components.h>
1.33 +#include <lemon/concepts/maps.h>
1.34 +#include <lemon/concept_check.h>
1.35 +
1.36 +#include <lemon/adaptors.h>
1.37 +
1.38 +#include "test/test_tools.h"
1.39 +#include "test/graph_test.h"
1.40 +
1.41 +using namespace lemon;
1.42 +
1.43 +void checkReverseDigraph() {
1.44 + // Check concepts
1.45 + checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
1.46 + checkConcept<concepts::Digraph, ReverseDigraph<ListDigraph> >();
1.47 + checkConcept<concepts::AlterableDigraphComponent<>,
1.48 + ReverseDigraph<ListDigraph> >();
1.49 + checkConcept<concepts::ExtendableDigraphComponent<>,
1.50 + ReverseDigraph<ListDigraph> >();
1.51 + checkConcept<concepts::ErasableDigraphComponent<>,
1.52 + ReverseDigraph<ListDigraph> >();
1.53 + checkConcept<concepts::ClearableDigraphComponent<>,
1.54 + ReverseDigraph<ListDigraph> >();
1.55 +
1.56 + // Create a digraph and an adaptor
1.57 + typedef ListDigraph Digraph;
1.58 + typedef ReverseDigraph<Digraph> Adaptor;
1.59 +
1.60 + Digraph digraph;
1.61 + Adaptor adaptor(digraph);
1.62 +
1.63 + // Add nodes and arcs to the original digraph
1.64 + Digraph::Node n1 = digraph.addNode();
1.65 + Digraph::Node n2 = digraph.addNode();
1.66 + Digraph::Node n3 = digraph.addNode();
1.67 +
1.68 + Digraph::Arc a1 = digraph.addArc(n1, n2);
1.69 + Digraph::Arc a2 = digraph.addArc(n1, n3);
1.70 + Digraph::Arc a3 = digraph.addArc(n2, n3);
1.71 +
1.72 + // Check the adaptor
1.73 + checkGraphNodeList(adaptor, 3);
1.74 + checkGraphArcList(adaptor, 3);
1.75 + checkGraphConArcList(adaptor, 3);
1.76 +
1.77 + checkGraphOutArcList(adaptor, n1, 0);
1.78 + checkGraphOutArcList(adaptor, n2, 1);
1.79 + checkGraphOutArcList(adaptor, n3, 2);
1.80 +
1.81 + checkGraphInArcList(adaptor, n1, 2);
1.82 + checkGraphInArcList(adaptor, n2, 1);
1.83 + checkGraphInArcList(adaptor, n3, 0);
1.84 +
1.85 + checkNodeIds(adaptor);
1.86 + checkArcIds(adaptor);
1.87 +
1.88 + checkGraphNodeMap(adaptor);
1.89 + checkGraphArcMap(adaptor);
1.90 +
1.91 + // Check the orientation of the arcs
1.92 + for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
1.93 + check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
1.94 + check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
1.95 + }
1.96 +
1.97 + // Add and erase nodes and arcs in the digraph through the adaptor
1.98 + Adaptor::Node n4 = adaptor.addNode();
1.99 +
1.100 + Adaptor::Arc a4 = adaptor.addArc(n4, n3);
1.101 + Adaptor::Arc a5 = adaptor.addArc(n2, n4);
1.102 + Adaptor::Arc a6 = adaptor.addArc(n2, n4);
1.103 + Adaptor::Arc a7 = adaptor.addArc(n1, n4);
1.104 + Adaptor::Arc a8 = adaptor.addArc(n1, n2);
1.105 +
1.106 + adaptor.erase(a1);
1.107 + adaptor.erase(n3);
1.108 +
1.109 + // Check the adaptor
1.110 + checkGraphNodeList(adaptor, 3);
1.111 + checkGraphArcList(adaptor, 4);
1.112 + checkGraphConArcList(adaptor, 4);
1.113 +
1.114 + checkGraphOutArcList(adaptor, n1, 2);
1.115 + checkGraphOutArcList(adaptor, n2, 2);
1.116 + checkGraphOutArcList(adaptor, n4, 0);
1.117 +
1.118 + checkGraphInArcList(adaptor, n1, 0);
1.119 + checkGraphInArcList(adaptor, n2, 1);
1.120 + checkGraphInArcList(adaptor, n4, 3);
1.121 +
1.122 + checkNodeIds(adaptor);
1.123 + checkArcIds(adaptor);
1.124 +
1.125 + checkGraphNodeMap(adaptor);
1.126 + checkGraphArcMap(adaptor);
1.127 +
1.128 + // Check the digraph
1.129 + checkGraphNodeList(digraph, 3);
1.130 + checkGraphArcList(digraph, 4);
1.131 + checkGraphConArcList(digraph, 4);
1.132 +
1.133 + checkGraphOutArcList(digraph, n1, 0);
1.134 + checkGraphOutArcList(digraph, n2, 1);
1.135 + checkGraphOutArcList(digraph, n4, 3);
1.136 +
1.137 + checkGraphInArcList(digraph, n1, 2);
1.138 + checkGraphInArcList(digraph, n2, 2);
1.139 + checkGraphInArcList(digraph, n4, 0);
1.140 +
1.141 + checkNodeIds(digraph);
1.142 + checkArcIds(digraph);
1.143 +
1.144 + checkGraphNodeMap(digraph);
1.145 + checkGraphArcMap(digraph);
1.146 +
1.147 + // Check the conversion of nodes and arcs
1.148 + Digraph::Node nd = n4;
1.149 + nd = n4;
1.150 + Adaptor::Node na = n1;
1.151 + na = n2;
1.152 + Digraph::Arc ad = a4;
1.153 + ad = a5;
1.154 + Adaptor::Arc aa = a1;
1.155 + aa = a2;
1.156 +}
1.157 +
1.158 +void checkSubDigraph() {
1.159 + // Check concepts
1.160 + checkConcept<concepts::Digraph, SubDigraph<concepts::Digraph> >();
1.161 + checkConcept<concepts::Digraph, SubDigraph<ListDigraph> >();
1.162 + checkConcept<concepts::AlterableDigraphComponent<>,
1.163 + SubDigraph<ListDigraph> >();
1.164 + checkConcept<concepts::ExtendableDigraphComponent<>,
1.165 + SubDigraph<ListDigraph> >();
1.166 + checkConcept<concepts::ErasableDigraphComponent<>,
1.167 + SubDigraph<ListDigraph> >();
1.168 + checkConcept<concepts::ClearableDigraphComponent<>,
1.169 + SubDigraph<ListDigraph> >();
1.170 +
1.171 + // Create a digraph and an adaptor
1.172 + typedef ListDigraph Digraph;
1.173 + typedef Digraph::NodeMap<bool> NodeFilter;
1.174 + typedef Digraph::ArcMap<bool> ArcFilter;
1.175 + typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
1.176 +
1.177 + Digraph digraph;
1.178 + NodeFilter node_filter(digraph);
1.179 + ArcFilter arc_filter(digraph);
1.180 + Adaptor adaptor(digraph, node_filter, arc_filter);
1.181 +
1.182 + // Add nodes and arcs to the original digraph and the adaptor
1.183 + Digraph::Node n1 = digraph.addNode();
1.184 + Digraph::Node n2 = digraph.addNode();
1.185 + Adaptor::Node n3 = adaptor.addNode();
1.186 +
1.187 + node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
1.188 +
1.189 + Digraph::Arc a1 = digraph.addArc(n1, n2);
1.190 + Digraph::Arc a2 = digraph.addArc(n1, n3);
1.191 + Adaptor::Arc a3 = adaptor.addArc(n2, n3);
1.192 +
1.193 + arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
1.194 +
1.195 + checkGraphNodeList(adaptor, 3);
1.196 + checkGraphArcList(adaptor, 3);
1.197 + checkGraphConArcList(adaptor, 3);
1.198 +
1.199 + checkGraphOutArcList(adaptor, n1, 2);
1.200 + checkGraphOutArcList(adaptor, n2, 1);
1.201 + checkGraphOutArcList(adaptor, n3, 0);
1.202 +
1.203 + checkGraphInArcList(adaptor, n1, 0);
1.204 + checkGraphInArcList(adaptor, n2, 1);
1.205 + checkGraphInArcList(adaptor, n3, 2);
1.206 +
1.207 + checkNodeIds(adaptor);
1.208 + checkArcIds(adaptor);
1.209 +
1.210 + checkGraphNodeMap(adaptor);
1.211 + checkGraphArcMap(adaptor);
1.212 +
1.213 + // Hide an arc
1.214 + adaptor.status(a2, false);
1.215 + adaptor.disable(a3);
1.216 + if (!adaptor.status(a3)) adaptor.enable(a3);
1.217 +
1.218 + checkGraphNodeList(adaptor, 3);
1.219 + checkGraphArcList(adaptor, 2);
1.220 + checkGraphConArcList(adaptor, 2);
1.221 +
1.222 + checkGraphOutArcList(adaptor, n1, 1);
1.223 + checkGraphOutArcList(adaptor, n2, 1);
1.224 + checkGraphOutArcList(adaptor, n3, 0);
1.225 +
1.226 + checkGraphInArcList(adaptor, n1, 0);
1.227 + checkGraphInArcList(adaptor, n2, 1);
1.228 + checkGraphInArcList(adaptor, n3, 1);
1.229 +
1.230 + checkNodeIds(adaptor);
1.231 + checkArcIds(adaptor);
1.232 +
1.233 + checkGraphNodeMap(adaptor);
1.234 + checkGraphArcMap(adaptor);
1.235 +
1.236 + // Hide a node
1.237 + adaptor.status(n1, false);
1.238 + adaptor.disable(n3);
1.239 + if (!adaptor.status(n3)) adaptor.enable(n3);
1.240 +
1.241 + checkGraphNodeList(adaptor, 2);
1.242 + checkGraphArcList(adaptor, 1);
1.243 + checkGraphConArcList(adaptor, 1);
1.244 +
1.245 + checkGraphOutArcList(adaptor, n2, 1);
1.246 + checkGraphOutArcList(adaptor, n3, 0);
1.247 +
1.248 + checkGraphInArcList(adaptor, n2, 0);
1.249 + checkGraphInArcList(adaptor, n3, 1);
1.250 +
1.251 + checkNodeIds(adaptor);
1.252 + checkArcIds(adaptor);
1.253 +
1.254 + checkGraphNodeMap(adaptor);
1.255 + checkGraphArcMap(adaptor);
1.256 +
1.257 + // Hide all nodes and arcs
1.258 + node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
1.259 + arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
1.260 +
1.261 + checkGraphNodeList(adaptor, 0);
1.262 + checkGraphArcList(adaptor, 0);
1.263 + checkGraphConArcList(adaptor, 0);
1.264 +
1.265 + checkNodeIds(adaptor);
1.266 + checkArcIds(adaptor);
1.267 +
1.268 + checkGraphNodeMap(adaptor);
1.269 + checkGraphArcMap(adaptor);
1.270 +
1.271 + // Check the conversion of nodes and arcs
1.272 + Digraph::Node nd = n3;
1.273 + nd = n3;
1.274 + Adaptor::Node na = n1;
1.275 + na = n2;
1.276 + Digraph::Arc ad = a3;
1.277 + ad = a3;
1.278 + Adaptor::Arc aa = a1;
1.279 + aa = a2;
1.280 +}
1.281 +
1.282 +void checkFilterNodes1() {
1.283 + // Check concepts
1.284 + checkConcept<concepts::Digraph, FilterNodes<concepts::Digraph> >();
1.285 + checkConcept<concepts::Digraph, FilterNodes<ListDigraph> >();
1.286 + checkConcept<concepts::AlterableDigraphComponent<>,
1.287 + FilterNodes<ListDigraph> >();
1.288 + checkConcept<concepts::ExtendableDigraphComponent<>,
1.289 + FilterNodes<ListDigraph> >();
1.290 + checkConcept<concepts::ErasableDigraphComponent<>,
1.291 + FilterNodes<ListDigraph> >();
1.292 + checkConcept<concepts::ClearableDigraphComponent<>,
1.293 + FilterNodes<ListDigraph> >();
1.294 +
1.295 + // Create a digraph and an adaptor
1.296 + typedef ListDigraph Digraph;
1.297 + typedef Digraph::NodeMap<bool> NodeFilter;
1.298 + typedef FilterNodes<Digraph, NodeFilter> Adaptor;
1.299 +
1.300 + Digraph digraph;
1.301 + NodeFilter node_filter(digraph);
1.302 + Adaptor adaptor(digraph, node_filter);
1.303 +
1.304 + // Add nodes and arcs to the original digraph and the adaptor
1.305 + Digraph::Node n1 = digraph.addNode();
1.306 + Digraph::Node n2 = digraph.addNode();
1.307 + Adaptor::Node n3 = adaptor.addNode();
1.308 +
1.309 + node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
1.310 +
1.311 + Digraph::Arc a1 = digraph.addArc(n1, n2);
1.312 + Digraph::Arc a2 = digraph.addArc(n1, n3);
1.313 + Adaptor::Arc a3 = adaptor.addArc(n2, n3);
1.314 +
1.315 + checkGraphNodeList(adaptor, 3);
1.316 + checkGraphArcList(adaptor, 3);
1.317 + checkGraphConArcList(adaptor, 3);
1.318 +
1.319 + checkGraphOutArcList(adaptor, n1, 2);
1.320 + checkGraphOutArcList(adaptor, n2, 1);
1.321 + checkGraphOutArcList(adaptor, n3, 0);
1.322 +
1.323 + checkGraphInArcList(adaptor, n1, 0);
1.324 + checkGraphInArcList(adaptor, n2, 1);
1.325 + checkGraphInArcList(adaptor, n3, 2);
1.326 +
1.327 + checkNodeIds(adaptor);
1.328 + checkArcIds(adaptor);
1.329 +
1.330 + checkGraphNodeMap(adaptor);
1.331 + checkGraphArcMap(adaptor);
1.332 +
1.333 + // Hide a node
1.334 + adaptor.status(n1, false);
1.335 + adaptor.disable(n3);
1.336 + if (!adaptor.status(n3)) adaptor.enable(n3);
1.337 +
1.338 + checkGraphNodeList(adaptor, 2);
1.339 + checkGraphArcList(adaptor, 1);
1.340 + checkGraphConArcList(adaptor, 1);
1.341 +
1.342 + checkGraphOutArcList(adaptor, n2, 1);
1.343 + checkGraphOutArcList(adaptor, n3, 0);
1.344 +
1.345 + checkGraphInArcList(adaptor, n2, 0);
1.346 + checkGraphInArcList(adaptor, n3, 1);
1.347 +
1.348 + checkNodeIds(adaptor);
1.349 + checkArcIds(adaptor);
1.350 +
1.351 + checkGraphNodeMap(adaptor);
1.352 + checkGraphArcMap(adaptor);
1.353 +
1.354 + // Hide all nodes
1.355 + node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
1.356 +
1.357 + checkGraphNodeList(adaptor, 0);
1.358 + checkGraphArcList(adaptor, 0);
1.359 + checkGraphConArcList(adaptor, 0);
1.360 +
1.361 + checkNodeIds(adaptor);
1.362 + checkArcIds(adaptor);
1.363 +
1.364 + checkGraphNodeMap(adaptor);
1.365 + checkGraphArcMap(adaptor);
1.366 +
1.367 + // Check the conversion of nodes and arcs
1.368 + Digraph::Node nd = n3;
1.369 + nd = n3;
1.370 + Adaptor::Node na = n1;
1.371 + na = n2;
1.372 + Digraph::Arc ad = a3;
1.373 + ad = a3;
1.374 + Adaptor::Arc aa = a1;
1.375 + aa = a2;
1.376 +}
1.377 +
1.378 +void checkFilterArcs() {
1.379 + // Check concepts
1.380 + checkConcept<concepts::Digraph, FilterArcs<concepts::Digraph> >();
1.381 + checkConcept<concepts::Digraph, FilterArcs<ListDigraph> >();
1.382 + checkConcept<concepts::AlterableDigraphComponent<>,
1.383 + FilterArcs<ListDigraph> >();
1.384 + checkConcept<concepts::ExtendableDigraphComponent<>,
1.385 + FilterArcs<ListDigraph> >();
1.386 + checkConcept<concepts::ErasableDigraphComponent<>,
1.387 + FilterArcs<ListDigraph> >();
1.388 + checkConcept<concepts::ClearableDigraphComponent<>,
1.389 + FilterArcs<ListDigraph> >();
1.390 +
1.391 + // Create a digraph and an adaptor
1.392 + typedef ListDigraph Digraph;
1.393 + typedef Digraph::ArcMap<bool> ArcFilter;
1.394 + typedef FilterArcs<Digraph, ArcFilter> Adaptor;
1.395 +
1.396 + Digraph digraph;
1.397 + ArcFilter arc_filter(digraph);
1.398 + Adaptor adaptor(digraph, arc_filter);
1.399 +
1.400 + // Add nodes and arcs to the original digraph and the adaptor
1.401 + Digraph::Node n1 = digraph.addNode();
1.402 + Digraph::Node n2 = digraph.addNode();
1.403 + Adaptor::Node n3 = adaptor.addNode();
1.404 +
1.405 + Digraph::Arc a1 = digraph.addArc(n1, n2);
1.406 + Digraph::Arc a2 = digraph.addArc(n1, n3);
1.407 + Adaptor::Arc a3 = adaptor.addArc(n2, n3);
1.408 +
1.409 + arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
1.410 +
1.411 + checkGraphNodeList(adaptor, 3);
1.412 + checkGraphArcList(adaptor, 3);
1.413 + checkGraphConArcList(adaptor, 3);
1.414 +
1.415 + checkGraphOutArcList(adaptor, n1, 2);
1.416 + checkGraphOutArcList(adaptor, n2, 1);
1.417 + checkGraphOutArcList(adaptor, n3, 0);
1.418 +
1.419 + checkGraphInArcList(adaptor, n1, 0);
1.420 + checkGraphInArcList(adaptor, n2, 1);
1.421 + checkGraphInArcList(adaptor, n3, 2);
1.422 +
1.423 + checkNodeIds(adaptor);
1.424 + checkArcIds(adaptor);
1.425 +
1.426 + checkGraphNodeMap(adaptor);
1.427 + checkGraphArcMap(adaptor);
1.428 +
1.429 + // Hide an arc
1.430 + adaptor.status(a2, false);
1.431 + adaptor.disable(a3);
1.432 + if (!adaptor.status(a3)) adaptor.enable(a3);
1.433 +
1.434 + checkGraphNodeList(adaptor, 3);
1.435 + checkGraphArcList(adaptor, 2);
1.436 + checkGraphConArcList(adaptor, 2);
1.437 +
1.438 + checkGraphOutArcList(adaptor, n1, 1);
1.439 + checkGraphOutArcList(adaptor, n2, 1);
1.440 + checkGraphOutArcList(adaptor, n3, 0);
1.441 +
1.442 + checkGraphInArcList(adaptor, n1, 0);
1.443 + checkGraphInArcList(adaptor, n2, 1);
1.444 + checkGraphInArcList(adaptor, n3, 1);
1.445 +
1.446 + checkNodeIds(adaptor);
1.447 + checkArcIds(adaptor);
1.448 +
1.449 + checkGraphNodeMap(adaptor);
1.450 + checkGraphArcMap(adaptor);
1.451 +
1.452 + // Hide all arcs
1.453 + arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
1.454 +
1.455 + checkGraphNodeList(adaptor, 3);
1.456 + checkGraphArcList(adaptor, 0);
1.457 + checkGraphConArcList(adaptor, 0);
1.458 +
1.459 + checkNodeIds(adaptor);
1.460 + checkArcIds(adaptor);
1.461 +
1.462 + checkGraphNodeMap(adaptor);
1.463 + checkGraphArcMap(adaptor);
1.464 +
1.465 + // Check the conversion of nodes and arcs
1.466 + Digraph::Node nd = n3;
1.467 + nd = n3;
1.468 + Adaptor::Node na = n1;
1.469 + na = n2;
1.470 + Digraph::Arc ad = a3;
1.471 + ad = a3;
1.472 + Adaptor::Arc aa = a1;
1.473 + aa = a2;
1.474 +}
1.475 +
1.476 +void checkUndirector() {
1.477 + // Check concepts
1.478 + checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
1.479 + checkConcept<concepts::Graph, Undirector<ListDigraph> >();
1.480 + checkConcept<concepts::AlterableGraphComponent<>,
1.481 + Undirector<ListDigraph> >();
1.482 + checkConcept<concepts::ExtendableGraphComponent<>,
1.483 + Undirector<ListDigraph> >();
1.484 + checkConcept<concepts::ErasableGraphComponent<>,
1.485 + Undirector<ListDigraph> >();
1.486 + checkConcept<concepts::ClearableGraphComponent<>,
1.487 + Undirector<ListDigraph> >();
1.488 +
1.489 +
1.490 + // Create a digraph and an adaptor
1.491 + typedef ListDigraph Digraph;
1.492 + typedef Undirector<Digraph> Adaptor;
1.493 +
1.494 + Digraph digraph;
1.495 + Adaptor adaptor(digraph);
1.496 +
1.497 + // Add nodes and arcs/edges to the original digraph and the adaptor
1.498 + Digraph::Node n1 = digraph.addNode();
1.499 + Digraph::Node n2 = digraph.addNode();
1.500 + Adaptor::Node n3 = adaptor.addNode();
1.501 +
1.502 + Digraph::Arc a1 = digraph.addArc(n1, n2);
1.503 + Digraph::Arc a2 = digraph.addArc(n1, n3);
1.504 + Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
1.505 +
1.506 + // Check the original digraph
1.507 + checkGraphNodeList(digraph, 3);
1.508 + checkGraphArcList(digraph, 3);
1.509 + checkGraphConArcList(digraph, 3);
1.510 +
1.511 + checkGraphOutArcList(digraph, n1, 2);
1.512 + checkGraphOutArcList(digraph, n2, 1);
1.513 + checkGraphOutArcList(digraph, n3, 0);
1.514 +
1.515 + checkGraphInArcList(digraph, n1, 0);
1.516 + checkGraphInArcList(digraph, n2, 1);
1.517 + checkGraphInArcList(digraph, n3, 2);
1.518 +
1.519 + checkNodeIds(digraph);
1.520 + checkArcIds(digraph);
1.521 +
1.522 + checkGraphNodeMap(digraph);
1.523 + checkGraphArcMap(digraph);
1.524 +
1.525 + // Check the adaptor
1.526 + checkGraphNodeList(adaptor, 3);
1.527 + checkGraphArcList(adaptor, 6);
1.528 + checkGraphEdgeList(adaptor, 3);
1.529 + checkGraphConArcList(adaptor, 6);
1.530 + checkGraphConEdgeList(adaptor, 3);
1.531 +
1.532 + checkGraphIncEdgeArcLists(adaptor, n1, 2);
1.533 + checkGraphIncEdgeArcLists(adaptor, n2, 2);
1.534 + checkGraphIncEdgeArcLists(adaptor, n3, 2);
1.535 +
1.536 + checkNodeIds(adaptor);
1.537 + checkArcIds(adaptor);
1.538 + checkEdgeIds(adaptor);
1.539 +
1.540 + checkGraphNodeMap(adaptor);
1.541 + checkGraphArcMap(adaptor);
1.542 + checkGraphEdgeMap(adaptor);
1.543 +
1.544 + // Check the edges of the adaptor
1.545 + for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {
1.546 + check(adaptor.u(e) == digraph.source(e), "Wrong undir");
1.547 + check(adaptor.v(e) == digraph.target(e), "Wrong undir");
1.548 + }
1.549 +
1.550 + // Check CombinedArcMap
1.551 + typedef Adaptor::CombinedArcMap
1.552 + <Digraph::ArcMap<int>, Digraph::ArcMap<int> > IntCombinedMap;
1.553 + typedef Adaptor::CombinedArcMap
1.554 + <Digraph::ArcMap<bool>, Digraph::ArcMap<bool> > BoolCombinedMap;
1.555 + checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,
1.556 + IntCombinedMap>();
1.557 + checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,
1.558 + BoolCombinedMap>();
1.559 +
1.560 + Digraph::ArcMap<int> fw_map(digraph), bk_map(digraph);
1.561 + for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
1.562 + fw_map[a] = digraph.id(a);
1.563 + bk_map[a] = -digraph.id(a);
1.564 + }
1.565 +
1.566 + Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::ArcMap<int> >
1.567 + comb_map(fw_map, bk_map);
1.568 + for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
1.569 + if (adaptor.source(a) == digraph.source(a)) {
1.570 + check(comb_map[a] == fw_map[a], "Wrong combined map");
1.571 + } else {
1.572 + check(comb_map[a] == bk_map[a], "Wrong combined map");
1.573 + }
1.574 + }
1.575 +
1.576 + // Check the conversion of nodes and arcs/edges
1.577 + Digraph::Node nd = n3;
1.578 + nd = n3;
1.579 + Adaptor::Node na = n1;
1.580 + na = n2;
1.581 + Digraph::Arc ad = e3;
1.582 + ad = e3;
1.583 + Adaptor::Edge ea = a1;
1.584 + ea = a2;
1.585 +}
1.586 +
1.587 +void checkResidualDigraph() {
1.588 + // Check concepts
1.589 + checkConcept<concepts::Digraph, ResidualDigraph<concepts::Digraph> >();
1.590 + checkConcept<concepts::Digraph, ResidualDigraph<ListDigraph> >();
1.591 +
1.592 + // Create a digraph and an adaptor
1.593 + typedef ListDigraph Digraph;
1.594 + typedef Digraph::ArcMap<int> IntArcMap;
1.595 + typedef ResidualDigraph<Digraph, IntArcMap> Adaptor;
1.596 +
1.597 + Digraph digraph;
1.598 + IntArcMap capacity(digraph), flow(digraph);
1.599 + Adaptor adaptor(digraph, capacity, flow);
1.600 +
1.601 + Digraph::Node n1 = digraph.addNode();
1.602 + Digraph::Node n2 = digraph.addNode();
1.603 + Digraph::Node n3 = digraph.addNode();
1.604 + Digraph::Node n4 = digraph.addNode();
1.605 +
1.606 + Digraph::Arc a1 = digraph.addArc(n1, n2);
1.607 + Digraph::Arc a2 = digraph.addArc(n1, n3);
1.608 + Digraph::Arc a3 = digraph.addArc(n1, n4);
1.609 + Digraph::Arc a4 = digraph.addArc(n2, n3);
1.610 + Digraph::Arc a5 = digraph.addArc(n2, n4);
1.611 + Digraph::Arc a6 = digraph.addArc(n3, n4);
1.612 +
1.613 + capacity[a1] = 8;
1.614 + capacity[a2] = 6;
1.615 + capacity[a3] = 4;
1.616 + capacity[a4] = 4;
1.617 + capacity[a5] = 6;
1.618 + capacity[a6] = 10;
1.619 +
1.620 + // Check the adaptor with various flow values
1.621 + for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
1.622 + flow[a] = 0;
1.623 + }
1.624 +
1.625 + checkGraphNodeList(adaptor, 4);
1.626 + checkGraphArcList(adaptor, 6);
1.627 + checkGraphConArcList(adaptor, 6);
1.628 +
1.629 + checkGraphOutArcList(adaptor, n1, 3);
1.630 + checkGraphOutArcList(adaptor, n2, 2);
1.631 + checkGraphOutArcList(adaptor, n3, 1);
1.632 + checkGraphOutArcList(adaptor, n4, 0);
1.633 +
1.634 + checkGraphInArcList(adaptor, n1, 0);
1.635 + checkGraphInArcList(adaptor, n2, 1);
1.636 + checkGraphInArcList(adaptor, n3, 2);
1.637 + checkGraphInArcList(adaptor, n4, 3);
1.638 +
1.639 + for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
1.640 + flow[a] = capacity[a] / 2;
1.641 + }
1.642 +
1.643 + checkGraphNodeList(adaptor, 4);
1.644 + checkGraphArcList(adaptor, 12);
1.645 + checkGraphConArcList(adaptor, 12);
1.646 +
1.647 + checkGraphOutArcList(adaptor, n1, 3);
1.648 + checkGraphOutArcList(adaptor, n2, 3);
1.649 + checkGraphOutArcList(adaptor, n3, 3);
1.650 + checkGraphOutArcList(adaptor, n4, 3);
1.651 +
1.652 + checkGraphInArcList(adaptor, n1, 3);
1.653 + checkGraphInArcList(adaptor, n2, 3);
1.654 + checkGraphInArcList(adaptor, n3, 3);
1.655 + checkGraphInArcList(adaptor, n4, 3);
1.656 +
1.657 + checkNodeIds(adaptor);
1.658 + checkArcIds(adaptor);
1.659 +
1.660 + checkGraphNodeMap(adaptor);
1.661 + checkGraphArcMap(adaptor);
1.662 +
1.663 + for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
1.664 + flow[a] = capacity[a];
1.665 + }
1.666 +
1.667 + checkGraphNodeList(adaptor, 4);
1.668 + checkGraphArcList(adaptor, 6);
1.669 + checkGraphConArcList(adaptor, 6);
1.670 +
1.671 + checkGraphOutArcList(adaptor, n1, 0);
1.672 + checkGraphOutArcList(adaptor, n2, 1);
1.673 + checkGraphOutArcList(adaptor, n3, 2);
1.674 + checkGraphOutArcList(adaptor, n4, 3);
1.675 +
1.676 + checkGraphInArcList(adaptor, n1, 3);
1.677 + checkGraphInArcList(adaptor, n2, 2);
1.678 + checkGraphInArcList(adaptor, n3, 1);
1.679 + checkGraphInArcList(adaptor, n4, 0);
1.680 +
1.681 + // Saturate all backward arcs
1.682 + // (set the flow to zero on all forward arcs)
1.683 + for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
1.684 + if (adaptor.backward(a))
1.685 + adaptor.augment(a, adaptor.residualCapacity(a));
1.686 + }
1.687 +
1.688 + checkGraphNodeList(adaptor, 4);
1.689 + checkGraphArcList(adaptor, 6);
1.690 + checkGraphConArcList(adaptor, 6);
1.691 +
1.692 + checkGraphOutArcList(adaptor, n1, 3);
1.693 + checkGraphOutArcList(adaptor, n2, 2);
1.694 + checkGraphOutArcList(adaptor, n3, 1);
1.695 + checkGraphOutArcList(adaptor, n4, 0);
1.696 +
1.697 + checkGraphInArcList(adaptor, n1, 0);
1.698 + checkGraphInArcList(adaptor, n2, 1);
1.699 + checkGraphInArcList(adaptor, n3, 2);
1.700 + checkGraphInArcList(adaptor, n4, 3);
1.701 +
1.702 + // Find maximum flow by augmenting along shortest paths
1.703 + int flow_value = 0;
1.704 + Adaptor::ResidualCapacity res_cap(adaptor);
1.705 + while (true) {
1.706 +
1.707 + Bfs<Adaptor> bfs(adaptor);
1.708 + bfs.run(n1, n4);
1.709 +
1.710 + if (!bfs.reached(n4)) break;
1.711 +
1.712 + Path<Adaptor> p = bfs.path(n4);
1.713 +
1.714 + int min = std::numeric_limits<int>::max();
1.715 + for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
1.716 + if (res_cap[a] < min) min = res_cap[a];
1.717 + }
1.718 +
1.719 + for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
1.720 + adaptor.augment(a, min);
1.721 + }
1.722 + flow_value += min;
1.723 + }
1.724 +
1.725 + check(flow_value == 18, "Wrong flow with res graph adaptor");
1.726 +
1.727 + // Check forward() and backward()
1.728 + for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
1.729 + check(adaptor.forward(a) != adaptor.backward(a),
1.730 + "Wrong forward() or backward()");
1.731 + check((adaptor.forward(a) && adaptor.forward(Digraph::Arc(a)) == a) ||
1.732 + (adaptor.backward(a) && adaptor.backward(Digraph::Arc(a)) == a),
1.733 + "Wrong forward() or backward()");
1.734 + }
1.735 +
1.736 + // Check the conversion of nodes and arcs
1.737 + Digraph::Node nd = Adaptor::NodeIt(adaptor);
1.738 + nd = ++Adaptor::NodeIt(adaptor);
1.739 + Adaptor::Node na = n1;
1.740 + na = n2;
1.741 + Digraph::Arc ad = Adaptor::ArcIt(adaptor);
1.742 + ad = ++Adaptor::ArcIt(adaptor);
1.743 +}
1.744 +
1.745 +void checkSplitNodes() {
1.746 + // Check concepts
1.747 + checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
1.748 + checkConcept<concepts::Digraph, SplitNodes<ListDigraph> >();
1.749 +
1.750 + // Create a digraph and an adaptor
1.751 + typedef ListDigraph Digraph;
1.752 + typedef SplitNodes<Digraph> Adaptor;
1.753 +
1.754 + Digraph digraph;
1.755 + Adaptor adaptor(digraph);
1.756 +
1.757 + Digraph::Node n1 = digraph.addNode();
1.758 + Digraph::Node n2 = digraph.addNode();
1.759 + Digraph::Node n3 = digraph.addNode();
1.760 +
1.761 + Digraph::Arc a1 = digraph.addArc(n1, n2);
1.762 + Digraph::Arc a2 = digraph.addArc(n1, n3);
1.763 + Digraph::Arc a3 = digraph.addArc(n2, n3);
1.764 +
1.765 + checkGraphNodeList(adaptor, 6);
1.766 + checkGraphArcList(adaptor, 6);
1.767 + checkGraphConArcList(adaptor, 6);
1.768 +
1.769 + checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
1.770 + checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2);
1.771 + checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
1.772 + checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1);
1.773 + checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
1.774 + checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0);
1.775 +
1.776 + checkGraphInArcList(adaptor, adaptor.inNode(n1), 0);
1.777 + checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
1.778 + checkGraphInArcList(adaptor, adaptor.inNode(n2), 1);
1.779 + checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
1.780 + checkGraphInArcList(adaptor, adaptor.inNode(n3), 2);
1.781 + checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
1.782 +
1.783 + checkNodeIds(adaptor);
1.784 + checkArcIds(adaptor);
1.785 +
1.786 + checkGraphNodeMap(adaptor);
1.787 + checkGraphArcMap(adaptor);
1.788 +
1.789 + // Check split
1.790 + for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
1.791 + if (adaptor.origArc(a)) {
1.792 + Digraph::Arc oa = a;
1.793 + check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),
1.794 + "Wrong split");
1.795 + check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),
1.796 + "Wrong split");
1.797 + } else {
1.798 + Digraph::Node on = a;
1.799 + check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");
1.800 + check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");
1.801 + }
1.802 + }
1.803 +
1.804 + // Check combined node map
1.805 + typedef Adaptor::CombinedNodeMap
1.806 + <Digraph::NodeMap<int>, Digraph::NodeMap<int> > IntCombinedNodeMap;
1.807 + typedef Adaptor::CombinedNodeMap
1.808 + <Digraph::NodeMap<bool>, Digraph::NodeMap<bool> > BoolCombinedNodeMap;
1.809 + checkConcept<concepts::ReferenceMap<Adaptor::Node, int, int&, const int&>,
1.810 + IntCombinedNodeMap>();
1.811 +//checkConcept<concepts::ReferenceMap<Adaptor::Node, bool, bool&, const bool&>,
1.812 +// BoolCombinedNodeMap>();
1.813 + checkConcept<concepts::ReadWriteMap<Adaptor::Node, bool>,
1.814 + BoolCombinedNodeMap>();
1.815 +
1.816 + Digraph::NodeMap<int> in_map(digraph), out_map(digraph);
1.817 + for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {
1.818 + in_map[n] = digraph.id(n);
1.819 + out_map[n] = -digraph.id(n);
1.820 + }
1.821 +
1.822 + Adaptor::CombinedNodeMap<Digraph::NodeMap<int>, Digraph::NodeMap<int> >
1.823 + node_map(in_map, out_map);
1.824 + for (Adaptor::NodeIt n(adaptor); n != INVALID; ++n) {
1.825 + if (adaptor.inNode(n)) {
1.826 + check(node_map[n] == in_map[n], "Wrong combined node map");
1.827 + } else {
1.828 + check(node_map[n] == out_map[n], "Wrong combined node map");
1.829 + }
1.830 + }
1.831 +
1.832 + // Check combined arc map
1.833 + typedef Adaptor::CombinedArcMap
1.834 + <Digraph::ArcMap<int>, Digraph::NodeMap<int> > IntCombinedArcMap;
1.835 + typedef Adaptor::CombinedArcMap
1.836 + <Digraph::ArcMap<bool>, Digraph::NodeMap<bool> > BoolCombinedArcMap;
1.837 + checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,
1.838 + IntCombinedArcMap>();
1.839 +//checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,
1.840 +// BoolCombinedArcMap>();
1.841 + checkConcept<concepts::ReadWriteMap<Adaptor::Arc, bool>,
1.842 + BoolCombinedArcMap>();
1.843 +
1.844 + Digraph::ArcMap<int> a_map(digraph);
1.845 + for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
1.846 + a_map[a] = digraph.id(a);
1.847 + }
1.848 +
1.849 + Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::NodeMap<int> >
1.850 + arc_map(a_map, out_map);
1.851 + for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {
1.852 + check(arc_map[adaptor.arc(a)] == a_map[a], "Wrong combined arc map");
1.853 + }
1.854 + for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {
1.855 + check(arc_map[adaptor.arc(n)] == out_map[n], "Wrong combined arc map");
1.856 + }
1.857 +
1.858 + // Check the conversion of nodes
1.859 + Digraph::Node nd = adaptor.inNode(n1);
1.860 + check (nd == n1, "Wrong node conversion");
1.861 + nd = adaptor.outNode(n2);
1.862 + check (nd == n2, "Wrong node conversion");
1.863 +}
1.864 +
1.865 +void checkSubGraph() {
1.866 + // Check concepts
1.867 + checkConcept<concepts::Graph, SubGraph<concepts::Graph> >();
1.868 + checkConcept<concepts::Graph, SubGraph<ListGraph> >();
1.869 + checkConcept<concepts::AlterableGraphComponent<>,
1.870 + SubGraph<ListGraph> >();
1.871 + checkConcept<concepts::ExtendableGraphComponent<>,
1.872 + SubGraph<ListGraph> >();
1.873 + checkConcept<concepts::ErasableGraphComponent<>,
1.874 + SubGraph<ListGraph> >();
1.875 + checkConcept<concepts::ClearableGraphComponent<>,
1.876 + SubGraph<ListGraph> >();
1.877 +
1.878 + // Create a graph and an adaptor
1.879 + typedef ListGraph Graph;
1.880 + typedef Graph::NodeMap<bool> NodeFilter;
1.881 + typedef Graph::EdgeMap<bool> EdgeFilter;
1.882 + typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;
1.883 +
1.884 + Graph graph;
1.885 + NodeFilter node_filter(graph);
1.886 + EdgeFilter edge_filter(graph);
1.887 + Adaptor adaptor(graph, node_filter, edge_filter);
1.888 +
1.889 + // Add nodes and edges to the original graph and the adaptor
1.890 + Graph::Node n1 = graph.addNode();
1.891 + Graph::Node n2 = graph.addNode();
1.892 + Adaptor::Node n3 = adaptor.addNode();
1.893 + Adaptor::Node n4 = adaptor.addNode();
1.894 +
1.895 + node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
1.896 +
1.897 + Graph::Edge e1 = graph.addEdge(n1, n2);
1.898 + Graph::Edge e2 = graph.addEdge(n1, n3);
1.899 + Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
1.900 + Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
1.901 +
1.902 + edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
1.903 +
1.904 + checkGraphNodeList(adaptor, 4);
1.905 + checkGraphArcList(adaptor, 8);
1.906 + checkGraphEdgeList(adaptor, 4);
1.907 + checkGraphConArcList(adaptor, 8);
1.908 + checkGraphConEdgeList(adaptor, 4);
1.909 +
1.910 + checkGraphIncEdgeArcLists(adaptor, n1, 2);
1.911 + checkGraphIncEdgeArcLists(adaptor, n2, 2);
1.912 + checkGraphIncEdgeArcLists(adaptor, n3, 3);
1.913 + checkGraphIncEdgeArcLists(adaptor, n4, 1);
1.914 +
1.915 + checkNodeIds(adaptor);
1.916 + checkArcIds(adaptor);
1.917 + checkEdgeIds(adaptor);
1.918 +
1.919 + checkGraphNodeMap(adaptor);
1.920 + checkGraphArcMap(adaptor);
1.921 + checkGraphEdgeMap(adaptor);
1.922 +
1.923 + // Hide an edge
1.924 + adaptor.status(e2, false);
1.925 + adaptor.disable(e3);
1.926 + if (!adaptor.status(e3)) adaptor.enable(e3);
1.927 +
1.928 + checkGraphNodeList(adaptor, 4);
1.929 + checkGraphArcList(adaptor, 6);
1.930 + checkGraphEdgeList(adaptor, 3);
1.931 + checkGraphConArcList(adaptor, 6);
1.932 + checkGraphConEdgeList(adaptor, 3);
1.933 +
1.934 + checkGraphIncEdgeArcLists(adaptor, n1, 1);
1.935 + checkGraphIncEdgeArcLists(adaptor, n2, 2);
1.936 + checkGraphIncEdgeArcLists(adaptor, n3, 2);
1.937 + checkGraphIncEdgeArcLists(adaptor, n4, 1);
1.938 +
1.939 + checkNodeIds(adaptor);
1.940 + checkArcIds(adaptor);
1.941 + checkEdgeIds(adaptor);
1.942 +
1.943 + checkGraphNodeMap(adaptor);
1.944 + checkGraphArcMap(adaptor);
1.945 + checkGraphEdgeMap(adaptor);
1.946 +
1.947 + // Hide a node
1.948 + adaptor.status(n1, false);
1.949 + adaptor.disable(n3);
1.950 + if (!adaptor.status(n3)) adaptor.enable(n3);
1.951 +
1.952 + checkGraphNodeList(adaptor, 3);
1.953 + checkGraphArcList(adaptor, 4);
1.954 + checkGraphEdgeList(adaptor, 2);
1.955 + checkGraphConArcList(adaptor, 4);
1.956 + checkGraphConEdgeList(adaptor, 2);
1.957 +
1.958 + checkGraphIncEdgeArcLists(adaptor, n2, 1);
1.959 + checkGraphIncEdgeArcLists(adaptor, n3, 2);
1.960 + checkGraphIncEdgeArcLists(adaptor, n4, 1);
1.961 +
1.962 + checkNodeIds(adaptor);
1.963 + checkArcIds(adaptor);
1.964 + checkEdgeIds(adaptor);
1.965 +
1.966 + checkGraphNodeMap(adaptor);
1.967 + checkGraphArcMap(adaptor);
1.968 + checkGraphEdgeMap(adaptor);
1.969 +
1.970 + // Hide all nodes and edges
1.971 + node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
1.972 + edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
1.973 +
1.974 + checkGraphNodeList(adaptor, 0);
1.975 + checkGraphArcList(adaptor, 0);
1.976 + checkGraphEdgeList(adaptor, 0);
1.977 + checkGraphConArcList(adaptor, 0);
1.978 + checkGraphConEdgeList(adaptor, 0);
1.979 +
1.980 + checkNodeIds(adaptor);
1.981 + checkArcIds(adaptor);
1.982 + checkEdgeIds(adaptor);
1.983 +
1.984 + checkGraphNodeMap(adaptor);
1.985 + checkGraphArcMap(adaptor);
1.986 + checkGraphEdgeMap(adaptor);
1.987 +
1.988 + // Check the conversion of nodes and edges
1.989 + Graph::Node ng = n3;
1.990 + ng = n4;
1.991 + Adaptor::Node na = n1;
1.992 + na = n2;
1.993 + Graph::Edge eg = e3;
1.994 + eg = e4;
1.995 + Adaptor::Edge ea = e1;
1.996 + ea = e2;
1.997 +}
1.998 +
1.999 +void checkFilterNodes2() {
1.1000 + // Check concepts
1.1001 + checkConcept<concepts::Graph, FilterNodes<concepts::Graph> >();
1.1002 + checkConcept<concepts::Graph, FilterNodes<ListGraph> >();
1.1003 + checkConcept<concepts::AlterableGraphComponent<>,
1.1004 + FilterNodes<ListGraph> >();
1.1005 + checkConcept<concepts::ExtendableGraphComponent<>,
1.1006 + FilterNodes<ListGraph> >();
1.1007 + checkConcept<concepts::ErasableGraphComponent<>,
1.1008 + FilterNodes<ListGraph> >();
1.1009 + checkConcept<concepts::ClearableGraphComponent<>,
1.1010 + FilterNodes<ListGraph> >();
1.1011 +
1.1012 + // Create a graph and an adaptor
1.1013 + typedef ListGraph Graph;
1.1014 + typedef Graph::NodeMap<bool> NodeFilter;
1.1015 + typedef FilterNodes<Graph, NodeFilter> Adaptor;
1.1016 +
1.1017 + // Add nodes and edges to the original graph and the adaptor
1.1018 + Graph graph;
1.1019 + NodeFilter node_filter(graph);
1.1020 + Adaptor adaptor(graph, node_filter);
1.1021 +
1.1022 + Graph::Node n1 = graph.addNode();
1.1023 + Graph::Node n2 = graph.addNode();
1.1024 + Adaptor::Node n3 = adaptor.addNode();
1.1025 + Adaptor::Node n4 = adaptor.addNode();
1.1026 +
1.1027 + node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
1.1028 +
1.1029 + Graph::Edge e1 = graph.addEdge(n1, n2);
1.1030 + Graph::Edge e2 = graph.addEdge(n1, n3);
1.1031 + Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
1.1032 + Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
1.1033 +
1.1034 + checkGraphNodeList(adaptor, 4);
1.1035 + checkGraphArcList(adaptor, 8);
1.1036 + checkGraphEdgeList(adaptor, 4);
1.1037 + checkGraphConArcList(adaptor, 8);
1.1038 + checkGraphConEdgeList(adaptor, 4);
1.1039 +
1.1040 + checkGraphIncEdgeArcLists(adaptor, n1, 2);
1.1041 + checkGraphIncEdgeArcLists(adaptor, n2, 2);
1.1042 + checkGraphIncEdgeArcLists(adaptor, n3, 3);
1.1043 + checkGraphIncEdgeArcLists(adaptor, n4, 1);
1.1044 +
1.1045 + checkNodeIds(adaptor);
1.1046 + checkArcIds(adaptor);
1.1047 + checkEdgeIds(adaptor);
1.1048 +
1.1049 + checkGraphNodeMap(adaptor);
1.1050 + checkGraphArcMap(adaptor);
1.1051 + checkGraphEdgeMap(adaptor);
1.1052 +
1.1053 + // Hide a node
1.1054 + adaptor.status(n1, false);
1.1055 + adaptor.disable(n3);
1.1056 + if (!adaptor.status(n3)) adaptor.enable(n3);
1.1057 +
1.1058 + checkGraphNodeList(adaptor, 3);
1.1059 + checkGraphArcList(adaptor, 4);
1.1060 + checkGraphEdgeList(adaptor, 2);
1.1061 + checkGraphConArcList(adaptor, 4);
1.1062 + checkGraphConEdgeList(adaptor, 2);
1.1063 +
1.1064 + checkGraphIncEdgeArcLists(adaptor, n2, 1);
1.1065 + checkGraphIncEdgeArcLists(adaptor, n3, 2);
1.1066 + checkGraphIncEdgeArcLists(adaptor, n4, 1);
1.1067 +
1.1068 + checkNodeIds(adaptor);
1.1069 + checkArcIds(adaptor);
1.1070 + checkEdgeIds(adaptor);
1.1071 +
1.1072 + checkGraphNodeMap(adaptor);
1.1073 + checkGraphArcMap(adaptor);
1.1074 + checkGraphEdgeMap(adaptor);
1.1075 +
1.1076 + // Hide all nodes
1.1077 + node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
1.1078 +
1.1079 + checkGraphNodeList(adaptor, 0);
1.1080 + checkGraphArcList(adaptor, 0);
1.1081 + checkGraphEdgeList(adaptor, 0);
1.1082 + checkGraphConArcList(adaptor, 0);
1.1083 + checkGraphConEdgeList(adaptor, 0);
1.1084 +
1.1085 + checkNodeIds(adaptor);
1.1086 + checkArcIds(adaptor);
1.1087 + checkEdgeIds(adaptor);
1.1088 +
1.1089 + checkGraphNodeMap(adaptor);
1.1090 + checkGraphArcMap(adaptor);
1.1091 + checkGraphEdgeMap(adaptor);
1.1092 +
1.1093 + // Check the conversion of nodes and edges
1.1094 + Graph::Node ng = n3;
1.1095 + ng = n4;
1.1096 + Adaptor::Node na = n1;
1.1097 + na = n2;
1.1098 + Graph::Edge eg = e3;
1.1099 + eg = e4;
1.1100 + Adaptor::Edge ea = e1;
1.1101 + ea = e2;
1.1102 +}
1.1103 +
1.1104 +void checkFilterEdges() {
1.1105 + // Check concepts
1.1106 + checkConcept<concepts::Graph, FilterEdges<concepts::Graph> >();
1.1107 + checkConcept<concepts::Graph, FilterEdges<ListGraph> >();
1.1108 + checkConcept<concepts::AlterableGraphComponent<>,
1.1109 + FilterEdges<ListGraph> >();
1.1110 + checkConcept<concepts::ExtendableGraphComponent<>,
1.1111 + FilterEdges<ListGraph> >();
1.1112 + checkConcept<concepts::ErasableGraphComponent<>,
1.1113 + FilterEdges<ListGraph> >();
1.1114 + checkConcept<concepts::ClearableGraphComponent<>,
1.1115 + FilterEdges<ListGraph> >();
1.1116 +
1.1117 + // Create a graph and an adaptor
1.1118 + typedef ListGraph Graph;
1.1119 + typedef Graph::EdgeMap<bool> EdgeFilter;
1.1120 + typedef FilterEdges<Graph, EdgeFilter> Adaptor;
1.1121 +
1.1122 + Graph graph;
1.1123 + EdgeFilter edge_filter(graph);
1.1124 + Adaptor adaptor(graph, edge_filter);
1.1125 +
1.1126 + // Add nodes and edges to the original graph and the adaptor
1.1127 + Graph::Node n1 = graph.addNode();
1.1128 + Graph::Node n2 = graph.addNode();
1.1129 + Adaptor::Node n3 = adaptor.addNode();
1.1130 + Adaptor::Node n4 = adaptor.addNode();
1.1131 +
1.1132 + Graph::Edge e1 = graph.addEdge(n1, n2);
1.1133 + Graph::Edge e2 = graph.addEdge(n1, n3);
1.1134 + Adaptor::Edge e3 = adaptor.addEdge(n2, n3);
1.1135 + Adaptor::Edge e4 = adaptor.addEdge(n3, n4);
1.1136 +
1.1137 + edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
1.1138 +
1.1139 + checkGraphNodeList(adaptor, 4);
1.1140 + checkGraphArcList(adaptor, 8);
1.1141 + checkGraphEdgeList(adaptor, 4);
1.1142 + checkGraphConArcList(adaptor, 8);
1.1143 + checkGraphConEdgeList(adaptor, 4);
1.1144 +
1.1145 + checkGraphIncEdgeArcLists(adaptor, n1, 2);
1.1146 + checkGraphIncEdgeArcLists(adaptor, n2, 2);
1.1147 + checkGraphIncEdgeArcLists(adaptor, n3, 3);
1.1148 + checkGraphIncEdgeArcLists(adaptor, n4, 1);
1.1149 +
1.1150 + checkNodeIds(adaptor);
1.1151 + checkArcIds(adaptor);
1.1152 + checkEdgeIds(adaptor);
1.1153 +
1.1154 + checkGraphNodeMap(adaptor);
1.1155 + checkGraphArcMap(adaptor);
1.1156 + checkGraphEdgeMap(adaptor);
1.1157 +
1.1158 + // Hide an edge
1.1159 + adaptor.status(e2, false);
1.1160 + adaptor.disable(e3);
1.1161 + if (!adaptor.status(e3)) adaptor.enable(e3);
1.1162 +
1.1163 + checkGraphNodeList(adaptor, 4);
1.1164 + checkGraphArcList(adaptor, 6);
1.1165 + checkGraphEdgeList(adaptor, 3);
1.1166 + checkGraphConArcList(adaptor, 6);
1.1167 + checkGraphConEdgeList(adaptor, 3);
1.1168 +
1.1169 + checkGraphIncEdgeArcLists(adaptor, n1, 1);
1.1170 + checkGraphIncEdgeArcLists(adaptor, n2, 2);
1.1171 + checkGraphIncEdgeArcLists(adaptor, n3, 2);
1.1172 + checkGraphIncEdgeArcLists(adaptor, n4, 1);
1.1173 +
1.1174 + checkNodeIds(adaptor);
1.1175 + checkArcIds(adaptor);
1.1176 + checkEdgeIds(adaptor);
1.1177 +
1.1178 + checkGraphNodeMap(adaptor);
1.1179 + checkGraphArcMap(adaptor);
1.1180 + checkGraphEdgeMap(adaptor);
1.1181 +
1.1182 + // Hide all edges
1.1183 + edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
1.1184 +
1.1185 + checkGraphNodeList(adaptor, 4);
1.1186 + checkGraphArcList(adaptor, 0);
1.1187 + checkGraphEdgeList(adaptor, 0);
1.1188 + checkGraphConArcList(adaptor, 0);
1.1189 + checkGraphConEdgeList(adaptor, 0);
1.1190 +
1.1191 + checkNodeIds(adaptor);
1.1192 + checkArcIds(adaptor);
1.1193 + checkEdgeIds(adaptor);
1.1194 +
1.1195 + checkGraphNodeMap(adaptor);
1.1196 + checkGraphArcMap(adaptor);
1.1197 + checkGraphEdgeMap(adaptor);
1.1198 +
1.1199 + // Check the conversion of nodes and edges
1.1200 + Graph::Node ng = n3;
1.1201 + ng = n4;
1.1202 + Adaptor::Node na = n1;
1.1203 + na = n2;
1.1204 + Graph::Edge eg = e3;
1.1205 + eg = e4;
1.1206 + Adaptor::Edge ea = e1;
1.1207 + ea = e2;
1.1208 +}
1.1209 +
1.1210 +void checkOrienter() {
1.1211 + // Check concepts
1.1212 + checkConcept<concepts::Digraph, Orienter<concepts::Graph> >();
1.1213 + checkConcept<concepts::Digraph, Orienter<ListGraph> >();
1.1214 + checkConcept<concepts::AlterableDigraphComponent<>,
1.1215 + Orienter<ListGraph> >();
1.1216 + checkConcept<concepts::ExtendableDigraphComponent<>,
1.1217 + Orienter<ListGraph> >();
1.1218 + checkConcept<concepts::ErasableDigraphComponent<>,
1.1219 + Orienter<ListGraph> >();
1.1220 + checkConcept<concepts::ClearableDigraphComponent<>,
1.1221 + Orienter<ListGraph> >();
1.1222 +
1.1223 + // Create a graph and an adaptor
1.1224 + typedef ListGraph Graph;
1.1225 + typedef ListGraph::EdgeMap<bool> DirMap;
1.1226 + typedef Orienter<Graph> Adaptor;
1.1227 +
1.1228 + Graph graph;
1.1229 + DirMap dir(graph);
1.1230 + Adaptor adaptor(graph, dir);
1.1231 +
1.1232 + // Add nodes and edges to the original graph and the adaptor
1.1233 + Graph::Node n1 = graph.addNode();
1.1234 + Graph::Node n2 = graph.addNode();
1.1235 + Adaptor::Node n3 = adaptor.addNode();
1.1236 +
1.1237 + Graph::Edge e1 = graph.addEdge(n1, n2);
1.1238 + Graph::Edge e2 = graph.addEdge(n1, n3);
1.1239 + Adaptor::Arc e3 = adaptor.addArc(n2, n3);
1.1240 +
1.1241 + dir[e1] = dir[e2] = dir[e3] = true;
1.1242 +
1.1243 + // Check the original graph
1.1244 + checkGraphNodeList(graph, 3);
1.1245 + checkGraphArcList(graph, 6);
1.1246 + checkGraphConArcList(graph, 6);
1.1247 + checkGraphEdgeList(graph, 3);
1.1248 + checkGraphConEdgeList(graph, 3);
1.1249 +
1.1250 + checkGraphIncEdgeArcLists(graph, n1, 2);
1.1251 + checkGraphIncEdgeArcLists(graph, n2, 2);
1.1252 + checkGraphIncEdgeArcLists(graph, n3, 2);
1.1253 +
1.1254 + checkNodeIds(graph);
1.1255 + checkArcIds(graph);
1.1256 + checkEdgeIds(graph);
1.1257 +
1.1258 + checkGraphNodeMap(graph);
1.1259 + checkGraphArcMap(graph);
1.1260 + checkGraphEdgeMap(graph);
1.1261 +
1.1262 + // Check the adaptor
1.1263 + checkGraphNodeList(adaptor, 3);
1.1264 + checkGraphArcList(adaptor, 3);
1.1265 + checkGraphConArcList(adaptor, 3);
1.1266 +
1.1267 + checkGraphOutArcList(adaptor, n1, 2);
1.1268 + checkGraphOutArcList(adaptor, n2, 1);
1.1269 + checkGraphOutArcList(adaptor, n3, 0);
1.1270 +
1.1271 + checkGraphInArcList(adaptor, n1, 0);
1.1272 + checkGraphInArcList(adaptor, n2, 1);
1.1273 + checkGraphInArcList(adaptor, n3, 2);
1.1274 +
1.1275 + checkNodeIds(adaptor);
1.1276 + checkArcIds(adaptor);
1.1277 +
1.1278 + checkGraphNodeMap(adaptor);
1.1279 + checkGraphArcMap(adaptor);
1.1280 +
1.1281 + // Check direction changing
1.1282 + {
1.1283 + dir[e1] = true;
1.1284 + Adaptor::Node u = adaptor.source(e1);
1.1285 + Adaptor::Node v = adaptor.target(e1);
1.1286 +
1.1287 + dir[e1] = false;
1.1288 + check (u == adaptor.target(e1), "Wrong dir");
1.1289 + check (v == adaptor.source(e1), "Wrong dir");
1.1290 +
1.1291 + check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");
1.1292 + dir[e1] = n1 == u;
1.1293 + }
1.1294 +
1.1295 + {
1.1296 + dir[e2] = true;
1.1297 + Adaptor::Node u = adaptor.source(e2);
1.1298 + Adaptor::Node v = adaptor.target(e2);
1.1299 +
1.1300 + dir[e2] = false;
1.1301 + check (u == adaptor.target(e2), "Wrong dir");
1.1302 + check (v == adaptor.source(e2), "Wrong dir");
1.1303 +
1.1304 + check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");
1.1305 + dir[e2] = n3 == u;
1.1306 + }
1.1307 +
1.1308 + {
1.1309 + dir[e3] = true;
1.1310 + Adaptor::Node u = adaptor.source(e3);
1.1311 + Adaptor::Node v = adaptor.target(e3);
1.1312 +
1.1313 + dir[e3] = false;
1.1314 + check (u == adaptor.target(e3), "Wrong dir");
1.1315 + check (v == adaptor.source(e3), "Wrong dir");
1.1316 +
1.1317 + check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
1.1318 + dir[e3] = n2 == u;
1.1319 + }
1.1320 +
1.1321 + // Check the adaptor again
1.1322 + checkGraphNodeList(adaptor, 3);
1.1323 + checkGraphArcList(adaptor, 3);
1.1324 + checkGraphConArcList(adaptor, 3);
1.1325 +
1.1326 + checkGraphOutArcList(adaptor, n1, 1);
1.1327 + checkGraphOutArcList(adaptor, n2, 1);
1.1328 + checkGraphOutArcList(adaptor, n3, 1);
1.1329 +
1.1330 + checkGraphInArcList(adaptor, n1, 1);
1.1331 + checkGraphInArcList(adaptor, n2, 1);
1.1332 + checkGraphInArcList(adaptor, n3, 1);
1.1333 +
1.1334 + checkNodeIds(adaptor);
1.1335 + checkArcIds(adaptor);
1.1336 +
1.1337 + checkGraphNodeMap(adaptor);
1.1338 + checkGraphArcMap(adaptor);
1.1339 +
1.1340 + // Check reverseArc()
1.1341 + adaptor.reverseArc(e2);
1.1342 + adaptor.reverseArc(e3);
1.1343 + adaptor.reverseArc(e2);
1.1344 +
1.1345 + checkGraphNodeList(adaptor, 3);
1.1346 + checkGraphArcList(adaptor, 3);
1.1347 + checkGraphConArcList(adaptor, 3);
1.1348 +
1.1349 + checkGraphOutArcList(adaptor, n1, 1);
1.1350 + checkGraphOutArcList(adaptor, n2, 0);
1.1351 + checkGraphOutArcList(adaptor, n3, 2);
1.1352 +
1.1353 + checkGraphInArcList(adaptor, n1, 1);
1.1354 + checkGraphInArcList(adaptor, n2, 2);
1.1355 + checkGraphInArcList(adaptor, n3, 0);
1.1356 +
1.1357 + // Check the conversion of nodes and arcs/edges
1.1358 + Graph::Node ng = n3;
1.1359 + ng = n3;
1.1360 + Adaptor::Node na = n1;
1.1361 + na = n2;
1.1362 + Graph::Edge eg = e3;
1.1363 + eg = e3;
1.1364 + Adaptor::Arc aa = e1;
1.1365 + aa = e2;
1.1366 +}
1.1367 +
1.1368 +void checkCombiningAdaptors() {
1.1369 + // Create a grid graph
1.1370 + GridGraph graph(2,2);
1.1371 + GridGraph::Node n1 = graph(0,0);
1.1372 + GridGraph::Node n2 = graph(0,1);
1.1373 + GridGraph::Node n3 = graph(1,0);
1.1374 + GridGraph::Node n4 = graph(1,1);
1.1375 +
1.1376 + GridGraph::EdgeMap<bool> dir_map(graph);
1.1377 + dir_map[graph.right(n1)] = graph.u(graph.right(n1)) != n1;
1.1378 + dir_map[graph.up(n1)] = graph.u(graph.up(n1)) == n1;
1.1379 + dir_map[graph.left(n4)] = graph.u(graph.left(n4)) == n4;
1.1380 + dir_map[graph.down(n4)] = graph.u(graph.down(n4)) == n4;
1.1381 +
1.1382 + // Apply several adaptors on the grid graph
1.1383 + typedef SplitNodes<Orienter< const GridGraph, GridGraph::EdgeMap<bool> > >
1.1384 + SplitGridGraph;
1.1385 + typedef Undirector<const SplitGridGraph> USplitGridGraph;
1.1386 + checkConcept<concepts::Digraph, SplitGridGraph>();
1.1387 + checkConcept<concepts::Graph, USplitGridGraph>();
1.1388 +
1.1389 + SplitGridGraph adaptor = splitNodes(orienter(graph, dir_map));
1.1390 + USplitGridGraph uadaptor = undirector(adaptor);
1.1391 +
1.1392 + // Check adaptor
1.1393 + checkGraphNodeList(adaptor, 8);
1.1394 + checkGraphArcList(adaptor, 8);
1.1395 + checkGraphConArcList(adaptor, 8);
1.1396 +
1.1397 + checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
1.1398 + checkGraphOutArcList(adaptor, adaptor.outNode(n1), 1);
1.1399 + checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
1.1400 + checkGraphOutArcList(adaptor, adaptor.outNode(n2), 0);
1.1401 + checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
1.1402 + checkGraphOutArcList(adaptor, adaptor.outNode(n3), 1);
1.1403 + checkGraphOutArcList(adaptor, adaptor.inNode(n4), 1);
1.1404 + checkGraphOutArcList(adaptor, adaptor.outNode(n4), 2);
1.1405 +
1.1406 + checkGraphInArcList(adaptor, adaptor.inNode(n1), 1);
1.1407 + checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
1.1408 + checkGraphInArcList(adaptor, adaptor.inNode(n2), 2);
1.1409 + checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
1.1410 + checkGraphInArcList(adaptor, adaptor.inNode(n3), 1);
1.1411 + checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
1.1412 + checkGraphInArcList(adaptor, adaptor.inNode(n4), 0);
1.1413 + checkGraphInArcList(adaptor, adaptor.outNode(n4), 1);
1.1414 +
1.1415 + checkNodeIds(adaptor);
1.1416 + checkArcIds(adaptor);
1.1417 +
1.1418 + checkGraphNodeMap(adaptor);
1.1419 + checkGraphArcMap(adaptor);
1.1420 +
1.1421 + // Check uadaptor
1.1422 + checkGraphNodeList(uadaptor, 8);
1.1423 + checkGraphEdgeList(uadaptor, 8);
1.1424 + checkGraphArcList(uadaptor, 16);
1.1425 + checkGraphConEdgeList(uadaptor, 8);
1.1426 + checkGraphConArcList(uadaptor, 16);
1.1427 +
1.1428 + checkNodeIds(uadaptor);
1.1429 + checkEdgeIds(uadaptor);
1.1430 + checkArcIds(uadaptor);
1.1431 +
1.1432 + checkGraphNodeMap(uadaptor);
1.1433 + checkGraphEdgeMap(uadaptor);
1.1434 + checkGraphArcMap(uadaptor);
1.1435 +
1.1436 + checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n1), 2);
1.1437 + checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n1), 2);
1.1438 + checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n2), 3);
1.1439 + checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n2), 1);
1.1440 + checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n3), 2);
1.1441 + checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n3), 2);
1.1442 + checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n4), 1);
1.1443 + checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n4), 3);
1.1444 +}
1.1445 +
1.1446 +int main(int, const char **) {
1.1447 + // Check the digraph adaptors (using ListDigraph)
1.1448 + checkReverseDigraph();
1.1449 + checkSubDigraph();
1.1450 + checkFilterNodes1();
1.1451 + checkFilterArcs();
1.1452 + checkUndirector();
1.1453 + checkResidualDigraph();
1.1454 + checkSplitNodes();
1.1455 +
1.1456 + // Check the graph adaptors (using ListGraph)
1.1457 + checkSubGraph();
1.1458 + checkFilterNodes2();
1.1459 + checkFilterEdges();
1.1460 + checkOrienter();
1.1461 +
1.1462 + // Combine adaptors (using GridGraph)
1.1463 + checkCombiningAdaptors();
1.1464 +
1.1465 + return 0;
1.1466 +}