1.1 --- a/test/graph_adaptor_test.cc Mon Jan 12 12:26:02 2009 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,984 +0,0 @@
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<lemon/concept_check.h>
1.24 -
1.25 -#include<lemon/list_graph.h>
1.26 -#include<lemon/smart_graph.h>
1.27 -
1.28 -#include<lemon/concepts/digraph.h>
1.29 -#include<lemon/concepts/graph.h>
1.30 -
1.31 -#include<lemon/adaptors.h>
1.32 -
1.33 -#include <limits>
1.34 -#include <lemon/bfs.h>
1.35 -#include <lemon/path.h>
1.36 -
1.37 -#include"test/test_tools.h"
1.38 -#include"test/graph_test.h"
1.39 -
1.40 -using namespace lemon;
1.41 -
1.42 -void checkReverseDigraph() {
1.43 - checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
1.44 -
1.45 - typedef ListDigraph Digraph;
1.46 - typedef ReverseDigraph<Digraph> Adaptor;
1.47 -
1.48 - Digraph digraph;
1.49 - Adaptor adaptor(digraph);
1.50 -
1.51 - Digraph::Node n1 = digraph.addNode();
1.52 - Digraph::Node n2 = digraph.addNode();
1.53 - Digraph::Node n3 = digraph.addNode();
1.54 -
1.55 - Digraph::Arc a1 = digraph.addArc(n1, n2);
1.56 - Digraph::Arc a2 = digraph.addArc(n1, n3);
1.57 - Digraph::Arc a3 = digraph.addArc(n2, n3);
1.58 -
1.59 - checkGraphNodeList(adaptor, 3);
1.60 - checkGraphArcList(adaptor, 3);
1.61 - checkGraphConArcList(adaptor, 3);
1.62 -
1.63 - checkGraphOutArcList(adaptor, n1, 0);
1.64 - checkGraphOutArcList(adaptor, n2, 1);
1.65 - checkGraphOutArcList(adaptor, n3, 2);
1.66 -
1.67 - checkGraphInArcList(adaptor, n1, 2);
1.68 - checkGraphInArcList(adaptor, n2, 1);
1.69 - checkGraphInArcList(adaptor, n3, 0);
1.70 -
1.71 - checkNodeIds(adaptor);
1.72 - checkArcIds(adaptor);
1.73 -
1.74 - checkGraphNodeMap(adaptor);
1.75 - checkGraphArcMap(adaptor);
1.76 -
1.77 - for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
1.78 - check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
1.79 - check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
1.80 - }
1.81 -}
1.82 -
1.83 -void checkSubDigraph() {
1.84 - checkConcept<concepts::Digraph,
1.85 - SubDigraph<concepts::Digraph,
1.86 - concepts::Digraph::NodeMap<bool>,
1.87 - concepts::Digraph::ArcMap<bool> > >();
1.88 -
1.89 - typedef ListDigraph Digraph;
1.90 - typedef Digraph::NodeMap<bool> NodeFilter;
1.91 - typedef Digraph::ArcMap<bool> ArcFilter;
1.92 - typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
1.93 -
1.94 - Digraph digraph;
1.95 - NodeFilter node_filter(digraph);
1.96 - ArcFilter arc_filter(digraph);
1.97 - Adaptor adaptor(digraph, node_filter, arc_filter);
1.98 -
1.99 - Digraph::Node n1 = digraph.addNode();
1.100 - Digraph::Node n2 = digraph.addNode();
1.101 - Digraph::Node n3 = digraph.addNode();
1.102 -
1.103 - Digraph::Arc a1 = digraph.addArc(n1, n2);
1.104 - Digraph::Arc a2 = digraph.addArc(n1, n3);
1.105 - Digraph::Arc a3 = digraph.addArc(n2, n3);
1.106 -
1.107 - node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
1.108 - arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
1.109 -
1.110 - checkGraphNodeList(adaptor, 3);
1.111 - checkGraphArcList(adaptor, 3);
1.112 - checkGraphConArcList(adaptor, 3);
1.113 -
1.114 - checkGraphOutArcList(adaptor, n1, 2);
1.115 - checkGraphOutArcList(adaptor, n2, 1);
1.116 - checkGraphOutArcList(adaptor, n3, 0);
1.117 -
1.118 - checkGraphInArcList(adaptor, n1, 0);
1.119 - checkGraphInArcList(adaptor, n2, 1);
1.120 - checkGraphInArcList(adaptor, n3, 2);
1.121 -
1.122 - checkNodeIds(adaptor);
1.123 - checkArcIds(adaptor);
1.124 -
1.125 - checkGraphNodeMap(adaptor);
1.126 - checkGraphArcMap(adaptor);
1.127 -
1.128 - arc_filter[a2] = false;
1.129 -
1.130 - checkGraphNodeList(adaptor, 3);
1.131 - checkGraphArcList(adaptor, 2);
1.132 - checkGraphConArcList(adaptor, 2);
1.133 -
1.134 - checkGraphOutArcList(adaptor, n1, 1);
1.135 - checkGraphOutArcList(adaptor, n2, 1);
1.136 - checkGraphOutArcList(adaptor, n3, 0);
1.137 -
1.138 - checkGraphInArcList(adaptor, n1, 0);
1.139 - checkGraphInArcList(adaptor, n2, 1);
1.140 - checkGraphInArcList(adaptor, n3, 1);
1.141 -
1.142 - checkNodeIds(adaptor);
1.143 - checkArcIds(adaptor);
1.144 -
1.145 - checkGraphNodeMap(adaptor);
1.146 - checkGraphArcMap(adaptor);
1.147 -
1.148 - node_filter[n1] = false;
1.149 -
1.150 - checkGraphNodeList(adaptor, 2);
1.151 - checkGraphArcList(adaptor, 1);
1.152 - checkGraphConArcList(adaptor, 1);
1.153 -
1.154 - checkGraphOutArcList(adaptor, n2, 1);
1.155 - checkGraphOutArcList(adaptor, n3, 0);
1.156 -
1.157 - checkGraphInArcList(adaptor, n2, 0);
1.158 - checkGraphInArcList(adaptor, n3, 1);
1.159 -
1.160 - checkNodeIds(adaptor);
1.161 - checkArcIds(adaptor);
1.162 -
1.163 - checkGraphNodeMap(adaptor);
1.164 - checkGraphArcMap(adaptor);
1.165 -
1.166 - node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
1.167 - arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
1.168 -
1.169 - checkGraphNodeList(adaptor, 0);
1.170 - checkGraphArcList(adaptor, 0);
1.171 - checkGraphConArcList(adaptor, 0);
1.172 -
1.173 - checkNodeIds(adaptor);
1.174 - checkArcIds(adaptor);
1.175 -
1.176 - checkGraphNodeMap(adaptor);
1.177 - checkGraphArcMap(adaptor);
1.178 -}
1.179 -
1.180 -void checkFilterNodes1() {
1.181 - checkConcept<concepts::Digraph,
1.182 - FilterNodes<concepts::Digraph,
1.183 - concepts::Digraph::NodeMap<bool> > >();
1.184 -
1.185 - typedef ListDigraph Digraph;
1.186 - typedef Digraph::NodeMap<bool> NodeFilter;
1.187 - typedef FilterNodes<Digraph, NodeFilter> Adaptor;
1.188 -
1.189 - Digraph digraph;
1.190 - NodeFilter node_filter(digraph);
1.191 - Adaptor adaptor(digraph, node_filter);
1.192 -
1.193 - Digraph::Node n1 = digraph.addNode();
1.194 - Digraph::Node n2 = digraph.addNode();
1.195 - Digraph::Node n3 = digraph.addNode();
1.196 -
1.197 - Digraph::Arc a1 = digraph.addArc(n1, n2);
1.198 - Digraph::Arc a2 = digraph.addArc(n1, n3);
1.199 - Digraph::Arc a3 = digraph.addArc(n2, n3);
1.200 -
1.201 - node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
1.202 -
1.203 - checkGraphNodeList(adaptor, 3);
1.204 - checkGraphArcList(adaptor, 3);
1.205 - checkGraphConArcList(adaptor, 3);
1.206 -
1.207 - checkGraphOutArcList(adaptor, n1, 2);
1.208 - checkGraphOutArcList(adaptor, n2, 1);
1.209 - checkGraphOutArcList(adaptor, n3, 0);
1.210 -
1.211 - checkGraphInArcList(adaptor, n1, 0);
1.212 - checkGraphInArcList(adaptor, n2, 1);
1.213 - checkGraphInArcList(adaptor, n3, 2);
1.214 -
1.215 - checkNodeIds(adaptor);
1.216 - checkArcIds(adaptor);
1.217 -
1.218 - checkGraphNodeMap(adaptor);
1.219 - checkGraphArcMap(adaptor);
1.220 -
1.221 - node_filter[n1] = false;
1.222 -
1.223 - checkGraphNodeList(adaptor, 2);
1.224 - checkGraphArcList(adaptor, 1);
1.225 - checkGraphConArcList(adaptor, 1);
1.226 -
1.227 - checkGraphOutArcList(adaptor, n2, 1);
1.228 - checkGraphOutArcList(adaptor, n3, 0);
1.229 -
1.230 - checkGraphInArcList(adaptor, n2, 0);
1.231 - checkGraphInArcList(adaptor, n3, 1);
1.232 -
1.233 - checkNodeIds(adaptor);
1.234 - checkArcIds(adaptor);
1.235 -
1.236 - checkGraphNodeMap(adaptor);
1.237 - checkGraphArcMap(adaptor);
1.238 -
1.239 - node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
1.240 -
1.241 - checkGraphNodeList(adaptor, 0);
1.242 - checkGraphArcList(adaptor, 0);
1.243 - checkGraphConArcList(adaptor, 0);
1.244 -
1.245 - checkNodeIds(adaptor);
1.246 - checkArcIds(adaptor);
1.247 -
1.248 - checkGraphNodeMap(adaptor);
1.249 - checkGraphArcMap(adaptor);
1.250 -}
1.251 -
1.252 -void checkFilterArcs() {
1.253 - checkConcept<concepts::Digraph,
1.254 - FilterArcs<concepts::Digraph,
1.255 - concepts::Digraph::ArcMap<bool> > >();
1.256 -
1.257 - typedef ListDigraph Digraph;
1.258 - typedef Digraph::ArcMap<bool> ArcFilter;
1.259 - typedef FilterArcs<Digraph, ArcFilter> Adaptor;
1.260 -
1.261 - Digraph digraph;
1.262 - ArcFilter arc_filter(digraph);
1.263 - Adaptor adaptor(digraph, arc_filter);
1.264 -
1.265 - Digraph::Node n1 = digraph.addNode();
1.266 - Digraph::Node n2 = digraph.addNode();
1.267 - Digraph::Node n3 = digraph.addNode();
1.268 -
1.269 - Digraph::Arc a1 = digraph.addArc(n1, n2);
1.270 - Digraph::Arc a2 = digraph.addArc(n1, n3);
1.271 - Digraph::Arc a3 = digraph.addArc(n2, n3);
1.272 -
1.273 - arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
1.274 -
1.275 - checkGraphNodeList(adaptor, 3);
1.276 - checkGraphArcList(adaptor, 3);
1.277 - checkGraphConArcList(adaptor, 3);
1.278 -
1.279 - checkGraphOutArcList(adaptor, n1, 2);
1.280 - checkGraphOutArcList(adaptor, n2, 1);
1.281 - checkGraphOutArcList(adaptor, n3, 0);
1.282 -
1.283 - checkGraphInArcList(adaptor, n1, 0);
1.284 - checkGraphInArcList(adaptor, n2, 1);
1.285 - checkGraphInArcList(adaptor, n3, 2);
1.286 -
1.287 - checkNodeIds(adaptor);
1.288 - checkArcIds(adaptor);
1.289 -
1.290 - checkGraphNodeMap(adaptor);
1.291 - checkGraphArcMap(adaptor);
1.292 -
1.293 - arc_filter[a2] = false;
1.294 -
1.295 - checkGraphNodeList(adaptor, 3);
1.296 - checkGraphArcList(adaptor, 2);
1.297 - checkGraphConArcList(adaptor, 2);
1.298 -
1.299 - checkGraphOutArcList(adaptor, n1, 1);
1.300 - checkGraphOutArcList(adaptor, n2, 1);
1.301 - checkGraphOutArcList(adaptor, n3, 0);
1.302 -
1.303 - checkGraphInArcList(adaptor, n1, 0);
1.304 - checkGraphInArcList(adaptor, n2, 1);
1.305 - checkGraphInArcList(adaptor, n3, 1);
1.306 -
1.307 - checkNodeIds(adaptor);
1.308 - checkArcIds(adaptor);
1.309 -
1.310 - checkGraphNodeMap(adaptor);
1.311 - checkGraphArcMap(adaptor);
1.312 -
1.313 - arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
1.314 -
1.315 - checkGraphNodeList(adaptor, 3);
1.316 - checkGraphArcList(adaptor, 0);
1.317 - checkGraphConArcList(adaptor, 0);
1.318 -
1.319 - checkNodeIds(adaptor);
1.320 - checkArcIds(adaptor);
1.321 -
1.322 - checkGraphNodeMap(adaptor);
1.323 - checkGraphArcMap(adaptor);
1.324 -}
1.325 -
1.326 -void checkUndirector() {
1.327 - checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
1.328 -
1.329 - typedef ListDigraph Digraph;
1.330 - typedef Undirector<Digraph> Adaptor;
1.331 -
1.332 - Digraph digraph;
1.333 - Adaptor adaptor(digraph);
1.334 -
1.335 - Digraph::Node n1 = digraph.addNode();
1.336 - Digraph::Node n2 = digraph.addNode();
1.337 - Digraph::Node n3 = digraph.addNode();
1.338 -
1.339 - Digraph::Arc a1 = digraph.addArc(n1, n2);
1.340 - Digraph::Arc a2 = digraph.addArc(n1, n3);
1.341 - Digraph::Arc a3 = digraph.addArc(n2, n3);
1.342 -
1.343 - checkGraphNodeList(adaptor, 3);
1.344 - checkGraphArcList(adaptor, 6);
1.345 - checkGraphEdgeList(adaptor, 3);
1.346 - checkGraphConArcList(adaptor, 6);
1.347 - checkGraphConEdgeList(adaptor, 3);
1.348 -
1.349 - checkGraphOutArcList(adaptor, n1, 2);
1.350 - checkGraphOutArcList(adaptor, n2, 2);
1.351 - checkGraphOutArcList(adaptor, n3, 2);
1.352 -
1.353 - checkGraphInArcList(adaptor, n1, 2);
1.354 - checkGraphInArcList(adaptor, n2, 2);
1.355 - checkGraphInArcList(adaptor, n3, 2);
1.356 -
1.357 - checkGraphIncEdgeList(adaptor, n1, 2);
1.358 - checkGraphIncEdgeList(adaptor, n2, 2);
1.359 - checkGraphIncEdgeList(adaptor, n3, 2);
1.360 -
1.361 - checkNodeIds(adaptor);
1.362 - checkArcIds(adaptor);
1.363 - checkEdgeIds(adaptor);
1.364 -
1.365 - checkGraphNodeMap(adaptor);
1.366 - checkGraphArcMap(adaptor);
1.367 - checkGraphEdgeMap(adaptor);
1.368 -
1.369 - for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {
1.370 - check(adaptor.u(e) == digraph.source(e), "Wrong undir");
1.371 - check(adaptor.v(e) == digraph.target(e), "Wrong undir");
1.372 - }
1.373 -
1.374 -}
1.375 -
1.376 -void checkResidual() {
1.377 - checkConcept<concepts::Digraph,
1.378 - Residual<concepts::Digraph,
1.379 - concepts::Digraph::ArcMap<int>,
1.380 - concepts::Digraph::ArcMap<int> > >();
1.381 -
1.382 - typedef ListDigraph Digraph;
1.383 - typedef Digraph::ArcMap<int> IntArcMap;
1.384 - typedef Residual<Digraph, IntArcMap> Adaptor;
1.385 -
1.386 - Digraph digraph;
1.387 - IntArcMap capacity(digraph), flow(digraph);
1.388 - Adaptor adaptor(digraph, capacity, flow);
1.389 -
1.390 - Digraph::Node n1 = digraph.addNode();
1.391 - Digraph::Node n2 = digraph.addNode();
1.392 - Digraph::Node n3 = digraph.addNode();
1.393 - Digraph::Node n4 = digraph.addNode();
1.394 -
1.395 - Digraph::Arc a1 = digraph.addArc(n1, n2);
1.396 - Digraph::Arc a2 = digraph.addArc(n1, n3);
1.397 - Digraph::Arc a3 = digraph.addArc(n1, n4);
1.398 - Digraph::Arc a4 = digraph.addArc(n2, n3);
1.399 - Digraph::Arc a5 = digraph.addArc(n2, n4);
1.400 - Digraph::Arc a6 = digraph.addArc(n3, n4);
1.401 -
1.402 - capacity[a1] = 8;
1.403 - capacity[a2] = 6;
1.404 - capacity[a3] = 4;
1.405 - capacity[a4] = 4;
1.406 - capacity[a5] = 6;
1.407 - capacity[a6] = 10;
1.408 -
1.409 - for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
1.410 - flow[a] = 0;
1.411 - }
1.412 -
1.413 - checkGraphNodeList(adaptor, 4);
1.414 - checkGraphArcList(adaptor, 6);
1.415 - checkGraphConArcList(adaptor, 6);
1.416 -
1.417 - checkGraphOutArcList(adaptor, n1, 3);
1.418 - checkGraphOutArcList(adaptor, n2, 2);
1.419 - checkGraphOutArcList(adaptor, n3, 1);
1.420 - checkGraphOutArcList(adaptor, n4, 0);
1.421 -
1.422 - checkGraphInArcList(adaptor, n1, 0);
1.423 - checkGraphInArcList(adaptor, n2, 1);
1.424 - checkGraphInArcList(adaptor, n3, 2);
1.425 - checkGraphInArcList(adaptor, n4, 3);
1.426 -
1.427 - for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
1.428 - flow[a] = capacity[a] / 2;
1.429 - }
1.430 -
1.431 - checkGraphNodeList(adaptor, 4);
1.432 - checkGraphArcList(adaptor, 12);
1.433 - checkGraphConArcList(adaptor, 12);
1.434 -
1.435 - checkGraphOutArcList(adaptor, n1, 3);
1.436 - checkGraphOutArcList(adaptor, n2, 3);
1.437 - checkGraphOutArcList(adaptor, n3, 3);
1.438 - checkGraphOutArcList(adaptor, n4, 3);
1.439 -
1.440 - checkGraphInArcList(adaptor, n1, 3);
1.441 - checkGraphInArcList(adaptor, n2, 3);
1.442 - checkGraphInArcList(adaptor, n3, 3);
1.443 - checkGraphInArcList(adaptor, n4, 3);
1.444 -
1.445 - checkNodeIds(adaptor);
1.446 - checkArcIds(adaptor);
1.447 -
1.448 - checkGraphNodeMap(adaptor);
1.449 - checkGraphArcMap(adaptor);
1.450 -
1.451 - for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
1.452 - flow[a] = capacity[a];
1.453 - }
1.454 -
1.455 - checkGraphNodeList(adaptor, 4);
1.456 - checkGraphArcList(adaptor, 6);
1.457 - checkGraphConArcList(adaptor, 6);
1.458 -
1.459 - checkGraphOutArcList(adaptor, n1, 0);
1.460 - checkGraphOutArcList(adaptor, n2, 1);
1.461 - checkGraphOutArcList(adaptor, n3, 2);
1.462 - checkGraphOutArcList(adaptor, n4, 3);
1.463 -
1.464 - checkGraphInArcList(adaptor, n1, 3);
1.465 - checkGraphInArcList(adaptor, n2, 2);
1.466 - checkGraphInArcList(adaptor, n3, 1);
1.467 - checkGraphInArcList(adaptor, n4, 0);
1.468 -
1.469 - for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
1.470 - flow[a] = 0;
1.471 - }
1.472 -
1.473 - int flow_value = 0;
1.474 - while (true) {
1.475 -
1.476 - Bfs<Adaptor> bfs(adaptor);
1.477 - bfs.run(n1, n4);
1.478 -
1.479 - if (!bfs.reached(n4)) break;
1.480 -
1.481 - Path<Adaptor> p = bfs.path(n4);
1.482 -
1.483 - int min = std::numeric_limits<int>::max();
1.484 - for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
1.485 - if (adaptor.residualCapacity(a) < min)
1.486 - min = adaptor.residualCapacity(a);
1.487 - }
1.488 -
1.489 - for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
1.490 - adaptor.augment(a, min);
1.491 - }
1.492 - flow_value += min;
1.493 - }
1.494 -
1.495 - check(flow_value == 18, "Wrong flow with res graph adaptor");
1.496 -
1.497 -}
1.498 -
1.499 -void checkSplitNodes() {
1.500 - checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
1.501 -
1.502 - typedef ListDigraph Digraph;
1.503 - typedef SplitNodes<Digraph> Adaptor;
1.504 -
1.505 - Digraph digraph;
1.506 - Adaptor adaptor(digraph);
1.507 -
1.508 - Digraph::Node n1 = digraph.addNode();
1.509 - Digraph::Node n2 = digraph.addNode();
1.510 - Digraph::Node n3 = digraph.addNode();
1.511 -
1.512 - Digraph::Arc a1 = digraph.addArc(n1, n2);
1.513 - Digraph::Arc a2 = digraph.addArc(n1, n3);
1.514 - Digraph::Arc a3 = digraph.addArc(n2, n3);
1.515 -
1.516 - checkGraphNodeList(adaptor, 6);
1.517 - checkGraphArcList(adaptor, 6);
1.518 - checkGraphConArcList(adaptor, 6);
1.519 -
1.520 - checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
1.521 - checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2);
1.522 - checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
1.523 - checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1);
1.524 - checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
1.525 - checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0);
1.526 -
1.527 - checkGraphInArcList(adaptor, adaptor.inNode(n1), 0);
1.528 - checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
1.529 - checkGraphInArcList(adaptor, adaptor.inNode(n2), 1);
1.530 - checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
1.531 - checkGraphInArcList(adaptor, adaptor.inNode(n3), 2);
1.532 - checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
1.533 -
1.534 - checkNodeIds(adaptor);
1.535 - checkArcIds(adaptor);
1.536 -
1.537 - checkGraphNodeMap(adaptor);
1.538 - checkGraphArcMap(adaptor);
1.539 -
1.540 - for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
1.541 - if (adaptor.origArc(a)) {
1.542 - Digraph::Arc oa = a;
1.543 - check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),
1.544 - "Wrong split");
1.545 - check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),
1.546 - "Wrong split");
1.547 - } else {
1.548 - Digraph::Node on = a;
1.549 - check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");
1.550 - check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");
1.551 - }
1.552 - }
1.553 -}
1.554 -
1.555 -void checkSubGraph() {
1.556 - checkConcept<concepts::Graph,
1.557 - SubGraph<concepts::Graph,
1.558 - concepts::Graph::NodeMap<bool>,
1.559 - concepts::Graph::EdgeMap<bool> > >();
1.560 -
1.561 - typedef ListGraph Graph;
1.562 - typedef Graph::NodeMap<bool> NodeFilter;
1.563 - typedef Graph::EdgeMap<bool> EdgeFilter;
1.564 - typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;
1.565 -
1.566 - Graph graph;
1.567 - NodeFilter node_filter(graph);
1.568 - EdgeFilter edge_filter(graph);
1.569 - Adaptor adaptor(graph, node_filter, edge_filter);
1.570 -
1.571 - Graph::Node n1 = graph.addNode();
1.572 - Graph::Node n2 = graph.addNode();
1.573 - Graph::Node n3 = graph.addNode();
1.574 - Graph::Node n4 = graph.addNode();
1.575 -
1.576 - Graph::Edge e1 = graph.addEdge(n1, n2);
1.577 - Graph::Edge e2 = graph.addEdge(n1, n3);
1.578 - Graph::Edge e3 = graph.addEdge(n2, n3);
1.579 - Graph::Edge e4 = graph.addEdge(n3, n4);
1.580 -
1.581 - node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
1.582 - edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
1.583 -
1.584 - checkGraphNodeList(adaptor, 4);
1.585 - checkGraphArcList(adaptor, 8);
1.586 - checkGraphEdgeList(adaptor, 4);
1.587 - checkGraphConArcList(adaptor, 8);
1.588 - checkGraphConEdgeList(adaptor, 4);
1.589 -
1.590 - checkGraphOutArcList(adaptor, n1, 2);
1.591 - checkGraphOutArcList(adaptor, n2, 2);
1.592 - checkGraphOutArcList(adaptor, n3, 3);
1.593 - checkGraphOutArcList(adaptor, n4, 1);
1.594 -
1.595 - checkGraphInArcList(adaptor, n1, 2);
1.596 - checkGraphInArcList(adaptor, n2, 2);
1.597 - checkGraphInArcList(adaptor, n3, 3);
1.598 - checkGraphInArcList(adaptor, n4, 1);
1.599 -
1.600 - checkGraphIncEdgeList(adaptor, n1, 2);
1.601 - checkGraphIncEdgeList(adaptor, n2, 2);
1.602 - checkGraphIncEdgeList(adaptor, n3, 3);
1.603 - checkGraphIncEdgeList(adaptor, n4, 1);
1.604 -
1.605 - checkNodeIds(adaptor);
1.606 - checkArcIds(adaptor);
1.607 - checkEdgeIds(adaptor);
1.608 -
1.609 - checkGraphNodeMap(adaptor);
1.610 - checkGraphArcMap(adaptor);
1.611 - checkGraphEdgeMap(adaptor);
1.612 -
1.613 - edge_filter[e2] = false;
1.614 -
1.615 - checkGraphNodeList(adaptor, 4);
1.616 - checkGraphArcList(adaptor, 6);
1.617 - checkGraphEdgeList(adaptor, 3);
1.618 - checkGraphConArcList(adaptor, 6);
1.619 - checkGraphConEdgeList(adaptor, 3);
1.620 -
1.621 - checkGraphOutArcList(adaptor, n1, 1);
1.622 - checkGraphOutArcList(adaptor, n2, 2);
1.623 - checkGraphOutArcList(adaptor, n3, 2);
1.624 - checkGraphOutArcList(adaptor, n4, 1);
1.625 -
1.626 - checkGraphInArcList(adaptor, n1, 1);
1.627 - checkGraphInArcList(adaptor, n2, 2);
1.628 - checkGraphInArcList(adaptor, n3, 2);
1.629 - checkGraphInArcList(adaptor, n4, 1);
1.630 -
1.631 - checkGraphIncEdgeList(adaptor, n1, 1);
1.632 - checkGraphIncEdgeList(adaptor, n2, 2);
1.633 - checkGraphIncEdgeList(adaptor, n3, 2);
1.634 - checkGraphIncEdgeList(adaptor, n4, 1);
1.635 -
1.636 - checkNodeIds(adaptor);
1.637 - checkArcIds(adaptor);
1.638 - checkEdgeIds(adaptor);
1.639 -
1.640 - checkGraphNodeMap(adaptor);
1.641 - checkGraphArcMap(adaptor);
1.642 - checkGraphEdgeMap(adaptor);
1.643 -
1.644 - node_filter[n1] = false;
1.645 -
1.646 - checkGraphNodeList(adaptor, 3);
1.647 - checkGraphArcList(adaptor, 4);
1.648 - checkGraphEdgeList(adaptor, 2);
1.649 - checkGraphConArcList(adaptor, 4);
1.650 - checkGraphConEdgeList(adaptor, 2);
1.651 -
1.652 - checkGraphOutArcList(adaptor, n2, 1);
1.653 - checkGraphOutArcList(adaptor, n3, 2);
1.654 - checkGraphOutArcList(adaptor, n4, 1);
1.655 -
1.656 - checkGraphInArcList(adaptor, n2, 1);
1.657 - checkGraphInArcList(adaptor, n3, 2);
1.658 - checkGraphInArcList(adaptor, n4, 1);
1.659 -
1.660 - checkGraphIncEdgeList(adaptor, n2, 1);
1.661 - checkGraphIncEdgeList(adaptor, n3, 2);
1.662 - checkGraphIncEdgeList(adaptor, n4, 1);
1.663 -
1.664 - checkNodeIds(adaptor);
1.665 - checkArcIds(adaptor);
1.666 - checkEdgeIds(adaptor);
1.667 -
1.668 - checkGraphNodeMap(adaptor);
1.669 - checkGraphArcMap(adaptor);
1.670 - checkGraphEdgeMap(adaptor);
1.671 -
1.672 - node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
1.673 - edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
1.674 -
1.675 - checkGraphNodeList(adaptor, 0);
1.676 - checkGraphArcList(adaptor, 0);
1.677 - checkGraphEdgeList(adaptor, 0);
1.678 - checkGraphConArcList(adaptor, 0);
1.679 - checkGraphConEdgeList(adaptor, 0);
1.680 -
1.681 - checkNodeIds(adaptor);
1.682 - checkArcIds(adaptor);
1.683 - checkEdgeIds(adaptor);
1.684 -
1.685 - checkGraphNodeMap(adaptor);
1.686 - checkGraphArcMap(adaptor);
1.687 - checkGraphEdgeMap(adaptor);
1.688 -}
1.689 -
1.690 -void checkFilterNodes2() {
1.691 - checkConcept<concepts::Graph,
1.692 - FilterNodes<concepts::Graph,
1.693 - concepts::Graph::NodeMap<bool> > >();
1.694 -
1.695 - typedef ListGraph Graph;
1.696 - typedef Graph::NodeMap<bool> NodeFilter;
1.697 - typedef FilterNodes<Graph, NodeFilter> Adaptor;
1.698 -
1.699 - Graph graph;
1.700 - NodeFilter node_filter(graph);
1.701 - Adaptor adaptor(graph, node_filter);
1.702 -
1.703 - Graph::Node n1 = graph.addNode();
1.704 - Graph::Node n2 = graph.addNode();
1.705 - Graph::Node n3 = graph.addNode();
1.706 - Graph::Node n4 = graph.addNode();
1.707 -
1.708 - Graph::Edge e1 = graph.addEdge(n1, n2);
1.709 - Graph::Edge e2 = graph.addEdge(n1, n3);
1.710 - Graph::Edge e3 = graph.addEdge(n2, n3);
1.711 - Graph::Edge e4 = graph.addEdge(n3, n4);
1.712 -
1.713 - node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
1.714 -
1.715 - checkGraphNodeList(adaptor, 4);
1.716 - checkGraphArcList(adaptor, 8);
1.717 - checkGraphEdgeList(adaptor, 4);
1.718 - checkGraphConArcList(adaptor, 8);
1.719 - checkGraphConEdgeList(adaptor, 4);
1.720 -
1.721 - checkGraphOutArcList(adaptor, n1, 2);
1.722 - checkGraphOutArcList(adaptor, n2, 2);
1.723 - checkGraphOutArcList(adaptor, n3, 3);
1.724 - checkGraphOutArcList(adaptor, n4, 1);
1.725 -
1.726 - checkGraphInArcList(adaptor, n1, 2);
1.727 - checkGraphInArcList(adaptor, n2, 2);
1.728 - checkGraphInArcList(adaptor, n3, 3);
1.729 - checkGraphInArcList(adaptor, n4, 1);
1.730 -
1.731 - checkGraphIncEdgeList(adaptor, n1, 2);
1.732 - checkGraphIncEdgeList(adaptor, n2, 2);
1.733 - checkGraphIncEdgeList(adaptor, n3, 3);
1.734 - checkGraphIncEdgeList(adaptor, n4, 1);
1.735 -
1.736 - checkNodeIds(adaptor);
1.737 - checkArcIds(adaptor);
1.738 - checkEdgeIds(adaptor);
1.739 -
1.740 - checkGraphNodeMap(adaptor);
1.741 - checkGraphArcMap(adaptor);
1.742 - checkGraphEdgeMap(adaptor);
1.743 -
1.744 - node_filter[n1] = false;
1.745 -
1.746 - checkGraphNodeList(adaptor, 3);
1.747 - checkGraphArcList(adaptor, 4);
1.748 - checkGraphEdgeList(adaptor, 2);
1.749 - checkGraphConArcList(adaptor, 4);
1.750 - checkGraphConEdgeList(adaptor, 2);
1.751 -
1.752 - checkGraphOutArcList(adaptor, n2, 1);
1.753 - checkGraphOutArcList(adaptor, n3, 2);
1.754 - checkGraphOutArcList(adaptor, n4, 1);
1.755 -
1.756 - checkGraphInArcList(adaptor, n2, 1);
1.757 - checkGraphInArcList(adaptor, n3, 2);
1.758 - checkGraphInArcList(adaptor, n4, 1);
1.759 -
1.760 - checkGraphIncEdgeList(adaptor, n2, 1);
1.761 - checkGraphIncEdgeList(adaptor, n3, 2);
1.762 - checkGraphIncEdgeList(adaptor, n4, 1);
1.763 -
1.764 - checkNodeIds(adaptor);
1.765 - checkArcIds(adaptor);
1.766 - checkEdgeIds(adaptor);
1.767 -
1.768 - checkGraphNodeMap(adaptor);
1.769 - checkGraphArcMap(adaptor);
1.770 - checkGraphEdgeMap(adaptor);
1.771 -
1.772 - node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
1.773 -
1.774 - checkGraphNodeList(adaptor, 0);
1.775 - checkGraphArcList(adaptor, 0);
1.776 - checkGraphEdgeList(adaptor, 0);
1.777 - checkGraphConArcList(adaptor, 0);
1.778 - checkGraphConEdgeList(adaptor, 0);
1.779 -
1.780 - checkNodeIds(adaptor);
1.781 - checkArcIds(adaptor);
1.782 - checkEdgeIds(adaptor);
1.783 -
1.784 - checkGraphNodeMap(adaptor);
1.785 - checkGraphArcMap(adaptor);
1.786 - checkGraphEdgeMap(adaptor);
1.787 -}
1.788 -
1.789 -void checkFilterEdges() {
1.790 - checkConcept<concepts::Graph,
1.791 - FilterEdges<concepts::Graph,
1.792 - concepts::Graph::EdgeMap<bool> > >();
1.793 -
1.794 - typedef ListGraph Graph;
1.795 - typedef Graph::EdgeMap<bool> EdgeFilter;
1.796 - typedef FilterEdges<Graph, EdgeFilter> Adaptor;
1.797 -
1.798 - Graph graph;
1.799 - EdgeFilter edge_filter(graph);
1.800 - Adaptor adaptor(graph, edge_filter);
1.801 -
1.802 - Graph::Node n1 = graph.addNode();
1.803 - Graph::Node n2 = graph.addNode();
1.804 - Graph::Node n3 = graph.addNode();
1.805 - Graph::Node n4 = graph.addNode();
1.806 -
1.807 - Graph::Edge e1 = graph.addEdge(n1, n2);
1.808 - Graph::Edge e2 = graph.addEdge(n1, n3);
1.809 - Graph::Edge e3 = graph.addEdge(n2, n3);
1.810 - Graph::Edge e4 = graph.addEdge(n3, n4);
1.811 -
1.812 - edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
1.813 -
1.814 - checkGraphNodeList(adaptor, 4);
1.815 - checkGraphArcList(adaptor, 8);
1.816 - checkGraphEdgeList(adaptor, 4);
1.817 - checkGraphConArcList(adaptor, 8);
1.818 - checkGraphConEdgeList(adaptor, 4);
1.819 -
1.820 - checkGraphOutArcList(adaptor, n1, 2);
1.821 - checkGraphOutArcList(adaptor, n2, 2);
1.822 - checkGraphOutArcList(adaptor, n3, 3);
1.823 - checkGraphOutArcList(adaptor, n4, 1);
1.824 -
1.825 - checkGraphInArcList(adaptor, n1, 2);
1.826 - checkGraphInArcList(adaptor, n2, 2);
1.827 - checkGraphInArcList(adaptor, n3, 3);
1.828 - checkGraphInArcList(adaptor, n4, 1);
1.829 -
1.830 - checkGraphIncEdgeList(adaptor, n1, 2);
1.831 - checkGraphIncEdgeList(adaptor, n2, 2);
1.832 - checkGraphIncEdgeList(adaptor, n3, 3);
1.833 - checkGraphIncEdgeList(adaptor, n4, 1);
1.834 -
1.835 - checkNodeIds(adaptor);
1.836 - checkArcIds(adaptor);
1.837 - checkEdgeIds(adaptor);
1.838 -
1.839 - checkGraphNodeMap(adaptor);
1.840 - checkGraphArcMap(adaptor);
1.841 - checkGraphEdgeMap(adaptor);
1.842 -
1.843 - edge_filter[e2] = false;
1.844 -
1.845 - checkGraphNodeList(adaptor, 4);
1.846 - checkGraphArcList(adaptor, 6);
1.847 - checkGraphEdgeList(adaptor, 3);
1.848 - checkGraphConArcList(adaptor, 6);
1.849 - checkGraphConEdgeList(adaptor, 3);
1.850 -
1.851 - checkGraphOutArcList(adaptor, n1, 1);
1.852 - checkGraphOutArcList(adaptor, n2, 2);
1.853 - checkGraphOutArcList(adaptor, n3, 2);
1.854 - checkGraphOutArcList(adaptor, n4, 1);
1.855 -
1.856 - checkGraphInArcList(adaptor, n1, 1);
1.857 - checkGraphInArcList(adaptor, n2, 2);
1.858 - checkGraphInArcList(adaptor, n3, 2);
1.859 - checkGraphInArcList(adaptor, n4, 1);
1.860 -
1.861 - checkGraphIncEdgeList(adaptor, n1, 1);
1.862 - checkGraphIncEdgeList(adaptor, n2, 2);
1.863 - checkGraphIncEdgeList(adaptor, n3, 2);
1.864 - checkGraphIncEdgeList(adaptor, n4, 1);
1.865 -
1.866 - checkNodeIds(adaptor);
1.867 - checkArcIds(adaptor);
1.868 - checkEdgeIds(adaptor);
1.869 -
1.870 - checkGraphNodeMap(adaptor);
1.871 - checkGraphArcMap(adaptor);
1.872 - checkGraphEdgeMap(adaptor);
1.873 -
1.874 - edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
1.875 -
1.876 - checkGraphNodeList(adaptor, 4);
1.877 - checkGraphArcList(adaptor, 0);
1.878 - checkGraphEdgeList(adaptor, 0);
1.879 - checkGraphConArcList(adaptor, 0);
1.880 - checkGraphConEdgeList(adaptor, 0);
1.881 -
1.882 - checkNodeIds(adaptor);
1.883 - checkArcIds(adaptor);
1.884 - checkEdgeIds(adaptor);
1.885 -
1.886 - checkGraphNodeMap(adaptor);
1.887 - checkGraphArcMap(adaptor);
1.888 - checkGraphEdgeMap(adaptor);
1.889 -}
1.890 -
1.891 -void checkOrienter() {
1.892 - checkConcept<concepts::Digraph,
1.893 - Orienter<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
1.894 -
1.895 - typedef ListGraph Graph;
1.896 - typedef ListGraph::EdgeMap<bool> DirMap;
1.897 - typedef Orienter<Graph> Adaptor;
1.898 -
1.899 - Graph graph;
1.900 - DirMap dir(graph, true);
1.901 - Adaptor adaptor(graph, dir);
1.902 -
1.903 - Graph::Node n1 = graph.addNode();
1.904 - Graph::Node n2 = graph.addNode();
1.905 - Graph::Node n3 = graph.addNode();
1.906 -
1.907 - Graph::Edge e1 = graph.addEdge(n1, n2);
1.908 - Graph::Edge e2 = graph.addEdge(n1, n3);
1.909 - Graph::Edge e3 = graph.addEdge(n2, n3);
1.910 -
1.911 - checkGraphNodeList(adaptor, 3);
1.912 - checkGraphArcList(adaptor, 3);
1.913 - checkGraphConArcList(adaptor, 3);
1.914 -
1.915 - {
1.916 - dir[e1] = true;
1.917 - Adaptor::Node u = adaptor.source(e1);
1.918 - Adaptor::Node v = adaptor.target(e1);
1.919 -
1.920 - dir[e1] = false;
1.921 - check (u == adaptor.target(e1), "Wrong dir");
1.922 - check (v == adaptor.source(e1), "Wrong dir");
1.923 -
1.924 - check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");
1.925 - dir[e1] = n1 == u;
1.926 - }
1.927 -
1.928 - {
1.929 - dir[e2] = true;
1.930 - Adaptor::Node u = adaptor.source(e2);
1.931 - Adaptor::Node v = adaptor.target(e2);
1.932 -
1.933 - dir[e2] = false;
1.934 - check (u == adaptor.target(e2), "Wrong dir");
1.935 - check (v == adaptor.source(e2), "Wrong dir");
1.936 -
1.937 - check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");
1.938 - dir[e2] = n3 == u;
1.939 - }
1.940 -
1.941 - {
1.942 - dir[e3] = true;
1.943 - Adaptor::Node u = adaptor.source(e3);
1.944 - Adaptor::Node v = adaptor.target(e3);
1.945 -
1.946 - dir[e3] = false;
1.947 - check (u == adaptor.target(e3), "Wrong dir");
1.948 - check (v == adaptor.source(e3), "Wrong dir");
1.949 -
1.950 - check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
1.951 - dir[e3] = n2 == u;
1.952 - }
1.953 -
1.954 - checkGraphOutArcList(adaptor, n1, 1);
1.955 - checkGraphOutArcList(adaptor, n2, 1);
1.956 - checkGraphOutArcList(adaptor, n3, 1);
1.957 -
1.958 - checkGraphInArcList(adaptor, n1, 1);
1.959 - checkGraphInArcList(adaptor, n2, 1);
1.960 - checkGraphInArcList(adaptor, n3, 1);
1.961 -
1.962 - checkNodeIds(adaptor);
1.963 - checkArcIds(adaptor);
1.964 -
1.965 - checkGraphNodeMap(adaptor);
1.966 - checkGraphArcMap(adaptor);
1.967 -
1.968 -}
1.969 -
1.970 -
1.971 -int main(int, const char **) {
1.972 -
1.973 - checkReverseDigraph();
1.974 - checkSubDigraph();
1.975 - checkFilterNodes1();
1.976 - checkFilterArcs();
1.977 - checkUndirector();
1.978 - checkResidual();
1.979 - checkSplitNodes();
1.980 -
1.981 - checkSubGraph();
1.982 - checkFilterNodes2();
1.983 - checkFilterEdges();
1.984 - checkOrienter();
1.985 -
1.986 - return 0;
1.987 -}