lemon: test/graph_test.cc@660db48f324f

     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-2008

     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  */

    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>

    26 #include "test_tools.h"

    27 #include "graph_test.h"

    29 using namespace lemon;

    30 using namespace lemon::concepts;

    32 template <class Graph>

    33 void checkGraphBuild() {

    34   TEMPLATE_GRAPH_TYPEDEFS(Graph);

    36   Graph G;

    37   checkGraphNodeList(G, 0);

    38   checkGraphEdgeList(G, 0);

    39   checkGraphArcList(G, 0);

    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);

    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");

    53   checkGraphNodeList(G, 3);

    54   checkGraphEdgeList(G, 1);

    55   checkGraphArcList(G, 2);

    57   checkGraphIncEdgeArcLists(G, n1, 1);

    58   checkGraphIncEdgeArcLists(G, n2, 1);

    59   checkGraphIncEdgeArcLists(G, n3, 0);

    61   checkGraphConEdgeList(G, 1);

    62   checkGraphConArcList(G, 2);

    64   Edge e2 = G.addEdge(n2, n1),

    65        e3 = G.addEdge(n2, n3);

    67   checkGraphNodeList(G, 3);

    68   checkGraphEdgeList(G, 3);

    69   checkGraphArcList(G, 6);

    71   checkGraphIncEdgeArcLists(G, n1, 2);

    72   checkGraphIncEdgeArcLists(G, n2, 3);

    73   checkGraphIncEdgeArcLists(G, n3, 1);

    75   checkGraphConEdgeList(G, 3);

    76   checkGraphConArcList(G, 6);

    78   checkArcDirections(G);

    80   checkNodeIds(G);

    81   checkArcIds(G);

    82   checkEdgeIds(G);

    83   checkGraphNodeMap(G);

    84   checkGraphArcMap(G);

    85   checkGraphEdgeMap(G);

    86 }

    88 template <class Graph>

    89 void checkGraphAlter() {

    90   TEMPLATE_GRAPH_TYPEDEFS(Graph);

    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);

    99   checkGraphNodeList(G, 4);

   100   checkGraphEdgeList(G, 5);

   101   checkGraphArcList(G, 10);

   103   // Check changeU() and changeV()

   104   if (G.u(e2) == n2) {

   105     G.changeU(e2, n3);

   106   } else {

   107     G.changeV(e2, n3);

   108   }

   110   checkGraphNodeList(G, 4);

   111   checkGraphEdgeList(G, 5);

   112   checkGraphArcList(G, 10);

   114   checkGraphIncEdgeArcLists(G, n1, 3);

   115   checkGraphIncEdgeArcLists(G, n2, 2);

   116   checkGraphIncEdgeArcLists(G, n3, 3);

   117   checkGraphIncEdgeArcLists(G, n4, 2);

   119   checkGraphConEdgeList(G, 5);

   120   checkGraphConArcList(G, 10);

   122   if (G.u(e2) == n1) {

   123     G.changeU(e2, n2);

   124   } else {

   125     G.changeV(e2, n2);

   126   }

   128   checkGraphNodeList(G, 4);

   129   checkGraphEdgeList(G, 5);

   130   checkGraphArcList(G, 10);

   132   checkGraphIncEdgeArcLists(G, n1, 2);

   133   checkGraphIncEdgeArcLists(G, n2, 3);

   134   checkGraphIncEdgeArcLists(G, n3, 3);

   135   checkGraphIncEdgeArcLists(G, n4, 2);

   137   checkGraphConEdgeList(G, 5);

   138   checkGraphConArcList(G, 10);

   140   // Check contract()

   141   G.contract(n1, n4, false);

   143   checkGraphNodeList(G, 3);

   144   checkGraphEdgeList(G, 5);

   145   checkGraphArcList(G, 10);

   147   checkGraphIncEdgeArcLists(G, n1, 4);

   148   checkGraphIncEdgeArcLists(G, n2, 3);

   149   checkGraphIncEdgeArcLists(G, n3, 3);

   151   checkGraphConEdgeList(G, 5);

   152   checkGraphConArcList(G, 10);

   154   G.contract(n2, n3);

   156   checkGraphNodeList(G, 2);

   157   checkGraphEdgeList(G, 3);

   158   checkGraphArcList(G, 6);

   160   checkGraphIncEdgeArcLists(G, n1, 4);

   161   checkGraphIncEdgeArcLists(G, n2, 2);

   163   checkGraphConEdgeList(G, 3);

   164   checkGraphConArcList(G, 6);

   165 }

   167 template <class Graph>

   168 void checkGraphErase() {

   169   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   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);

   178   // Check edge deletion

   179   G.erase(e2);

   181   checkGraphNodeList(G, 4);

   182   checkGraphEdgeList(G, 4);

   183   checkGraphArcList(G, 8);

   185   checkGraphIncEdgeArcLists(G, n1, 2);

   186   checkGraphIncEdgeArcLists(G, n2, 2);

   187   checkGraphIncEdgeArcLists(G, n3, 2);

   188   checkGraphIncEdgeArcLists(G, n4, 2);

   190   checkGraphConEdgeList(G, 4);

   191   checkGraphConArcList(G, 8);

   193   // Check node deletion

   194   G.erase(n3);

   196   checkGraphNodeList(G, 3);

   197   checkGraphEdgeList(G, 2);

   198   checkGraphArcList(G, 4);

   200   checkGraphIncEdgeArcLists(G, n1, 2);

   201   checkGraphIncEdgeArcLists(G, n2, 1);

   202   checkGraphIncEdgeArcLists(G, n4, 1);

   204   checkGraphConEdgeList(G, 2);

   205   checkGraphConArcList(G, 4);

   206 }

   209 template <class Graph>

   210 void checkGraphSnapshot() {

   211   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   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);

   218   checkGraphNodeList(G, 3);

   219   checkGraphEdgeList(G, 3);

   220   checkGraphArcList(G, 6);

   222   typename Graph::Snapshot snapshot(G);

   224   Node n = G.addNode();

   225   G.addEdge(n3, n);

   226   G.addEdge(n, n3);

   227   G.addEdge(n3, n2);

   229   checkGraphNodeList(G, 4);

   230   checkGraphEdgeList(G, 6);

   231   checkGraphArcList(G, 12);

   233   snapshot.restore();

   235   checkGraphNodeList(G, 3);

   236   checkGraphEdgeList(G, 3);

   237   checkGraphArcList(G, 6);

   239   checkGraphIncEdgeArcLists(G, n1, 2);

   240   checkGraphIncEdgeArcLists(G, n2, 3);

   241   checkGraphIncEdgeArcLists(G, n3, 1);

   243   checkGraphConEdgeList(G, 3);

   244   checkGraphConArcList(G, 6);

   246   checkNodeIds(G);

   247   checkEdgeIds(G);

   248   checkArcIds(G);

   249   checkGraphNodeMap(G);

   250   checkGraphEdgeMap(G);

   251   checkGraphArcMap(G);

   253   G.addNode();

   254   snapshot.save(G);

   256   G.addEdge(G.addNode(), G.addNode());

   258   snapshot.restore();

   260   checkGraphNodeList(G, 4);

   261   checkGraphEdgeList(G, 3);

   262   checkGraphArcList(G, 6);

   263 }

   265 void checkFullGraph(int num) {

   266   typedef FullGraph Graph;

   267   GRAPH_TYPEDEFS(Graph);

   269   Graph G(num);

   270   checkGraphNodeList(G, num);

   271   checkGraphEdgeList(G, num * (num - 1) / 2);

   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   }

   279   checkGraphConArcList(G, num * (num - 1));

   280   checkGraphConEdgeList(G, num * (num - 1) / 2);

   282   checkArcDirections(G);

   284   checkNodeIds(G);

   285   checkArcIds(G);

   286   checkEdgeIds(G);

   287   checkGraphNodeMap(G);

   288   checkGraphArcMap(G);

   289   checkGraphEdgeMap(G);

   292   for (int i = 0; i < G.nodeNum(); ++i) {

   293     check(G.index(G(i)) == i, "Wrong index");

   294   }

   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 }

   312 void checkConcepts() {

   313   { // Checking graph components

   314     checkConcept<BaseGraphComponent, BaseGraphComponent >();

   316     checkConcept<IDableGraphComponent<>,

   317       IDableGraphComponent<> >();

   319     checkConcept<IterableGraphComponent<>,

   320       IterableGraphComponent<> >();

   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 }

   352 template <typename Graph>

   353 void checkGraphValidity() {

   354   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   355   Graph g;

   357   Node

   358     n1 = g.addNode(),

   359     n2 = g.addNode(),

   360     n3 = g.addNode();

   362   Edge

   363     e1 = g.addEdge(n1, n2),

   364     e2 = g.addEdge(n2, n3);

   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");

   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 }

   375 template <typename Graph>

   376 void checkGraphValidityErase() {

   377   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   378   Graph g;

   380   Node

   381     n1 = g.addNode(),

   382     n2 = g.addNode(),

   383     n3 = g.addNode();

   385   Edge

   386     e1 = g.addEdge(n1, n2),

   387     e2 = g.addEdge(n2, n3);

   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");

   393   g.erase(n1);

   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");

   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 }

   406 void checkGridGraph(int width, int height) {

   407   typedef GridGraph Graph;

   408   GRAPH_TYPEDEFS(Graph);

   409   Graph G(width, height);

   411   check(G.width() == width, "Wrong column number");

   412   check(G.height() == height, "Wrong row number");

   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   }

   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   }

   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   }

   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   }

   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   }

   455   checkGraphNodeList(G, width * height);

   456   checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);

   457   checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));

   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;

   466     checkGraphOutArcList(G, n, nb);

   467     checkGraphInArcList(G, n, nb);

   468     checkGraphIncEdgeList(G, n, nb);

   469   }

   471   checkArcDirections(G);

   473   checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));

   474   checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);

   476   checkNodeIds(G);

   477   checkArcIds(G);

   478   checkEdgeIds(G);

   479   checkGraphNodeMap(G);

   480   checkGraphArcMap(G);

   481   checkGraphEdgeMap(G);

   483 }

   485 void checkHypercubeGraph(int dim) {

   486   GRAPH_TYPEDEFS(HypercubeGraph);

   488   HypercubeGraph G(dim);

   489   checkGraphNodeList(G, 1 << dim);

   490   checkGraphEdgeList(G, dim * (1 << (dim-1)));

   491   checkGraphArcList(G, dim * (1 << dim));

   493   Node n = G.nodeFromId(dim);

   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     }

   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     }

   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   }

   520   checkGraphConArcList(G, (1 << dim) * dim);

   521   checkGraphConEdgeList(G, dim * (1 << (dim-1)));

   523   checkArcDirections(G);

   525   checkNodeIds(G);

   526   checkArcIds(G);

   527   checkEdgeIds(G);

   528   checkGraphNodeMap(G);

   529   checkGraphArcMap(G);

   530   checkGraphEdgeMap(G);

   531 }

   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 }

   565 int main() {

   566   checkConcepts();

   567   checkGraphs();

   568   return 0;

   569 }

author	Alpar Juttner <alpar@cs.elte.hu>
	Fri, 21 Nov 2008 14:11:29 +0000
changeset 404	660db48f324f
parent 385	7b6466ed488a
parent 387	49d9a36b3b84
child 463	88ed40ad0d4f
permissions	-rw-r--r--