test/graph_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 22 Aug 2010 23:54:10 +0200
changeset 895 dca9eed2c375
parent 740 819ca5b50de0
child 998 7fdaa05a69a1
permissions -rw-r--r--
Improve the tree update process and a pivot rule (#391)
and make some parts of the code clearer using better names
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <lemon/concepts/graph.h>
    20 #include <lemon/list_graph.h>
    21 #include <lemon/smart_graph.h>
    22 #include <lemon/full_graph.h>
    23 #include <lemon/grid_graph.h>
    24 #include <lemon/hypercube_graph.h>
    25 
    26 #include "test_tools.h"
    27 #include "graph_test.h"
    28 
    29 using namespace lemon;
    30 using namespace lemon::concepts;
    31 
    32 template <class Graph>
    33 void checkGraphBuild() {
    34   TEMPLATE_GRAPH_TYPEDEFS(Graph);
    35 
    36   Graph G;
    37   checkGraphNodeList(G, 0);
    38   checkGraphEdgeList(G, 0);
    39   checkGraphArcList(G, 0);
    40 
    41   G.reserveNode(3);
    42   G.reserveEdge(3);
    43 
    44   Node
    45     n1 = G.addNode(),
    46     n2 = G.addNode(),
    47     n3 = G.addNode();
    48   checkGraphNodeList(G, 3);
    49   checkGraphEdgeList(G, 0);
    50   checkGraphArcList(G, 0);
    51 
    52   Edge e1 = G.addEdge(n1, n2);
    53   check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
    54         "Wrong edge");
    55 
    56   checkGraphNodeList(G, 3);
    57   checkGraphEdgeList(G, 1);
    58   checkGraphArcList(G, 2);
    59 
    60   checkGraphIncEdgeArcLists(G, n1, 1);
    61   checkGraphIncEdgeArcLists(G, n2, 1);
    62   checkGraphIncEdgeArcLists(G, n3, 0);
    63 
    64   checkGraphConEdgeList(G, 1);
    65   checkGraphConArcList(G, 2);
    66 
    67   Edge e2 = G.addEdge(n2, n1),
    68        e3 = G.addEdge(n2, n3);
    69 
    70   checkGraphNodeList(G, 3);
    71   checkGraphEdgeList(G, 3);
    72   checkGraphArcList(G, 6);
    73 
    74   checkGraphIncEdgeArcLists(G, n1, 2);
    75   checkGraphIncEdgeArcLists(G, n2, 3);
    76   checkGraphIncEdgeArcLists(G, n3, 1);
    77 
    78   checkGraphConEdgeList(G, 3);
    79   checkGraphConArcList(G, 6);
    80 
    81   checkArcDirections(G);
    82 
    83   checkNodeIds(G);
    84   checkArcIds(G);
    85   checkEdgeIds(G);
    86   checkGraphNodeMap(G);
    87   checkGraphArcMap(G);
    88   checkGraphEdgeMap(G);
    89 }
    90 
    91 template <class Graph>
    92 void checkGraphAlter() {
    93   TEMPLATE_GRAPH_TYPEDEFS(Graph);
    94 
    95   Graph G;
    96   Node n1 = G.addNode(), n2 = G.addNode(),
    97        n3 = G.addNode(), n4 = G.addNode();
    98   Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
    99        e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
   100        e5 = G.addEdge(n4, n3);
   101 
   102   checkGraphNodeList(G, 4);
   103   checkGraphEdgeList(G, 5);
   104   checkGraphArcList(G, 10);
   105 
   106   // Check changeU() and changeV()
   107   if (G.u(e2) == n2) {
   108     G.changeU(e2, n3);
   109   } else {
   110     G.changeV(e2, n3);
   111   }
   112 
   113   checkGraphNodeList(G, 4);
   114   checkGraphEdgeList(G, 5);
   115   checkGraphArcList(G, 10);
   116 
   117   checkGraphIncEdgeArcLists(G, n1, 3);
   118   checkGraphIncEdgeArcLists(G, n2, 2);
   119   checkGraphIncEdgeArcLists(G, n3, 3);
   120   checkGraphIncEdgeArcLists(G, n4, 2);
   121 
   122   checkGraphConEdgeList(G, 5);
   123   checkGraphConArcList(G, 10);
   124 
   125   if (G.u(e2) == n1) {
   126     G.changeU(e2, n2);
   127   } else {
   128     G.changeV(e2, n2);
   129   }
   130 
   131   checkGraphNodeList(G, 4);
   132   checkGraphEdgeList(G, 5);
   133   checkGraphArcList(G, 10);
   134 
   135   checkGraphIncEdgeArcLists(G, n1, 2);
   136   checkGraphIncEdgeArcLists(G, n2, 3);
   137   checkGraphIncEdgeArcLists(G, n3, 3);
   138   checkGraphIncEdgeArcLists(G, n4, 2);
   139 
   140   checkGraphConEdgeList(G, 5);
   141   checkGraphConArcList(G, 10);
   142 
   143   // Check contract()
   144   G.contract(n1, n4, false);
   145 
   146   checkGraphNodeList(G, 3);
   147   checkGraphEdgeList(G, 5);
   148   checkGraphArcList(G, 10);
   149 
   150   checkGraphIncEdgeArcLists(G, n1, 4);
   151   checkGraphIncEdgeArcLists(G, n2, 3);
   152   checkGraphIncEdgeArcLists(G, n3, 3);
   153 
   154   checkGraphConEdgeList(G, 5);
   155   checkGraphConArcList(G, 10);
   156 
   157   G.contract(n2, n3);
   158 
   159   checkGraphNodeList(G, 2);
   160   checkGraphEdgeList(G, 3);
   161   checkGraphArcList(G, 6);
   162 
   163   checkGraphIncEdgeArcLists(G, n1, 4);
   164   checkGraphIncEdgeArcLists(G, n2, 2);
   165 
   166   checkGraphConEdgeList(G, 3);
   167   checkGraphConArcList(G, 6);
   168 }
   169 
   170 template <class Graph>
   171 void checkGraphErase() {
   172   TEMPLATE_GRAPH_TYPEDEFS(Graph);
   173 
   174   Graph G;
   175   Node n1 = G.addNode(), n2 = G.addNode(),
   176        n3 = G.addNode(), n4 = G.addNode();
   177   Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
   178        e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
   179        e5 = G.addEdge(n4, n3);
   180 
   181   // Check edge deletion
   182   G.erase(e2);
   183 
   184   checkGraphNodeList(G, 4);
   185   checkGraphEdgeList(G, 4);
   186   checkGraphArcList(G, 8);
   187 
   188   checkGraphIncEdgeArcLists(G, n1, 2);
   189   checkGraphIncEdgeArcLists(G, n2, 2);
   190   checkGraphIncEdgeArcLists(G, n3, 2);
   191   checkGraphIncEdgeArcLists(G, n4, 2);
   192 
   193   checkGraphConEdgeList(G, 4);
   194   checkGraphConArcList(G, 8);
   195 
   196   // Check node deletion
   197   G.erase(n3);
   198 
   199   checkGraphNodeList(G, 3);
   200   checkGraphEdgeList(G, 2);
   201   checkGraphArcList(G, 4);
   202 
   203   checkGraphIncEdgeArcLists(G, n1, 2);
   204   checkGraphIncEdgeArcLists(G, n2, 1);
   205   checkGraphIncEdgeArcLists(G, n4, 1);
   206 
   207   checkGraphConEdgeList(G, 2);
   208   checkGraphConArcList(G, 4);
   209 }
   210 
   211 
   212 template <class Graph>
   213 void checkGraphSnapshot() {
   214   TEMPLATE_GRAPH_TYPEDEFS(Graph);
   215 
   216   Graph G;
   217   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
   218   Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
   219        e3 = G.addEdge(n2, n3);
   220 
   221   checkGraphNodeList(G, 3);
   222   checkGraphEdgeList(G, 3);
   223   checkGraphArcList(G, 6);
   224 
   225   typename Graph::Snapshot snapshot(G);
   226 
   227   Node n = G.addNode();
   228   G.addEdge(n3, n);
   229   G.addEdge(n, n3);
   230   G.addEdge(n3, n2);
   231 
   232   checkGraphNodeList(G, 4);
   233   checkGraphEdgeList(G, 6);
   234   checkGraphArcList(G, 12);
   235 
   236   snapshot.restore();
   237 
   238   checkGraphNodeList(G, 3);
   239   checkGraphEdgeList(G, 3);
   240   checkGraphArcList(G, 6);
   241 
   242   checkGraphIncEdgeArcLists(G, n1, 2);
   243   checkGraphIncEdgeArcLists(G, n2, 3);
   244   checkGraphIncEdgeArcLists(G, n3, 1);
   245 
   246   checkGraphConEdgeList(G, 3);
   247   checkGraphConArcList(G, 6);
   248 
   249   checkNodeIds(G);
   250   checkEdgeIds(G);
   251   checkArcIds(G);
   252   checkGraphNodeMap(G);
   253   checkGraphEdgeMap(G);
   254   checkGraphArcMap(G);
   255 
   256   G.addNode();
   257   snapshot.save(G);
   258 
   259   G.addEdge(G.addNode(), G.addNode());
   260 
   261   snapshot.restore();
   262   snapshot.save(G);
   263 
   264   checkGraphNodeList(G, 4);
   265   checkGraphEdgeList(G, 3);
   266   checkGraphArcList(G, 6);
   267 
   268   G.addEdge(G.addNode(), G.addNode());
   269 
   270   snapshot.restore();
   271 
   272   checkGraphNodeList(G, 4);
   273   checkGraphEdgeList(G, 3);
   274   checkGraphArcList(G, 6);
   275 }
   276 
   277 void checkFullGraph(int num) {
   278   typedef FullGraph Graph;
   279   GRAPH_TYPEDEFS(Graph);
   280 
   281   Graph G(num);
   282   check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
   283         "Wrong size");
   284 
   285   G.resize(num);
   286   check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
   287         "Wrong size");
   288 
   289   checkGraphNodeList(G, num);
   290   checkGraphEdgeList(G, num * (num - 1) / 2);
   291 
   292   for (NodeIt n(G); n != INVALID; ++n) {
   293     checkGraphOutArcList(G, n, num - 1);
   294     checkGraphInArcList(G, n, num - 1);
   295     checkGraphIncEdgeList(G, n, num - 1);
   296   }
   297 
   298   checkGraphConArcList(G, num * (num - 1));
   299   checkGraphConEdgeList(G, num * (num - 1) / 2);
   300 
   301   checkArcDirections(G);
   302 
   303   checkNodeIds(G);
   304   checkArcIds(G);
   305   checkEdgeIds(G);
   306   checkGraphNodeMap(G);
   307   checkGraphArcMap(G);
   308   checkGraphEdgeMap(G);
   309 
   310 
   311   for (int i = 0; i < G.nodeNum(); ++i) {
   312     check(G.index(G(i)) == i, "Wrong index");
   313   }
   314 
   315   for (NodeIt u(G); u != INVALID; ++u) {
   316     for (NodeIt v(G); v != INVALID; ++v) {
   317       Edge e = G.edge(u, v);
   318       Arc a = G.arc(u, v);
   319       if (u == v) {
   320         check(e == INVALID, "Wrong edge lookup");
   321         check(a == INVALID, "Wrong arc lookup");
   322       } else {
   323         check((G.u(e) == u && G.v(e) == v) ||
   324               (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
   325         check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
   326       }
   327     }
   328   }
   329 }
   330 
   331 void checkConcepts() {
   332   { // Checking graph components
   333     checkConcept<BaseGraphComponent, BaseGraphComponent >();
   334 
   335     checkConcept<IDableGraphComponent<>,
   336       IDableGraphComponent<> >();
   337 
   338     checkConcept<IterableGraphComponent<>,
   339       IterableGraphComponent<> >();
   340 
   341     checkConcept<MappableGraphComponent<>,
   342       MappableGraphComponent<> >();
   343   }
   344   { // Checking skeleton graph
   345     checkConcept<Graph, Graph>();
   346   }
   347   { // Checking ListGraph
   348     checkConcept<Graph, ListGraph>();
   349     checkConcept<AlterableGraphComponent<>, ListGraph>();
   350     checkConcept<ExtendableGraphComponent<>, ListGraph>();
   351     checkConcept<ClearableGraphComponent<>, ListGraph>();
   352     checkConcept<ErasableGraphComponent<>, ListGraph>();
   353   }
   354   { // Checking SmartGraph
   355     checkConcept<Graph, SmartGraph>();
   356     checkConcept<AlterableGraphComponent<>, SmartGraph>();
   357     checkConcept<ExtendableGraphComponent<>, SmartGraph>();
   358     checkConcept<ClearableGraphComponent<>, SmartGraph>();
   359   }
   360   { // Checking FullGraph
   361     checkConcept<Graph, FullGraph>();
   362   }
   363   { // Checking GridGraph
   364     checkConcept<Graph, GridGraph>();
   365   }
   366   { // Checking HypercubeGraph
   367     checkConcept<Graph, HypercubeGraph>();
   368   }
   369 }
   370 
   371 template <typename Graph>
   372 void checkGraphValidity() {
   373   TEMPLATE_GRAPH_TYPEDEFS(Graph);
   374   Graph g;
   375 
   376   Node
   377     n1 = g.addNode(),
   378     n2 = g.addNode(),
   379     n3 = g.addNode();
   380 
   381   Edge
   382     e1 = g.addEdge(n1, n2),
   383     e2 = g.addEdge(n2, n3);
   384 
   385   check(g.valid(n1), "Wrong validity check");
   386   check(g.valid(e1), "Wrong validity check");
   387   check(g.valid(g.direct(e1, true)), "Wrong validity check");
   388 
   389   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   390   check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
   391   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   392 }
   393 
   394 template <typename Graph>
   395 void checkGraphValidityErase() {
   396   TEMPLATE_GRAPH_TYPEDEFS(Graph);
   397   Graph g;
   398 
   399   Node
   400     n1 = g.addNode(),
   401     n2 = g.addNode(),
   402     n3 = g.addNode();
   403 
   404   Edge
   405     e1 = g.addEdge(n1, n2),
   406     e2 = g.addEdge(n2, n3);
   407 
   408   check(g.valid(n1), "Wrong validity check");
   409   check(g.valid(e1), "Wrong validity check");
   410   check(g.valid(g.direct(e1, true)), "Wrong validity check");
   411 
   412   g.erase(n1);
   413 
   414   check(!g.valid(n1), "Wrong validity check");
   415   check(g.valid(n2), "Wrong validity check");
   416   check(g.valid(n3), "Wrong validity check");
   417   check(!g.valid(e1), "Wrong validity check");
   418   check(g.valid(e2), "Wrong validity check");
   419 
   420   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   421   check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
   422   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   423 }
   424 
   425 void checkGridGraph(int width, int height) {
   426   typedef GridGraph Graph;
   427   GRAPH_TYPEDEFS(Graph);
   428   Graph G(width, height);
   429 
   430   check(G.width() == width, "Wrong column number");
   431   check(G.height() == height, "Wrong row number");
   432 
   433   G.resize(width, height);
   434   check(G.width() == width, "Wrong column number");
   435   check(G.height() == height, "Wrong row number");
   436 
   437   for (int i = 0; i < width; ++i) {
   438     for (int j = 0; j < height; ++j) {
   439       check(G.col(G(i, j)) == i, "Wrong column");
   440       check(G.row(G(i, j)) == j, "Wrong row");
   441       check(G.pos(G(i, j)).x == i, "Wrong column");
   442       check(G.pos(G(i, j)).y == j, "Wrong row");
   443     }
   444   }
   445 
   446   for (int j = 0; j < height; ++j) {
   447     for (int i = 0; i < width - 1; ++i) {
   448       check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");
   449       check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");
   450     }
   451     check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
   452   }
   453 
   454   for (int j = 0; j < height; ++j) {
   455     for (int i = 1; i < width; ++i) {
   456       check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");
   457       check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");
   458     }
   459     check(G.left(G(0, j)) == INVALID, "Wrong left");
   460   }
   461 
   462   for (int i = 0; i < width; ++i) {
   463     for (int j = 0; j < height - 1; ++j) {
   464       check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");
   465       check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");
   466     }
   467     check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
   468   }
   469 
   470   for (int i = 0; i < width; ++i) {
   471     for (int j = 1; j < height; ++j) {
   472       check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");
   473       check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");
   474     }
   475     check(G.down(G(i, 0)) == INVALID, "Wrong down");
   476   }
   477 
   478   checkGraphNodeList(G, width * height);
   479   checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
   480   checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
   481 
   482   for (NodeIt n(G); n != INVALID; ++n) {
   483     int nb = 4;
   484     if (G.col(n) == 0) --nb;
   485     if (G.col(n) == width - 1) --nb;
   486     if (G.row(n) == 0) --nb;
   487     if (G.row(n) == height - 1) --nb;
   488 
   489     checkGraphOutArcList(G, n, nb);
   490     checkGraphInArcList(G, n, nb);
   491     checkGraphIncEdgeList(G, n, nb);
   492   }
   493 
   494   checkArcDirections(G);
   495 
   496   checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
   497   checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
   498 
   499   checkNodeIds(G);
   500   checkArcIds(G);
   501   checkEdgeIds(G);
   502   checkGraphNodeMap(G);
   503   checkGraphArcMap(G);
   504   checkGraphEdgeMap(G);
   505 
   506 }
   507 
   508 void checkHypercubeGraph(int dim) {
   509   GRAPH_TYPEDEFS(HypercubeGraph);
   510 
   511   HypercubeGraph G(dim);
   512   check(G.dimension() == dim, "Wrong dimension");
   513 
   514   G.resize(dim);
   515   check(G.dimension() == dim, "Wrong dimension");
   516 
   517   checkGraphNodeList(G, 1 << dim);
   518   checkGraphEdgeList(G, dim * (1 << (dim-1)));
   519   checkGraphArcList(G, dim * (1 << dim));
   520 
   521   Node n = G.nodeFromId(dim);
   522 
   523   for (NodeIt n(G); n != INVALID; ++n) {
   524     checkGraphIncEdgeList(G, n, dim);
   525     for (IncEdgeIt e(G, n); e != INVALID; ++e) {
   526       check( (G.u(e) == n &&
   527               G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) ||
   528              (G.v(e) == n &&
   529               G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))),
   530              "Wrong edge or wrong dimension");
   531     }
   532 
   533     checkGraphOutArcList(G, n, dim);
   534     for (OutArcIt a(G, n); a != INVALID; ++a) {
   535       check(G.source(a) == n &&
   536             G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))),
   537             "Wrong arc or wrong dimension");
   538     }
   539 
   540     checkGraphInArcList(G, n, dim);
   541     for (InArcIt a(G, n); a != INVALID; ++a) {
   542       check(G.target(a) == n &&
   543             G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))),
   544             "Wrong arc or wrong dimension");
   545     }
   546   }
   547 
   548   checkGraphConArcList(G, (1 << dim) * dim);
   549   checkGraphConEdgeList(G, dim * (1 << (dim-1)));
   550 
   551   checkArcDirections(G);
   552 
   553   checkNodeIds(G);
   554   checkArcIds(G);
   555   checkEdgeIds(G);
   556   checkGraphNodeMap(G);
   557   checkGraphArcMap(G);
   558   checkGraphEdgeMap(G);
   559 }
   560 
   561 void checkGraphs() {
   562   { // Checking ListGraph
   563     checkGraphBuild<ListGraph>();
   564     checkGraphAlter<ListGraph>();
   565     checkGraphErase<ListGraph>();
   566     checkGraphSnapshot<ListGraph>();
   567     checkGraphValidityErase<ListGraph>();
   568   }
   569   { // Checking SmartGraph
   570     checkGraphBuild<SmartGraph>();
   571     checkGraphSnapshot<SmartGraph>();
   572     checkGraphValidity<SmartGraph>();
   573   }
   574   { // Checking FullGraph
   575     checkFullGraph(7);
   576     checkFullGraph(8);
   577   }
   578   { // Checking GridGraph
   579     checkGridGraph(5, 8);
   580     checkGridGraph(8, 5);
   581     checkGridGraph(5, 5);
   582     checkGridGraph(0, 0);
   583     checkGridGraph(1, 1);
   584   }
   585   { // Checking HypercubeGraph
   586     checkHypercubeGraph(1);
   587     checkHypercubeGraph(2);
   588     checkHypercubeGraph(3);
   589     checkHypercubeGraph(4);
   590   }
   591 }
   592 
   593 int main() {
   594   checkConcepts();
   595   checkGraphs();
   596   return 0;
   597 }