Mercuriallemon / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/graph_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 05 Nov 2008 08:11:44 +0000
changeset 374 51597950d0fe
parent 348 052cecabcb71
parent 365 37557a46e298
child 377 a12eef1f82b2
permissions -rw-r--r--
Merge 
     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  */

    18 

    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 

    25 #include "test_tools.h"

    26 #include "graph_test.h"

    27 

    28 using namespace lemon;

    29 using namespace lemon::concepts;

    30 

    31 template <class Graph>

    32 void checkGraph() {

    33   TEMPLATE_GRAPH_TYPEDEFS(Graph);

    34 

    35   Graph G;

    36   checkGraphNodeList(G, 0);

    37   checkGraphEdgeList(G, 0);

    38 

    39   Node

    40     n1 = G.addNode(),

    41     n2 = G.addNode(),

    42     n3 = G.addNode();

    43   checkGraphNodeList(G, 3);

    44   checkGraphEdgeList(G, 0);

    45 

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

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

    48         "Wrong edge");

    49   checkGraphNodeList(G, 3);

    50   checkGraphArcList(G, 2);

    51   checkGraphEdgeList(G, 1);

    52 

    53   checkGraphOutArcList(G, n1, 1);

    54   checkGraphOutArcList(G, n2, 1);

    55   checkGraphOutArcList(G, n3, 0);

    56 

    57   checkGraphInArcList(G, n1, 1);

    58   checkGraphInArcList(G, n2, 1);

    59   checkGraphInArcList(G, n3, 0);

    60 

    61   checkGraphIncEdgeList(G, n1, 1);

    62   checkGraphIncEdgeList(G, n2, 1);

    63   checkGraphIncEdgeList(G, n3, 0);

    64 

    65   checkGraphConArcList(G, 2);

    66   checkGraphConEdgeList(G, 1);

    67 

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

    69   checkGraphNodeList(G, 3);

    70   checkGraphArcList(G, 6);

    71   checkGraphEdgeList(G, 3);

    72 

    73   checkGraphOutArcList(G, n1, 2);

    74   checkGraphOutArcList(G, n2, 3);

    75   checkGraphOutArcList(G, n3, 1);

    76 

    77   checkGraphInArcList(G, n1, 2);

    78   checkGraphInArcList(G, n2, 3);

    79   checkGraphInArcList(G, n3, 1);

    80 

    81   checkGraphIncEdgeList(G, n1, 2);

    82   checkGraphIncEdgeList(G, n2, 3);

    83   checkGraphIncEdgeList(G, n3, 1);

    84 

    85   checkGraphConArcList(G, 6);

    86   checkGraphConEdgeList(G, 3);

    87 

    88   checkArcDirections(G);

    89 

    90   checkNodeIds(G);

    91   checkArcIds(G);

    92   checkEdgeIds(G);

    93   checkGraphNodeMap(G);

    94   checkGraphArcMap(G);

    95   checkGraphEdgeMap(G);

    96 }

    97 

    98 void checkFullGraph(int num) {

    99   typedef FullGraph Graph;

   100   GRAPH_TYPEDEFS(Graph);

   101 

   102   Graph G(num);

   103   checkGraphNodeList(G, num);

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

   105 

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

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

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

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

   110   }

   111 

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

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

   114 

   115   checkArcDirections(G);

   116 

   117   checkNodeIds(G);

   118   checkArcIds(G);

   119   checkEdgeIds(G);

   120   checkGraphNodeMap(G);

   121   checkGraphArcMap(G);

   122   checkGraphEdgeMap(G);

   123 

   124   

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

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

   127   }

   128 

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

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

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

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

   133       if (u == v) {

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

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

   136       } else {

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

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

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

   140       }

   141     }

   142   }

   143 }

   144 

   145 void checkConcepts() {

   146   { // Checking graph components

   147     checkConcept<BaseGraphComponent, BaseGraphComponent >();

   148 

   149     checkConcept<IDableGraphComponent<>,

   150       IDableGraphComponent<> >();

   151 

   152     checkConcept<IterableGraphComponent<>,

   153       IterableGraphComponent<> >();

   154 

   155     checkConcept<MappableGraphComponent<>,

   156       MappableGraphComponent<> >();

   157   }

   158   { // Checking skeleton graph

   159     checkConcept<Graph, Graph>();

   160   }

   161   { // Checking ListGraph

   162     checkConcept<Graph, ListGraph>();

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

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

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

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

   167   }

   168   { // Checking SmartGraph

   169     checkConcept<Graph, SmartGraph>();

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

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

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

   173   }

   174   { // Checking FullGraph

   175     checkConcept<Graph, FullGraph>();

   176   }

   177   { // Checking GridGraph

   178     checkConcept<Graph, GridGraph>();

   179   }

   180 }

   181 

   182 template <typename Graph>

   183 void checkGraphValidity() {

   184   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   185   Graph g;

   186 

   187   Node

   188     n1 = g.addNode(),

   189     n2 = g.addNode(),

   190     n3 = g.addNode();

   191 

   192   Edge

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

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

   195 

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

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

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

   199 

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

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

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

   203 }

   204 

   205 template <typename Graph>

   206 void checkGraphValidityErase() {

   207   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   208   Graph g;

   209 

   210   Node

   211     n1 = g.addNode(),

   212     n2 = g.addNode(),

   213     n3 = g.addNode();

   214 

   215   Edge

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

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

   218 

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

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

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

   222 

   223   g.erase(n1);

   224 

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

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

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

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

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

   230 

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

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

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

   234 }

   235 

   236 void checkGridGraph(int width, int height) {

   237   typedef GridGraph Graph;

   238   GRAPH_TYPEDEFS(Graph);

   239   Graph G(width, height);

   240 

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

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

   243 

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

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

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

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

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

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

   250     }

   251   }

   252 

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

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

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

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

   257     }

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

   259   }

   260 

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

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

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

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

   265     }

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

   267   }

   268 

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

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

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

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

   273     }

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

   275   }

   276 

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

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

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

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

   281     }

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

   283   }

   284 

   285   checkGraphNodeList(G, width * height);

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

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

   288 

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

   290     int nb = 4;

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

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

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

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

   295 

   296     checkGraphOutArcList(G, n, nb);

   297     checkGraphInArcList(G, n, nb);

   298     checkGraphIncEdgeList(G, n, nb);

   299   }

   300 

   301   checkArcDirections(G);

   302 

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

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

   305 

   306   checkNodeIds(G);

   307   checkArcIds(G);

   308   checkEdgeIds(G);

   309   checkGraphNodeMap(G);

   310   checkGraphArcMap(G);

   311   checkGraphEdgeMap(G);

   312 

   313 }

   314 

   315 void checkGraphs() {

   316   { // Checking ListGraph

   317     checkGraph<ListGraph>();

   318     checkGraphValidityErase<ListGraph>();

   319   }

   320   { // Checking SmartGraph

   321     checkGraph<SmartGraph>();

   322     checkGraphValidity<SmartGraph>();

   323   }

   324   { // Checking FullGraph   

   325     checkFullGraph(7);

   326     checkFullGraph(8);

   327   }

   328   { // Checking GridGraph

   329     checkGridGraph(5, 8);

   330     checkGridGraph(8, 5);

   331     checkGridGraph(5, 5);

   332     checkGridGraph(0, 0);

   333     checkGridGraph(1, 1);

   334   }

   335 }

   336 

   337 int main() {

   338   checkConcepts();

   339   checkGraphs();

   340   return 0;

   341 }
lemon