test/graph_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Mon, 14 Jul 2008 16:20:12 +0200
changeset 216 6d7bfcf5b48e
parent 171 02f4d5d9bfd7
child 228 b6732e0d38c5
permissions -rw-r--r--
Doc improvement for kruskal() (ticket #114)
     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 #include "graph_maps_test.h"
    28 
    29 using namespace lemon;
    30 using namespace lemon::concepts;
    31 
    32 void check_concepts() {
    33   { // Checking graph components
    34     checkConcept<BaseGraphComponent, BaseGraphComponent >();
    35 
    36     checkConcept<IDableGraphComponent<>,
    37       IDableGraphComponent<> >();
    38 
    39     checkConcept<IterableGraphComponent<>,
    40       IterableGraphComponent<> >();
    41 
    42     checkConcept<MappableGraphComponent<>,
    43       MappableGraphComponent<> >();
    44   }
    45   { // Checking skeleton graph
    46     checkConcept<Graph, Graph>();
    47   }
    48   { // Checking ListGraph
    49     checkConcept<Graph, ListGraph>();
    50     checkConcept<AlterableGraphComponent<>, ListGraph>();
    51     checkConcept<ExtendableGraphComponent<>, ListGraph>();
    52     checkConcept<ClearableGraphComponent<>, ListGraph>();
    53     checkConcept<ErasableGraphComponent<>, ListGraph>();
    54     checkGraphIterators<ListGraph>();
    55   }
    56   { // Checking SmartGraph
    57     checkConcept<Graph, SmartGraph>();
    58     checkConcept<AlterableGraphComponent<>, SmartGraph>();
    59     checkConcept<ExtendableGraphComponent<>, SmartGraph>();
    60     checkConcept<ClearableGraphComponent<>, SmartGraph>();
    61     checkGraphIterators<SmartGraph>();
    62   }
    63 //  { // Checking FullGraph
    64 //    checkConcept<Graph, FullGraph>();
    65 //    checkGraphIterators<FullGraph>();
    66 //  }
    67 //  { // Checking GridGraph
    68 //    checkConcept<Graph, GridGraph>();
    69 //    checkGraphIterators<GridGraph>();
    70 //  }
    71 }
    72 
    73 template <typename Graph>
    74 void check_graph_validity() {
    75   TEMPLATE_GRAPH_TYPEDEFS(Graph);
    76   Graph g;
    77 
    78   Node
    79     n1 = g.addNode(),
    80     n2 = g.addNode(),
    81     n3 = g.addNode();
    82 
    83   Edge
    84     e1 = g.addEdge(n1, n2),
    85     e2 = g.addEdge(n2, n3);
    86 
    87   check(g.valid(n1), "Wrong validity check");
    88   check(g.valid(e1), "Wrong validity check");
    89   check(g.valid(g.direct(e1, true)), "Wrong validity check");
    90 
    91   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
    92   check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
    93   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
    94 }
    95 
    96 template <typename Graph>
    97 void check_graph_validity_erase() {
    98   TEMPLATE_GRAPH_TYPEDEFS(Graph);
    99   Graph g;
   100 
   101   Node
   102     n1 = g.addNode(),
   103     n2 = g.addNode(),
   104     n3 = g.addNode();
   105 
   106   Edge
   107     e1 = g.addEdge(n1, n2),
   108     e2 = g.addEdge(n2, n3);
   109 
   110   check(g.valid(n1), "Wrong validity check");
   111   check(g.valid(e1), "Wrong validity check");
   112   check(g.valid(g.direct(e1, true)), "Wrong validity check");
   113 
   114   g.erase(n1);
   115 
   116   check(!g.valid(n1), "Wrong validity check");
   117   check(g.valid(n2), "Wrong validity check");
   118   check(g.valid(n3), "Wrong validity check");
   119   check(!g.valid(e1), "Wrong validity check");
   120   check(g.valid(e2), "Wrong validity check");
   121 
   122   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   123   check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
   124   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   125 }
   126 
   127 // void checkGridGraph(const GridGraph& g, int w, int h) {
   128 //   check(g.width() == w, "Wrong width");
   129 //   check(g.height() == h, "Wrong height");
   130 
   131 //   for (int i = 0; i < w; ++i) {
   132 //     for (int j = 0; j < h; ++j) {
   133 //       check(g.col(g(i, j)) == i, "Wrong col");
   134 //       check(g.row(g(i, j)) == j, "Wrong row");
   135 //     }
   136 //   }
   137 
   138 //   for (int i = 0; i < w; ++i) {
   139 //     for (int j = 0; j < h - 1; ++j) {
   140 //       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
   141 //       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
   142 //     }
   143 //     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
   144 //   }
   145 
   146 //   for (int i = 0; i < w; ++i) {
   147 //     for (int j = 1; j < h; ++j) {
   148 //       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
   149 //       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
   150 //     }
   151 //     check(g.up(g(i, 0)) == INVALID, "Wrong up");
   152 //   }
   153 
   154 //   for (int j = 0; j < h; ++j) {
   155 //     for (int i = 0; i < w - 1; ++i) {
   156 //       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
   157 //       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
   158 //     }
   159 //     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
   160 //   }
   161 
   162 //   for (int j = 0; j < h; ++j) {
   163 //     for (int i = 1; i < w; ++i) {
   164 //       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
   165 //       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
   166 //     }
   167 //     check(g.left(g(0, j)) == INVALID, "Wrong left");
   168 //   }
   169 // }
   170 
   171 void check_graphs() {
   172   { // Checking ListGraph
   173     checkGraph<ListGraph>();
   174     checkGraphNodeMap<ListGraph>();
   175     checkGraphEdgeMap<ListGraph>();
   176 
   177     check_graph_validity_erase<ListGraph>();
   178   }
   179   { // Checking SmartGraph
   180     checkGraph<SmartGraph>();
   181     checkGraphNodeMap<SmartGraph>();
   182     checkGraphEdgeMap<SmartGraph>();
   183 
   184     check_graph_validity<SmartGraph>();
   185   }
   186 //   { // Checking FullGraph
   187 //     FullGraph g(5);
   188 //     checkGraphNodeList(g, 5);
   189 //     checkGraphEdgeList(g, 10);
   190 //   }
   191 //   { // Checking GridGraph
   192 //     GridGraph g(5, 6);
   193 //     checkGraphNodeList(g, 30);
   194 //     checkGraphEdgeList(g, 49);
   195 //     checkGridGraph(g, 5, 6);
   196 //   }
   197 }
   198 
   199 int main() {
   200   check_concepts();
   201   check_graphs();
   202   return 0;
   203 }