test/edge_set_test.cc
changeset 469 04c0631fd332
child 488 9b9ffe7d9b75
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/test/edge_set_test.cc	Mon Jan 12 13:37:37 2009 +0000
     1.3 @@ -0,0 +1,380 @@
     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-2008
     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 <iostream>
    1.23 +#include <vector>
    1.24 +
    1.25 +#include <lemon/concepts/digraph.h>
    1.26 +#include <lemon/concepts/graph.h>
    1.27 +#include <lemon/concept_check.h>
    1.28 +
    1.29 +#include <lemon/list_graph.h>
    1.30 +
    1.31 +#include <lemon/edge_set.h>
    1.32 +
    1.33 +#include "graph_test.h"
    1.34 +#include "test_tools.h"
    1.35 +
    1.36 +using namespace lemon;
    1.37 +
    1.38 +void checkSmartArcSet() {
    1.39 +  checkConcept<concepts::Digraph, SmartArcSet<concepts::Digraph> >();
    1.40 +
    1.41 +  typedef ListDigraph Digraph;
    1.42 +  typedef SmartArcSet<Digraph> ArcSet;
    1.43 +
    1.44 +  Digraph digraph;
    1.45 +  Digraph::Node
    1.46 +    n1 = digraph.addNode(),
    1.47 +    n2 = digraph.addNode();
    1.48 +
    1.49 +  Digraph::Arc ga1 = digraph.addArc(n1, n2);
    1.50 +
    1.51 +  ArcSet arc_set(digraph);
    1.52 +
    1.53 +  Digraph::Arc ga2 = digraph.addArc(n2, n1);
    1.54 +
    1.55 +  checkGraphNodeList(arc_set, 2);
    1.56 +  checkGraphArcList(arc_set, 0);
    1.57 +
    1.58 +  Digraph::Node
    1.59 +    n3 = digraph.addNode();
    1.60 +  checkGraphNodeList(arc_set, 3);
    1.61 +  checkGraphArcList(arc_set, 0);
    1.62 +
    1.63 +  ArcSet::Arc a1 = arc_set.addArc(n1, n2);
    1.64 +  check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc");
    1.65 +  checkGraphNodeList(arc_set, 3);
    1.66 +  checkGraphArcList(arc_set, 1);
    1.67 +
    1.68 +  checkGraphOutArcList(arc_set, n1, 1);
    1.69 +  checkGraphOutArcList(arc_set, n2, 0);
    1.70 +  checkGraphOutArcList(arc_set, n3, 0);
    1.71 +
    1.72 +  checkGraphInArcList(arc_set, n1, 0);
    1.73 +  checkGraphInArcList(arc_set, n2, 1);
    1.74 +  checkGraphInArcList(arc_set, n3, 0);
    1.75 +
    1.76 +  checkGraphConArcList(arc_set, 1);
    1.77 +
    1.78 +  ArcSet::Arc a2 = arc_set.addArc(n2, n1),
    1.79 +    a3 = arc_set.addArc(n2, n3),
    1.80 +    a4 = arc_set.addArc(n2, n3);
    1.81 +  checkGraphNodeList(arc_set, 3);
    1.82 +  checkGraphArcList(arc_set, 4);
    1.83 +
    1.84 +  checkGraphOutArcList(arc_set, n1, 1);
    1.85 +  checkGraphOutArcList(arc_set, n2, 3);
    1.86 +  checkGraphOutArcList(arc_set, n3, 0);
    1.87 +
    1.88 +  checkGraphInArcList(arc_set, n1, 1);
    1.89 +  checkGraphInArcList(arc_set, n2, 1);
    1.90 +  checkGraphInArcList(arc_set, n3, 2);
    1.91 +
    1.92 +  checkGraphConArcList(arc_set, 4);
    1.93 +
    1.94 +  checkNodeIds(arc_set);
    1.95 +  checkArcIds(arc_set);
    1.96 +  checkGraphNodeMap(arc_set);
    1.97 +  checkGraphArcMap(arc_set);
    1.98 +
    1.99 +  check(arc_set.valid(), "Wrong validity");
   1.100 +  digraph.erase(n1);
   1.101 +  check(!arc_set.valid(), "Wrong validity");
   1.102 +}
   1.103 +
   1.104 +void checkListArcSet() {
   1.105 +  checkConcept<concepts::Digraph, SmartArcSet<concepts::Digraph> >();
   1.106 +
   1.107 +  typedef ListDigraph Digraph;
   1.108 +  typedef ListArcSet<Digraph> ArcSet;
   1.109 +
   1.110 +  Digraph digraph;
   1.111 +  Digraph::Node
   1.112 +    n1 = digraph.addNode(),
   1.113 +    n2 = digraph.addNode();
   1.114 +
   1.115 +  Digraph::Arc ga1 = digraph.addArc(n1, n2);
   1.116 +
   1.117 +  ArcSet arc_set(digraph);
   1.118 +
   1.119 +  Digraph::Arc ga2 = digraph.addArc(n2, n1);
   1.120 +
   1.121 +  checkGraphNodeList(arc_set, 2);
   1.122 +  checkGraphArcList(arc_set, 0);
   1.123 +
   1.124 +  Digraph::Node
   1.125 +    n3 = digraph.addNode();
   1.126 +  checkGraphNodeList(arc_set, 3);
   1.127 +  checkGraphArcList(arc_set, 0);
   1.128 +
   1.129 +  ArcSet::Arc a1 = arc_set.addArc(n1, n2);
   1.130 +  check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc");
   1.131 +  checkGraphNodeList(arc_set, 3);
   1.132 +  checkGraphArcList(arc_set, 1);
   1.133 +
   1.134 +  checkGraphOutArcList(arc_set, n1, 1);
   1.135 +  checkGraphOutArcList(arc_set, n2, 0);
   1.136 +  checkGraphOutArcList(arc_set, n3, 0);
   1.137 +
   1.138 +  checkGraphInArcList(arc_set, n1, 0);
   1.139 +  checkGraphInArcList(arc_set, n2, 1);
   1.140 +  checkGraphInArcList(arc_set, n3, 0);
   1.141 +
   1.142 +  checkGraphConArcList(arc_set, 1);
   1.143 +
   1.144 +  ArcSet::Arc a2 = arc_set.addArc(n2, n1),
   1.145 +    a3 = arc_set.addArc(n2, n3),
   1.146 +    a4 = arc_set.addArc(n2, n3);
   1.147 +  checkGraphNodeList(arc_set, 3);
   1.148 +  checkGraphArcList(arc_set, 4);
   1.149 +
   1.150 +  checkGraphOutArcList(arc_set, n1, 1);
   1.151 +  checkGraphOutArcList(arc_set, n2, 3);
   1.152 +  checkGraphOutArcList(arc_set, n3, 0);
   1.153 +
   1.154 +  checkGraphInArcList(arc_set, n1, 1);
   1.155 +  checkGraphInArcList(arc_set, n2, 1);
   1.156 +  checkGraphInArcList(arc_set, n3, 2);
   1.157 +
   1.158 +  checkGraphConArcList(arc_set, 4);
   1.159 +
   1.160 +  checkNodeIds(arc_set);
   1.161 +  checkArcIds(arc_set);
   1.162 +  checkGraphNodeMap(arc_set);
   1.163 +  checkGraphArcMap(arc_set);
   1.164 +
   1.165 +  digraph.erase(n1);
   1.166 +
   1.167 +  checkGraphNodeList(arc_set, 2);
   1.168 +  checkGraphArcList(arc_set, 2);
   1.169 +
   1.170 +  checkGraphOutArcList(arc_set, n2, 2);
   1.171 +  checkGraphOutArcList(arc_set, n3, 0);
   1.172 +
   1.173 +  checkGraphInArcList(arc_set, n2, 0);
   1.174 +  checkGraphInArcList(arc_set, n3, 2);
   1.175 +
   1.176 +  checkNodeIds(arc_set);
   1.177 +  checkArcIds(arc_set);
   1.178 +  checkGraphNodeMap(arc_set);
   1.179 +  checkGraphArcMap(arc_set);
   1.180 +
   1.181 +  checkGraphConArcList(arc_set, 2);
   1.182 +}
   1.183 +
   1.184 +void checkSmartEdgeSet() {
   1.185 +  checkConcept<concepts::Digraph, SmartEdgeSet<concepts::Digraph> >();
   1.186 +
   1.187 +  typedef ListDigraph Digraph;
   1.188 +  typedef SmartEdgeSet<Digraph> EdgeSet;
   1.189 +
   1.190 +  Digraph digraph;
   1.191 +  Digraph::Node
   1.192 +    n1 = digraph.addNode(),
   1.193 +    n2 = digraph.addNode();
   1.194 +
   1.195 +  Digraph::Arc ga1 = digraph.addArc(n1, n2);
   1.196 +
   1.197 +  EdgeSet edge_set(digraph);
   1.198 +
   1.199 +  Digraph::Arc ga2 = digraph.addArc(n2, n1);
   1.200 +
   1.201 +  checkGraphNodeList(edge_set, 2);
   1.202 +  checkGraphArcList(edge_set, 0);
   1.203 +  checkGraphEdgeList(edge_set, 0);
   1.204 +
   1.205 +  Digraph::Node
   1.206 +    n3 = digraph.addNode();
   1.207 +  checkGraphNodeList(edge_set, 3);
   1.208 +  checkGraphArcList(edge_set, 0);
   1.209 +  checkGraphEdgeList(edge_set, 0);
   1.210 +
   1.211 +  EdgeSet::Edge e1 = edge_set.addEdge(n1, n2);
   1.212 +  check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) ||
   1.213 +        (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge");
   1.214 +  checkGraphNodeList(edge_set, 3);
   1.215 +  checkGraphArcList(edge_set, 2);
   1.216 +  checkGraphEdgeList(edge_set, 1);
   1.217 +
   1.218 +  checkGraphOutArcList(edge_set, n1, 1);
   1.219 +  checkGraphOutArcList(edge_set, n2, 1);
   1.220 +  checkGraphOutArcList(edge_set, n3, 0);
   1.221 +
   1.222 +  checkGraphInArcList(edge_set, n1, 1);
   1.223 +  checkGraphInArcList(edge_set, n2, 1);
   1.224 +  checkGraphInArcList(edge_set, n3, 0);
   1.225 +
   1.226 +  checkGraphIncEdgeList(edge_set, n1, 1);
   1.227 +  checkGraphIncEdgeList(edge_set, n2, 1);
   1.228 +  checkGraphIncEdgeList(edge_set, n3, 0);
   1.229 +
   1.230 +  checkGraphConEdgeList(edge_set, 1);
   1.231 +  checkGraphConArcList(edge_set, 2);
   1.232 +
   1.233 +  EdgeSet::Edge e2 = edge_set.addEdge(n2, n1),
   1.234 +    e3 = edge_set.addEdge(n2, n3),
   1.235 +    e4 = edge_set.addEdge(n2, n3);
   1.236 +  checkGraphNodeList(edge_set, 3);
   1.237 +  checkGraphEdgeList(edge_set, 4);
   1.238 +
   1.239 +  checkGraphOutArcList(edge_set, n1, 2);
   1.240 +  checkGraphOutArcList(edge_set, n2, 4);
   1.241 +  checkGraphOutArcList(edge_set, n3, 2);
   1.242 +
   1.243 +  checkGraphInArcList(edge_set, n1, 2);
   1.244 +  checkGraphInArcList(edge_set, n2, 4);
   1.245 +  checkGraphInArcList(edge_set, n3, 2);
   1.246 +
   1.247 +  checkGraphIncEdgeList(edge_set, n1, 2);
   1.248 +  checkGraphIncEdgeList(edge_set, n2, 4);
   1.249 +  checkGraphIncEdgeList(edge_set, n3, 2);
   1.250 +
   1.251 +  checkGraphConEdgeList(edge_set, 4);
   1.252 +  checkGraphConArcList(edge_set, 8);
   1.253 +
   1.254 +  checkArcDirections(edge_set);
   1.255 +
   1.256 +  checkNodeIds(edge_set);
   1.257 +  checkArcIds(edge_set);
   1.258 +  checkEdgeIds(edge_set);
   1.259 +  checkGraphNodeMap(edge_set);
   1.260 +  checkGraphArcMap(edge_set);
   1.261 +  checkGraphEdgeMap(edge_set);
   1.262 +
   1.263 +  check(edge_set.valid(), "Wrong validity");
   1.264 +  digraph.erase(n1);
   1.265 +  check(!edge_set.valid(), "Wrong validity");
   1.266 +}
   1.267 +
   1.268 +void checkListEdgeSet() {
   1.269 +  checkConcept<concepts::Digraph, ListEdgeSet<concepts::Digraph> >();
   1.270 +
   1.271 +  typedef ListDigraph Digraph;
   1.272 +  typedef ListEdgeSet<Digraph> EdgeSet;
   1.273 +
   1.274 +  Digraph digraph;
   1.275 +  Digraph::Node
   1.276 +    n1 = digraph.addNode(),
   1.277 +    n2 = digraph.addNode();
   1.278 +
   1.279 +  Digraph::Arc ga1 = digraph.addArc(n1, n2);
   1.280 +
   1.281 +  EdgeSet edge_set(digraph);
   1.282 +
   1.283 +  Digraph::Arc ga2 = digraph.addArc(n2, n1);
   1.284 +
   1.285 +  checkGraphNodeList(edge_set, 2);
   1.286 +  checkGraphArcList(edge_set, 0);
   1.287 +  checkGraphEdgeList(edge_set, 0);
   1.288 +
   1.289 +  Digraph::Node
   1.290 +    n3 = digraph.addNode();
   1.291 +  checkGraphNodeList(edge_set, 3);
   1.292 +  checkGraphArcList(edge_set, 0);
   1.293 +  checkGraphEdgeList(edge_set, 0);
   1.294 +
   1.295 +  EdgeSet::Edge e1 = edge_set.addEdge(n1, n2);
   1.296 +  check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) ||
   1.297 +        (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge");
   1.298 +  checkGraphNodeList(edge_set, 3);
   1.299 +  checkGraphArcList(edge_set, 2);
   1.300 +  checkGraphEdgeList(edge_set, 1);
   1.301 +
   1.302 +  checkGraphOutArcList(edge_set, n1, 1);
   1.303 +  checkGraphOutArcList(edge_set, n2, 1);
   1.304 +  checkGraphOutArcList(edge_set, n3, 0);
   1.305 +
   1.306 +  checkGraphInArcList(edge_set, n1, 1);
   1.307 +  checkGraphInArcList(edge_set, n2, 1);
   1.308 +  checkGraphInArcList(edge_set, n3, 0);
   1.309 +
   1.310 +  checkGraphIncEdgeList(edge_set, n1, 1);
   1.311 +  checkGraphIncEdgeList(edge_set, n2, 1);
   1.312 +  checkGraphIncEdgeList(edge_set, n3, 0);
   1.313 +
   1.314 +  checkGraphConEdgeList(edge_set, 1);
   1.315 +  checkGraphConArcList(edge_set, 2);
   1.316 +
   1.317 +  EdgeSet::Edge e2 = edge_set.addEdge(n2, n1),
   1.318 +    e3 = edge_set.addEdge(n2, n3),
   1.319 +    e4 = edge_set.addEdge(n2, n3);
   1.320 +  checkGraphNodeList(edge_set, 3);
   1.321 +  checkGraphEdgeList(edge_set, 4);
   1.322 +
   1.323 +  checkGraphOutArcList(edge_set, n1, 2);
   1.324 +  checkGraphOutArcList(edge_set, n2, 4);
   1.325 +  checkGraphOutArcList(edge_set, n3, 2);
   1.326 +
   1.327 +  checkGraphInArcList(edge_set, n1, 2);
   1.328 +  checkGraphInArcList(edge_set, n2, 4);
   1.329 +  checkGraphInArcList(edge_set, n3, 2);
   1.330 +
   1.331 +  checkGraphIncEdgeList(edge_set, n1, 2);
   1.332 +  checkGraphIncEdgeList(edge_set, n2, 4);
   1.333 +  checkGraphIncEdgeList(edge_set, n3, 2);
   1.334 +
   1.335 +  checkGraphConEdgeList(edge_set, 4);
   1.336 +  checkGraphConArcList(edge_set, 8);
   1.337 +
   1.338 +  checkArcDirections(edge_set);
   1.339 +
   1.340 +  checkNodeIds(edge_set);
   1.341 +  checkArcIds(edge_set);
   1.342 +  checkEdgeIds(edge_set);
   1.343 +  checkGraphNodeMap(edge_set);
   1.344 +  checkGraphArcMap(edge_set);
   1.345 +  checkGraphEdgeMap(edge_set);
   1.346 +
   1.347 +  digraph.erase(n1);
   1.348 +
   1.349 +  checkGraphNodeList(edge_set, 2);
   1.350 +  checkGraphArcList(edge_set, 4);
   1.351 +  checkGraphEdgeList(edge_set, 2);
   1.352 +
   1.353 +  checkGraphOutArcList(edge_set, n2, 2);
   1.354 +  checkGraphOutArcList(edge_set, n3, 2);
   1.355 +
   1.356 +  checkGraphInArcList(edge_set, n2, 2);
   1.357 +  checkGraphInArcList(edge_set, n3, 2);
   1.358 +
   1.359 +  checkGraphIncEdgeList(edge_set, n2, 2);
   1.360 +  checkGraphIncEdgeList(edge_set, n3, 2);
   1.361 +
   1.362 +  checkNodeIds(edge_set);
   1.363 +  checkArcIds(edge_set);
   1.364 +  checkEdgeIds(edge_set);
   1.365 +  checkGraphNodeMap(edge_set);
   1.366 +  checkGraphArcMap(edge_set);
   1.367 +  checkGraphEdgeMap(edge_set);
   1.368 +
   1.369 +  checkGraphConEdgeList(edge_set, 2);
   1.370 +  checkGraphConArcList(edge_set, 4);
   1.371 +
   1.372 +}
   1.373 +
   1.374 +
   1.375 +int main() {
   1.376 +
   1.377 +  checkSmartArcSet();
   1.378 +  checkListArcSet();
   1.379 +  checkSmartEdgeSet();
   1.380 +  checkListEdgeSet();
   1.381 +
   1.382 +  return 0;
   1.383 +}