lemon: test/graph_test.cc@115031ac8001

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

    66   ignore_unused_variable_warning(e2,e3);

    68   checkGraphNodeList(G, 3);

    69   checkGraphEdgeList(G, 3);

    70   checkGraphArcList(G, 6);

    72   checkGraphIncEdgeArcLists(G, n1, 2);

    73   checkGraphIncEdgeArcLists(G, n2, 3);

    74   checkGraphIncEdgeArcLists(G, n3, 1);

    76   checkGraphConEdgeList(G, 3);

    77   checkGraphConArcList(G, 6);

    79   checkArcDirections(G);

    81   checkNodeIds(G);

    82   checkArcIds(G);

    83   checkEdgeIds(G);

    84   checkGraphNodeMap(G);

    85   checkGraphArcMap(G);

    86   checkGraphEdgeMap(G);

    87 }

    89 template <class Graph>

    90 void checkGraphAlter() {

    91   TEMPLATE_GRAPH_TYPEDEFS(Graph);

    93   Graph G;

    94   Node n1 = G.addNode(), n2 = G.addNode(),

    95        n3 = G.addNode(), n4 = G.addNode();

    96   Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),

    97        e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),

    98        e5 = G.addEdge(n4, n3);

    99   ignore_unused_variable_warning(e1,e3,e4,e5);

   101   checkGraphNodeList(G, 4);

   102   checkGraphEdgeList(G, 5);

   103   checkGraphArcList(G, 10);

   105   // Check changeU() and changeV()

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

   107     G.changeU(e2, n3);

   108   } else {

   109     G.changeV(e2, n3);

   110   }

   112   checkGraphNodeList(G, 4);

   113   checkGraphEdgeList(G, 5);

   114   checkGraphArcList(G, 10);

   116   checkGraphIncEdgeArcLists(G, n1, 3);

   117   checkGraphIncEdgeArcLists(G, n2, 2);

   118   checkGraphIncEdgeArcLists(G, n3, 3);

   119   checkGraphIncEdgeArcLists(G, n4, 2);

   121   checkGraphConEdgeList(G, 5);

   122   checkGraphConArcList(G, 10);

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

   125     G.changeU(e2, n2);

   126   } else {

   127     G.changeV(e2, n2);

   128   }

   130   checkGraphNodeList(G, 4);

   131   checkGraphEdgeList(G, 5);

   132   checkGraphArcList(G, 10);

   134   checkGraphIncEdgeArcLists(G, n1, 2);

   135   checkGraphIncEdgeArcLists(G, n2, 3);

   136   checkGraphIncEdgeArcLists(G, n3, 3);

   137   checkGraphIncEdgeArcLists(G, n4, 2);

   139   checkGraphConEdgeList(G, 5);

   140   checkGraphConArcList(G, 10);

   142   // Check contract()

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

   145   checkGraphNodeList(G, 3);

   146   checkGraphEdgeList(G, 5);

   147   checkGraphArcList(G, 10);

   149   checkGraphIncEdgeArcLists(G, n1, 4);

   150   checkGraphIncEdgeArcLists(G, n2, 3);

   151   checkGraphIncEdgeArcLists(G, n3, 3);

   153   checkGraphConEdgeList(G, 5);

   154   checkGraphConArcList(G, 10);

   156   G.contract(n2, n3);

   158   checkGraphNodeList(G, 2);

   159   checkGraphEdgeList(G, 3);

   160   checkGraphArcList(G, 6);

   162   checkGraphIncEdgeArcLists(G, n1, 4);

   163   checkGraphIncEdgeArcLists(G, n2, 2);

   165   checkGraphConEdgeList(G, 3);

   166   checkGraphConArcList(G, 6);

   167 }

   169 template <class Graph>

   170 void checkGraphErase() {

   171   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   173   Graph G;

   174   Node n1 = G.addNode(), n2 = G.addNode(),

   175        n3 = G.addNode(), n4 = G.addNode();

   176   Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),

   177        e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),

   178        e5 = G.addEdge(n4, n3);

   179   ignore_unused_variable_warning(e1,e3,e4,e5);

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

   220   ignore_unused_variable_warning(e1,e2,e3);

   222   checkGraphNodeList(G, 3);

   223   checkGraphEdgeList(G, 3);

   224   checkGraphArcList(G, 6);

   226   typename Graph::Snapshot snapshot(G);

   228   Node n = G.addNode();

   229   G.addEdge(n3, n);

   230   G.addEdge(n, n3);

   231   G.addEdge(n3, n2);

   233   checkGraphNodeList(G, 4);

   234   checkGraphEdgeList(G, 6);

   235   checkGraphArcList(G, 12);

   237   snapshot.restore();

   239   checkGraphNodeList(G, 3);

   240   checkGraphEdgeList(G, 3);

   241   checkGraphArcList(G, 6);

   243   checkGraphIncEdgeArcLists(G, n1, 2);

   244   checkGraphIncEdgeArcLists(G, n2, 3);

   245   checkGraphIncEdgeArcLists(G, n3, 1);

   247   checkGraphConEdgeList(G, 3);

   248   checkGraphConArcList(G, 6);

   250   checkNodeIds(G);

   251   checkEdgeIds(G);

   252   checkArcIds(G);

   253   checkGraphNodeMap(G);

   254   checkGraphEdgeMap(G);

   255   checkGraphArcMap(G);

   257   G.addNode();

   258   snapshot.save(G);

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

   262   snapshot.restore();

   264   checkGraphNodeList(G, 4);

   265   checkGraphEdgeList(G, 3);

   266   checkGraphArcList(G, 6);

   267 }

   269 void checkFullGraph(int num) {

   270   typedef FullGraph Graph;

   271   GRAPH_TYPEDEFS(Graph);

   273   Graph G(num);

   274   checkGraphNodeList(G, num);

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

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

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

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

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

   281   }

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

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

   286   checkArcDirections(G);

   288   checkNodeIds(G);

   289   checkArcIds(G);

   290   checkEdgeIds(G);

   291   checkGraphNodeMap(G);

   292   checkGraphArcMap(G);

   293   checkGraphEdgeMap(G);

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

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

   298   }

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

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

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

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

   304       if (u == v) {

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

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

   307       } else {

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

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

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

   311       }

   312     }

   313   }

   314 }

   316 void checkConcepts() {

   317   { // Checking graph components

   318     checkConcept<BaseGraphComponent, BaseGraphComponent >();

   320     checkConcept<IDableGraphComponent<>,

   321       IDableGraphComponent<> >();

   323     checkConcept<IterableGraphComponent<>,

   324       IterableGraphComponent<> >();

   326     checkConcept<MappableGraphComponent<>,

   327       MappableGraphComponent<> >();

   328   }

   329   { // Checking skeleton graph

   330     checkConcept<Graph, Graph>();

   331   }

   332   { // Checking ListGraph

   333     checkConcept<Graph, ListGraph>();

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

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

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

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

   338   }

   339   { // Checking SmartGraph

   340     checkConcept<Graph, SmartGraph>();

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

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

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

   344   }

   345   { // Checking FullGraph

   346     checkConcept<Graph, FullGraph>();

   347   }

   348   { // Checking GridGraph

   349     checkConcept<Graph, GridGraph>();

   350   }

   351   { // Checking HypercubeGraph

   352     checkConcept<Graph, HypercubeGraph>();

   353   }

   354 }

   356 template <typename Graph>

   357 void checkGraphValidity() {

   358   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   359   Graph g;

   361   Node

   362     n1 = g.addNode(),

   363     n2 = g.addNode(),

   364     n3 = g.addNode();

   366   Edge

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

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

   369   ignore_unused_variable_warning(e2);

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

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

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

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

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

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

   378 }

   380 template <typename Graph>

   381 void checkGraphValidityErase() {

   382   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   383   Graph g;

   385   Node

   386     n1 = g.addNode(),

   387     n2 = g.addNode(),

   388     n3 = g.addNode();

   390   Edge

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

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

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

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

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

   398   g.erase(n1);

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

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

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

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

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

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

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

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

   409 }

   411 void checkGridGraph(int width, int height) {

   412   typedef GridGraph Graph;

   413   GRAPH_TYPEDEFS(Graph);

   414   Graph G(width, height);

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

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

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

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

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

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

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

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

   425     }

   426   }

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

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

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

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

   432     }

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

   434   }

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

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

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

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

   440     }

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

   442   }

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

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

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

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

   448     }

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

   450   }

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

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

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

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

   456     }

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

   458   }

   460   checkGraphNodeList(G, width * height);

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

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

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

   465     int nb = 4;

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

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

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

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

   471     checkGraphOutArcList(G, n, nb);

   472     checkGraphInArcList(G, n, nb);

   473     checkGraphIncEdgeList(G, n, nb);

   474   }

   476   checkArcDirections(G);

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

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

   481   checkNodeIds(G);

   482   checkArcIds(G);

   483   checkEdgeIds(G);

   484   checkGraphNodeMap(G);

   485   checkGraphArcMap(G);

   486   checkGraphEdgeMap(G);

   488 }

   490 void checkHypercubeGraph(int dim) {

   491   GRAPH_TYPEDEFS(HypercubeGraph);

   493   HypercubeGraph G(dim);

   494   checkGraphNodeList(G, 1 << dim);

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

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

   498   Node n = G.nodeFromId(dim);

   499   ignore_unused_variable_warning(n);

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

   502     checkGraphIncEdgeList(G, n, dim);

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

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

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

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

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

   508              "Wrong edge or wrong dimension");

   509     }

   511     checkGraphOutArcList(G, n, dim);

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

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

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

   515             "Wrong arc or wrong dimension");

   516     }

   518     checkGraphInArcList(G, n, dim);

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

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

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

   522             "Wrong arc or wrong dimension");

   523     }

   524   }

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

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

   529   checkArcDirections(G);

   531   checkNodeIds(G);

   532   checkArcIds(G);

   533   checkEdgeIds(G);

   534   checkGraphNodeMap(G);

   535   checkGraphArcMap(G);

   536   checkGraphEdgeMap(G);

   537 }

   539 void checkGraphs() {

   540   { // Checking ListGraph

   541     checkGraphBuild<ListGraph>();

   542     checkGraphAlter<ListGraph>();

   543     checkGraphErase<ListGraph>();

   544     checkGraphSnapshot<ListGraph>();

   545     checkGraphValidityErase<ListGraph>();

   546   }

   547   { // Checking SmartGraph

   548     checkGraphBuild<SmartGraph>();

   549     checkGraphSnapshot<SmartGraph>();

   550     checkGraphValidity<SmartGraph>();

   551   }

   552   { // Checking FullGraph

   553     checkFullGraph(7);

   554     checkFullGraph(8);

   555   }

   556   { // Checking GridGraph

   557     checkGridGraph(5, 8);

   558     checkGridGraph(8, 5);

   559     checkGridGraph(5, 5);

   560     checkGridGraph(0, 0);

   561     checkGridGraph(1, 1);

   562   }

   563   { // Checking HypercubeGraph

   564     checkHypercubeGraph(1);

   565     checkHypercubeGraph(2);

   566     checkHypercubeGraph(3);

   567     checkHypercubeGraph(4);

   568   }

   569 }

   571 int main() {

   572   checkConcepts();

   573   checkGraphs();

   574   return 0;

   575 }

author	Alpar Juttner <alpar@cs.elte.hu>
	Tue, 06 Aug 2013 12:04:13 +0200
changeset 1247	115031ac8001
parent 463	88ed40ad0d4f
child 1159	7fdaa05a69a1
child 1257	3e711ee55d31
permissions	-rw-r--r--