lemon-main: test/graph_test.cc@456fa5bc3256

     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   check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,

   274         "Wrong size");

   276   G.resize(num);

   277   check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,

   278         "Wrong size");

   280   checkGraphNodeList(G, num);

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

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

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

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

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

   287   }

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

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

   292   checkArcDirections(G);

   294   checkNodeIds(G);

   295   checkArcIds(G);

   296   checkEdgeIds(G);

   297   checkGraphNodeMap(G);

   298   checkGraphArcMap(G);

   299   checkGraphEdgeMap(G);

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

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

   304   }

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

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

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

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

   310       if (u == v) {

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

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

   313       } else {

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

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

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

   317       }

   318     }

   319   }

   320 }

   322 void checkConcepts() {

   323   { // Checking graph components

   324     checkConcept<BaseGraphComponent, BaseGraphComponent >();

   326     checkConcept<IDableGraphComponent<>,

   327       IDableGraphComponent<> >();

   329     checkConcept<IterableGraphComponent<>,

   330       IterableGraphComponent<> >();

   332     checkConcept<MappableGraphComponent<>,

   333       MappableGraphComponent<> >();

   334   }

   335   { // Checking skeleton graph

   336     checkConcept<Graph, Graph>();

   337   }

   338   { // Checking ListGraph

   339     checkConcept<Graph, ListGraph>();

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

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

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

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

   344   }

   345   { // Checking SmartGraph

   346     checkConcept<Graph, SmartGraph>();

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

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

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

   350   }

   351   { // Checking FullGraph

   352     checkConcept<Graph, FullGraph>();

   353   }

   354   { // Checking GridGraph

   355     checkConcept<Graph, GridGraph>();

   356   }

   357   { // Checking HypercubeGraph

   358     checkConcept<Graph, HypercubeGraph>();

   359   }

   360 }

   362 template <typename Graph>

   363 void checkGraphValidity() {

   364   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   365   Graph g;

   367   Node

   368     n1 = g.addNode(),

   369     n2 = g.addNode(),

   370     n3 = g.addNode();

   372   Edge

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

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

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

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

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

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

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

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

   383 }

   385 template <typename Graph>

   386 void checkGraphValidityErase() {

   387   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   388   Graph g;

   390   Node

   391     n1 = g.addNode(),

   392     n2 = g.addNode(),

   393     n3 = g.addNode();

   395   Edge

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

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

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

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

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

   403   g.erase(n1);

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

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

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

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

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

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

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

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

   414 }

   416 void checkGridGraph(int width, int height) {

   417   typedef GridGraph Graph;

   418   GRAPH_TYPEDEFS(Graph);

   419   Graph G(width, height);

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

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

   424   G.resize(width, height);

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

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

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

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

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

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

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

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

   434     }

   435   }

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

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

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

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

   441     }

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

   443   }

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

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

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

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

   449     }

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

   451   }

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

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

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

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

   457     }

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

   459   }

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

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

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

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

   465     }

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

   467   }

   469   checkGraphNodeList(G, width * height);

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

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

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

   474     int nb = 4;

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

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

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

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

   480     checkGraphOutArcList(G, n, nb);

   481     checkGraphInArcList(G, n, nb);

   482     checkGraphIncEdgeList(G, n, nb);

   483   }

   485   checkArcDirections(G);

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

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

   490   checkNodeIds(G);

   491   checkArcIds(G);

   492   checkEdgeIds(G);

   493   checkGraphNodeMap(G);

   494   checkGraphArcMap(G);

   495   checkGraphEdgeMap(G);

   497 }

   499 void checkHypercubeGraph(int dim) {

   500   GRAPH_TYPEDEFS(HypercubeGraph);

   502   HypercubeGraph G(dim);

   503   check(G.dimension() == dim, "Wrong dimension");

   505   G.resize(dim);

   506   check(G.dimension() == dim, "Wrong dimension");

   508   checkGraphNodeList(G, 1 << dim);

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

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

   512   Node n = G.nodeFromId(dim);

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

   515     checkGraphIncEdgeList(G, n, dim);

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

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

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

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

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

   521              "Wrong edge or wrong dimension");

   522     }

   524     checkGraphOutArcList(G, n, dim);

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

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

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

   528             "Wrong arc or wrong dimension");

   529     }

   531     checkGraphInArcList(G, n, dim);

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

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

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

   535             "Wrong arc or wrong dimension");

   536     }

   537   }

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

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

   542   checkArcDirections(G);

   544   checkNodeIds(G);

   545   checkArcIds(G);

   546   checkEdgeIds(G);

   547   checkGraphNodeMap(G);

   548   checkGraphArcMap(G);

   549   checkGraphEdgeMap(G);

   550 }

   552 void checkGraphs() {

   553   { // Checking ListGraph

   554     checkGraphBuild<ListGraph>();

   555     checkGraphAlter<ListGraph>();

   556     checkGraphErase<ListGraph>();

   557     checkGraphSnapshot<ListGraph>();

   558     checkGraphValidityErase<ListGraph>();

   559   }

   560   { // Checking SmartGraph

   561     checkGraphBuild<SmartGraph>();

   562     checkGraphSnapshot<SmartGraph>();

   563     checkGraphValidity<SmartGraph>();

   564   }

   565   { // Checking FullGraph

   566     checkFullGraph(7);

   567     checkFullGraph(8);

   568   }

   569   { // Checking GridGraph

   570     checkGridGraph(5, 8);

   571     checkGridGraph(8, 5);

   572     checkGridGraph(5, 5);

   573     checkGridGraph(0, 0);

   574     checkGridGraph(1, 1);

   575   }

   576   { // Checking HypercubeGraph

   577     checkHypercubeGraph(1);

   578     checkHypercubeGraph(2);

   579     checkHypercubeGraph(3);

   580     checkHypercubeGraph(4);

   581   }

   582 }

   584 int main() {

   585   checkConcepts();

   586   checkGraphs();

   587   return 0;

   588 }

author	Peter Kovacs <kpeter@inf.elte.hu>
	Sun, 23 Aug 2009 11:13:21 +0200
changeset 738	456fa5bc3256
parent 736	2e20aad15754
child 740	819ca5b50de0
permissions	-rw-r--r--