lemon-main: test/graph_test.cc@2e20aad15754

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

    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   G.reserveNode(3);

    42   G.reserveEdge(3);

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

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

    56   checkGraphNodeList(G, 3);

    57   checkGraphEdgeList(G, 1);

    58   checkGraphArcList(G, 2);

    60   checkGraphIncEdgeArcLists(G, n1, 1);

    61   checkGraphIncEdgeArcLists(G, n2, 1);

    62   checkGraphIncEdgeArcLists(G, n3, 0);

    64   checkGraphConEdgeList(G, 1);

    65   checkGraphConArcList(G, 2);

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

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

    70   checkGraphNodeList(G, 3);

    71   checkGraphEdgeList(G, 3);

    72   checkGraphArcList(G, 6);

    74   checkGraphIncEdgeArcLists(G, n1, 2);

    75   checkGraphIncEdgeArcLists(G, n2, 3);

    76   checkGraphIncEdgeArcLists(G, n3, 1);

    78   checkGraphConEdgeList(G, 3);

    79   checkGraphConArcList(G, 6);

    81   checkArcDirections(G);

    83   checkNodeIds(G);

    84   checkArcIds(G);

    85   checkEdgeIds(G);

    86   checkGraphNodeMap(G);

    87   checkGraphArcMap(G);

    88   checkGraphEdgeMap(G);

    89 }

    91 template <class Graph>

    92 void checkGraphAlter() {

    93   TEMPLATE_GRAPH_TYPEDEFS(Graph);

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

   102   checkGraphNodeList(G, 4);

   103   checkGraphEdgeList(G, 5);

   104   checkGraphArcList(G, 10);

   106   // Check changeU() and changeV()

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

   108     G.changeU(e2, n3);

   109   } else {

   110     G.changeV(e2, n3);

   111   }

   113   checkGraphNodeList(G, 4);

   114   checkGraphEdgeList(G, 5);

   115   checkGraphArcList(G, 10);

   117   checkGraphIncEdgeArcLists(G, n1, 3);

   118   checkGraphIncEdgeArcLists(G, n2, 2);

   119   checkGraphIncEdgeArcLists(G, n3, 3);

   120   checkGraphIncEdgeArcLists(G, n4, 2);

   122   checkGraphConEdgeList(G, 5);

   123   checkGraphConArcList(G, 10);

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

   126     G.changeU(e2, n2);

   127   } else {

   128     G.changeV(e2, n2);

   129   }

   131   checkGraphNodeList(G, 4);

   132   checkGraphEdgeList(G, 5);

   133   checkGraphArcList(G, 10);

   135   checkGraphIncEdgeArcLists(G, n1, 2);

   136   checkGraphIncEdgeArcLists(G, n2, 3);

   137   checkGraphIncEdgeArcLists(G, n3, 3);

   138   checkGraphIncEdgeArcLists(G, n4, 2);

   140   checkGraphConEdgeList(G, 5);

   141   checkGraphConArcList(G, 10);

   143   // Check contract()

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

   146   checkGraphNodeList(G, 3);

   147   checkGraphEdgeList(G, 5);

   148   checkGraphArcList(G, 10);

   150   checkGraphIncEdgeArcLists(G, n1, 4);

   151   checkGraphIncEdgeArcLists(G, n2, 3);

   152   checkGraphIncEdgeArcLists(G, n3, 3);

   154   checkGraphConEdgeList(G, 5);

   155   checkGraphConArcList(G, 10);

   157   G.contract(n2, n3);

   159   checkGraphNodeList(G, 2);

   160   checkGraphEdgeList(G, 3);

   161   checkGraphArcList(G, 6);

   163   checkGraphIncEdgeArcLists(G, n1, 4);

   164   checkGraphIncEdgeArcLists(G, n2, 2);

   166   checkGraphConEdgeList(G, 3);

   167   checkGraphConArcList(G, 6);

   168 }

   170 template <class Graph>

   171 void checkGraphErase() {

   172   TEMPLATE_GRAPH_TYPEDEFS(Graph);

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

   181   // Check edge deletion

   182   G.erase(e2);

   184   checkGraphNodeList(G, 4);

   185   checkGraphEdgeList(G, 4);

   186   checkGraphArcList(G, 8);

   188   checkGraphIncEdgeArcLists(G, n1, 2);

   189   checkGraphIncEdgeArcLists(G, n2, 2);

   190   checkGraphIncEdgeArcLists(G, n3, 2);

   191   checkGraphIncEdgeArcLists(G, n4, 2);

   193   checkGraphConEdgeList(G, 4);

   194   checkGraphConArcList(G, 8);

   196   // Check node deletion

   197   G.erase(n3);

   199   checkGraphNodeList(G, 3);

   200   checkGraphEdgeList(G, 2);

   201   checkGraphArcList(G, 4);

   203   checkGraphIncEdgeArcLists(G, n1, 2);

   204   checkGraphIncEdgeArcLists(G, n2, 1);

   205   checkGraphIncEdgeArcLists(G, n4, 1);

   207   checkGraphConEdgeList(G, 2);

   208   checkGraphConArcList(G, 4);

   209 }

   212 template <class Graph>

   213 void checkGraphSnapshot() {

   214   TEMPLATE_GRAPH_TYPEDEFS(Graph);

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

   221   checkGraphNodeList(G, 3);

   222   checkGraphEdgeList(G, 3);

   223   checkGraphArcList(G, 6);

   225   typename Graph::Snapshot snapshot(G);

   227   Node n = G.addNode();

   228   G.addEdge(n3, n);

   229   G.addEdge(n, n3);

   230   G.addEdge(n3, n2);

   232   checkGraphNodeList(G, 4);

   233   checkGraphEdgeList(G, 6);

   234   checkGraphArcList(G, 12);

   236   snapshot.restore();

   238   checkGraphNodeList(G, 3);

   239   checkGraphEdgeList(G, 3);

   240   checkGraphArcList(G, 6);

   242   checkGraphIncEdgeArcLists(G, n1, 2);

   243   checkGraphIncEdgeArcLists(G, n2, 3);

   244   checkGraphIncEdgeArcLists(G, n3, 1);

   246   checkGraphConEdgeList(G, 3);

   247   checkGraphConArcList(G, 6);

   249   checkNodeIds(G);

   250   checkEdgeIds(G);

   251   checkArcIds(G);

   252   checkGraphNodeMap(G);

   253   checkGraphEdgeMap(G);

   254   checkGraphArcMap(G);

   256   G.addNode();

   257   snapshot.save(G);

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

   261   snapshot.restore();

   263   checkGraphNodeList(G, 4);

   264   checkGraphEdgeList(G, 3);

   265   checkGraphArcList(G, 6);

   266 }

   268 void checkFullGraph(int num) {

   269   typedef FullGraph Graph;

   270   GRAPH_TYPEDEFS(Graph);

   272   Graph G(num);

   273   checkGraphNodeList(G, num);

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

   276   for (NodeIt n(G); n != INVALID; ++n) {

   277     checkGraphOutArcList(G, n, num - 1);

   278     checkGraphInArcList(G, n, num - 1);

   279     checkGraphIncEdgeList(G, n, num - 1);

   280   }

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

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

   285   checkArcDirections(G);

   287   checkNodeIds(G);

   288   checkArcIds(G);

   289   checkEdgeIds(G);

   290   checkGraphNodeMap(G);

   291   checkGraphArcMap(G);

   292   checkGraphEdgeMap(G);

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

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

   297   }

   299   for (NodeIt u(G); u != INVALID; ++u) {

   300     for (NodeIt v(G); v != INVALID; ++v) {

   301       Edge e = G.edge(u, v);

   302       Arc a = G.arc(u, v);

   303       if (u == v) {

   304         check(e == INVALID, "Wrong edge lookup");

   305         check(a == INVALID, "Wrong arc lookup");

   306       } else {

   307         check((G.u(e) == u && G.v(e) == v) ||

   308               (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");

   309         check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");

   310       }

   311     }

   312   }

   313 }

   315 void checkConcepts() {

   316   { // Checking graph components

   317     checkConcept<BaseGraphComponent, BaseGraphComponent >();

   319     checkConcept<IDableGraphComponent<>,

   320       IDableGraphComponent<> >();

   322     checkConcept<IterableGraphComponent<>,

   323       IterableGraphComponent<> >();

   325     checkConcept<MappableGraphComponent<>,

   326       MappableGraphComponent<> >();

   327   }

   328   { // Checking skeleton graph

   329     checkConcept<Graph, Graph>();

   330   }

   331   { // Checking ListGraph

   332     checkConcept<Graph, ListGraph>();

   333     checkConcept<AlterableGraphComponent<>, ListGraph>();

   334     checkConcept<ExtendableGraphComponent<>, ListGraph>();

   335     checkConcept<ClearableGraphComponent<>, ListGraph>();

   336     checkConcept<ErasableGraphComponent<>, ListGraph>();

   337   }

   338   { // Checking SmartGraph

   339     checkConcept<Graph, SmartGraph>();

   340     checkConcept<AlterableGraphComponent<>, SmartGraph>();

   341     checkConcept<ExtendableGraphComponent<>, SmartGraph>();

   342     checkConcept<ClearableGraphComponent<>, SmartGraph>();

   343   }

   344   { // Checking FullGraph

   345     checkConcept<Graph, FullGraph>();

   346   }

   347   { // Checking GridGraph

   348     checkConcept<Graph, GridGraph>();

   349   }

   350   { // Checking HypercubeGraph

   351     checkConcept<Graph, HypercubeGraph>();

   352   }

   353 }

   355 template <typename Graph>

   356 void checkGraphValidity() {

   357   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   358   Graph g;

   360   Node

   361     n1 = g.addNode(),

   362     n2 = g.addNode(),

   363     n3 = g.addNode();

   365   Edge

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

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

   369   check(g.valid(n1), "Wrong validity check");

   370   check(g.valid(e1), "Wrong validity check");

   371   check(g.valid(g.direct(e1, true)), "Wrong validity check");

   373   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");

   374   check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");

   375   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");

   376 }

   378 template <typename Graph>

   379 void checkGraphValidityErase() {

   380   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   381   Graph g;

   383   Node

   384     n1 = g.addNode(),

   385     n2 = g.addNode(),

   386     n3 = g.addNode();

   388   Edge

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

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

   392   check(g.valid(n1), "Wrong validity check");

   393   check(g.valid(e1), "Wrong validity check");

   394   check(g.valid(g.direct(e1, true)), "Wrong validity check");

   396   g.erase(n1);

   398   check(!g.valid(n1), "Wrong validity check");

   399   check(g.valid(n2), "Wrong validity check");

   400   check(g.valid(n3), "Wrong validity check");

   401   check(!g.valid(e1), "Wrong validity check");

   402   check(g.valid(e2), "Wrong validity check");

   404   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");

   405   check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");

   406   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");

   407 }

   409 void checkGridGraph(int width, int height) {

   410   typedef GridGraph Graph;

   411   GRAPH_TYPEDEFS(Graph);

   412   Graph G(width, height);

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

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

   417   for (int i = 0; i < width; ++i) {

   418     for (int j = 0; j < height; ++j) {

   419       check(G.col(G(i, j)) == i, "Wrong column");

   420       check(G.row(G(i, j)) == j, "Wrong row");

   421       check(G.pos(G(i, j)).x == i, "Wrong column");

   422       check(G.pos(G(i, j)).y == j, "Wrong row");

   423     }

   424   }

   426   for (int j = 0; j < height; ++j) {

   427     for (int i = 0; i < width - 1; ++i) {

   428       check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");

   429       check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");

   430     }

   431     check(G.right(G(width - 1, j)) == INVALID, "Wrong right");

   432   }

   434   for (int j = 0; j < height; ++j) {

   435     for (int i = 1; i < width; ++i) {

   436       check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");

   437       check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");

   438     }

   439     check(G.left(G(0, j)) == INVALID, "Wrong left");

   440   }

   442   for (int i = 0; i < width; ++i) {

   443     for (int j = 0; j < height - 1; ++j) {

   444       check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");

   445       check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");

   446     }

   447     check(G.up(G(i, height - 1)) == INVALID, "Wrong up");

   448   }

   450   for (int i = 0; i < width; ++i) {

   451     for (int j = 1; j < height; ++j) {

   452       check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");

   453       check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");

   454     }

   455     check(G.down(G(i, 0)) == INVALID, "Wrong down");

   456   }

   458   checkGraphNodeList(G, width * height);

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

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

   462   for (NodeIt n(G); n != INVALID; ++n) {

   463     int nb = 4;

   464     if (G.col(n) == 0) --nb;

   465     if (G.col(n) == width - 1) --nb;

   466     if (G.row(n) == 0) --nb;

   467     if (G.row(n) == height - 1) --nb;

   469     checkGraphOutArcList(G, n, nb);

   470     checkGraphInArcList(G, n, nb);

   471     checkGraphIncEdgeList(G, n, nb);

   472   }

   474   checkArcDirections(G);

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

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

   479   checkNodeIds(G);

   480   checkArcIds(G);

   481   checkEdgeIds(G);

   482   checkGraphNodeMap(G);

   483   checkGraphArcMap(G);

   484   checkGraphEdgeMap(G);

   486 }

   488 void checkHypercubeGraph(int dim) {

   489   GRAPH_TYPEDEFS(HypercubeGraph);

   491   HypercubeGraph G(dim);

   492   checkGraphNodeList(G, 1 << dim);

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

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

   496   Node n = G.nodeFromId(dim);

   498   for (NodeIt n(G); n != INVALID; ++n) {

   499     checkGraphIncEdgeList(G, n, dim);

   500     for (IncEdgeIt e(G, n); e != INVALID; ++e) {

   501       check( (G.u(e) == n &&

   502               G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) ||

   503              (G.v(e) == n &&

   504               G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))),

   505              "Wrong edge or wrong dimension");

   506     }

   508     checkGraphOutArcList(G, n, dim);

   509     for (OutArcIt a(G, n); a != INVALID; ++a) {

   510       check(G.source(a) == n &&

   511             G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))),

   512             "Wrong arc or wrong dimension");

   513     }

   515     checkGraphInArcList(G, n, dim);

   516     for (InArcIt a(G, n); a != INVALID; ++a) {

   517       check(G.target(a) == n &&

   518             G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))),

   519             "Wrong arc or wrong dimension");

   520     }

   521   }

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

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

   526   checkArcDirections(G);

   528   checkNodeIds(G);

   529   checkArcIds(G);

   530   checkEdgeIds(G);

   531   checkGraphNodeMap(G);

   532   checkGraphArcMap(G);

   533   checkGraphEdgeMap(G);

   534 }

   536 void checkGraphs() {

   537   { // Checking ListGraph

   538     checkGraphBuild<ListGraph>();

   539     checkGraphAlter<ListGraph>();

   540     checkGraphErase<ListGraph>();

   541     checkGraphSnapshot<ListGraph>();

   542     checkGraphValidityErase<ListGraph>();

   543   }

   544   { // Checking SmartGraph

   545     checkGraphBuild<SmartGraph>();

   546     checkGraphSnapshot<SmartGraph>();

   547     checkGraphValidity<SmartGraph>();

   548   }

   549   { // Checking FullGraph

   550     checkFullGraph(7);

   551     checkFullGraph(8);

   552   }

   553   { // Checking GridGraph

   554     checkGridGraph(5, 8);

   555     checkGridGraph(8, 5);

   556     checkGridGraph(5, 5);

   557     checkGridGraph(0, 0);

   558     checkGridGraph(1, 1);

   559   }

   560   { // Checking HypercubeGraph

   561     checkHypercubeGraph(1);

   562     checkHypercubeGraph(2);

   563     checkHypercubeGraph(3);

   564     checkHypercubeGraph(4);

   565   }

   566 }

   568 int main() {

   569   checkConcepts();

   570   checkGraphs();

   571   return 0;

   572 }

author	Peter Kovacs <kpeter@inf.elte.hu>
	Sun, 23 Aug 2009 11:10:40 +0200
changeset 736	2e20aad15754
parent 440	88ed40ad0d4f
child 737	9d6c3e8b2421
permissions	-rw-r--r--