1.1 --- a/lemon/adaptors.h Mon Jan 12 12:26:02 2009 +0000
1.2 +++ b/lemon/adaptors.h Mon Jan 12 13:18:03 2009 +0000
1.3 @@ -2666,10 +2666,10 @@
1.4 /// \brief Adaptor class for composing the residual digraph for directed
1.5 /// flow and circulation problems.
1.6 ///
1.7 - /// Residual can be used for composing the \e residual digraph for directed
1.8 - /// flow and circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
1.9 - /// and let \f$ F \f$ be a number type. Let \f$ flow, cap: A\to F \f$ be
1.10 - /// functions on the arcs.
1.11 + /// ResidualDigraph can be used for composing the \e residual digraph
1.12 + /// for directed flow and circulation problems. Let \f$ G=(V, A) \f$
1.13 + /// be a directed graph and let \f$ F \f$ be a number type.
1.14 + /// Let \f$ flow, cap: A\to F \f$ be functions on the arcs.
1.15 /// This adaptor implements a digraph structure with node set \f$ V \f$
1.16 /// and arc set \f$ A_{forward}\cup A_{backward} \f$,
1.17 /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and
1.18 @@ -2704,13 +2704,13 @@
1.19 /// is convertible to the \c Arc type of the adapted digraph.
1.20 #ifdef DOXYGEN
1.21 template<typename GR, typename CM, typename FM, typename TL>
1.22 - class Residual
1.23 + class ResidualDigraph
1.24 #else
1.25 template<typename GR,
1.26 typename CM = typename GR::template ArcMap<int>,
1.27 typename FM = CM,
1.28 typename TL = Tolerance<typename CM::Value> >
1.29 - class Residual :
1.30 + class ResidualDigraph :
1.31 public FilterArcs<
1.32 Undirector<const GR>,
1.33 typename Undirector<const GR>::template CombinedArcMap<
1.34 @@ -2730,7 +2730,7 @@
1.35 typedef TL Tolerance;
1.36
1.37 typedef typename CapacityMap::Value Value;
1.38 - typedef Residual Adaptor;
1.39 + typedef ResidualDigraph Adaptor;
1.40
1.41 protected:
1.42
1.43 @@ -2761,8 +2761,8 @@
1.44 ///
1.45 /// Constructor of the residual digraph adaptor. The parameters are the
1.46 /// digraph, the capacity map, the flow map, and a tolerance object.
1.47 - Residual(const Digraph& digraph, const CapacityMap& capacity,
1.48 - FlowMap& flow, const Tolerance& tolerance = Tolerance())
1.49 + ResidualDigraph(const Digraph& digraph, const CapacityMap& capacity,
1.50 + FlowMap& flow, const Tolerance& tolerance = Tolerance())
1.51 : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph),
1.52 _forward_filter(capacity, flow, tolerance),
1.53 _backward_filter(capacity, flow, tolerance),
1.54 @@ -2869,10 +2869,9 @@
1.55 /// \ingroup graph_adaptors
1.56 /// \relates Residual
1.57 template<typename GR, typename CM, typename FM>
1.58 - Residual<GR, CM, FM> residual(const GR& digraph,
1.59 - const CM& capacity_map,
1.60 - FM& flow_map) {
1.61 - return Residual<GR, CM, FM> (digraph, capacity_map, flow_map);
1.62 + ResidualDigraph<GR, CM, FM>
1.63 + residualDigraph(const GR& digraph, const CM& capacity_map, FM& flow_map) {
1.64 + return ResidualDigraph<GR, CM, FM> (digraph, capacity_map, flow_map);
1.65 }
1.66
1.67
2.1 --- a/test/CMakeLists.txt Mon Jan 12 12:26:02 2009 +0000
2.2 +++ b/test/CMakeLists.txt Mon Jan 12 13:18:03 2009 +0000
2.3 @@ -3,6 +3,7 @@
2.4 LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
2.5
2.6 SET(TESTS
2.7 + adaptors_test
2.8 bfs_test
2.9 circulation_test
2.10 counter_test
2.11 @@ -11,7 +12,6 @@
2.12 dijkstra_test
2.13 dim_test
2.14 error_test
2.15 - graph_adaptor_test
2.16 graph_copy_test
2.17 graph_test
2.18 graph_utils_test
3.1 --- a/test/Makefile.am Mon Jan 12 12:26:02 2009 +0000
3.2 +++ b/test/Makefile.am Mon Jan 12 13:18:03 2009 +0000
3.3 @@ -6,6 +6,7 @@
3.4 test/test_tools.h
3.5
3.6 check_PROGRAMS += \
3.7 + test/adaptors_test \
3.8 test/bfs_test \
3.9 test/circulation_test \
3.10 test/counter_test \
3.11 @@ -14,7 +15,6 @@
3.12 test/dijkstra_test \
3.13 test/dim_test \
3.14 test/error_test \
3.15 - test/graph_adaptor_test \
3.16 test/graph_copy_test \
3.17 test/graph_test \
3.18 test/graph_utils_test \
3.19 @@ -43,6 +43,7 @@
3.20 TESTS += $(check_PROGRAMS)
3.21 XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
3.22
3.23 +test_adaptors_test_SOURCES = test/adaptors_test.cc
3.24 test_bfs_test_SOURCES = test/bfs_test.cc
3.25 test_circulation_test_SOURCES = test/circulation_test.cc
3.26 test_counter_test_SOURCES = test/counter_test.cc
3.27 @@ -51,7 +52,6 @@
3.28 test_dijkstra_test_SOURCES = test/dijkstra_test.cc
3.29 test_dim_test_SOURCES = test/dim_test.cc
3.30 test_error_test_SOURCES = test/error_test.cc
3.31 -test_graph_adaptor_test_SOURCES = test/graph_adaptor_test.cc
3.32 test_graph_copy_test_SOURCES = test/graph_copy_test.cc
3.33 test_graph_test_SOURCES = test/graph_test.cc
3.34 test_graph_utils_test_SOURCES = test/graph_utils_test.cc
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/test/adaptors_test.cc Mon Jan 12 13:18:03 2009 +0000
4.3 @@ -0,0 +1,1486 @@
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 +}
5.1 --- a/test/graph_adaptor_test.cc Mon Jan 12 12:26:02 2009 +0000
5.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
5.3 @@ -1,984 +0,0 @@
5.4 -/* -*- mode: C++; indent-tabs-mode: nil; -*-
5.5 - *
5.6 - * This file is a part of LEMON, a generic C++ optimization library.
5.7 - *
5.8 - * Copyright (C) 2003-2009
5.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
5.11 - *
5.12 - * Permission to use, modify and distribute this software is granted
5.13 - * provided that this copyright notice appears in all copies. For
5.14 - * precise terms see the accompanying LICENSE file.
5.15 - *
5.16 - * This software is provided "AS IS" with no warranty of any kind,
5.17 - * express or implied, and with no claim as to its suitability for any
5.18 - * purpose.
5.19 - *
5.20 - */
5.21 -
5.22 -#include<iostream>
5.23 -#include<lemon/concept_check.h>
5.24 -
5.25 -#include<lemon/list_graph.h>
5.26 -#include<lemon/smart_graph.h>
5.27 -
5.28 -#include<lemon/concepts/digraph.h>
5.29 -#include<lemon/concepts/graph.h>
5.30 -
5.31 -#include<lemon/adaptors.h>
5.32 -
5.33 -#include <limits>
5.34 -#include <lemon/bfs.h>
5.35 -#include <lemon/path.h>
5.36 -
5.37 -#include"test/test_tools.h"
5.38 -#include"test/graph_test.h"
5.39 -
5.40 -using namespace lemon;
5.41 -
5.42 -void checkReverseDigraph() {
5.43 - checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
5.44 -
5.45 - typedef ListDigraph Digraph;
5.46 - typedef ReverseDigraph<Digraph> Adaptor;
5.47 -
5.48 - Digraph digraph;
5.49 - Adaptor adaptor(digraph);
5.50 -
5.51 - Digraph::Node n1 = digraph.addNode();
5.52 - Digraph::Node n2 = digraph.addNode();
5.53 - Digraph::Node n3 = digraph.addNode();
5.54 -
5.55 - Digraph::Arc a1 = digraph.addArc(n1, n2);
5.56 - Digraph::Arc a2 = digraph.addArc(n1, n3);
5.57 - Digraph::Arc a3 = digraph.addArc(n2, n3);
5.58 -
5.59 - checkGraphNodeList(adaptor, 3);
5.60 - checkGraphArcList(adaptor, 3);
5.61 - checkGraphConArcList(adaptor, 3);
5.62 -
5.63 - checkGraphOutArcList(adaptor, n1, 0);
5.64 - checkGraphOutArcList(adaptor, n2, 1);
5.65 - checkGraphOutArcList(adaptor, n3, 2);
5.66 -
5.67 - checkGraphInArcList(adaptor, n1, 2);
5.68 - checkGraphInArcList(adaptor, n2, 1);
5.69 - checkGraphInArcList(adaptor, n3, 0);
5.70 -
5.71 - checkNodeIds(adaptor);
5.72 - checkArcIds(adaptor);
5.73 -
5.74 - checkGraphNodeMap(adaptor);
5.75 - checkGraphArcMap(adaptor);
5.76 -
5.77 - for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
5.78 - check(adaptor.source(a) == digraph.target(a), "Wrong reverse");
5.79 - check(adaptor.target(a) == digraph.source(a), "Wrong reverse");
5.80 - }
5.81 -}
5.82 -
5.83 -void checkSubDigraph() {
5.84 - checkConcept<concepts::Digraph,
5.85 - SubDigraph<concepts::Digraph,
5.86 - concepts::Digraph::NodeMap<bool>,
5.87 - concepts::Digraph::ArcMap<bool> > >();
5.88 -
5.89 - typedef ListDigraph Digraph;
5.90 - typedef Digraph::NodeMap<bool> NodeFilter;
5.91 - typedef Digraph::ArcMap<bool> ArcFilter;
5.92 - typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
5.93 -
5.94 - Digraph digraph;
5.95 - NodeFilter node_filter(digraph);
5.96 - ArcFilter arc_filter(digraph);
5.97 - Adaptor adaptor(digraph, node_filter, arc_filter);
5.98 -
5.99 - Digraph::Node n1 = digraph.addNode();
5.100 - Digraph::Node n2 = digraph.addNode();
5.101 - Digraph::Node n3 = digraph.addNode();
5.102 -
5.103 - Digraph::Arc a1 = digraph.addArc(n1, n2);
5.104 - Digraph::Arc a2 = digraph.addArc(n1, n3);
5.105 - Digraph::Arc a3 = digraph.addArc(n2, n3);
5.106 -
5.107 - node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
5.108 - arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
5.109 -
5.110 - checkGraphNodeList(adaptor, 3);
5.111 - checkGraphArcList(adaptor, 3);
5.112 - checkGraphConArcList(adaptor, 3);
5.113 -
5.114 - checkGraphOutArcList(adaptor, n1, 2);
5.115 - checkGraphOutArcList(adaptor, n2, 1);
5.116 - checkGraphOutArcList(adaptor, n3, 0);
5.117 -
5.118 - checkGraphInArcList(adaptor, n1, 0);
5.119 - checkGraphInArcList(adaptor, n2, 1);
5.120 - checkGraphInArcList(adaptor, n3, 2);
5.121 -
5.122 - checkNodeIds(adaptor);
5.123 - checkArcIds(adaptor);
5.124 -
5.125 - checkGraphNodeMap(adaptor);
5.126 - checkGraphArcMap(adaptor);
5.127 -
5.128 - arc_filter[a2] = false;
5.129 -
5.130 - checkGraphNodeList(adaptor, 3);
5.131 - checkGraphArcList(adaptor, 2);
5.132 - checkGraphConArcList(adaptor, 2);
5.133 -
5.134 - checkGraphOutArcList(adaptor, n1, 1);
5.135 - checkGraphOutArcList(adaptor, n2, 1);
5.136 - checkGraphOutArcList(adaptor, n3, 0);
5.137 -
5.138 - checkGraphInArcList(adaptor, n1, 0);
5.139 - checkGraphInArcList(adaptor, n2, 1);
5.140 - checkGraphInArcList(adaptor, n3, 1);
5.141 -
5.142 - checkNodeIds(adaptor);
5.143 - checkArcIds(adaptor);
5.144 -
5.145 - checkGraphNodeMap(adaptor);
5.146 - checkGraphArcMap(adaptor);
5.147 -
5.148 - node_filter[n1] = false;
5.149 -
5.150 - checkGraphNodeList(adaptor, 2);
5.151 - checkGraphArcList(adaptor, 1);
5.152 - checkGraphConArcList(adaptor, 1);
5.153 -
5.154 - checkGraphOutArcList(adaptor, n2, 1);
5.155 - checkGraphOutArcList(adaptor, n3, 0);
5.156 -
5.157 - checkGraphInArcList(adaptor, n2, 0);
5.158 - checkGraphInArcList(adaptor, n3, 1);
5.159 -
5.160 - checkNodeIds(adaptor);
5.161 - checkArcIds(adaptor);
5.162 -
5.163 - checkGraphNodeMap(adaptor);
5.164 - checkGraphArcMap(adaptor);
5.165 -
5.166 - node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
5.167 - arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
5.168 -
5.169 - checkGraphNodeList(adaptor, 0);
5.170 - checkGraphArcList(adaptor, 0);
5.171 - checkGraphConArcList(adaptor, 0);
5.172 -
5.173 - checkNodeIds(adaptor);
5.174 - checkArcIds(adaptor);
5.175 -
5.176 - checkGraphNodeMap(adaptor);
5.177 - checkGraphArcMap(adaptor);
5.178 -}
5.179 -
5.180 -void checkFilterNodes1() {
5.181 - checkConcept<concepts::Digraph,
5.182 - FilterNodes<concepts::Digraph,
5.183 - concepts::Digraph::NodeMap<bool> > >();
5.184 -
5.185 - typedef ListDigraph Digraph;
5.186 - typedef Digraph::NodeMap<bool> NodeFilter;
5.187 - typedef FilterNodes<Digraph, NodeFilter> Adaptor;
5.188 -
5.189 - Digraph digraph;
5.190 - NodeFilter node_filter(digraph);
5.191 - Adaptor adaptor(digraph, node_filter);
5.192 -
5.193 - Digraph::Node n1 = digraph.addNode();
5.194 - Digraph::Node n2 = digraph.addNode();
5.195 - Digraph::Node n3 = digraph.addNode();
5.196 -
5.197 - Digraph::Arc a1 = digraph.addArc(n1, n2);
5.198 - Digraph::Arc a2 = digraph.addArc(n1, n3);
5.199 - Digraph::Arc a3 = digraph.addArc(n2, n3);
5.200 -
5.201 - node_filter[n1] = node_filter[n2] = node_filter[n3] = true;
5.202 -
5.203 - checkGraphNodeList(adaptor, 3);
5.204 - checkGraphArcList(adaptor, 3);
5.205 - checkGraphConArcList(adaptor, 3);
5.206 -
5.207 - checkGraphOutArcList(adaptor, n1, 2);
5.208 - checkGraphOutArcList(adaptor, n2, 1);
5.209 - checkGraphOutArcList(adaptor, n3, 0);
5.210 -
5.211 - checkGraphInArcList(adaptor, n1, 0);
5.212 - checkGraphInArcList(adaptor, n2, 1);
5.213 - checkGraphInArcList(adaptor, n3, 2);
5.214 -
5.215 - checkNodeIds(adaptor);
5.216 - checkArcIds(adaptor);
5.217 -
5.218 - checkGraphNodeMap(adaptor);
5.219 - checkGraphArcMap(adaptor);
5.220 -
5.221 - node_filter[n1] = false;
5.222 -
5.223 - checkGraphNodeList(adaptor, 2);
5.224 - checkGraphArcList(adaptor, 1);
5.225 - checkGraphConArcList(adaptor, 1);
5.226 -
5.227 - checkGraphOutArcList(adaptor, n2, 1);
5.228 - checkGraphOutArcList(adaptor, n3, 0);
5.229 -
5.230 - checkGraphInArcList(adaptor, n2, 0);
5.231 - checkGraphInArcList(adaptor, n3, 1);
5.232 -
5.233 - checkNodeIds(adaptor);
5.234 - checkArcIds(adaptor);
5.235 -
5.236 - checkGraphNodeMap(adaptor);
5.237 - checkGraphArcMap(adaptor);
5.238 -
5.239 - node_filter[n1] = node_filter[n2] = node_filter[n3] = false;
5.240 -
5.241 - checkGraphNodeList(adaptor, 0);
5.242 - checkGraphArcList(adaptor, 0);
5.243 - checkGraphConArcList(adaptor, 0);
5.244 -
5.245 - checkNodeIds(adaptor);
5.246 - checkArcIds(adaptor);
5.247 -
5.248 - checkGraphNodeMap(adaptor);
5.249 - checkGraphArcMap(adaptor);
5.250 -}
5.251 -
5.252 -void checkFilterArcs() {
5.253 - checkConcept<concepts::Digraph,
5.254 - FilterArcs<concepts::Digraph,
5.255 - concepts::Digraph::ArcMap<bool> > >();
5.256 -
5.257 - typedef ListDigraph Digraph;
5.258 - typedef Digraph::ArcMap<bool> ArcFilter;
5.259 - typedef FilterArcs<Digraph, ArcFilter> Adaptor;
5.260 -
5.261 - Digraph digraph;
5.262 - ArcFilter arc_filter(digraph);
5.263 - Adaptor adaptor(digraph, arc_filter);
5.264 -
5.265 - Digraph::Node n1 = digraph.addNode();
5.266 - Digraph::Node n2 = digraph.addNode();
5.267 - Digraph::Node n3 = digraph.addNode();
5.268 -
5.269 - Digraph::Arc a1 = digraph.addArc(n1, n2);
5.270 - Digraph::Arc a2 = digraph.addArc(n1, n3);
5.271 - Digraph::Arc a3 = digraph.addArc(n2, n3);
5.272 -
5.273 - arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;
5.274 -
5.275 - checkGraphNodeList(adaptor, 3);
5.276 - checkGraphArcList(adaptor, 3);
5.277 - checkGraphConArcList(adaptor, 3);
5.278 -
5.279 - checkGraphOutArcList(adaptor, n1, 2);
5.280 - checkGraphOutArcList(adaptor, n2, 1);
5.281 - checkGraphOutArcList(adaptor, n3, 0);
5.282 -
5.283 - checkGraphInArcList(adaptor, n1, 0);
5.284 - checkGraphInArcList(adaptor, n2, 1);
5.285 - checkGraphInArcList(adaptor, n3, 2);
5.286 -
5.287 - checkNodeIds(adaptor);
5.288 - checkArcIds(adaptor);
5.289 -
5.290 - checkGraphNodeMap(adaptor);
5.291 - checkGraphArcMap(adaptor);
5.292 -
5.293 - arc_filter[a2] = false;
5.294 -
5.295 - checkGraphNodeList(adaptor, 3);
5.296 - checkGraphArcList(adaptor, 2);
5.297 - checkGraphConArcList(adaptor, 2);
5.298 -
5.299 - checkGraphOutArcList(adaptor, n1, 1);
5.300 - checkGraphOutArcList(adaptor, n2, 1);
5.301 - checkGraphOutArcList(adaptor, n3, 0);
5.302 -
5.303 - checkGraphInArcList(adaptor, n1, 0);
5.304 - checkGraphInArcList(adaptor, n2, 1);
5.305 - checkGraphInArcList(adaptor, n3, 1);
5.306 -
5.307 - checkNodeIds(adaptor);
5.308 - checkArcIds(adaptor);
5.309 -
5.310 - checkGraphNodeMap(adaptor);
5.311 - checkGraphArcMap(adaptor);
5.312 -
5.313 - arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;
5.314 -
5.315 - checkGraphNodeList(adaptor, 3);
5.316 - checkGraphArcList(adaptor, 0);
5.317 - checkGraphConArcList(adaptor, 0);
5.318 -
5.319 - checkNodeIds(adaptor);
5.320 - checkArcIds(adaptor);
5.321 -
5.322 - checkGraphNodeMap(adaptor);
5.323 - checkGraphArcMap(adaptor);
5.324 -}
5.325 -
5.326 -void checkUndirector() {
5.327 - checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
5.328 -
5.329 - typedef ListDigraph Digraph;
5.330 - typedef Undirector<Digraph> Adaptor;
5.331 -
5.332 - Digraph digraph;
5.333 - Adaptor adaptor(digraph);
5.334 -
5.335 - Digraph::Node n1 = digraph.addNode();
5.336 - Digraph::Node n2 = digraph.addNode();
5.337 - Digraph::Node n3 = digraph.addNode();
5.338 -
5.339 - Digraph::Arc a1 = digraph.addArc(n1, n2);
5.340 - Digraph::Arc a2 = digraph.addArc(n1, n3);
5.341 - Digraph::Arc a3 = digraph.addArc(n2, n3);
5.342 -
5.343 - checkGraphNodeList(adaptor, 3);
5.344 - checkGraphArcList(adaptor, 6);
5.345 - checkGraphEdgeList(adaptor, 3);
5.346 - checkGraphConArcList(adaptor, 6);
5.347 - checkGraphConEdgeList(adaptor, 3);
5.348 -
5.349 - checkGraphOutArcList(adaptor, n1, 2);
5.350 - checkGraphOutArcList(adaptor, n2, 2);
5.351 - checkGraphOutArcList(adaptor, n3, 2);
5.352 -
5.353 - checkGraphInArcList(adaptor, n1, 2);
5.354 - checkGraphInArcList(adaptor, n2, 2);
5.355 - checkGraphInArcList(adaptor, n3, 2);
5.356 -
5.357 - checkGraphIncEdgeList(adaptor, n1, 2);
5.358 - checkGraphIncEdgeList(adaptor, n2, 2);
5.359 - checkGraphIncEdgeList(adaptor, n3, 2);
5.360 -
5.361 - checkNodeIds(adaptor);
5.362 - checkArcIds(adaptor);
5.363 - checkEdgeIds(adaptor);
5.364 -
5.365 - checkGraphNodeMap(adaptor);
5.366 - checkGraphArcMap(adaptor);
5.367 - checkGraphEdgeMap(adaptor);
5.368 -
5.369 - for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {
5.370 - check(adaptor.u(e) == digraph.source(e), "Wrong undir");
5.371 - check(adaptor.v(e) == digraph.target(e), "Wrong undir");
5.372 - }
5.373 -
5.374 -}
5.375 -
5.376 -void checkResidual() {
5.377 - checkConcept<concepts::Digraph,
5.378 - Residual<concepts::Digraph,
5.379 - concepts::Digraph::ArcMap<int>,
5.380 - concepts::Digraph::ArcMap<int> > >();
5.381 -
5.382 - typedef ListDigraph Digraph;
5.383 - typedef Digraph::ArcMap<int> IntArcMap;
5.384 - typedef Residual<Digraph, IntArcMap> Adaptor;
5.385 -
5.386 - Digraph digraph;
5.387 - IntArcMap capacity(digraph), flow(digraph);
5.388 - Adaptor adaptor(digraph, capacity, flow);
5.389 -
5.390 - Digraph::Node n1 = digraph.addNode();
5.391 - Digraph::Node n2 = digraph.addNode();
5.392 - Digraph::Node n3 = digraph.addNode();
5.393 - Digraph::Node n4 = digraph.addNode();
5.394 -
5.395 - Digraph::Arc a1 = digraph.addArc(n1, n2);
5.396 - Digraph::Arc a2 = digraph.addArc(n1, n3);
5.397 - Digraph::Arc a3 = digraph.addArc(n1, n4);
5.398 - Digraph::Arc a4 = digraph.addArc(n2, n3);
5.399 - Digraph::Arc a5 = digraph.addArc(n2, n4);
5.400 - Digraph::Arc a6 = digraph.addArc(n3, n4);
5.401 -
5.402 - capacity[a1] = 8;
5.403 - capacity[a2] = 6;
5.404 - capacity[a3] = 4;
5.405 - capacity[a4] = 4;
5.406 - capacity[a5] = 6;
5.407 - capacity[a6] = 10;
5.408 -
5.409 - for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
5.410 - flow[a] = 0;
5.411 - }
5.412 -
5.413 - checkGraphNodeList(adaptor, 4);
5.414 - checkGraphArcList(adaptor, 6);
5.415 - checkGraphConArcList(adaptor, 6);
5.416 -
5.417 - checkGraphOutArcList(adaptor, n1, 3);
5.418 - checkGraphOutArcList(adaptor, n2, 2);
5.419 - checkGraphOutArcList(adaptor, n3, 1);
5.420 - checkGraphOutArcList(adaptor, n4, 0);
5.421 -
5.422 - checkGraphInArcList(adaptor, n1, 0);
5.423 - checkGraphInArcList(adaptor, n2, 1);
5.424 - checkGraphInArcList(adaptor, n3, 2);
5.425 - checkGraphInArcList(adaptor, n4, 3);
5.426 -
5.427 - for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
5.428 - flow[a] = capacity[a] / 2;
5.429 - }
5.430 -
5.431 - checkGraphNodeList(adaptor, 4);
5.432 - checkGraphArcList(adaptor, 12);
5.433 - checkGraphConArcList(adaptor, 12);
5.434 -
5.435 - checkGraphOutArcList(adaptor, n1, 3);
5.436 - checkGraphOutArcList(adaptor, n2, 3);
5.437 - checkGraphOutArcList(adaptor, n3, 3);
5.438 - checkGraphOutArcList(adaptor, n4, 3);
5.439 -
5.440 - checkGraphInArcList(adaptor, n1, 3);
5.441 - checkGraphInArcList(adaptor, n2, 3);
5.442 - checkGraphInArcList(adaptor, n3, 3);
5.443 - checkGraphInArcList(adaptor, n4, 3);
5.444 -
5.445 - checkNodeIds(adaptor);
5.446 - checkArcIds(adaptor);
5.447 -
5.448 - checkGraphNodeMap(adaptor);
5.449 - checkGraphArcMap(adaptor);
5.450 -
5.451 - for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
5.452 - flow[a] = capacity[a];
5.453 - }
5.454 -
5.455 - checkGraphNodeList(adaptor, 4);
5.456 - checkGraphArcList(adaptor, 6);
5.457 - checkGraphConArcList(adaptor, 6);
5.458 -
5.459 - checkGraphOutArcList(adaptor, n1, 0);
5.460 - checkGraphOutArcList(adaptor, n2, 1);
5.461 - checkGraphOutArcList(adaptor, n3, 2);
5.462 - checkGraphOutArcList(adaptor, n4, 3);
5.463 -
5.464 - checkGraphInArcList(adaptor, n1, 3);
5.465 - checkGraphInArcList(adaptor, n2, 2);
5.466 - checkGraphInArcList(adaptor, n3, 1);
5.467 - checkGraphInArcList(adaptor, n4, 0);
5.468 -
5.469 - for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
5.470 - flow[a] = 0;
5.471 - }
5.472 -
5.473 - int flow_value = 0;
5.474 - while (true) {
5.475 -
5.476 - Bfs<Adaptor> bfs(adaptor);
5.477 - bfs.run(n1, n4);
5.478 -
5.479 - if (!bfs.reached(n4)) break;
5.480 -
5.481 - Path<Adaptor> p = bfs.path(n4);
5.482 -
5.483 - int min = std::numeric_limits<int>::max();
5.484 - for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
5.485 - if (adaptor.residualCapacity(a) < min)
5.486 - min = adaptor.residualCapacity(a);
5.487 - }
5.488 -
5.489 - for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {
5.490 - adaptor.augment(a, min);
5.491 - }
5.492 - flow_value += min;
5.493 - }
5.494 -
5.495 - check(flow_value == 18, "Wrong flow with res graph adaptor");
5.496 -
5.497 -}
5.498 -
5.499 -void checkSplitNodes() {
5.500 - checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
5.501 -
5.502 - typedef ListDigraph Digraph;
5.503 - typedef SplitNodes<Digraph> Adaptor;
5.504 -
5.505 - Digraph digraph;
5.506 - Adaptor adaptor(digraph);
5.507 -
5.508 - Digraph::Node n1 = digraph.addNode();
5.509 - Digraph::Node n2 = digraph.addNode();
5.510 - Digraph::Node n3 = digraph.addNode();
5.511 -
5.512 - Digraph::Arc a1 = digraph.addArc(n1, n2);
5.513 - Digraph::Arc a2 = digraph.addArc(n1, n3);
5.514 - Digraph::Arc a3 = digraph.addArc(n2, n3);
5.515 -
5.516 - checkGraphNodeList(adaptor, 6);
5.517 - checkGraphArcList(adaptor, 6);
5.518 - checkGraphConArcList(adaptor, 6);
5.519 -
5.520 - checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
5.521 - checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2);
5.522 - checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
5.523 - checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1);
5.524 - checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
5.525 - checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0);
5.526 -
5.527 - checkGraphInArcList(adaptor, adaptor.inNode(n1), 0);
5.528 - checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
5.529 - checkGraphInArcList(adaptor, adaptor.inNode(n2), 1);
5.530 - checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
5.531 - checkGraphInArcList(adaptor, adaptor.inNode(n3), 2);
5.532 - checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
5.533 -
5.534 - checkNodeIds(adaptor);
5.535 - checkArcIds(adaptor);
5.536 -
5.537 - checkGraphNodeMap(adaptor);
5.538 - checkGraphArcMap(adaptor);
5.539 -
5.540 - for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {
5.541 - if (adaptor.origArc(a)) {
5.542 - Digraph::Arc oa = a;
5.543 - check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),
5.544 - "Wrong split");
5.545 - check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),
5.546 - "Wrong split");
5.547 - } else {
5.548 - Digraph::Node on = a;
5.549 - check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");
5.550 - check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");
5.551 - }
5.552 - }
5.553 -}
5.554 -
5.555 -void checkSubGraph() {
5.556 - checkConcept<concepts::Graph,
5.557 - SubGraph<concepts::Graph,
5.558 - concepts::Graph::NodeMap<bool>,
5.559 - concepts::Graph::EdgeMap<bool> > >();
5.560 -
5.561 - typedef ListGraph Graph;
5.562 - typedef Graph::NodeMap<bool> NodeFilter;
5.563 - typedef Graph::EdgeMap<bool> EdgeFilter;
5.564 - typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;
5.565 -
5.566 - Graph graph;
5.567 - NodeFilter node_filter(graph);
5.568 - EdgeFilter edge_filter(graph);
5.569 - Adaptor adaptor(graph, node_filter, edge_filter);
5.570 -
5.571 - Graph::Node n1 = graph.addNode();
5.572 - Graph::Node n2 = graph.addNode();
5.573 - Graph::Node n3 = graph.addNode();
5.574 - Graph::Node n4 = graph.addNode();
5.575 -
5.576 - Graph::Edge e1 = graph.addEdge(n1, n2);
5.577 - Graph::Edge e2 = graph.addEdge(n1, n3);
5.578 - Graph::Edge e3 = graph.addEdge(n2, n3);
5.579 - Graph::Edge e4 = graph.addEdge(n3, n4);
5.580 -
5.581 - node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
5.582 - edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
5.583 -
5.584 - checkGraphNodeList(adaptor, 4);
5.585 - checkGraphArcList(adaptor, 8);
5.586 - checkGraphEdgeList(adaptor, 4);
5.587 - checkGraphConArcList(adaptor, 8);
5.588 - checkGraphConEdgeList(adaptor, 4);
5.589 -
5.590 - checkGraphOutArcList(adaptor, n1, 2);
5.591 - checkGraphOutArcList(adaptor, n2, 2);
5.592 - checkGraphOutArcList(adaptor, n3, 3);
5.593 - checkGraphOutArcList(adaptor, n4, 1);
5.594 -
5.595 - checkGraphInArcList(adaptor, n1, 2);
5.596 - checkGraphInArcList(adaptor, n2, 2);
5.597 - checkGraphInArcList(adaptor, n3, 3);
5.598 - checkGraphInArcList(adaptor, n4, 1);
5.599 -
5.600 - checkGraphIncEdgeList(adaptor, n1, 2);
5.601 - checkGraphIncEdgeList(adaptor, n2, 2);
5.602 - checkGraphIncEdgeList(adaptor, n3, 3);
5.603 - checkGraphIncEdgeList(adaptor, n4, 1);
5.604 -
5.605 - checkNodeIds(adaptor);
5.606 - checkArcIds(adaptor);
5.607 - checkEdgeIds(adaptor);
5.608 -
5.609 - checkGraphNodeMap(adaptor);
5.610 - checkGraphArcMap(adaptor);
5.611 - checkGraphEdgeMap(adaptor);
5.612 -
5.613 - edge_filter[e2] = false;
5.614 -
5.615 - checkGraphNodeList(adaptor, 4);
5.616 - checkGraphArcList(adaptor, 6);
5.617 - checkGraphEdgeList(adaptor, 3);
5.618 - checkGraphConArcList(adaptor, 6);
5.619 - checkGraphConEdgeList(adaptor, 3);
5.620 -
5.621 - checkGraphOutArcList(adaptor, n1, 1);
5.622 - checkGraphOutArcList(adaptor, n2, 2);
5.623 - checkGraphOutArcList(adaptor, n3, 2);
5.624 - checkGraphOutArcList(adaptor, n4, 1);
5.625 -
5.626 - checkGraphInArcList(adaptor, n1, 1);
5.627 - checkGraphInArcList(adaptor, n2, 2);
5.628 - checkGraphInArcList(adaptor, n3, 2);
5.629 - checkGraphInArcList(adaptor, n4, 1);
5.630 -
5.631 - checkGraphIncEdgeList(adaptor, n1, 1);
5.632 - checkGraphIncEdgeList(adaptor, n2, 2);
5.633 - checkGraphIncEdgeList(adaptor, n3, 2);
5.634 - checkGraphIncEdgeList(adaptor, n4, 1);
5.635 -
5.636 - checkNodeIds(adaptor);
5.637 - checkArcIds(adaptor);
5.638 - checkEdgeIds(adaptor);
5.639 -
5.640 - checkGraphNodeMap(adaptor);
5.641 - checkGraphArcMap(adaptor);
5.642 - checkGraphEdgeMap(adaptor);
5.643 -
5.644 - node_filter[n1] = false;
5.645 -
5.646 - checkGraphNodeList(adaptor, 3);
5.647 - checkGraphArcList(adaptor, 4);
5.648 - checkGraphEdgeList(adaptor, 2);
5.649 - checkGraphConArcList(adaptor, 4);
5.650 - checkGraphConEdgeList(adaptor, 2);
5.651 -
5.652 - checkGraphOutArcList(adaptor, n2, 1);
5.653 - checkGraphOutArcList(adaptor, n3, 2);
5.654 - checkGraphOutArcList(adaptor, n4, 1);
5.655 -
5.656 - checkGraphInArcList(adaptor, n2, 1);
5.657 - checkGraphInArcList(adaptor, n3, 2);
5.658 - checkGraphInArcList(adaptor, n4, 1);
5.659 -
5.660 - checkGraphIncEdgeList(adaptor, n2, 1);
5.661 - checkGraphIncEdgeList(adaptor, n3, 2);
5.662 - checkGraphIncEdgeList(adaptor, n4, 1);
5.663 -
5.664 - checkNodeIds(adaptor);
5.665 - checkArcIds(adaptor);
5.666 - checkEdgeIds(adaptor);
5.667 -
5.668 - checkGraphNodeMap(adaptor);
5.669 - checkGraphArcMap(adaptor);
5.670 - checkGraphEdgeMap(adaptor);
5.671 -
5.672 - node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
5.673 - edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
5.674 -
5.675 - checkGraphNodeList(adaptor, 0);
5.676 - checkGraphArcList(adaptor, 0);
5.677 - checkGraphEdgeList(adaptor, 0);
5.678 - checkGraphConArcList(adaptor, 0);
5.679 - checkGraphConEdgeList(adaptor, 0);
5.680 -
5.681 - checkNodeIds(adaptor);
5.682 - checkArcIds(adaptor);
5.683 - checkEdgeIds(adaptor);
5.684 -
5.685 - checkGraphNodeMap(adaptor);
5.686 - checkGraphArcMap(adaptor);
5.687 - checkGraphEdgeMap(adaptor);
5.688 -}
5.689 -
5.690 -void checkFilterNodes2() {
5.691 - checkConcept<concepts::Graph,
5.692 - FilterNodes<concepts::Graph,
5.693 - concepts::Graph::NodeMap<bool> > >();
5.694 -
5.695 - typedef ListGraph Graph;
5.696 - typedef Graph::NodeMap<bool> NodeFilter;
5.697 - typedef FilterNodes<Graph, NodeFilter> Adaptor;
5.698 -
5.699 - Graph graph;
5.700 - NodeFilter node_filter(graph);
5.701 - Adaptor adaptor(graph, node_filter);
5.702 -
5.703 - Graph::Node n1 = graph.addNode();
5.704 - Graph::Node n2 = graph.addNode();
5.705 - Graph::Node n3 = graph.addNode();
5.706 - Graph::Node n4 = graph.addNode();
5.707 -
5.708 - Graph::Edge e1 = graph.addEdge(n1, n2);
5.709 - Graph::Edge e2 = graph.addEdge(n1, n3);
5.710 - Graph::Edge e3 = graph.addEdge(n2, n3);
5.711 - Graph::Edge e4 = graph.addEdge(n3, n4);
5.712 -
5.713 - node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;
5.714 -
5.715 - checkGraphNodeList(adaptor, 4);
5.716 - checkGraphArcList(adaptor, 8);
5.717 - checkGraphEdgeList(adaptor, 4);
5.718 - checkGraphConArcList(adaptor, 8);
5.719 - checkGraphConEdgeList(adaptor, 4);
5.720 -
5.721 - checkGraphOutArcList(adaptor, n1, 2);
5.722 - checkGraphOutArcList(adaptor, n2, 2);
5.723 - checkGraphOutArcList(adaptor, n3, 3);
5.724 - checkGraphOutArcList(adaptor, n4, 1);
5.725 -
5.726 - checkGraphInArcList(adaptor, n1, 2);
5.727 - checkGraphInArcList(adaptor, n2, 2);
5.728 - checkGraphInArcList(adaptor, n3, 3);
5.729 - checkGraphInArcList(adaptor, n4, 1);
5.730 -
5.731 - checkGraphIncEdgeList(adaptor, n1, 2);
5.732 - checkGraphIncEdgeList(adaptor, n2, 2);
5.733 - checkGraphIncEdgeList(adaptor, n3, 3);
5.734 - checkGraphIncEdgeList(adaptor, n4, 1);
5.735 -
5.736 - checkNodeIds(adaptor);
5.737 - checkArcIds(adaptor);
5.738 - checkEdgeIds(adaptor);
5.739 -
5.740 - checkGraphNodeMap(adaptor);
5.741 - checkGraphArcMap(adaptor);
5.742 - checkGraphEdgeMap(adaptor);
5.743 -
5.744 - node_filter[n1] = false;
5.745 -
5.746 - checkGraphNodeList(adaptor, 3);
5.747 - checkGraphArcList(adaptor, 4);
5.748 - checkGraphEdgeList(adaptor, 2);
5.749 - checkGraphConArcList(adaptor, 4);
5.750 - checkGraphConEdgeList(adaptor, 2);
5.751 -
5.752 - checkGraphOutArcList(adaptor, n2, 1);
5.753 - checkGraphOutArcList(adaptor, n3, 2);
5.754 - checkGraphOutArcList(adaptor, n4, 1);
5.755 -
5.756 - checkGraphInArcList(adaptor, n2, 1);
5.757 - checkGraphInArcList(adaptor, n3, 2);
5.758 - checkGraphInArcList(adaptor, n4, 1);
5.759 -
5.760 - checkGraphIncEdgeList(adaptor, n2, 1);
5.761 - checkGraphIncEdgeList(adaptor, n3, 2);
5.762 - checkGraphIncEdgeList(adaptor, n4, 1);
5.763 -
5.764 - checkNodeIds(adaptor);
5.765 - checkArcIds(adaptor);
5.766 - checkEdgeIds(adaptor);
5.767 -
5.768 - checkGraphNodeMap(adaptor);
5.769 - checkGraphArcMap(adaptor);
5.770 - checkGraphEdgeMap(adaptor);
5.771 -
5.772 - node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;
5.773 -
5.774 - checkGraphNodeList(adaptor, 0);
5.775 - checkGraphArcList(adaptor, 0);
5.776 - checkGraphEdgeList(adaptor, 0);
5.777 - checkGraphConArcList(adaptor, 0);
5.778 - checkGraphConEdgeList(adaptor, 0);
5.779 -
5.780 - checkNodeIds(adaptor);
5.781 - checkArcIds(adaptor);
5.782 - checkEdgeIds(adaptor);
5.783 -
5.784 - checkGraphNodeMap(adaptor);
5.785 - checkGraphArcMap(adaptor);
5.786 - checkGraphEdgeMap(adaptor);
5.787 -}
5.788 -
5.789 -void checkFilterEdges() {
5.790 - checkConcept<concepts::Graph,
5.791 - FilterEdges<concepts::Graph,
5.792 - concepts::Graph::EdgeMap<bool> > >();
5.793 -
5.794 - typedef ListGraph Graph;
5.795 - typedef Graph::EdgeMap<bool> EdgeFilter;
5.796 - typedef FilterEdges<Graph, EdgeFilter> Adaptor;
5.797 -
5.798 - Graph graph;
5.799 - EdgeFilter edge_filter(graph);
5.800 - Adaptor adaptor(graph, edge_filter);
5.801 -
5.802 - Graph::Node n1 = graph.addNode();
5.803 - Graph::Node n2 = graph.addNode();
5.804 - Graph::Node n3 = graph.addNode();
5.805 - Graph::Node n4 = graph.addNode();
5.806 -
5.807 - Graph::Edge e1 = graph.addEdge(n1, n2);
5.808 - Graph::Edge e2 = graph.addEdge(n1, n3);
5.809 - Graph::Edge e3 = graph.addEdge(n2, n3);
5.810 - Graph::Edge e4 = graph.addEdge(n3, n4);
5.811 -
5.812 - edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;
5.813 -
5.814 - checkGraphNodeList(adaptor, 4);
5.815 - checkGraphArcList(adaptor, 8);
5.816 - checkGraphEdgeList(adaptor, 4);
5.817 - checkGraphConArcList(adaptor, 8);
5.818 - checkGraphConEdgeList(adaptor, 4);
5.819 -
5.820 - checkGraphOutArcList(adaptor, n1, 2);
5.821 - checkGraphOutArcList(adaptor, n2, 2);
5.822 - checkGraphOutArcList(adaptor, n3, 3);
5.823 - checkGraphOutArcList(adaptor, n4, 1);
5.824 -
5.825 - checkGraphInArcList(adaptor, n1, 2);
5.826 - checkGraphInArcList(adaptor, n2, 2);
5.827 - checkGraphInArcList(adaptor, n3, 3);
5.828 - checkGraphInArcList(adaptor, n4, 1);
5.829 -
5.830 - checkGraphIncEdgeList(adaptor, n1, 2);
5.831 - checkGraphIncEdgeList(adaptor, n2, 2);
5.832 - checkGraphIncEdgeList(adaptor, n3, 3);
5.833 - checkGraphIncEdgeList(adaptor, n4, 1);
5.834 -
5.835 - checkNodeIds(adaptor);
5.836 - checkArcIds(adaptor);
5.837 - checkEdgeIds(adaptor);
5.838 -
5.839 - checkGraphNodeMap(adaptor);
5.840 - checkGraphArcMap(adaptor);
5.841 - checkGraphEdgeMap(adaptor);
5.842 -
5.843 - edge_filter[e2] = false;
5.844 -
5.845 - checkGraphNodeList(adaptor, 4);
5.846 - checkGraphArcList(adaptor, 6);
5.847 - checkGraphEdgeList(adaptor, 3);
5.848 - checkGraphConArcList(adaptor, 6);
5.849 - checkGraphConEdgeList(adaptor, 3);
5.850 -
5.851 - checkGraphOutArcList(adaptor, n1, 1);
5.852 - checkGraphOutArcList(adaptor, n2, 2);
5.853 - checkGraphOutArcList(adaptor, n3, 2);
5.854 - checkGraphOutArcList(adaptor, n4, 1);
5.855 -
5.856 - checkGraphInArcList(adaptor, n1, 1);
5.857 - checkGraphInArcList(adaptor, n2, 2);
5.858 - checkGraphInArcList(adaptor, n3, 2);
5.859 - checkGraphInArcList(adaptor, n4, 1);
5.860 -
5.861 - checkGraphIncEdgeList(adaptor, n1, 1);
5.862 - checkGraphIncEdgeList(adaptor, n2, 2);
5.863 - checkGraphIncEdgeList(adaptor, n3, 2);
5.864 - checkGraphIncEdgeList(adaptor, n4, 1);
5.865 -
5.866 - checkNodeIds(adaptor);
5.867 - checkArcIds(adaptor);
5.868 - checkEdgeIds(adaptor);
5.869 -
5.870 - checkGraphNodeMap(adaptor);
5.871 - checkGraphArcMap(adaptor);
5.872 - checkGraphEdgeMap(adaptor);
5.873 -
5.874 - edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;
5.875 -
5.876 - checkGraphNodeList(adaptor, 4);
5.877 - checkGraphArcList(adaptor, 0);
5.878 - checkGraphEdgeList(adaptor, 0);
5.879 - checkGraphConArcList(adaptor, 0);
5.880 - checkGraphConEdgeList(adaptor, 0);
5.881 -
5.882 - checkNodeIds(adaptor);
5.883 - checkArcIds(adaptor);
5.884 - checkEdgeIds(adaptor);
5.885 -
5.886 - checkGraphNodeMap(adaptor);
5.887 - checkGraphArcMap(adaptor);
5.888 - checkGraphEdgeMap(adaptor);
5.889 -}
5.890 -
5.891 -void checkOrienter() {
5.892 - checkConcept<concepts::Digraph,
5.893 - Orienter<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
5.894 -
5.895 - typedef ListGraph Graph;
5.896 - typedef ListGraph::EdgeMap<bool> DirMap;
5.897 - typedef Orienter<Graph> Adaptor;
5.898 -
5.899 - Graph graph;
5.900 - DirMap dir(graph, true);
5.901 - Adaptor adaptor(graph, dir);
5.902 -
5.903 - Graph::Node n1 = graph.addNode();
5.904 - Graph::Node n2 = graph.addNode();
5.905 - Graph::Node n3 = graph.addNode();
5.906 -
5.907 - Graph::Edge e1 = graph.addEdge(n1, n2);
5.908 - Graph::Edge e2 = graph.addEdge(n1, n3);
5.909 - Graph::Edge e3 = graph.addEdge(n2, n3);
5.910 -
5.911 - checkGraphNodeList(adaptor, 3);
5.912 - checkGraphArcList(adaptor, 3);
5.913 - checkGraphConArcList(adaptor, 3);
5.914 -
5.915 - {
5.916 - dir[e1] = true;
5.917 - Adaptor::Node u = adaptor.source(e1);
5.918 - Adaptor::Node v = adaptor.target(e1);
5.919 -
5.920 - dir[e1] = false;
5.921 - check (u == adaptor.target(e1), "Wrong dir");
5.922 - check (v == adaptor.source(e1), "Wrong dir");
5.923 -
5.924 - check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");
5.925 - dir[e1] = n1 == u;
5.926 - }
5.927 -
5.928 - {
5.929 - dir[e2] = true;
5.930 - Adaptor::Node u = adaptor.source(e2);
5.931 - Adaptor::Node v = adaptor.target(e2);
5.932 -
5.933 - dir[e2] = false;
5.934 - check (u == adaptor.target(e2), "Wrong dir");
5.935 - check (v == adaptor.source(e2), "Wrong dir");
5.936 -
5.937 - check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");
5.938 - dir[e2] = n3 == u;
5.939 - }
5.940 -
5.941 - {
5.942 - dir[e3] = true;
5.943 - Adaptor::Node u = adaptor.source(e3);
5.944 - Adaptor::Node v = adaptor.target(e3);
5.945 -
5.946 - dir[e3] = false;
5.947 - check (u == adaptor.target(e3), "Wrong dir");
5.948 - check (v == adaptor.source(e3), "Wrong dir");
5.949 -
5.950 - check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");
5.951 - dir[e3] = n2 == u;
5.952 - }
5.953 -
5.954 - checkGraphOutArcList(adaptor, n1, 1);
5.955 - checkGraphOutArcList(adaptor, n2, 1);
5.956 - checkGraphOutArcList(adaptor, n3, 1);
5.957 -
5.958 - checkGraphInArcList(adaptor, n1, 1);
5.959 - checkGraphInArcList(adaptor, n2, 1);
5.960 - checkGraphInArcList(adaptor, n3, 1);
5.961 -
5.962 - checkNodeIds(adaptor);
5.963 - checkArcIds(adaptor);
5.964 -
5.965 - checkGraphNodeMap(adaptor);
5.966 - checkGraphArcMap(adaptor);
5.967 -
5.968 -}
5.969 -
5.970 -
5.971 -int main(int, const char **) {
5.972 -
5.973 - checkReverseDigraph();
5.974 - checkSubDigraph();
5.975 - checkFilterNodes1();
5.976 - checkFilterArcs();
5.977 - checkUndirector();
5.978 - checkResidual();
5.979 - checkSplitNodes();
5.980 -
5.981 - checkSubGraph();
5.982 - checkFilterNodes2();
5.983 - checkFilterEdges();
5.984 - checkOrienter();
5.985 -
5.986 - return 0;
5.987 -}
6.1 --- a/tools/lemon-0.x-to-1.x.sh Mon Jan 12 12:26:02 2009 +0000
6.2 +++ b/tools/lemon-0.x-to-1.x.sh Mon Jan 12 13:18:03 2009 +0000
6.3 @@ -92,6 +92,30 @@
6.4 -e "s/\<storeBoolMap\>/loggerBoolMap/g"\
6.5 -e "s/\<BoundingBox\>/Box/g"\
6.6 -e "s/\<readNauty\>/readNautyGraph/g"\
6.7 + -e "s/\<RevDigraphAdaptor\>/ReverseDigraph/g"\
6.8 + -e "s/\<revDigraphAdaptor\>/reverseDigraph/g"\
6.9 + -e "s/\<SubDigraphAdaptor\>/SubDigraph/g"\
6.10 + -e "s/\<subDigraphAdaptor\>/subDigraph/g"\
6.11 + -e "s/\<SubGraphAdaptor\>/SubGraph/g"\
6.12 + -e "s/\<subGraphAdaptor\>/subGraph/g"\
6.13 + -e "s/\<NodeSubDigraphAdaptor\>/FilterNodes/g"\
6.14 + -e "s/\<nodeSubDigraphAdaptor\>/filterNodes/g"\
6.15 + -e "s/\<ArcSubDigraphAdaptor\>/FilterArcs/g"\
6.16 + -e "s/\<arcSubDigraphAdaptor\>/filterArcs/g"\
6.17 + -e "s/\<UndirDigraphAdaptor\>/Undirector/g"\
6.18 + -e "s/\<undirDigraphAdaptor\>/undirector/g"\
6.19 + -e "s/\<ResDigraphAdaptor\>/ResidualDigraph/g"\
6.20 + -e "s/\<resDigraphAdaptor\>/residualDigraph/g"\
6.21 + -e "s/\<SplitDigraphAdaptor\>/SplitNodes/g"\
6.22 + -e "s/\<splitDigraphAdaptor\>/splitNodes/g"\
6.23 + -e "s/\<SubGraphAdaptor\>/SubGraph/g"\
6.24 + -e "s/\<subGraphAdaptor\>/subGraph/g"\
6.25 + -e "s/\<NodeSubGraphAdaptor\>/FilterNodes/g"\
6.26 + -e "s/\<nodeSubGraphAdaptor\>/filterNodes/g"\
6.27 + -e "s/\<ArcSubGraphAdaptor\>/FilterEdges/g"\
6.28 + -e "s/\<arcSubGraphAdaptor\>/filterEdges/g"\
6.29 + -e "s/\<DirGraphAdaptor\>/Orienter/g"\
6.30 + -e "s/\<dirGraphAdaptor\>/orienter/g"\
6.31 <$i > $TMP
6.32 mv $TMP $i
6.33 done