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 Peter Kovacs <kpeter@inf.elte.hu>
Sat, 01 Nov 2008 19:22:18 +0100
changeset 366 80a4d0742e98
parent 228 b6732e0d38c5
child 368 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 }
lemon