test/graph_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 22 Oct 2008 22:14:00 +0100
changeset 337 560e4b6d020d
parent 335 160bf92c7cdc
child 356 99f1bdf8f7db
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 checkConcepts() {
    99   { // Checking graph components
   100     checkConcept<BaseGraphComponent, BaseGraphComponent >();
   101 
   102     checkConcept<IDableGraphComponent<>,
   103       IDableGraphComponent<> >();
   104 
   105     checkConcept<IterableGraphComponent<>,
   106       IterableGraphComponent<> >();
   107 
   108     checkConcept<MappableGraphComponent<>,
   109       MappableGraphComponent<> >();
   110   }
   111   { // Checking skeleton graph
   112     checkConcept<Graph, Graph>();
   113   }
   114   { // Checking ListGraph
   115     checkConcept<Graph, ListGraph>();
   116     checkConcept<AlterableGraphComponent<>, ListGraph>();
   117     checkConcept<ExtendableGraphComponent<>, ListGraph>();
   118     checkConcept<ClearableGraphComponent<>, ListGraph>();
   119     checkConcept<ErasableGraphComponent<>, ListGraph>();
   120   }
   121   { // Checking SmartGraph
   122     checkConcept<Graph, SmartGraph>();
   123     checkConcept<AlterableGraphComponent<>, SmartGraph>();
   124     checkConcept<ExtendableGraphComponent<>, SmartGraph>();
   125     checkConcept<ClearableGraphComponent<>, SmartGraph>();
   126   }
   127 //  { // Checking FullGraph
   128 //    checkConcept<Graph, FullGraph>();
   129 //    checkGraphIterators<FullGraph>();
   130 //  }
   131   { // Checking GridGraph
   132     checkConcept<Graph, GridGraph>();
   133   }
   134 }
   135 
   136 template <typename Graph>
   137 void checkGraphValidity() {
   138   TEMPLATE_GRAPH_TYPEDEFS(Graph);
   139   Graph g;
   140 
   141   Node
   142     n1 = g.addNode(),
   143     n2 = g.addNode(),
   144     n3 = g.addNode();
   145 
   146   Edge
   147     e1 = g.addEdge(n1, n2),
   148     e2 = g.addEdge(n2, n3);
   149 
   150   check(g.valid(n1), "Wrong validity check");
   151   check(g.valid(e1), "Wrong validity check");
   152   check(g.valid(g.direct(e1, true)), "Wrong validity check");
   153 
   154   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   155   check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
   156   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   157 }
   158 
   159 template <typename Graph>
   160 void checkGraphValidityErase() {
   161   TEMPLATE_GRAPH_TYPEDEFS(Graph);
   162   Graph g;
   163 
   164   Node
   165     n1 = g.addNode(),
   166     n2 = g.addNode(),
   167     n3 = g.addNode();
   168 
   169   Edge
   170     e1 = g.addEdge(n1, n2),
   171     e2 = g.addEdge(n2, n3);
   172 
   173   check(g.valid(n1), "Wrong validity check");
   174   check(g.valid(e1), "Wrong validity check");
   175   check(g.valid(g.direct(e1, true)), "Wrong validity check");
   176 
   177   g.erase(n1);
   178 
   179   check(!g.valid(n1), "Wrong validity check");
   180   check(g.valid(n2), "Wrong validity check");
   181   check(g.valid(n3), "Wrong validity check");
   182   check(!g.valid(e1), "Wrong validity check");
   183   check(g.valid(e2), "Wrong validity check");
   184 
   185   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   186   check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
   187   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   188 }
   189 
   190 void checkGridGraph(int width, int height) {
   191   typedef GridGraph Graph;
   192   GRAPH_TYPEDEFS(Graph);
   193   Graph G(width, height);
   194 
   195   check(G.width() == width, "Wrong column number");
   196   check(G.height() == height, "Wrong row number");
   197 
   198   for (int i = 0; i < width; ++i) {
   199     for (int j = 0; j < height; ++j) {
   200       check(G.col(G(i, j)) == i, "Wrong column");
   201       check(G.row(G(i, j)) == j, "Wrong row");
   202       check(G.pos(G(i, j)).x == i, "Wrong column");
   203       check(G.pos(G(i, j)).y == j, "Wrong row");
   204     }
   205   }
   206 
   207   for (int j = 0; j < height; ++j) {
   208     for (int i = 0; i < width - 1; ++i) {
   209       check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");
   210       check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");
   211     }
   212     check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
   213   }
   214 
   215   for (int j = 0; j < height; ++j) {
   216     for (int i = 1; i < width; ++i) {
   217       check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");
   218       check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");
   219     }
   220     check(G.left(G(0, j)) == INVALID, "Wrong left");
   221   }
   222 
   223   for (int i = 0; i < width; ++i) {
   224     for (int j = 0; j < height - 1; ++j) {
   225       check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");
   226       check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");
   227     }
   228     check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
   229   }
   230 
   231   for (int i = 0; i < width; ++i) {
   232     for (int j = 1; j < height; ++j) {
   233       check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");
   234       check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");
   235     }
   236     check(G.down(G(i, 0)) == INVALID, "Wrong down");
   237   }
   238 
   239   checkGraphNodeList(G, width * height);
   240   checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
   241   checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
   242 
   243   for (NodeIt n(G); n != INVALID; ++n) {
   244     int nb = 4;
   245     if (G.col(n) == 0) --nb;
   246     if (G.col(n) == width - 1) --nb;
   247     if (G.row(n) == 0) --nb;
   248     if (G.row(n) == height - 1) --nb;
   249 
   250     checkGraphOutArcList(G, n, nb);
   251     checkGraphInArcList(G, n, nb);
   252     checkGraphIncEdgeList(G, n, nb);
   253   }
   254 
   255   checkArcDirections(G);
   256 
   257   checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
   258   checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
   259 
   260   checkNodeIds(G);
   261   checkArcIds(G);
   262   checkEdgeIds(G);
   263   checkGraphNodeMap(G);
   264   checkGraphArcMap(G);
   265   checkGraphEdgeMap(G);
   266 
   267 }
   268 
   269 void checkGraphs() {
   270   { // Checking ListGraph
   271     checkGraph<ListGraph>();
   272     checkGraphValidityErase<ListGraph>();
   273   }
   274   { // Checking SmartGraph
   275     checkGraph<SmartGraph>();
   276     checkGraphValidity<SmartGraph>();
   277   }
   278 //   { // Checking FullGraph
   279 //     FullGraph g(5);
   280 //     checkGraphNodeList(g, 5);
   281 //     checkGraphEdgeList(g, 10);
   282 //   }
   283   { // Checking GridGraph
   284     checkGridGraph(5, 8);
   285     checkGridGraph(8, 5);
   286     checkGridGraph(5, 5);
   287     checkGridGraph(0, 0);
   288     checkGridGraph(1, 1);
   289   }
   290 }
   291 
   292 int main() {
   293   checkConcepts();
   294   checkGraphs();
   295   return 0;
   296 }