1.1 --- a/test/digraph_test.cc Fri Oct 16 10:21:37 2009 +0200
1.2 +++ b/test/digraph_test.cc Thu Nov 05 15:50:01 2009 +0100
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2008
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 @@ -19,8 +19,8 @@
1.13 #include <lemon/concepts/digraph.h>
1.14 #include <lemon/list_graph.h>
1.15 #include <lemon/smart_graph.h>
1.16 -//#include <lemon/full_graph.h>
1.17 -//#include <lemon/hypercube_graph.h>
1.18 +#include <lemon/static_graph.h>
1.19 +#include <lemon/full_graph.h>
1.20
1.21 #include "test_tools.h"
1.22 #include "graph_test.h"
1.23 @@ -29,13 +29,16 @@
1.24 using namespace lemon::concepts;
1.25
1.26 template <class Digraph>
1.27 -void checkDigraph() {
1.28 +void checkDigraphBuild() {
1.29 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.30 Digraph G;
1.31
1.32 checkGraphNodeList(G, 0);
1.33 checkGraphArcList(G, 0);
1.34
1.35 + G.reserveNode(3);
1.36 + G.reserveArc(4);
1.37 +
1.38 Node
1.39 n1 = G.addNode(),
1.40 n2 = G.addNode(),
1.41 @@ -58,7 +61,208 @@
1.42
1.43 checkGraphConArcList(G, 1);
1.44
1.45 - Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
1.46 + Arc a2 = G.addArc(n2, n1),
1.47 + a3 = G.addArc(n2, n3),
1.48 + a4 = G.addArc(n2, n3);
1.49 +
1.50 + checkGraphNodeList(G, 3);
1.51 + checkGraphArcList(G, 4);
1.52 +
1.53 + checkGraphOutArcList(G, n1, 1);
1.54 + checkGraphOutArcList(G, n2, 3);
1.55 + checkGraphOutArcList(G, n3, 0);
1.56 +
1.57 + checkGraphInArcList(G, n1, 1);
1.58 + checkGraphInArcList(G, n2, 1);
1.59 + checkGraphInArcList(G, n3, 2);
1.60 +
1.61 + checkGraphConArcList(G, 4);
1.62 +
1.63 + checkNodeIds(G);
1.64 + checkArcIds(G);
1.65 + checkGraphNodeMap(G);
1.66 + checkGraphArcMap(G);
1.67 +}
1.68 +
1.69 +template <class Digraph>
1.70 +void checkDigraphSplit() {
1.71 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.72 +
1.73 + Digraph G;
1.74 + Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
1.75 + Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
1.76 + a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
1.77 +
1.78 + Node n4 = G.split(n2);
1.79 +
1.80 + check(G.target(OutArcIt(G, n2)) == n4 &&
1.81 + G.source(InArcIt(G, n4)) == n2,
1.82 + "Wrong split.");
1.83 +
1.84 + checkGraphNodeList(G, 4);
1.85 + checkGraphArcList(G, 5);
1.86 +
1.87 + checkGraphOutArcList(G, n1, 1);
1.88 + checkGraphOutArcList(G, n2, 1);
1.89 + checkGraphOutArcList(G, n3, 0);
1.90 + checkGraphOutArcList(G, n4, 3);
1.91 +
1.92 + checkGraphInArcList(G, n1, 1);
1.93 + checkGraphInArcList(G, n2, 1);
1.94 + checkGraphInArcList(G, n3, 2);
1.95 + checkGraphInArcList(G, n4, 1);
1.96 +
1.97 + checkGraphConArcList(G, 5);
1.98 +}
1.99 +
1.100 +template <class Digraph>
1.101 +void checkDigraphAlter() {
1.102 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.103 +
1.104 + Digraph G;
1.105 + Node n1 = G.addNode(), n2 = G.addNode(),
1.106 + n3 = G.addNode(), n4 = G.addNode();
1.107 + Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
1.108 + a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),
1.109 + a5 = G.addArc(n2, n4);
1.110 +
1.111 + checkGraphNodeList(G, 4);
1.112 + checkGraphArcList(G, 5);
1.113 +
1.114 + // Check changeSource() and changeTarget()
1.115 + G.changeTarget(a4, n1);
1.116 +
1.117 + checkGraphNodeList(G, 4);
1.118 + checkGraphArcList(G, 5);
1.119 +
1.120 + checkGraphOutArcList(G, n1, 1);
1.121 + checkGraphOutArcList(G, n2, 1);
1.122 + checkGraphOutArcList(G, n3, 0);
1.123 + checkGraphOutArcList(G, n4, 3);
1.124 +
1.125 + checkGraphInArcList(G, n1, 2);
1.126 + checkGraphInArcList(G, n2, 1);
1.127 + checkGraphInArcList(G, n3, 1);
1.128 + checkGraphInArcList(G, n4, 1);
1.129 +
1.130 + checkGraphConArcList(G, 5);
1.131 +
1.132 + G.changeSource(a4, n3);
1.133 +
1.134 + checkGraphNodeList(G, 4);
1.135 + checkGraphArcList(G, 5);
1.136 +
1.137 + checkGraphOutArcList(G, n1, 1);
1.138 + checkGraphOutArcList(G, n2, 1);
1.139 + checkGraphOutArcList(G, n3, 1);
1.140 + checkGraphOutArcList(G, n4, 2);
1.141 +
1.142 + checkGraphInArcList(G, n1, 2);
1.143 + checkGraphInArcList(G, n2, 1);
1.144 + checkGraphInArcList(G, n3, 1);
1.145 + checkGraphInArcList(G, n4, 1);
1.146 +
1.147 + checkGraphConArcList(G, 5);
1.148 +
1.149 + // Check contract()
1.150 + G.contract(n2, n4, false);
1.151 +
1.152 + checkGraphNodeList(G, 3);
1.153 + checkGraphArcList(G, 5);
1.154 +
1.155 + checkGraphOutArcList(G, n1, 1);
1.156 + checkGraphOutArcList(G, n2, 3);
1.157 + checkGraphOutArcList(G, n3, 1);
1.158 +
1.159 + checkGraphInArcList(G, n1, 2);
1.160 + checkGraphInArcList(G, n2, 2);
1.161 + checkGraphInArcList(G, n3, 1);
1.162 +
1.163 + checkGraphConArcList(G, 5);
1.164 +
1.165 + G.contract(n2, n1);
1.166 +
1.167 + checkGraphNodeList(G, 2);
1.168 + checkGraphArcList(G, 3);
1.169 +
1.170 + checkGraphOutArcList(G, n2, 2);
1.171 + checkGraphOutArcList(G, n3, 1);
1.172 +
1.173 + checkGraphInArcList(G, n2, 2);
1.174 + checkGraphInArcList(G, n3, 1);
1.175 +
1.176 + checkGraphConArcList(G, 3);
1.177 +}
1.178 +
1.179 +template <class Digraph>
1.180 +void checkDigraphErase() {
1.181 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.182 +
1.183 + Digraph G;
1.184 + Node n1 = G.addNode(), n2 = G.addNode(),
1.185 + n3 = G.addNode(), n4 = G.addNode();
1.186 + Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
1.187 + a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1),
1.188 + a5 = G.addArc(n2, n4);
1.189 +
1.190 + // Check arc deletion
1.191 + G.erase(a1);
1.192 +
1.193 + checkGraphNodeList(G, 4);
1.194 + checkGraphArcList(G, 4);
1.195 +
1.196 + checkGraphOutArcList(G, n1, 0);
1.197 + checkGraphOutArcList(G, n2, 1);
1.198 + checkGraphOutArcList(G, n3, 1);
1.199 + checkGraphOutArcList(G, n4, 2);
1.200 +
1.201 + checkGraphInArcList(G, n1, 2);
1.202 + checkGraphInArcList(G, n2, 0);
1.203 + checkGraphInArcList(G, n3, 1);
1.204 + checkGraphInArcList(G, n4, 1);
1.205 +
1.206 + checkGraphConArcList(G, 4);
1.207 +
1.208 + // Check node deletion
1.209 + G.erase(n4);
1.210 +
1.211 + checkGraphNodeList(G, 3);
1.212 + checkGraphArcList(G, 1);
1.213 +
1.214 + checkGraphOutArcList(G, n1, 0);
1.215 + checkGraphOutArcList(G, n2, 0);
1.216 + checkGraphOutArcList(G, n3, 1);
1.217 + checkGraphOutArcList(G, n4, 0);
1.218 +
1.219 + checkGraphInArcList(G, n1, 1);
1.220 + checkGraphInArcList(G, n2, 0);
1.221 + checkGraphInArcList(G, n3, 0);
1.222 + checkGraphInArcList(G, n4, 0);
1.223 +
1.224 + checkGraphConArcList(G, 1);
1.225 +}
1.226 +
1.227 +
1.228 +template <class Digraph>
1.229 +void checkDigraphSnapshot() {
1.230 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.231 +
1.232 + Digraph G;
1.233 + Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
1.234 + Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
1.235 + a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
1.236 +
1.237 + typename Digraph::Snapshot snapshot(G);
1.238 +
1.239 + Node n = G.addNode();
1.240 + G.addArc(n3, n);
1.241 + G.addArc(n, n3);
1.242 +
1.243 + checkGraphNodeList(G, 4);
1.244 + checkGraphArcList(G, 6);
1.245 +
1.246 + snapshot.restore();
1.247 +
1.248 checkGraphNodeList(G, 3);
1.249 checkGraphArcList(G, 4);
1.250
1.251 @@ -77,9 +281,25 @@
1.252 checkGraphNodeMap(G);
1.253 checkGraphArcMap(G);
1.254
1.255 + G.addNode();
1.256 + snapshot.save(G);
1.257 +
1.258 + G.addArc(G.addNode(), G.addNode());
1.259 +
1.260 + snapshot.restore();
1.261 + snapshot.save(G);
1.262 +
1.263 + checkGraphNodeList(G, 4);
1.264 + checkGraphArcList(G, 4);
1.265 +
1.266 + G.addArc(G.addNode(), G.addNode());
1.267 +
1.268 + snapshot.restore();
1.269 +
1.270 + checkGraphNodeList(G, 4);
1.271 + checkGraphArcList(G, 4);
1.272 }
1.273
1.274 -
1.275 void checkConcepts() {
1.276 { // Checking digraph components
1.277 checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
1.278 @@ -109,12 +329,13 @@
1.279 checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
1.280 checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
1.281 }
1.282 -// { // Checking FullDigraph
1.283 -// checkConcept<Digraph, FullDigraph>();
1.284 -// }
1.285 -// { // Checking HyperCubeDigraph
1.286 -// checkConcept<Digraph, HyperCubeDigraph>();
1.287 -// }
1.288 + { // Checking StaticDigraph
1.289 + checkConcept<Digraph, StaticDigraph>();
1.290 + checkConcept<ClearableDigraphComponent<>, StaticDigraph>();
1.291 + }
1.292 + { // Checking FullDigraph
1.293 + checkConcept<Digraph, FullDigraph>();
1.294 + }
1.295 }
1.296
1.297 template <typename Digraph>
1.298 @@ -167,15 +388,171 @@
1.299 check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
1.300 }
1.301
1.302 +void checkStaticDigraph() {
1.303 + SmartDigraph g;
1.304 + SmartDigraph::NodeMap<StaticDigraph::Node> nref(g);
1.305 + SmartDigraph::ArcMap<StaticDigraph::Arc> aref(g);
1.306 +
1.307 + StaticDigraph G;
1.308 +
1.309 + checkGraphNodeList(G, 0);
1.310 + checkGraphArcList(G, 0);
1.311 +
1.312 + G.build(g, nref, aref);
1.313 +
1.314 + checkGraphNodeList(G, 0);
1.315 + checkGraphArcList(G, 0);
1.316 +
1.317 + SmartDigraph::Node
1.318 + n1 = g.addNode(),
1.319 + n2 = g.addNode(),
1.320 + n3 = g.addNode();
1.321 +
1.322 + G.build(g, nref, aref);
1.323 +
1.324 + checkGraphNodeList(G, 3);
1.325 + checkGraphArcList(G, 0);
1.326 +
1.327 + SmartDigraph::Arc a1 = g.addArc(n1, n2);
1.328 +
1.329 + G.build(g, nref, aref);
1.330 +
1.331 + check(G.source(aref[a1]) == nref[n1] && G.target(aref[a1]) == nref[n2],
1.332 + "Wrong arc or wrong references");
1.333 + checkGraphNodeList(G, 3);
1.334 + checkGraphArcList(G, 1);
1.335 +
1.336 + checkGraphOutArcList(G, nref[n1], 1);
1.337 + checkGraphOutArcList(G, nref[n2], 0);
1.338 + checkGraphOutArcList(G, nref[n3], 0);
1.339 +
1.340 + checkGraphInArcList(G, nref[n1], 0);
1.341 + checkGraphInArcList(G, nref[n2], 1);
1.342 + checkGraphInArcList(G, nref[n3], 0);
1.343 +
1.344 + checkGraphConArcList(G, 1);
1.345 +
1.346 + SmartDigraph::Arc
1.347 + a2 = g.addArc(n2, n1),
1.348 + a3 = g.addArc(n2, n3),
1.349 + a4 = g.addArc(n2, n3);
1.350 +
1.351 + digraphCopy(g, G).nodeRef(nref).run();
1.352 +
1.353 + checkGraphNodeList(G, 3);
1.354 + checkGraphArcList(G, 4);
1.355 +
1.356 + checkGraphOutArcList(G, nref[n1], 1);
1.357 + checkGraphOutArcList(G, nref[n2], 3);
1.358 + checkGraphOutArcList(G, nref[n3], 0);
1.359 +
1.360 + checkGraphInArcList(G, nref[n1], 1);
1.361 + checkGraphInArcList(G, nref[n2], 1);
1.362 + checkGraphInArcList(G, nref[n3], 2);
1.363 +
1.364 + checkGraphConArcList(G, 4);
1.365 +
1.366 + std::vector<std::pair<int,int> > arcs;
1.367 + arcs.push_back(std::make_pair(0,1));
1.368 + arcs.push_back(std::make_pair(0,2));
1.369 + arcs.push_back(std::make_pair(1,3));
1.370 + arcs.push_back(std::make_pair(1,2));
1.371 + arcs.push_back(std::make_pair(3,0));
1.372 + arcs.push_back(std::make_pair(3,3));
1.373 + arcs.push_back(std::make_pair(4,2));
1.374 + arcs.push_back(std::make_pair(4,3));
1.375 + arcs.push_back(std::make_pair(4,1));
1.376 +
1.377 + G.build(6, arcs.begin(), arcs.end());
1.378 +
1.379 + checkGraphNodeList(G, 6);
1.380 + checkGraphArcList(G, 9);
1.381 +
1.382 + checkGraphOutArcList(G, G.node(0), 2);
1.383 + checkGraphOutArcList(G, G.node(1), 2);
1.384 + checkGraphOutArcList(G, G.node(2), 0);
1.385 + checkGraphOutArcList(G, G.node(3), 2);
1.386 + checkGraphOutArcList(G, G.node(4), 3);
1.387 + checkGraphOutArcList(G, G.node(5), 0);
1.388 +
1.389 + checkGraphInArcList(G, G.node(0), 1);
1.390 + checkGraphInArcList(G, G.node(1), 2);
1.391 + checkGraphInArcList(G, G.node(2), 3);
1.392 + checkGraphInArcList(G, G.node(3), 3);
1.393 + checkGraphInArcList(G, G.node(4), 0);
1.394 + checkGraphInArcList(G, G.node(5), 0);
1.395 +
1.396 + checkGraphConArcList(G, 9);
1.397 +
1.398 + checkNodeIds(G);
1.399 + checkArcIds(G);
1.400 + checkGraphNodeMap(G);
1.401 + checkGraphArcMap(G);
1.402 +
1.403 + int n = G.nodeNum();
1.404 + int m = G.arcNum();
1.405 + check(G.index(G.node(n-1)) == n-1, "Wrong index.");
1.406 + check(G.index(G.arc(m-1)) == m-1, "Wrong index.");
1.407 +}
1.408 +
1.409 +void checkFullDigraph(int num) {
1.410 + typedef FullDigraph Digraph;
1.411 + DIGRAPH_TYPEDEFS(Digraph);
1.412 +
1.413 + Digraph G(num);
1.414 + check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
1.415 +
1.416 + G.resize(num);
1.417 + check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
1.418 +
1.419 + checkGraphNodeList(G, num);
1.420 + checkGraphArcList(G, num * num);
1.421 +
1.422 + for (NodeIt n(G); n != INVALID; ++n) {
1.423 + checkGraphOutArcList(G, n, num);
1.424 + checkGraphInArcList(G, n, num);
1.425 + }
1.426 +
1.427 + checkGraphConArcList(G, num * num);
1.428 +
1.429 + checkNodeIds(G);
1.430 + checkArcIds(G);
1.431 + checkGraphNodeMap(G);
1.432 + checkGraphArcMap(G);
1.433 +
1.434 + for (int i = 0; i < G.nodeNum(); ++i) {
1.435 + check(G.index(G(i)) == i, "Wrong index");
1.436 + }
1.437 +
1.438 + for (NodeIt s(G); s != INVALID; ++s) {
1.439 + for (NodeIt t(G); t != INVALID; ++t) {
1.440 + Arc a = G.arc(s, t);
1.441 + check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
1.442 + }
1.443 + }
1.444 +}
1.445 +
1.446 void checkDigraphs() {
1.447 { // Checking ListDigraph
1.448 - checkDigraph<ListDigraph>();
1.449 + checkDigraphBuild<ListDigraph>();
1.450 + checkDigraphSplit<ListDigraph>();
1.451 + checkDigraphAlter<ListDigraph>();
1.452 + checkDigraphErase<ListDigraph>();
1.453 + checkDigraphSnapshot<ListDigraph>();
1.454 checkDigraphValidityErase<ListDigraph>();
1.455 }
1.456 { // Checking SmartDigraph
1.457 - checkDigraph<SmartDigraph>();
1.458 + checkDigraphBuild<SmartDigraph>();
1.459 + checkDigraphSplit<SmartDigraph>();
1.460 + checkDigraphSnapshot<SmartDigraph>();
1.461 checkDigraphValidity<SmartDigraph>();
1.462 }
1.463 + { // Checking StaticDigraph
1.464 + checkStaticDigraph();
1.465 + }
1.466 + { // Checking FullDigraph
1.467 + checkFullDigraph(8);
1.468 + }
1.469 }
1.470
1.471 int main() {