test/graph_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 01 Nov 2008 19:22:18 +0100
changeset 354 80a4d0742e98
parent 228 b6732e0d38c5
child 356 99f1bdf8f7db
permissions -rw-r--r--
Improvements related to full graphs (#57)
     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(const GridGraph& g, int w, int h) {
   237 //   check(g.width() == w, "Wrong width");
   238 //   check(g.height() == h, "Wrong height");
   239 
   240 //   for (int i = 0; i < w; ++i) {
   241 //     for (int j = 0; j < h; ++j) {
   242 //       check(g.col(g(i, j)) == i, "Wrong col");
   243 //       check(g.row(g(i, j)) == j, "Wrong row");
   244 //     }
   245 //   }
   246 
   247 //   for (int i = 0; i < w; ++i) {
   248 //     for (int j = 0; j < h - 1; ++j) {
   249 //       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
   250 //       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
   251 //     }
   252 //     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
   253 //   }
   254 
   255 //   for (int i = 0; i < w; ++i) {
   256 //     for (int j = 1; j < h; ++j) {
   257 //       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
   258 //       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
   259 //     }
   260 //     check(g.up(g(i, 0)) == INVALID, "Wrong up");
   261 //   }
   262 
   263 //   for (int j = 0; j < h; ++j) {
   264 //     for (int i = 0; i < w - 1; ++i) {
   265 //       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
   266 //       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
   267 //     }
   268 //     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
   269 //   }
   270 
   271 //   for (int j = 0; j < h; ++j) {
   272 //     for (int i = 1; i < w; ++i) {
   273 //       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
   274 //       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
   275 //     }
   276 //     check(g.left(g(0, j)) == INVALID, "Wrong left");
   277 //   }
   278 // }
   279 
   280 void checkGraphs() {
   281   { // Checking ListGraph
   282     checkGraph<ListGraph>();
   283     checkGraphValidityErase<ListGraph>();
   284   }
   285   { // Checking SmartGraph
   286     checkGraph<SmartGraph>();
   287     checkGraphValidity<SmartGraph>();
   288   }
   289   { // Checking FullGraph   
   290     checkFullGraph(7);
   291     checkFullGraph(8);
   292   }
   293 //   { // Checking GridGraph
   294 //     GridGraph g(5, 6);
   295 //     checkGraphNodeList(g, 30);
   296 //     checkGraphEdgeList(g, 49);
   297 //     checkGridGraph(g, 5, 6);
   298 //   }
   299 }
   300 
   301 int main() {
   302   checkConcepts();
   303   checkGraphs();
   304   return 0;
   305 }