test/graph_test.cc
author Balazs Dezso <deba@inf.elte.hu>
Thu, 17 Jul 2008 17:39:53 +0200
changeset 222 f9a18c21dba8
parent 171 02f4d5d9bfd7
child 228 b6732e0d38c5
permissions -rw-r--r--
Fixing bfs test (Ticket #128)
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@57
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@57
     4
 *
alpar@107
     5
 * Copyright (C) 2003-2008
deba@57
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@57
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@57
     8
 *
deba@57
     9
 * Permission to use, modify and distribute this software is granted
deba@57
    10
 * provided that this copyright notice appears in all copies. For
deba@57
    11
 * precise terms see the accompanying LICENSE file.
deba@57
    12
 *
deba@57
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@57
    14
 * express or implied, and with no claim as to its suitability for any
deba@57
    15
 * purpose.
deba@57
    16
 *
deba@57
    17
 */
deba@57
    18
deba@57
    19
#include <lemon/concepts/graph.h>
deba@57
    20
#include <lemon/list_graph.h>
deba@109
    21
#include <lemon/smart_graph.h>
deba@57
    22
// #include <lemon/full_graph.h>
deba@57
    23
// #include <lemon/grid_graph.h>
deba@57
    24
deba@57
    25
#include "test_tools.h"
kpeter@171
    26
#include "graph_test.h"
kpeter@171
    27
#include "graph_maps_test.h"
deba@57
    28
deba@57
    29
using namespace lemon;
deba@57
    30
using namespace lemon::concepts;
deba@57
    31
deba@57
    32
void check_concepts() {
kpeter@171
    33
  { // Checking graph components
deba@57
    34
    checkConcept<BaseGraphComponent, BaseGraphComponent >();
deba@57
    35
alpar@209
    36
    checkConcept<IDableGraphComponent<>,
deba@57
    37
      IDableGraphComponent<> >();
deba@57
    38
alpar@209
    39
    checkConcept<IterableGraphComponent<>,
deba@57
    40
      IterableGraphComponent<> >();
deba@57
    41
alpar@209
    42
    checkConcept<MappableGraphComponent<>,
deba@57
    43
      MappableGraphComponent<> >();
deba@57
    44
  }
kpeter@171
    45
  { // Checking skeleton graph
kpeter@171
    46
    checkConcept<Graph, Graph>();
deba@57
    47
  }
kpeter@171
    48
  { // Checking ListGraph
kpeter@171
    49
    checkConcept<Graph, ListGraph>();
kpeter@171
    50
    checkConcept<AlterableGraphComponent<>, ListGraph>();
kpeter@171
    51
    checkConcept<ExtendableGraphComponent<>, ListGraph>();
kpeter@171
    52
    checkConcept<ClearableGraphComponent<>, ListGraph>();
kpeter@171
    53
    checkConcept<ErasableGraphComponent<>, ListGraph>();
kpeter@171
    54
    checkGraphIterators<ListGraph>();
kpeter@171
    55
  }
kpeter@171
    56
  { // Checking SmartGraph
kpeter@171
    57
    checkConcept<Graph, SmartGraph>();
kpeter@171
    58
    checkConcept<AlterableGraphComponent<>, SmartGraph>();
kpeter@171
    59
    checkConcept<ExtendableGraphComponent<>, SmartGraph>();
kpeter@171
    60
    checkConcept<ClearableGraphComponent<>, SmartGraph>();
kpeter@171
    61
    checkGraphIterators<SmartGraph>();
kpeter@171
    62
  }
kpeter@171
    63
//  { // Checking FullGraph
kpeter@171
    64
//    checkConcept<Graph, FullGraph>();
kpeter@171
    65
//    checkGraphIterators<FullGraph>();
kpeter@171
    66
//  }
kpeter@171
    67
//  { // Checking GridGraph
kpeter@171
    68
//    checkConcept<Graph, GridGraph>();
kpeter@171
    69
//    checkGraphIterators<GridGraph>();
kpeter@171
    70
//  }
deba@57
    71
}
deba@57
    72
deba@57
    73
template <typename Graph>
kpeter@171
    74
void check_graph_validity() {
deba@149
    75
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
deba@57
    76
  Graph g;
deba@57
    77
deba@57
    78
  Node
deba@57
    79
    n1 = g.addNode(),
deba@57
    80
    n2 = g.addNode(),
deba@57
    81
    n3 = g.addNode();
deba@57
    82
deba@57
    83
  Edge
deba@57
    84
    e1 = g.addEdge(n1, n2),
deba@57
    85
    e2 = g.addEdge(n2, n3);
deba@57
    86
kpeter@171
    87
  check(g.valid(n1), "Wrong validity check");
kpeter@171
    88
  check(g.valid(e1), "Wrong validity check");
kpeter@171
    89
  check(g.valid(g.direct(e1, true)), "Wrong validity check");
kpeter@171
    90
kpeter@171
    91
  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
kpeter@171
    92
  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
kpeter@171
    93
  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
deba@57
    94
}
deba@57
    95
deba@149
    96
template <typename Graph>
kpeter@171
    97
void check_graph_validity_erase() {
deba@149
    98
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
deba@149
    99
  Graph g;
deba@149
   100
deba@149
   101
  Node
deba@149
   102
    n1 = g.addNode(),
deba@149
   103
    n2 = g.addNode(),
deba@149
   104
    n3 = g.addNode();
deba@149
   105
deba@149
   106
  Edge
deba@149
   107
    e1 = g.addEdge(n1, n2),
deba@149
   108
    e2 = g.addEdge(n2, n3);
deba@149
   109
kpeter@171
   110
  check(g.valid(n1), "Wrong validity check");
kpeter@171
   111
  check(g.valid(e1), "Wrong validity check");
kpeter@171
   112
  check(g.valid(g.direct(e1, true)), "Wrong validity check");
deba@149
   113
deba@149
   114
  g.erase(n1);
deba@149
   115
kpeter@171
   116
  check(!g.valid(n1), "Wrong validity check");
kpeter@171
   117
  check(g.valid(n2), "Wrong validity check");
kpeter@171
   118
  check(g.valid(n3), "Wrong validity check");
kpeter@171
   119
  check(!g.valid(e1), "Wrong validity check");
kpeter@171
   120
  check(g.valid(e2), "Wrong validity check");
deba@149
   121
kpeter@171
   122
  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
kpeter@171
   123
  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
kpeter@171
   124
  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
deba@149
   125
}
deba@149
   126
deba@57
   127
// void checkGridGraph(const GridGraph& g, int w, int h) {
deba@57
   128
//   check(g.width() == w, "Wrong width");
deba@57
   129
//   check(g.height() == h, "Wrong height");
deba@57
   130
deba@57
   131
//   for (int i = 0; i < w; ++i) {
deba@57
   132
//     for (int j = 0; j < h; ++j) {
deba@57
   133
//       check(g.col(g(i, j)) == i, "Wrong col");
deba@57
   134
//       check(g.row(g(i, j)) == j, "Wrong row");
deba@57
   135
//     }
deba@57
   136
//   }
alpar@209
   137
deba@57
   138
//   for (int i = 0; i < w; ++i) {
deba@57
   139
//     for (int j = 0; j < h - 1; ++j) {
deba@57
   140
//       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
deba@57
   141
//       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
deba@57
   142
//     }
deba@57
   143
//     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
deba@57
   144
//   }
deba@57
   145
deba@57
   146
//   for (int i = 0; i < w; ++i) {
deba@57
   147
//     for (int j = 1; j < h; ++j) {
deba@57
   148
//       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
deba@57
   149
//       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
deba@57
   150
//     }
deba@57
   151
//     check(g.up(g(i, 0)) == INVALID, "Wrong up");
deba@57
   152
//   }
deba@57
   153
deba@57
   154
//   for (int j = 0; j < h; ++j) {
deba@57
   155
//     for (int i = 0; i < w - 1; ++i) {
deba@57
   156
//       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
alpar@209
   157
//       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
deba@57
   158
//     }
alpar@209
   159
//     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
deba@57
   160
//   }
deba@57
   161
deba@57
   162
//   for (int j = 0; j < h; ++j) {
deba@57
   163
//     for (int i = 1; i < w; ++i) {
deba@57
   164
//       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
alpar@209
   165
//       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
deba@57
   166
//     }
alpar@209
   167
//     check(g.left(g(0, j)) == INVALID, "Wrong left");
deba@57
   168
//   }
deba@57
   169
// }
deba@57
   170
kpeter@171
   171
void check_graphs() {
kpeter@171
   172
  { // Checking ListGraph
kpeter@171
   173
    checkGraph<ListGraph>();
kpeter@171
   174
    checkGraphNodeMap<ListGraph>();
kpeter@171
   175
    checkGraphEdgeMap<ListGraph>();
kpeter@171
   176
kpeter@171
   177
    check_graph_validity_erase<ListGraph>();
kpeter@171
   178
  }
kpeter@171
   179
  { // Checking SmartGraph
kpeter@171
   180
    checkGraph<SmartGraph>();
kpeter@171
   181
    checkGraphNodeMap<SmartGraph>();
kpeter@171
   182
    checkGraphEdgeMap<SmartGraph>();
kpeter@171
   183
kpeter@171
   184
    check_graph_validity<SmartGraph>();
kpeter@171
   185
  }
kpeter@171
   186
//   { // Checking FullGraph
kpeter@171
   187
//     FullGraph g(5);
kpeter@171
   188
//     checkGraphNodeList(g, 5);
kpeter@171
   189
//     checkGraphEdgeList(g, 10);
kpeter@171
   190
//   }
kpeter@171
   191
//   { // Checking GridGraph
kpeter@171
   192
//     GridGraph g(5, 6);
kpeter@171
   193
//     checkGraphNodeList(g, 30);
kpeter@171
   194
//     checkGraphEdgeList(g, 49);
kpeter@171
   195
//     checkGridGraph(g, 5, 6);
kpeter@171
   196
//   }
kpeter@171
   197
}
kpeter@171
   198
deba@57
   199
int main() {
deba@57
   200
  check_concepts();
kpeter@171
   201
  check_graphs();
deba@57
   202
  return 0;
deba@57
   203
}