1.1 --- a/test/digraph_test.cc Fri Nov 13 12:33:33 2009 +0100
1.2 +++ b/test/digraph_test.cc Thu Dec 10 17:05:35 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,7 @@
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/full_graph.h>
1.19
1.20 #include "test_tools.h"
1.21 #include "graph_test.h"
1.22 @@ -29,7 +28,7 @@
1.23 using namespace lemon::concepts;
1.24
1.25 template <class Digraph>
1.26 -void checkDigraph() {
1.27 +void checkDigraphBuild() {
1.28 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.29 Digraph G;
1.30
1.31 @@ -58,7 +57,208 @@
1.32
1.33 checkGraphConArcList(G, 1);
1.34
1.35 - Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
1.36 + Arc a2 = G.addArc(n2, n1),
1.37 + a3 = G.addArc(n2, n3),
1.38 + a4 = G.addArc(n2, n3);
1.39 +
1.40 + checkGraphNodeList(G, 3);
1.41 + checkGraphArcList(G, 4);
1.42 +
1.43 + checkGraphOutArcList(G, n1, 1);
1.44 + checkGraphOutArcList(G, n2, 3);
1.45 + checkGraphOutArcList(G, n3, 0);
1.46 +
1.47 + checkGraphInArcList(G, n1, 1);
1.48 + checkGraphInArcList(G, n2, 1);
1.49 + checkGraphInArcList(G, n3, 2);
1.50 +
1.51 + checkGraphConArcList(G, 4);
1.52 +
1.53 + checkNodeIds(G);
1.54 + checkArcIds(G);
1.55 + checkGraphNodeMap(G);
1.56 + checkGraphArcMap(G);
1.57 +}
1.58 +
1.59 +template <class Digraph>
1.60 +void checkDigraphSplit() {
1.61 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.62 +
1.63 + Digraph G;
1.64 + Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
1.65 + Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
1.66 + a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
1.67 +
1.68 + Node n4 = G.split(n2);
1.69 +
1.70 + check(G.target(OutArcIt(G, n2)) == n4 &&
1.71 + G.source(InArcIt(G, n4)) == n2,
1.72 + "Wrong split.");
1.73 +
1.74 + checkGraphNodeList(G, 4);
1.75 + checkGraphArcList(G, 5);
1.76 +
1.77 + checkGraphOutArcList(G, n1, 1);
1.78 + checkGraphOutArcList(G, n2, 1);
1.79 + checkGraphOutArcList(G, n3, 0);
1.80 + checkGraphOutArcList(G, n4, 3);
1.81 +
1.82 + checkGraphInArcList(G, n1, 1);
1.83 + checkGraphInArcList(G, n2, 1);
1.84 + checkGraphInArcList(G, n3, 2);
1.85 + checkGraphInArcList(G, n4, 1);
1.86 +
1.87 + checkGraphConArcList(G, 5);
1.88 +}
1.89 +
1.90 +template <class Digraph>
1.91 +void checkDigraphAlter() {
1.92 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.93 +
1.94 + Digraph G;
1.95 + Node n1 = G.addNode(), n2 = G.addNode(),
1.96 + n3 = G.addNode(), n4 = G.addNode();
1.97 + Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
1.98 + a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),
1.99 + a5 = G.addArc(n2, n4);
1.100 +
1.101 + checkGraphNodeList(G, 4);
1.102 + checkGraphArcList(G, 5);
1.103 +
1.104 + // Check changeSource() and changeTarget()
1.105 + G.changeTarget(a4, n1);
1.106 +
1.107 + checkGraphNodeList(G, 4);
1.108 + checkGraphArcList(G, 5);
1.109 +
1.110 + checkGraphOutArcList(G, n1, 1);
1.111 + checkGraphOutArcList(G, n2, 1);
1.112 + checkGraphOutArcList(G, n3, 0);
1.113 + checkGraphOutArcList(G, n4, 3);
1.114 +
1.115 + checkGraphInArcList(G, n1, 2);
1.116 + checkGraphInArcList(G, n2, 1);
1.117 + checkGraphInArcList(G, n3, 1);
1.118 + checkGraphInArcList(G, n4, 1);
1.119 +
1.120 + checkGraphConArcList(G, 5);
1.121 +
1.122 + G.changeSource(a4, n3);
1.123 +
1.124 + checkGraphNodeList(G, 4);
1.125 + checkGraphArcList(G, 5);
1.126 +
1.127 + checkGraphOutArcList(G, n1, 1);
1.128 + checkGraphOutArcList(G, n2, 1);
1.129 + checkGraphOutArcList(G, n3, 1);
1.130 + checkGraphOutArcList(G, n4, 2);
1.131 +
1.132 + checkGraphInArcList(G, n1, 2);
1.133 + checkGraphInArcList(G, n2, 1);
1.134 + checkGraphInArcList(G, n3, 1);
1.135 + checkGraphInArcList(G, n4, 1);
1.136 +
1.137 + checkGraphConArcList(G, 5);
1.138 +
1.139 + // Check contract()
1.140 + G.contract(n2, n4, false);
1.141 +
1.142 + checkGraphNodeList(G, 3);
1.143 + checkGraphArcList(G, 5);
1.144 +
1.145 + checkGraphOutArcList(G, n1, 1);
1.146 + checkGraphOutArcList(G, n2, 3);
1.147 + checkGraphOutArcList(G, n3, 1);
1.148 +
1.149 + checkGraphInArcList(G, n1, 2);
1.150 + checkGraphInArcList(G, n2, 2);
1.151 + checkGraphInArcList(G, n3, 1);
1.152 +
1.153 + checkGraphConArcList(G, 5);
1.154 +
1.155 + G.contract(n2, n1);
1.156 +
1.157 + checkGraphNodeList(G, 2);
1.158 + checkGraphArcList(G, 3);
1.159 +
1.160 + checkGraphOutArcList(G, n2, 2);
1.161 + checkGraphOutArcList(G, n3, 1);
1.162 +
1.163 + checkGraphInArcList(G, n2, 2);
1.164 + checkGraphInArcList(G, n3, 1);
1.165 +
1.166 + checkGraphConArcList(G, 3);
1.167 +}
1.168 +
1.169 +template <class Digraph>
1.170 +void checkDigraphErase() {
1.171 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.172 +
1.173 + Digraph G;
1.174 + Node n1 = G.addNode(), n2 = G.addNode(),
1.175 + n3 = G.addNode(), n4 = G.addNode();
1.176 + Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
1.177 + a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1),
1.178 + a5 = G.addArc(n2, n4);
1.179 +
1.180 + // Check arc deletion
1.181 + G.erase(a1);
1.182 +
1.183 + checkGraphNodeList(G, 4);
1.184 + checkGraphArcList(G, 4);
1.185 +
1.186 + checkGraphOutArcList(G, n1, 0);
1.187 + checkGraphOutArcList(G, n2, 1);
1.188 + checkGraphOutArcList(G, n3, 1);
1.189 + checkGraphOutArcList(G, n4, 2);
1.190 +
1.191 + checkGraphInArcList(G, n1, 2);
1.192 + checkGraphInArcList(G, n2, 0);
1.193 + checkGraphInArcList(G, n3, 1);
1.194 + checkGraphInArcList(G, n4, 1);
1.195 +
1.196 + checkGraphConArcList(G, 4);
1.197 +
1.198 + // Check node deletion
1.199 + G.erase(n4);
1.200 +
1.201 + checkGraphNodeList(G, 3);
1.202 + checkGraphArcList(G, 1);
1.203 +
1.204 + checkGraphOutArcList(G, n1, 0);
1.205 + checkGraphOutArcList(G, n2, 0);
1.206 + checkGraphOutArcList(G, n3, 1);
1.207 + checkGraphOutArcList(G, n4, 0);
1.208 +
1.209 + checkGraphInArcList(G, n1, 1);
1.210 + checkGraphInArcList(G, n2, 0);
1.211 + checkGraphInArcList(G, n3, 0);
1.212 + checkGraphInArcList(G, n4, 0);
1.213 +
1.214 + checkGraphConArcList(G, 1);
1.215 +}
1.216 +
1.217 +
1.218 +template <class Digraph>
1.219 +void checkDigraphSnapshot() {
1.220 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.221 +
1.222 + Digraph G;
1.223 + Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
1.224 + Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
1.225 + a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
1.226 +
1.227 + typename Digraph::Snapshot snapshot(G);
1.228 +
1.229 + Node n = G.addNode();
1.230 + G.addArc(n3, n);
1.231 + G.addArc(n, n3);
1.232 +
1.233 + checkGraphNodeList(G, 4);
1.234 + checkGraphArcList(G, 6);
1.235 +
1.236 + snapshot.restore();
1.237 +
1.238 checkGraphNodeList(G, 3);
1.239 checkGraphArcList(G, 4);
1.240
1.241 @@ -77,9 +277,17 @@
1.242 checkGraphNodeMap(G);
1.243 checkGraphArcMap(G);
1.244
1.245 + G.addNode();
1.246 + snapshot.save(G);
1.247 +
1.248 + G.addArc(G.addNode(), G.addNode());
1.249 +
1.250 + snapshot.restore();
1.251 +
1.252 + checkGraphNodeList(G, 4);
1.253 + checkGraphArcList(G, 4);
1.254 }
1.255
1.256 -
1.257 void checkConcepts() {
1.258 { // Checking digraph components
1.259 checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
1.260 @@ -109,12 +317,9 @@
1.261 checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
1.262 checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
1.263 }
1.264 -// { // Checking FullDigraph
1.265 -// checkConcept<Digraph, FullDigraph>();
1.266 -// }
1.267 -// { // Checking HyperCubeDigraph
1.268 -// checkConcept<Digraph, HyperCubeDigraph>();
1.269 -// }
1.270 + { // Checking FullDigraph
1.271 + checkConcept<Digraph, FullDigraph>();
1.272 + }
1.273 }
1.274
1.275 template <typename Digraph>
1.276 @@ -167,15 +372,56 @@
1.277 check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
1.278 }
1.279
1.280 +void checkFullDigraph(int num) {
1.281 + typedef FullDigraph Digraph;
1.282 + DIGRAPH_TYPEDEFS(Digraph);
1.283 + Digraph G(num);
1.284 +
1.285 + checkGraphNodeList(G, num);
1.286 + checkGraphArcList(G, num * num);
1.287 +
1.288 + for (NodeIt n(G); n != INVALID; ++n) {
1.289 + checkGraphOutArcList(G, n, num);
1.290 + checkGraphInArcList(G, n, num);
1.291 + }
1.292 +
1.293 + checkGraphConArcList(G, num * num);
1.294 +
1.295 + checkNodeIds(G);
1.296 + checkArcIds(G);
1.297 + checkGraphNodeMap(G);
1.298 + checkGraphArcMap(G);
1.299 +
1.300 + for (int i = 0; i < G.nodeNum(); ++i) {
1.301 + check(G.index(G(i)) == i, "Wrong index");
1.302 + }
1.303 +
1.304 + for (NodeIt s(G); s != INVALID; ++s) {
1.305 + for (NodeIt t(G); t != INVALID; ++t) {
1.306 + Arc a = G.arc(s, t);
1.307 + check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
1.308 + }
1.309 + }
1.310 +}
1.311 +
1.312 void checkDigraphs() {
1.313 { // Checking ListDigraph
1.314 - checkDigraph<ListDigraph>();
1.315 + checkDigraphBuild<ListDigraph>();
1.316 + checkDigraphSplit<ListDigraph>();
1.317 + checkDigraphAlter<ListDigraph>();
1.318 + checkDigraphErase<ListDigraph>();
1.319 + checkDigraphSnapshot<ListDigraph>();
1.320 checkDigraphValidityErase<ListDigraph>();
1.321 }
1.322 { // Checking SmartDigraph
1.323 - checkDigraph<SmartDigraph>();
1.324 + checkDigraphBuild<SmartDigraph>();
1.325 + checkDigraphSplit<SmartDigraph>();
1.326 + checkDigraphSnapshot<SmartDigraph>();
1.327 checkDigraphValidity<SmartDigraph>();
1.328 }
1.329 + { // Checking FullDigraph
1.330 + checkFullDigraph(8);
1.331 + }
1.332 }
1.333
1.334 int main() {