test/undir_graph_test.cc
author alpar
Fri, 07 Oct 2005 11:05:08 +0000
changeset 1715 e71778873dd0
parent 1568 f694f75de683
child 1795 ed3c253b9c29
permissions -rw-r--r--
Doc improvments
klao@962
     1
// -*- C++ -*-
klao@962
     2
deba@1307
     3
#include <lemon/bits/undir_graph_extender.h>
klao@962
     4
#include <lemon/concept/undir_graph.h>
klao@962
     5
#include <lemon/list_graph.h>
klao@962
     6
#include <lemon/smart_graph.h>
klao@962
     7
#include <lemon/full_graph.h>
deba@1680
     8
#include <lemon/grid_graph.h>
klao@962
     9
klao@1053
    10
#include <lemon/graph_utils.h>
klao@1053
    11
klao@962
    12
#include "test_tools.h"
klao@962
    13
klao@962
    14
klao@962
    15
using namespace lemon;
klao@962
    16
using namespace lemon::concept;
klao@962
    17
klao@1053
    18
void check_concepts() {
klao@962
    19
  typedef UndirGraphExtender<ListGraphBase> UndirListGraphBase;
klao@962
    20
klao@962
    21
  typedef IterableUndirGraphExtender<
klao@962
    22
    AlterableUndirGraphExtender<UndirListGraphBase> > IterableUndirListGraph;
klao@962
    23
klao@1022
    24
  typedef MappableUndirGraphExtender<IterableUndirListGraph>
klao@1022
    25
    MappableUndirListGraph;
klao@1022
    26
klao@1022
    27
  typedef ErasableUndirGraphExtender<
klao@1022
    28
    ClearableUndirGraphExtender<
klao@1022
    29
    ExtendableUndirGraphExtender<MappableUndirListGraph> > > Graph;
klao@1022
    30
klao@1022
    31
  checkConcept<BaseIterableUndirGraphConcept, Graph>();
klao@1022
    32
  checkConcept<IterableUndirGraphConcept, Graph>();
klao@1022
    33
  checkConcept<MappableUndirGraphConcept, Graph>();
klao@1022
    34
klao@1022
    35
  checkConcept<UndirGraph, Graph>();
klao@1022
    36
  checkConcept<ErasableUndirGraph, Graph>();
klao@962
    37
klao@1034
    38
  checkConcept<UndirGraph, UndirListGraph>();
klao@1034
    39
  checkConcept<ErasableUndirGraph, UndirListGraph>();
klao@1034
    40
klao@1034
    41
  checkConcept<UndirGraph, UndirSmartGraph>();
klao@1034
    42
  checkConcept<ExtendableUndirGraph, UndirSmartGraph>();
klao@1034
    43
deba@1568
    44
  checkConcept<UndirGraph, UndirFullGraph>();
deba@1568
    45
klao@1030
    46
  checkConcept<UndirGraph, UndirGraph>();
deba@1680
    47
deba@1680
    48
  checkConcept<UndirGraph, GridGraph>();
klao@1053
    49
}
klao@1053
    50
klao@1054
    51
template <typename Graph>
klao@1053
    52
void check_item_counts(Graph &g, int n, int e) {
deba@1680
    53
  int nn = 0;
deba@1680
    54
  for (typename Graph::NodeIt it(g); it != INVALID; ++it) {
deba@1680
    55
    ++nn;
deba@1680
    56
  }
deba@1680
    57
deba@1680
    58
  check(nn == n, "Wrong node number.");
deba@1680
    59
  check(countNodes(g) == n, "Wrong node number.");
deba@1680
    60
deba@1680
    61
  int ee = 0;
deba@1680
    62
  for (typename Graph::EdgeIt it(g); it != INVALID; ++it) {
deba@1680
    63
    ++ee;
deba@1680
    64
  }
deba@1680
    65
deba@1680
    66
  check(ee == 2*e, "Wrong edge number.");
deba@1680
    67
  check(countEdges(g) == 2*e, "Wrong edge number.");
deba@1680
    68
deba@1680
    69
  int uee = 0;
deba@1680
    70
  for (typename Graph::UndirEdgeIt it(g); it != INVALID; ++it) {
deba@1680
    71
    ++uee;
deba@1680
    72
  }
deba@1680
    73
deba@1680
    74
  check(uee == e, "Wrong undir edge number.");
deba@1680
    75
  check(countUndirEdges(g) == e, "Wrong undir edge number.");
klao@1053
    76
}
klao@1053
    77
klao@1054
    78
template <typename Graph>
klao@1053
    79
void print_items(Graph &g) {
klao@1054
    80
klao@1054
    81
  typedef typename Graph::NodeIt NodeIt;
klao@1054
    82
  typedef typename Graph::UndirEdgeIt UEdgeIt;
klao@1054
    83
  typedef typename Graph::EdgeIt EdgeIt;
klao@1054
    84
alpar@1367
    85
  std::cout << "Nodes" << std::endl;
klao@1053
    86
  int i=0;
klao@1053
    87
  for(NodeIt it(g); it!=INVALID; ++it, ++i) {
alpar@1367
    88
    std::cout << "  " << i << ": " << g.id(it) << std::endl;
klao@1053
    89
  }
klao@1053
    90
alpar@1367
    91
  std::cout << "UndirEdge" << std::endl;
klao@1053
    92
  i=0;
klao@1053
    93
  for(UEdgeIt it(g); it!=INVALID; ++it, ++i) {
alpar@1367
    94
    std::cout << "  " << i << ": " << g.id(it) 
klao@1053
    95
	 << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it)) 
alpar@1367
    96
	 << ")" << std::endl;
klao@1053
    97
  }
klao@1053
    98
alpar@1367
    99
  std::cout << "Edge" << std::endl;
klao@1053
   100
  i=0;
klao@1053
   101
  for(EdgeIt it(g); it!=INVALID; ++it, ++i) {
alpar@1367
   102
    std::cout << "  " << i << ": " << g.id(it)
klao@1053
   103
	 << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it)) 
alpar@1367
   104
	 << ")" << std::endl;
klao@1053
   105
  }
klao@1053
   106
klao@1053
   107
}
klao@1053
   108
klao@1054
   109
template <typename Graph>
klao@1054
   110
void check_graph() {
klao@1053
   111
klao@1054
   112
  typedef typename Graph::Node Node;
klao@1054
   113
  typedef typename Graph::UndirEdge UEdge;
klao@1054
   114
  typedef typename Graph::Edge Edge;
klao@1054
   115
  typedef typename Graph::NodeIt NodeIt;
klao@1054
   116
  typedef typename Graph::UndirEdgeIt UEdgeIt;
klao@1054
   117
  typedef typename Graph::EdgeIt EdgeIt;
klao@1053
   118
klao@1053
   119
  Graph g;
klao@1053
   120
klao@1053
   121
  check_item_counts(g,0,0);
klao@1053
   122
klao@1053
   123
  Node
klao@1053
   124
    n1 = g.addNode(),
klao@1053
   125
    n2 = g.addNode(),
klao@1053
   126
    n3 = g.addNode();
klao@1053
   127
klao@1053
   128
  UEdge
klao@1053
   129
    e1 = g.addEdge(n1, n2),
klao@1053
   130
    e2 = g.addEdge(n2, n3);
klao@1053
   131
klao@1053
   132
  // print_items(g);
klao@1053
   133
klao@1053
   134
  check_item_counts(g,3,2);
deba@1680
   135
}
klao@1030
   136
deba@1680
   137
void checkGridGraph(const GridGraph& g, int w, int h) {
deba@1680
   138
  check(g.width() == w, "Wrong width");
deba@1680
   139
  check(g.height() == h, "Wrong height");
klao@1054
   140
deba@1680
   141
  for (int i = 0; i < w; ++i) {
deba@1680
   142
    for (int j = 0; j < h; ++j) {
deba@1680
   143
      check(g.col(g(i, j)) == i, "Wrong col");
deba@1680
   144
      check(g.row(g(i, j)) == j, "Wrong row");
deba@1680
   145
    }
deba@1680
   146
  }
deba@1680
   147
  
deba@1680
   148
  for (int i = 0; i < w; ++i) {
deba@1680
   149
    for (int j = 0; j < h - 1; ++j) {
deba@1680
   150
      check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
deba@1680
   151
      check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
deba@1680
   152
    }
deba@1680
   153
    check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
deba@1680
   154
  }
deba@1680
   155
deba@1680
   156
  for (int i = 0; i < w; ++i) {
deba@1680
   157
    for (int j = 1; j < h; ++j) {
deba@1680
   158
      check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
deba@1680
   159
      check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
deba@1680
   160
    }
deba@1680
   161
    check(g.up(g(i, 0)) == INVALID, "Wrong up");
deba@1680
   162
  }
deba@1680
   163
deba@1680
   164
  for (int j = 0; j < h; ++j) {
deba@1680
   165
    for (int i = 0; i < w - 1; ++i) {
deba@1680
   166
      check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
deba@1680
   167
      check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");      
deba@1680
   168
    }
deba@1680
   169
    check(g.right(g(w - 1, j)) == INVALID, "Wrong right");    
deba@1680
   170
  }
deba@1680
   171
deba@1680
   172
  for (int j = 0; j < h; ++j) {
deba@1680
   173
    for (int i = 1; i < w; ++i) {
deba@1680
   174
      check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
deba@1680
   175
      check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");      
deba@1680
   176
    }
deba@1680
   177
    check(g.left(g(0, j)) == INVALID, "Wrong left");    
deba@1680
   178
  }
klao@1054
   179
}
klao@1054
   180
klao@1054
   181
int main() {
klao@1054
   182
  check_concepts();
klao@1054
   183
klao@1054
   184
  check_graph<UndirListGraph>();
klao@1054
   185
  check_graph<UndirSmartGraph>();
klao@1054
   186
deba@1568
   187
  {
deba@1568
   188
    UndirFullGraph g(5);
deba@1568
   189
    check_item_counts(g, 5, 10);
deba@1568
   190
  }
deba@1568
   191
deba@1680
   192
  {
deba@1680
   193
    GridGraph g(5, 6);
deba@1680
   194
    check_item_counts(g, 30, 49);
deba@1680
   195
    checkGridGraph(g, 5, 6);
deba@1680
   196
  }
deba@1680
   197
deba@1680
   198
  std::cout << __FILE__ ": All tests passed.\n";
deba@1680
   199
klao@962
   200
  return 0;
klao@962
   201
}