lemon: test/graph_test.cc@50b6b66daafd

     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>

    25 #include "test_tools.h"

    26 #include "graph_test.h"

    28 using namespace lemon;

    29 using namespace lemon::concepts;

    31 template <class Graph>

    32 void checkGraphBuild() {

    33   TEMPLATE_GRAPH_TYPEDEFS(Graph);

    35   Graph G;

    36   checkGraphNodeList(G, 0);

    37   checkGraphEdgeList(G, 0);

    38   checkGraphArcList(G, 0);

    40   Node

    41     n1 = G.addNode(),

    42     n2 = G.addNode(),

    43     n3 = G.addNode();

    44   checkGraphNodeList(G, 3);

    45   checkGraphEdgeList(G, 0);

    46   checkGraphArcList(G, 0);

    48   Edge e1 = G.addEdge(n1, n2);

    49   check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),

    50         "Wrong edge");

    52   checkGraphNodeList(G, 3);

    53   checkGraphEdgeList(G, 1);

    54   checkGraphArcList(G, 2);

    56   checkGraphIncEdgeArcLists(G, n1, 1);

    57   checkGraphIncEdgeArcLists(G, n2, 1);

    58   checkGraphIncEdgeArcLists(G, n3, 0);

    60   checkGraphConEdgeList(G, 1);

    61   checkGraphConArcList(G, 2);

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

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

    66   checkGraphNodeList(G, 3);

    67   checkGraphEdgeList(G, 3);

    68   checkGraphArcList(G, 6);

    70   checkGraphIncEdgeArcLists(G, n1, 2);

    71   checkGraphIncEdgeArcLists(G, n2, 3);

    72   checkGraphIncEdgeArcLists(G, n3, 1);

    74   checkGraphConEdgeList(G, 3);

    75   checkGraphConArcList(G, 6);

    77   checkArcDirections(G);

    79   checkNodeIds(G);

    80   checkArcIds(G);

    81   checkEdgeIds(G);

    82   checkGraphNodeMap(G);

    83   checkGraphArcMap(G);

    84   checkGraphEdgeMap(G);

    85 }

    87 template <class Graph>

    88 void checkGraphAlter() {

    89   TEMPLATE_GRAPH_TYPEDEFS(Graph);

    91   Graph G;

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

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

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

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

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

    98   checkGraphNodeList(G, 4);

    99   checkGraphEdgeList(G, 5);

   100   checkGraphArcList(G, 10);

   102   // Check changeU() and changeV()

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

   104     G.changeU(e2, n3);

   105   } else {

   106     G.changeV(e2, n3);

   107   }

   109   checkGraphNodeList(G, 4);

   110   checkGraphEdgeList(G, 5);

   111   checkGraphArcList(G, 10);

   113   checkGraphIncEdgeArcLists(G, n1, 3);

   114   checkGraphIncEdgeArcLists(G, n2, 2);

   115   checkGraphIncEdgeArcLists(G, n3, 3);

   116   checkGraphIncEdgeArcLists(G, n4, 2);

   118   checkGraphConEdgeList(G, 5);

   119   checkGraphConArcList(G, 10);

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

   122     G.changeU(e2, n2);

   123   } else {

   124     G.changeV(e2, n2);

   125   }

   127   checkGraphNodeList(G, 4);

   128   checkGraphEdgeList(G, 5);

   129   checkGraphArcList(G, 10);

   131   checkGraphIncEdgeArcLists(G, n1, 2);

   132   checkGraphIncEdgeArcLists(G, n2, 3);

   133   checkGraphIncEdgeArcLists(G, n3, 3);

   134   checkGraphIncEdgeArcLists(G, n4, 2);

   136   checkGraphConEdgeList(G, 5);

   137   checkGraphConArcList(G, 10);

   139   // Check contract()

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

   142   checkGraphNodeList(G, 3);

   143   checkGraphEdgeList(G, 5);

   144   checkGraphArcList(G, 10);

   146   checkGraphIncEdgeArcLists(G, n1, 4);

   147   checkGraphIncEdgeArcLists(G, n2, 3);

   148   checkGraphIncEdgeArcLists(G, n3, 3);

   150   checkGraphConEdgeList(G, 5);

   151   checkGraphConArcList(G, 10);

   153   G.contract(n2, n3);

   155   checkGraphNodeList(G, 2);

   156   checkGraphEdgeList(G, 3);

   157   checkGraphArcList(G, 6);

   159   checkGraphIncEdgeArcLists(G, n1, 4);

   160   checkGraphIncEdgeArcLists(G, n2, 2);

   162   checkGraphConEdgeList(G, 3);

   163   checkGraphConArcList(G, 6);

   164 }

   166 template <class Graph>

   167 void checkGraphErase() {

   168   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   170   Graph G;

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

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

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

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

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

   177   // Check edge deletion

   178   G.erase(e2);

   180   checkGraphNodeList(G, 4);

   181   checkGraphEdgeList(G, 4);

   182   checkGraphArcList(G, 8);

   184   checkGraphIncEdgeArcLists(G, n1, 2);

   185   checkGraphIncEdgeArcLists(G, n2, 2);

   186   checkGraphIncEdgeArcLists(G, n3, 2);

   187   checkGraphIncEdgeArcLists(G, n4, 2);

   189   checkGraphConEdgeList(G, 4);

   190   checkGraphConArcList(G, 8);

   192   // Check node deletion

   193   G.erase(n3);

   195   checkGraphNodeList(G, 3);

   196   checkGraphEdgeList(G, 2);

   197   checkGraphArcList(G, 4);

   199   checkGraphIncEdgeArcLists(G, n1, 2);

   200   checkGraphIncEdgeArcLists(G, n2, 1);

   201   checkGraphIncEdgeArcLists(G, n4, 1);

   203   checkGraphConEdgeList(G, 2);

   204   checkGraphConArcList(G, 4);

   205 }

   208 template <class Graph>

   209 void checkGraphSnapshot() {

   210   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   212   Graph G;

   213   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();

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

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

   217   checkGraphNodeList(G, 3);

   218   checkGraphEdgeList(G, 3);

   219   checkGraphArcList(G, 6);

   221   typename Graph::Snapshot snapshot(G);

   223   Node n = G.addNode();

   224   G.addEdge(n3, n);

   225   G.addEdge(n, n3);

   226   G.addEdge(n3, n2);

   228   checkGraphNodeList(G, 4);

   229   checkGraphEdgeList(G, 6);

   230   checkGraphArcList(G, 12);

   232   snapshot.restore();

   234   checkGraphNodeList(G, 3);

   235   checkGraphEdgeList(G, 3);

   236   checkGraphArcList(G, 6);

   238   checkGraphIncEdgeArcLists(G, n1, 2);

   239   checkGraphIncEdgeArcLists(G, n2, 3);

   240   checkGraphIncEdgeArcLists(G, n3, 1);

   242   checkGraphConEdgeList(G, 3);

   243   checkGraphConArcList(G, 6);

   245   checkNodeIds(G);

   246   checkEdgeIds(G);

   247   checkArcIds(G);

   248   checkGraphNodeMap(G);

   249   checkGraphEdgeMap(G);

   250   checkGraphArcMap(G);

   252   G.addNode();

   253   snapshot.save(G);

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

   257   snapshot.restore();

   259   checkGraphNodeList(G, 4);

   260   checkGraphEdgeList(G, 3);

   261   checkGraphArcList(G, 6);

   262 }

   264 void checkConcepts() {

   265   { // Checking graph components

   266     checkConcept<BaseGraphComponent, BaseGraphComponent >();

   268     checkConcept<IDableGraphComponent<>,

   269       IDableGraphComponent<> >();

   271     checkConcept<IterableGraphComponent<>,

   272       IterableGraphComponent<> >();

   274     checkConcept<MappableGraphComponent<>,

   275       MappableGraphComponent<> >();

   276   }

   277   { // Checking skeleton graph

   278     checkConcept<Graph, Graph>();

   279   }

   280   { // Checking ListGraph

   281     checkConcept<Graph, ListGraph>();

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

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

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

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

   286   }

   287   { // Checking SmartGraph

   288     checkConcept<Graph, SmartGraph>();

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

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

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

   292   }

   293 //  { // Checking FullGraph

   294 //    checkConcept<Graph, FullGraph>();

   295 //    checkGraphIterators<FullGraph>();

   296 //  }

   297 //  { // Checking GridGraph

   298 //    checkConcept<Graph, GridGraph>();

   299 //    checkGraphIterators<GridGraph>();

   300 //  }

   301 }

   303 template <typename Graph>

   304 void checkGraphValidity() {

   305   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   306   Graph g;

   308   Node

   309     n1 = g.addNode(),

   310     n2 = g.addNode(),

   311     n3 = g.addNode();

   313   Edge

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

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

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

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

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

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

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

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

   324 }

   326 template <typename Graph>

   327 void checkGraphValidityErase() {

   328   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   329   Graph g;

   331   Node

   332     n1 = g.addNode(),

   333     n2 = g.addNode(),

   334     n3 = g.addNode();

   336   Edge

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

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

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

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

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

   344   g.erase(n1);

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

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

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

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

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

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

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

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

   355 }

   357 // void checkGridGraph(const GridGraph& g, int w, int h) {

   358 //   check(g.width() == w, "Wrong width");

   359 //   check(g.height() == h, "Wrong height");

   361 //   for (int i = 0; i < w; ++i) {

   362 //     for (int j = 0; j < h; ++j) {

   363 //       check(g.col(g(i, j)) == i, "Wrong col");

   364 //       check(g.row(g(i, j)) == j, "Wrong row");

   365 //     }

   366 //   }

   368 //   for (int i = 0; i < w; ++i) {

   369 //     for (int j = 0; j < h - 1; ++j) {

   370 //       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");

   371 //       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");

   372 //     }

   373 //     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");

   374 //   }

   376 //   for (int i = 0; i < w; ++i) {

   377 //     for (int j = 1; j < h; ++j) {

   378 //       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");

   379 //       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");

   380 //     }

   381 //     check(g.up(g(i, 0)) == INVALID, "Wrong up");

   382 //   }

   384 //   for (int j = 0; j < h; ++j) {

   385 //     for (int i = 0; i < w - 1; ++i) {

   386 //       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");

   387 //       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");

   388 //     }

   389 //     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");

   390 //   }

   392 //   for (int j = 0; j < h; ++j) {

   393 //     for (int i = 1; i < w; ++i) {

   394 //       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");

   395 //       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");

   396 //     }

   397 //     check(g.left(g(0, j)) == INVALID, "Wrong left");

   398 //   }

   399 // }

   401 void checkGraphs() {

   402   { // Checking ListGraph

   403     checkGraphBuild<ListGraph>();

   404     checkGraphAlter<ListGraph>();

   405     checkGraphErase<ListGraph>();

   406     checkGraphSnapshot<ListGraph>();

   407     checkGraphValidityErase<ListGraph>();

   408   }

   409   { // Checking SmartGraph

   410     checkGraphBuild<SmartGraph>();

   411     checkGraphSnapshot<SmartGraph>();

   412     checkGraphValidity<SmartGraph>();

   413   }

   414 //   { // Checking FullGraph

   415 //     FullGraph g(5);

   416 //     checkGraphNodeList(g, 5);

   417 //     checkGraphEdgeList(g, 10);

   418 //   }

   419 //   { // Checking GridGraph

   420 //     GridGraph g(5, 6);

   421 //     checkGraphNodeList(g, 30);

   422 //     checkGraphEdgeList(g, 49);

   423 //     checkGridGraph(g, 5, 6);

   424 //   }

   425 }

   427 int main() {

   428   checkConcepts();

   429   checkGraphs();

   430   return 0;

   431 }

author	Alpar Juttner <alpar@cs.elte.hu>
	Sun, 07 Mar 2010 09:34:56 +0000
branch	1.0
changeset 937	50b6b66daafd
parent 228	b6732e0d38c5
child 388	2d87dbd7f8c8
permissions	-rw-r--r--