test/graph_test.cc
author Balazs Dezso <deba@inf.elte.hu>
Sat, 18 Apr 2009 21:01:12 +0200
changeset 597 2ca0cdb5f366
parent 375 2d87dbd7f8c8
child 736 2e20aad15754
child 997 761fe0846f49
permissions -rw-r--r--
Fix in HaoOrlin (#264)
     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-2009
     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   Node
    42     n1 = G.addNode(),
    43     n2 = G.addNode(),
    44     n3 = G.addNode();
    45   checkGraphNodeList(G, 3);
    46   checkGraphEdgeList(G, 0);
    47   checkGraphArcList(G, 0);
    48 
    49   Edge e1 = G.addEdge(n1, n2);
    50   check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
    51         "Wrong edge");
    52 
    53   checkGraphNodeList(G, 3);
    54   checkGraphEdgeList(G, 1);
    55   checkGraphArcList(G, 2);
    56 
    57   checkGraphIncEdgeArcLists(G, n1, 1);
    58   checkGraphIncEdgeArcLists(G, n2, 1);
    59   checkGraphIncEdgeArcLists(G, n3, 0);
    60 
    61   checkGraphConEdgeList(G, 1);
    62   checkGraphConArcList(G, 2);
    63 
    64   Edge e2 = G.addEdge(n2, n1),
    65        e3 = G.addEdge(n2, n3);
    66 
    67   checkGraphNodeList(G, 3);
    68   checkGraphEdgeList(G, 3);
    69   checkGraphArcList(G, 6);
    70 
    71   checkGraphIncEdgeArcLists(G, n1, 2);
    72   checkGraphIncEdgeArcLists(G, n2, 3);
    73   checkGraphIncEdgeArcLists(G, n3, 1);
    74 
    75   checkGraphConEdgeList(G, 3);
    76   checkGraphConArcList(G, 6);
    77 
    78   checkArcDirections(G);
    79 
    80   checkNodeIds(G);
    81   checkArcIds(G);
    82   checkEdgeIds(G);
    83   checkGraphNodeMap(G);
    84   checkGraphArcMap(G);
    85   checkGraphEdgeMap(G);
    86 }
    87 
    88 template <class Graph>
    89 void checkGraphAlter() {
    90   TEMPLATE_GRAPH_TYPEDEFS(Graph);
    91 
    92   Graph G;
    93   Node n1 = G.addNode(), n2 = G.addNode(),
    94        n3 = G.addNode(), n4 = G.addNode();
    95   Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
    96        e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
    97        e5 = G.addEdge(n4, n3);
    98 
    99   checkGraphNodeList(G, 4);
   100   checkGraphEdgeList(G, 5);
   101   checkGraphArcList(G, 10);
   102 
   103   // Check changeU() and changeV()
   104   if (G.u(e2) == n2) {
   105     G.changeU(e2, n3);
   106   } else {
   107     G.changeV(e2, n3);
   108   }
   109 
   110   checkGraphNodeList(G, 4);
   111   checkGraphEdgeList(G, 5);
   112   checkGraphArcList(G, 10);
   113 
   114   checkGraphIncEdgeArcLists(G, n1, 3);
   115   checkGraphIncEdgeArcLists(G, n2, 2);
   116   checkGraphIncEdgeArcLists(G, n3, 3);
   117   checkGraphIncEdgeArcLists(G, n4, 2);
   118 
   119   checkGraphConEdgeList(G, 5);
   120   checkGraphConArcList(G, 10);
   121 
   122   if (G.u(e2) == n1) {
   123     G.changeU(e2, n2);
   124   } else {
   125     G.changeV(e2, n2);
   126   }
   127 
   128   checkGraphNodeList(G, 4);
   129   checkGraphEdgeList(G, 5);
   130   checkGraphArcList(G, 10);
   131 
   132   checkGraphIncEdgeArcLists(G, n1, 2);
   133   checkGraphIncEdgeArcLists(G, n2, 3);
   134   checkGraphIncEdgeArcLists(G, n3, 3);
   135   checkGraphIncEdgeArcLists(G, n4, 2);
   136 
   137   checkGraphConEdgeList(G, 5);
   138   checkGraphConArcList(G, 10);
   139 
   140   // Check contract()
   141   G.contract(n1, n4, false);
   142 
   143   checkGraphNodeList(G, 3);
   144   checkGraphEdgeList(G, 5);
   145   checkGraphArcList(G, 10);
   146 
   147   checkGraphIncEdgeArcLists(G, n1, 4);
   148   checkGraphIncEdgeArcLists(G, n2, 3);
   149   checkGraphIncEdgeArcLists(G, n3, 3);
   150 
   151   checkGraphConEdgeList(G, 5);
   152   checkGraphConArcList(G, 10);
   153 
   154   G.contract(n2, n3);
   155 
   156   checkGraphNodeList(G, 2);
   157   checkGraphEdgeList(G, 3);
   158   checkGraphArcList(G, 6);
   159 
   160   checkGraphIncEdgeArcLists(G, n1, 4);
   161   checkGraphIncEdgeArcLists(G, n2, 2);
   162 
   163   checkGraphConEdgeList(G, 3);
   164   checkGraphConArcList(G, 6);
   165 }
   166 
   167 template <class Graph>
   168 void checkGraphErase() {
   169   TEMPLATE_GRAPH_TYPEDEFS(Graph);
   170 
   171   Graph G;
   172   Node n1 = G.addNode(), n2 = G.addNode(),
   173        n3 = G.addNode(), n4 = G.addNode();
   174   Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
   175        e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
   176        e5 = G.addEdge(n4, n3);
   177 
   178   // Check edge deletion
   179   G.erase(e2);
   180 
   181   checkGraphNodeList(G, 4);
   182   checkGraphEdgeList(G, 4);
   183   checkGraphArcList(G, 8);
   184 
   185   checkGraphIncEdgeArcLists(G, n1, 2);
   186   checkGraphIncEdgeArcLists(G, n2, 2);
   187   checkGraphIncEdgeArcLists(G, n3, 2);
   188   checkGraphIncEdgeArcLists(G, n4, 2);
   189 
   190   checkGraphConEdgeList(G, 4);
   191   checkGraphConArcList(G, 8);
   192 
   193   // Check node deletion
   194   G.erase(n3);
   195 
   196   checkGraphNodeList(G, 3);
   197   checkGraphEdgeList(G, 2);
   198   checkGraphArcList(G, 4);
   199 
   200   checkGraphIncEdgeArcLists(G, n1, 2);
   201   checkGraphIncEdgeArcLists(G, n2, 1);
   202   checkGraphIncEdgeArcLists(G, n4, 1);
   203 
   204   checkGraphConEdgeList(G, 2);
   205   checkGraphConArcList(G, 4);
   206 }
   207 
   208 
   209 template <class Graph>
   210 void checkGraphSnapshot() {
   211   TEMPLATE_GRAPH_TYPEDEFS(Graph);
   212 
   213   Graph G;
   214   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
   215   Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
   216        e3 = G.addEdge(n2, n3);
   217 
   218   checkGraphNodeList(G, 3);
   219   checkGraphEdgeList(G, 3);
   220   checkGraphArcList(G, 6);
   221 
   222   typename Graph::Snapshot snapshot(G);
   223 
   224   Node n = G.addNode();
   225   G.addEdge(n3, n);
   226   G.addEdge(n, n3);
   227   G.addEdge(n3, n2);
   228 
   229   checkGraphNodeList(G, 4);
   230   checkGraphEdgeList(G, 6);
   231   checkGraphArcList(G, 12);
   232 
   233   snapshot.restore();
   234 
   235   checkGraphNodeList(G, 3);
   236   checkGraphEdgeList(G, 3);
   237   checkGraphArcList(G, 6);
   238 
   239   checkGraphIncEdgeArcLists(G, n1, 2);
   240   checkGraphIncEdgeArcLists(G, n2, 3);
   241   checkGraphIncEdgeArcLists(G, n3, 1);
   242 
   243   checkGraphConEdgeList(G, 3);
   244   checkGraphConArcList(G, 6);
   245 
   246   checkNodeIds(G);
   247   checkEdgeIds(G);
   248   checkArcIds(G);
   249   checkGraphNodeMap(G);
   250   checkGraphEdgeMap(G);
   251   checkGraphArcMap(G);
   252 
   253   G.addNode();
   254   snapshot.save(G);
   255 
   256   G.addEdge(G.addNode(), G.addNode());
   257 
   258   snapshot.restore();
   259 
   260   checkGraphNodeList(G, 4);
   261   checkGraphEdgeList(G, 3);
   262   checkGraphArcList(G, 6);
   263 }
   264 
   265 void checkFullGraph(int num) {
   266   typedef FullGraph Graph;
   267   GRAPH_TYPEDEFS(Graph);
   268 
   269   Graph G(num);
   270   checkGraphNodeList(G, num);
   271   checkGraphEdgeList(G, num * (num - 1) / 2);
   272 
   273   for (NodeIt n(G); n != INVALID; ++n) {
   274     checkGraphOutArcList(G, n, num - 1);
   275     checkGraphInArcList(G, n, num - 1);
   276     checkGraphIncEdgeList(G, n, num - 1);
   277   }
   278 
   279   checkGraphConArcList(G, num * (num - 1));
   280   checkGraphConEdgeList(G, num * (num - 1) / 2);
   281 
   282   checkArcDirections(G);
   283 
   284   checkNodeIds(G);
   285   checkArcIds(G);
   286   checkEdgeIds(G);
   287   checkGraphNodeMap(G);
   288   checkGraphArcMap(G);
   289   checkGraphEdgeMap(G);
   290 
   291 
   292   for (int i = 0; i < G.nodeNum(); ++i) {
   293     check(G.index(G(i)) == i, "Wrong index");
   294   }
   295 
   296   for (NodeIt u(G); u != INVALID; ++u) {
   297     for (NodeIt v(G); v != INVALID; ++v) {
   298       Edge e = G.edge(u, v);
   299       Arc a = G.arc(u, v);
   300       if (u == v) {
   301         check(e == INVALID, "Wrong edge lookup");
   302         check(a == INVALID, "Wrong arc lookup");
   303       } else {
   304         check((G.u(e) == u && G.v(e) == v) ||
   305               (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
   306         check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
   307       }
   308     }
   309   }
   310 }
   311 
   312 void checkConcepts() {
   313   { // Checking graph components
   314     checkConcept<BaseGraphComponent, BaseGraphComponent >();
   315 
   316     checkConcept<IDableGraphComponent<>,
   317       IDableGraphComponent<> >();
   318 
   319     checkConcept<IterableGraphComponent<>,
   320       IterableGraphComponent<> >();
   321 
   322     checkConcept<MappableGraphComponent<>,
   323       MappableGraphComponent<> >();
   324   }
   325   { // Checking skeleton graph
   326     checkConcept<Graph, Graph>();
   327   }
   328   { // Checking ListGraph
   329     checkConcept<Graph, ListGraph>();
   330     checkConcept<AlterableGraphComponent<>, ListGraph>();
   331     checkConcept<ExtendableGraphComponent<>, ListGraph>();
   332     checkConcept<ClearableGraphComponent<>, ListGraph>();
   333     checkConcept<ErasableGraphComponent<>, ListGraph>();
   334   }
   335   { // Checking SmartGraph
   336     checkConcept<Graph, SmartGraph>();
   337     checkConcept<AlterableGraphComponent<>, SmartGraph>();
   338     checkConcept<ExtendableGraphComponent<>, SmartGraph>();
   339     checkConcept<ClearableGraphComponent<>, SmartGraph>();
   340   }
   341   { // Checking FullGraph
   342     checkConcept<Graph, FullGraph>();
   343   }
   344   { // Checking GridGraph
   345     checkConcept<Graph, GridGraph>();
   346   }
   347   { // Checking HypercubeGraph
   348     checkConcept<Graph, HypercubeGraph>();
   349   }
   350 }
   351 
   352 template <typename Graph>
   353 void checkGraphValidity() {
   354   TEMPLATE_GRAPH_TYPEDEFS(Graph);
   355   Graph g;
   356 
   357   Node
   358     n1 = g.addNode(),
   359     n2 = g.addNode(),
   360     n3 = g.addNode();
   361 
   362   Edge
   363     e1 = g.addEdge(n1, n2),
   364     e2 = g.addEdge(n2, n3);
   365 
   366   check(g.valid(n1), "Wrong validity check");
   367   check(g.valid(e1), "Wrong validity check");
   368   check(g.valid(g.direct(e1, true)), "Wrong validity check");
   369 
   370   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   371   check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
   372   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   373 }
   374 
   375 template <typename Graph>
   376 void checkGraphValidityErase() {
   377   TEMPLATE_GRAPH_TYPEDEFS(Graph);
   378   Graph g;
   379 
   380   Node
   381     n1 = g.addNode(),
   382     n2 = g.addNode(),
   383     n3 = g.addNode();
   384 
   385   Edge
   386     e1 = g.addEdge(n1, n2),
   387     e2 = g.addEdge(n2, n3);
   388 
   389   check(g.valid(n1), "Wrong validity check");
   390   check(g.valid(e1), "Wrong validity check");
   391   check(g.valid(g.direct(e1, true)), "Wrong validity check");
   392 
   393   g.erase(n1);
   394 
   395   check(!g.valid(n1), "Wrong validity check");
   396   check(g.valid(n2), "Wrong validity check");
   397   check(g.valid(n3), "Wrong validity check");
   398   check(!g.valid(e1), "Wrong validity check");
   399   check(g.valid(e2), "Wrong validity check");
   400 
   401   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   402   check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
   403   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   404 }
   405 
   406 void checkGridGraph(int width, int height) {
   407   typedef GridGraph Graph;
   408   GRAPH_TYPEDEFS(Graph);
   409   Graph G(width, height);
   410 
   411   check(G.width() == width, "Wrong column number");
   412   check(G.height() == height, "Wrong row number");
   413 
   414   for (int i = 0; i < width; ++i) {
   415     for (int j = 0; j < height; ++j) {
   416       check(G.col(G(i, j)) == i, "Wrong column");
   417       check(G.row(G(i, j)) == j, "Wrong row");
   418       check(G.pos(G(i, j)).x == i, "Wrong column");
   419       check(G.pos(G(i, j)).y == j, "Wrong row");
   420     }
   421   }
   422 
   423   for (int j = 0; j < height; ++j) {
   424     for (int i = 0; i < width - 1; ++i) {
   425       check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");
   426       check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");
   427     }
   428     check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
   429   }
   430 
   431   for (int j = 0; j < height; ++j) {
   432     for (int i = 1; i < width; ++i) {
   433       check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");
   434       check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");
   435     }
   436     check(G.left(G(0, j)) == INVALID, "Wrong left");
   437   }
   438 
   439   for (int i = 0; i < width; ++i) {
   440     for (int j = 0; j < height - 1; ++j) {
   441       check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");
   442       check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");
   443     }
   444     check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
   445   }
   446 
   447   for (int i = 0; i < width; ++i) {
   448     for (int j = 1; j < height; ++j) {
   449       check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");
   450       check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");
   451     }
   452     check(G.down(G(i, 0)) == INVALID, "Wrong down");
   453   }
   454 
   455   checkGraphNodeList(G, width * height);
   456   checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
   457   checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
   458 
   459   for (NodeIt n(G); n != INVALID; ++n) {
   460     int nb = 4;
   461     if (G.col(n) == 0) --nb;
   462     if (G.col(n) == width - 1) --nb;
   463     if (G.row(n) == 0) --nb;
   464     if (G.row(n) == height - 1) --nb;
   465 
   466     checkGraphOutArcList(G, n, nb);
   467     checkGraphInArcList(G, n, nb);
   468     checkGraphIncEdgeList(G, n, nb);
   469   }
   470 
   471   checkArcDirections(G);
   472 
   473   checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
   474   checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
   475 
   476   checkNodeIds(G);
   477   checkArcIds(G);
   478   checkEdgeIds(G);
   479   checkGraphNodeMap(G);
   480   checkGraphArcMap(G);
   481   checkGraphEdgeMap(G);
   482 
   483 }
   484 
   485 void checkHypercubeGraph(int dim) {
   486   GRAPH_TYPEDEFS(HypercubeGraph);
   487 
   488   HypercubeGraph G(dim);
   489   checkGraphNodeList(G, 1 << dim);
   490   checkGraphEdgeList(G, dim * (1 << (dim-1)));
   491   checkGraphArcList(G, dim * (1 << dim));
   492 
   493   Node n = G.nodeFromId(dim);
   494 
   495   for (NodeIt n(G); n != INVALID; ++n) {
   496     checkGraphIncEdgeList(G, n, dim);
   497     for (IncEdgeIt e(G, n); e != INVALID; ++e) {
   498       check( (G.u(e) == n &&
   499               G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) ||
   500              (G.v(e) == n &&
   501               G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))),
   502              "Wrong edge or wrong dimension");
   503     }
   504 
   505     checkGraphOutArcList(G, n, dim);
   506     for (OutArcIt a(G, n); a != INVALID; ++a) {
   507       check(G.source(a) == n &&
   508             G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))),
   509             "Wrong arc or wrong dimension");
   510     }
   511 
   512     checkGraphInArcList(G, n, dim);
   513     for (InArcIt a(G, n); a != INVALID; ++a) {
   514       check(G.target(a) == n &&
   515             G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))),
   516             "Wrong arc or wrong dimension");
   517     }
   518   }
   519 
   520   checkGraphConArcList(G, (1 << dim) * dim);
   521   checkGraphConEdgeList(G, dim * (1 << (dim-1)));
   522 
   523   checkArcDirections(G);
   524 
   525   checkNodeIds(G);
   526   checkArcIds(G);
   527   checkEdgeIds(G);
   528   checkGraphNodeMap(G);
   529   checkGraphArcMap(G);
   530   checkGraphEdgeMap(G);
   531 }
   532 
   533 void checkGraphs() {
   534   { // Checking ListGraph
   535     checkGraphBuild<ListGraph>();
   536     checkGraphAlter<ListGraph>();
   537     checkGraphErase<ListGraph>();
   538     checkGraphSnapshot<ListGraph>();
   539     checkGraphValidityErase<ListGraph>();
   540   }
   541   { // Checking SmartGraph
   542     checkGraphBuild<SmartGraph>();
   543     checkGraphSnapshot<SmartGraph>();
   544     checkGraphValidity<SmartGraph>();
   545   }
   546   { // Checking FullGraph
   547     checkFullGraph(7);
   548     checkFullGraph(8);
   549   }
   550   { // Checking GridGraph
   551     checkGridGraph(5, 8);
   552     checkGridGraph(8, 5);
   553     checkGridGraph(5, 5);
   554     checkGridGraph(0, 0);
   555     checkGridGraph(1, 1);
   556   }
   557   { // Checking HypercubeGraph
   558     checkHypercubeGraph(1);
   559     checkHypercubeGraph(2);
   560     checkHypercubeGraph(3);
   561     checkHypercubeGraph(4);
   562   }
   563 }
   564 
   565 int main() {
   566   checkConcepts();
   567   checkGraphs();
   568   return 0;
   569 }