1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/bpgraph_test.cc Wed Oct 17 19:14:07 2018 +0200
1.3 @@ -0,0 +1,456 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2013
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#include <lemon/concepts/bpgraph.h>
1.23 +#include <lemon/list_graph.h>
1.24 +#include <lemon/smart_graph.h>
1.25 +#include <lemon/full_graph.h>
1.26 +
1.27 +#include "test_tools.h"
1.28 +#include "graph_test.h"
1.29 +
1.30 +using namespace lemon;
1.31 +using namespace lemon::concepts;
1.32 +
1.33 +template <class BpGraph>
1.34 +void checkBpGraphBuild() {
1.35 + TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
1.36 +
1.37 + BpGraph G;
1.38 + checkGraphNodeList(G, 0);
1.39 + checkGraphRedNodeList(G, 0);
1.40 + checkGraphBlueNodeList(G, 0);
1.41 + checkGraphEdgeList(G, 0);
1.42 + checkGraphArcList(G, 0);
1.43 +
1.44 + G.reserveNode(3);
1.45 + G.reserveEdge(3);
1.46 +
1.47 + RedNode
1.48 + rn1 = G.addRedNode();
1.49 + checkGraphNodeList(G, 1);
1.50 + checkGraphRedNodeList(G, 1);
1.51 + checkGraphBlueNodeList(G, 0);
1.52 + checkGraphEdgeList(G, 0);
1.53 + checkGraphArcList(G, 0);
1.54 +
1.55 + BlueNode
1.56 + bn1 = G.addBlueNode(),
1.57 + bn2 = G.addBlueNode();
1.58 + checkGraphNodeList(G, 3);
1.59 + checkGraphRedNodeList(G, 1);
1.60 + checkGraphBlueNodeList(G, 2);
1.61 + checkGraphEdgeList(G, 0);
1.62 + checkGraphArcList(G, 0);
1.63 +
1.64 + Edge e1 = G.addEdge(rn1, bn2);
1.65 + check(G.redNode(e1) == rn1 && G.blueNode(e1) == bn2, "Wrong edge");
1.66 + check(G.u(e1) == rn1 && G.v(e1) == bn2, "Wrong edge");
1.67 +
1.68 + checkGraphNodeList(G, 3);
1.69 + checkGraphRedNodeList(G, 1);
1.70 + checkGraphBlueNodeList(G, 2);
1.71 + checkGraphEdgeList(G, 1);
1.72 + checkGraphArcList(G, 2);
1.73 +
1.74 + checkGraphIncEdgeArcLists(G, rn1, 1);
1.75 + checkGraphIncEdgeArcLists(G, bn1, 0);
1.76 + checkGraphIncEdgeArcLists(G, bn2, 1);
1.77 +
1.78 + checkGraphConEdgeList(G, 1);
1.79 + checkGraphConArcList(G, 2);
1.80 +
1.81 + Edge
1.82 + e2 = G.addEdge(bn1, rn1),
1.83 + e3 = G.addEdge(rn1, bn2);
1.84 + ::lemon::ignore_unused_variable_warning(e2,e3);
1.85 +
1.86 + checkGraphNodeList(G, 3);
1.87 + checkGraphRedNodeList(G, 1);
1.88 + checkGraphBlueNodeList(G, 2);
1.89 + checkGraphEdgeList(G, 3);
1.90 + checkGraphArcList(G, 6);
1.91 +
1.92 + checkGraphIncEdgeArcLists(G, rn1, 3);
1.93 + checkGraphIncEdgeArcLists(G, bn1, 1);
1.94 + checkGraphIncEdgeArcLists(G, bn2, 2);
1.95 +
1.96 + checkGraphConEdgeList(G, 3);
1.97 + checkGraphConArcList(G, 6);
1.98 +
1.99 + checkArcDirections(G);
1.100 +
1.101 + checkNodeIds(G);
1.102 + checkRedNodeIds(G);
1.103 + checkBlueNodeIds(G);
1.104 + checkArcIds(G);
1.105 + checkEdgeIds(G);
1.106 +
1.107 + checkGraphNodeMap(G);
1.108 + checkGraphRedNodeMap(G);
1.109 + checkGraphBlueNodeMap(G);
1.110 + checkGraphArcMap(G);
1.111 + checkGraphEdgeMap(G);
1.112 +}
1.113 +
1.114 +template <class BpGraph>
1.115 +void checkBpGraphErase() {
1.116 + TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
1.117 +
1.118 + BpGraph G;
1.119 + RedNode
1.120 + n1 = G.addRedNode(), n4 = G.addRedNode();
1.121 + BlueNode
1.122 + n2 = G.addBlueNode(), n3 = G.addBlueNode();
1.123 + Edge
1.124 + e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),
1.125 + e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3);
1.126 + ::lemon::ignore_unused_variable_warning(e1,e3,e4);
1.127 +
1.128 + // Check edge deletion
1.129 + G.erase(e2);
1.130 +
1.131 + checkGraphNodeList(G, 4);
1.132 + checkGraphRedNodeList(G, 2);
1.133 + checkGraphBlueNodeList(G, 2);
1.134 + checkGraphEdgeList(G, 3);
1.135 + checkGraphArcList(G, 6);
1.136 +
1.137 + checkGraphIncEdgeArcLists(G, n1, 1);
1.138 + checkGraphIncEdgeArcLists(G, n2, 2);
1.139 + checkGraphIncEdgeArcLists(G, n3, 1);
1.140 + checkGraphIncEdgeArcLists(G, n4, 2);
1.141 +
1.142 + checkGraphConEdgeList(G, 3);
1.143 + checkGraphConArcList(G, 6);
1.144 +
1.145 + // Check node deletion
1.146 + G.erase(n3);
1.147 +
1.148 + checkGraphNodeList(G, 3);
1.149 + checkGraphRedNodeList(G, 2);
1.150 + checkGraphBlueNodeList(G, 1);
1.151 + checkGraphEdgeList(G, 2);
1.152 + checkGraphArcList(G, 4);
1.153 +
1.154 + checkGraphIncEdgeArcLists(G, n1, 1);
1.155 + checkGraphIncEdgeArcLists(G, n2, 2);
1.156 + checkGraphIncEdgeArcLists(G, n4, 1);
1.157 +
1.158 + checkGraphConEdgeList(G, 2);
1.159 + checkGraphConArcList(G, 4);
1.160 +
1.161 +}
1.162 +
1.163 +template <class BpGraph>
1.164 +void checkBpGraphAlter() {
1.165 + TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
1.166 +
1.167 + BpGraph G;
1.168 + RedNode
1.169 + n1 = G.addRedNode(), n4 = G.addRedNode();
1.170 + BlueNode
1.171 + n2 = G.addBlueNode(), n3 = G.addBlueNode();
1.172 + Edge
1.173 + e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),
1.174 + e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3);
1.175 + ::lemon::ignore_unused_variable_warning(e1,e3,e4);
1.176 +
1.177 + G.changeRed(e2, n4);
1.178 + check(G.redNode(e2) == n4, "Wrong red node");
1.179 + check(G.blueNode(e2) == n3, "Wrong blue node");
1.180 +
1.181 + checkGraphNodeList(G, 4);
1.182 + checkGraphRedNodeList(G, 2);
1.183 + checkGraphBlueNodeList(G, 2);
1.184 + checkGraphEdgeList(G, 4);
1.185 + checkGraphArcList(G, 8);
1.186 +
1.187 + checkGraphIncEdgeArcLists(G, n1, 1);
1.188 + checkGraphIncEdgeArcLists(G, n2, 2);
1.189 + checkGraphIncEdgeArcLists(G, n3, 2);
1.190 + checkGraphIncEdgeArcLists(G, n4, 3);
1.191 +
1.192 + checkGraphConEdgeList(G, 4);
1.193 + checkGraphConArcList(G, 8);
1.194 +
1.195 + G.changeBlue(e2, n2);
1.196 + check(G.redNode(e2) == n4, "Wrong red node");
1.197 + check(G.blueNode(e2) == n2, "Wrong blue node");
1.198 +
1.199 + checkGraphNodeList(G, 4);
1.200 + checkGraphRedNodeList(G, 2);
1.201 + checkGraphBlueNodeList(G, 2);
1.202 + checkGraphEdgeList(G, 4);
1.203 + checkGraphArcList(G, 8);
1.204 +
1.205 + checkGraphIncEdgeArcLists(G, n1, 1);
1.206 + checkGraphIncEdgeArcLists(G, n2, 3);
1.207 + checkGraphIncEdgeArcLists(G, n3, 1);
1.208 + checkGraphIncEdgeArcLists(G, n4, 3);
1.209 +
1.210 + checkGraphConEdgeList(G, 4);
1.211 + checkGraphConArcList(G, 8);
1.212 +}
1.213 +
1.214 +
1.215 +template <class BpGraph>
1.216 +void checkBpGraphSnapshot() {
1.217 + TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
1.218 +
1.219 + BpGraph G;
1.220 + RedNode
1.221 + n1 = G.addRedNode();
1.222 + BlueNode
1.223 + n2 = G.addBlueNode(),
1.224 + n3 = G.addBlueNode();
1.225 + Edge
1.226 + e1 = G.addEdge(n1, n2),
1.227 + e2 = G.addEdge(n1, n3);
1.228 + ::lemon::ignore_unused_variable_warning(e1,e2);
1.229 +
1.230 + checkGraphNodeList(G, 3);
1.231 + checkGraphRedNodeList(G, 1);
1.232 + checkGraphBlueNodeList(G, 2);
1.233 + checkGraphEdgeList(G, 2);
1.234 + checkGraphArcList(G, 4);
1.235 +
1.236 + typename BpGraph::Snapshot snapshot(G);
1.237 +
1.238 + RedNode n4 = G.addRedNode();
1.239 + G.addEdge(n4, n2);
1.240 + G.addEdge(n4, n3);
1.241 +
1.242 + checkGraphNodeList(G, 4);
1.243 + checkGraphRedNodeList(G, 2);
1.244 + checkGraphBlueNodeList(G, 2);
1.245 + checkGraphEdgeList(G, 4);
1.246 + checkGraphArcList(G, 8);
1.247 +
1.248 + snapshot.restore();
1.249 +
1.250 + checkGraphNodeList(G, 3);
1.251 + checkGraphRedNodeList(G, 1);
1.252 + checkGraphBlueNodeList(G, 2);
1.253 + checkGraphEdgeList(G, 2);
1.254 + checkGraphArcList(G, 4);
1.255 +
1.256 + checkGraphIncEdgeArcLists(G, n1, 2);
1.257 + checkGraphIncEdgeArcLists(G, n2, 1);
1.258 + checkGraphIncEdgeArcLists(G, n3, 1);
1.259 +
1.260 + checkGraphConEdgeList(G, 2);
1.261 + checkGraphConArcList(G, 4);
1.262 +
1.263 + checkNodeIds(G);
1.264 + checkRedNodeIds(G);
1.265 + checkBlueNodeIds(G);
1.266 + checkArcIds(G);
1.267 + checkEdgeIds(G);
1.268 +
1.269 + checkGraphNodeMap(G);
1.270 + checkGraphRedNodeMap(G);
1.271 + checkGraphBlueNodeMap(G);
1.272 + checkGraphArcMap(G);
1.273 + checkGraphEdgeMap(G);
1.274 +
1.275 + G.addRedNode();
1.276 + snapshot.save(G);
1.277 +
1.278 + G.addEdge(G.addRedNode(), G.addBlueNode());
1.279 +
1.280 + snapshot.restore();
1.281 + snapshot.save(G);
1.282 +
1.283 + checkGraphNodeList(G, 4);
1.284 + checkGraphRedNodeList(G, 2);
1.285 + checkGraphBlueNodeList(G, 2);
1.286 + checkGraphEdgeList(G, 2);
1.287 + checkGraphArcList(G, 4);
1.288 +
1.289 + G.addEdge(G.addRedNode(), G.addBlueNode());
1.290 +
1.291 + snapshot.restore();
1.292 +
1.293 + checkGraphNodeList(G, 4);
1.294 + checkGraphRedNodeList(G, 2);
1.295 + checkGraphBlueNodeList(G, 2);
1.296 + checkGraphEdgeList(G, 2);
1.297 + checkGraphArcList(G, 4);
1.298 +}
1.299 +
1.300 +template <typename BpGraph>
1.301 +void checkBpGraphValidity() {
1.302 + TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
1.303 + BpGraph g;
1.304 +
1.305 + RedNode
1.306 + n1 = g.addRedNode();
1.307 + BlueNode
1.308 + n2 = g.addBlueNode(),
1.309 + n3 = g.addBlueNode();
1.310 +
1.311 + Edge
1.312 + e1 = g.addEdge(n1, n2),
1.313 + e2 = g.addEdge(n1, n3);
1.314 + ::lemon::ignore_unused_variable_warning(e2);
1.315 +
1.316 + check(g.valid(n1), "Wrong validity check");
1.317 + check(g.valid(e1), "Wrong validity check");
1.318 + check(g.valid(g.direct(e1, true)), "Wrong validity check");
1.319 +
1.320 + check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
1.321 + check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
1.322 + check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
1.323 +}
1.324 +
1.325 +void checkConcepts() {
1.326 + { // Checking graph components
1.327 + checkConcept<BaseBpGraphComponent, BaseBpGraphComponent >();
1.328 +
1.329 + checkConcept<IDableBpGraphComponent<>,
1.330 + IDableBpGraphComponent<> >();
1.331 +
1.332 + checkConcept<IterableBpGraphComponent<>,
1.333 + IterableBpGraphComponent<> >();
1.334 +
1.335 + checkConcept<AlterableBpGraphComponent<>,
1.336 + AlterableBpGraphComponent<> >();
1.337 +
1.338 + checkConcept<MappableBpGraphComponent<>,
1.339 + MappableBpGraphComponent<> >();
1.340 +
1.341 + checkConcept<ExtendableBpGraphComponent<>,
1.342 + ExtendableBpGraphComponent<> >();
1.343 +
1.344 + checkConcept<ErasableBpGraphComponent<>,
1.345 + ErasableBpGraphComponent<> >();
1.346 +
1.347 + checkConcept<ClearableBpGraphComponent<>,
1.348 + ClearableBpGraphComponent<> >();
1.349 +
1.350 + }
1.351 + { // Checking skeleton graph
1.352 + checkConcept<BpGraph, BpGraph>();
1.353 + }
1.354 + { // Checking SmartBpGraph
1.355 + checkConcept<BpGraph, SmartBpGraph>();
1.356 + checkConcept<AlterableBpGraphComponent<>, SmartBpGraph>();
1.357 + checkConcept<ExtendableBpGraphComponent<>, SmartBpGraph>();
1.358 + checkConcept<ClearableBpGraphComponent<>, SmartBpGraph>();
1.359 + }
1.360 +}
1.361 +
1.362 +void checkFullBpGraph(int redNum, int blueNum) {
1.363 + typedef FullBpGraph BpGraph;
1.364 + BPGRAPH_TYPEDEFS(BpGraph);
1.365 +
1.366 + BpGraph G(redNum, blueNum);
1.367 + checkGraphNodeList(G, redNum + blueNum);
1.368 + checkGraphRedNodeList(G, redNum);
1.369 + checkGraphBlueNodeList(G, blueNum);
1.370 + checkGraphEdgeList(G, redNum * blueNum);
1.371 + checkGraphArcList(G, 2 * redNum * blueNum);
1.372 +
1.373 + G.resize(redNum, blueNum);
1.374 + checkGraphNodeList(G, redNum + blueNum);
1.375 + checkGraphRedNodeList(G, redNum);
1.376 + checkGraphBlueNodeList(G, blueNum);
1.377 + checkGraphEdgeList(G, redNum * blueNum);
1.378 + checkGraphArcList(G, 2 * redNum * blueNum);
1.379 +
1.380 + for (RedNodeIt n(G); n != INVALID; ++n) {
1.381 + checkGraphOutArcList(G, n, blueNum);
1.382 + checkGraphInArcList(G, n, blueNum);
1.383 + checkGraphIncEdgeList(G, n, blueNum);
1.384 + }
1.385 +
1.386 + for (BlueNodeIt n(G); n != INVALID; ++n) {
1.387 + checkGraphOutArcList(G, n, redNum);
1.388 + checkGraphInArcList(G, n, redNum);
1.389 + checkGraphIncEdgeList(G, n, redNum);
1.390 + }
1.391 +
1.392 + checkGraphConArcList(G, 2 * redNum * blueNum);
1.393 + checkGraphConEdgeList(G, redNum * blueNum);
1.394 +
1.395 + checkArcDirections(G);
1.396 +
1.397 + checkNodeIds(G);
1.398 + checkRedNodeIds(G);
1.399 + checkBlueNodeIds(G);
1.400 + checkArcIds(G);
1.401 + checkEdgeIds(G);
1.402 +
1.403 + checkGraphNodeMap(G);
1.404 + checkGraphRedNodeMap(G);
1.405 + checkGraphBlueNodeMap(G);
1.406 + checkGraphArcMap(G);
1.407 + checkGraphEdgeMap(G);
1.408 +
1.409 + for (int i = 0; i < G.redNum(); ++i) {
1.410 + check(G.red(G.redNode(i)), "Wrong node");
1.411 + check(G.index(G.redNode(i)) == i, "Wrong index");
1.412 + }
1.413 +
1.414 + for (int i = 0; i < G.blueNum(); ++i) {
1.415 + check(G.blue(G.blueNode(i)), "Wrong node");
1.416 + check(G.index(G.blueNode(i)) == i, "Wrong index");
1.417 + }
1.418 +
1.419 + for (NodeIt u(G); u != INVALID; ++u) {
1.420 + for (NodeIt v(G); v != INVALID; ++v) {
1.421 + Edge e = G.edge(u, v);
1.422 + Arc a = G.arc(u, v);
1.423 + if (G.red(u) == G.red(v)) {
1.424 + check(e == INVALID, "Wrong edge lookup");
1.425 + check(a == INVALID, "Wrong arc lookup");
1.426 + } else {
1.427 + check((G.u(e) == u && G.v(e) == v) ||
1.428 + (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
1.429 + check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
1.430 + }
1.431 + }
1.432 + }
1.433 +
1.434 +}
1.435 +
1.436 +void checkGraphs() {
1.437 + { // Checking ListGraph
1.438 + checkBpGraphBuild<ListBpGraph>();
1.439 + checkBpGraphErase<ListBpGraph>();
1.440 + checkBpGraphAlter<ListBpGraph>();
1.441 + checkBpGraphSnapshot<ListBpGraph>();
1.442 + checkBpGraphValidity<ListBpGraph>();
1.443 + }
1.444 + { // Checking SmartGraph
1.445 + checkBpGraphBuild<SmartBpGraph>();
1.446 + checkBpGraphSnapshot<SmartBpGraph>();
1.447 + checkBpGraphValidity<SmartBpGraph>();
1.448 + }
1.449 + { // Checking FullBpGraph
1.450 + checkFullBpGraph(6, 8);
1.451 + checkFullBpGraph(7, 4);
1.452 + }
1.453 +}
1.454 +
1.455 +int main() {
1.456 + checkConcepts();
1.457 + checkGraphs();
1.458 + return 0;
1.459 +}