test/graph_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 04 Nov 2008 10:25:47 +0000
changeset 357 3fb8ed1322de
parent 336 052cecabcb71
parent 353 37557a46e298
child 365 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 }