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