test/graph_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 03 Apr 2009 18:59:15 +0200
changeset 608 6ac5d9ae1d3d
parent 375 2d87dbd7f8c8
child 736 2e20aad15754
child 997 761fe0846f49
permissions -rw-r--r--
Support real types + numerical stability fix in NS (#254)

- Real types are supported by appropriate inicialization.
- A feature of the XTI spanning tree structure is removed to ensure
numerical stability (could cause problems using integer types).
The node potentials are updated always on the lower subtree,
in order to prevent overflow problems.
The former method isn't notably faster during to our tests.
     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 }