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