src/test/graph_test.cc
author jacint
Wed, 05 May 2004 17:51:56 +0000
changeset 537 acd69f60b9c7
parent 504 6ef30329dd50
child 542 69bde1d90c04
permissions -rw-r--r--
Contains Edmonds' matching algorithm in a plain and in a heuristical form.
alpar@503
     1
#include<iostream>
alpar@503
     2
#include<smart_graph.h>
alpar@503
     3
#include<skeletons/graph.h>
alpar@503
     4
#include<../work/alpar/list_graph.h>
alpar@503
     5
alpar@503
     6
/*
alpar@503
     7
This test makes consistency checks of list graph structures.
alpar@503
     8
alpar@503
     9
G.addNode(), G.addEdge(), G.valid(), G.tail(), G.head()
alpar@503
    10
alpar@503
    11
*/
alpar@503
    12
alpar@503
    13
using namespace hugo;
alpar@503
    14
alpar@503
    15
// void check(bool rc, const char *msg) {
alpar@503
    16
//   if(!rc) {
alpar@503
    17
//     std::cerr << msg << std::endl;
alpar@503
    18
//     exit(1);
alpar@503
    19
//   }
alpar@503
    20
// }
alpar@503
    21
alpar@503
    22
#define check(rc, msg) \
alpar@503
    23
  if(!rc) { \
alpar@503
    24
    std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \
alpar@503
    25
    exit(1); \
alpar@503
    26
  } else { } \
alpar@503
    27
alpar@503
    28
alpar@503
    29
template<class Graph> void checkCompile(Graph &G) 
alpar@503
    30
{
alpar@503
    31
  typedef typename Graph::Node Node;
alpar@503
    32
  typedef typename Graph::NodeIt NodeIt;
alpar@503
    33
  typedef typename Graph::Edge Edge;
alpar@503
    34
  typedef typename Graph::EdgeIt EdgeIt;
alpar@503
    35
  typedef typename Graph::InEdgeIt InEdgeIt;
alpar@503
    36
  typedef typename Graph::OutEdgeIt OutEdgeIt;
alpar@503
    37
  
alpar@503
    38
  {
alpar@503
    39
    Node i; Node j(i); Node k(INVALID);
alpar@503
    40
    i=j;
alpar@503
    41
    bool b=G.valid(i); b=b;
alpar@503
    42
    b=(i==j); b=(i!=j); b=(i<j);
alpar@503
    43
  }
alpar@503
    44
  {
alpar@503
    45
    NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);
alpar@503
    46
    i=j;
alpar@503
    47
    j=G.first(i);
alpar@503
    48
    j=G.next(i);
alpar@503
    49
    bool b=G.valid(i); b=b;
alpar@503
    50
    Node n(i);
alpar@503
    51
    n=i;
alpar@503
    52
    b=(i==j); b=(i!=j); b=(i<j);
alpar@503
    53
  }
alpar@503
    54
  {
alpar@503
    55
    Edge i; Edge j(i); Edge k(INVALID);
alpar@503
    56
    i=j;
alpar@503
    57
    bool b=G.valid(i); b=b;
alpar@503
    58
    b=(i==j); b=(i!=j); b=(i<j);
alpar@503
    59
  }
alpar@503
    60
  {
alpar@503
    61
    EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);
alpar@503
    62
    i=j;
alpar@503
    63
    j=G.first(i);
alpar@503
    64
    j=G.next(i);
alpar@503
    65
    bool b=G.valid(i); b=b;
alpar@503
    66
    Edge e(i);
alpar@503
    67
    e=i;
alpar@503
    68
    b=(i==j); b=(i!=j); b=(i<j);
alpar@503
    69
  }
alpar@503
    70
  {
alpar@503
    71
    Node n;
alpar@503
    72
    InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);
alpar@503
    73
    i=j;
alpar@503
    74
    j=G.first(i,n);
alpar@503
    75
    j=G.next(i);
alpar@503
    76
    bool b=G.valid(i); b=b;
alpar@503
    77
    Edge e(i);
alpar@503
    78
    e=i;
alpar@503
    79
    b=(i==j); b=(i!=j); b=(i<j);
alpar@503
    80
  }
alpar@503
    81
  {
alpar@503
    82
    Node n;
alpar@503
    83
    OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);
alpar@503
    84
    i=j;
alpar@503
    85
    j=G.first(i,n);
alpar@503
    86
    j=G.next(i);
alpar@503
    87
    bool b=G.valid(i); b=b;
alpar@503
    88
    Edge e(i);
alpar@503
    89
    e=i;
alpar@503
    90
    b=(i==j); b=(i!=j); b=(i<j);
alpar@503
    91
  }
alpar@503
    92
alpar@503
    93
  Node n,m;
alpar@503
    94
  n=G.addNode();
alpar@503
    95
  Edge e;
alpar@503
    96
  e=G.addEdge(n,m);
alpar@503
    97
  n=G.tail(e);
alpar@503
    98
  n=G.head(e);
alpar@503
    99
alpar@503
   100
  //aNode, bNode ?
alpar@503
   101
alpar@503
   102
  // id tests
alpar@503
   103
  { int i=G.id(n); i=i; }
alpar@503
   104
  { int i=G.id(e); i=i; }
alpar@503
   105
  
alpar@503
   106
  G.clear();
alpar@503
   107
alpar@503
   108
  //NodeMap tests
alpar@503
   109
  {
alpar@503
   110
    Node k;
alpar@515
   111
    typename Graph::template NodeMap<int> m(G);
alpar@515
   112
    typename Graph::template NodeMap<int> const &cm = m;  //Const map
alpar@515
   113
    //Inicialize with default value
alpar@515
   114
    typename Graph::template NodeMap<int> mdef(G,12);
alpar@515
   115
    typename Graph::template NodeMap<int> mm(cm);   //Copy
alpar@515
   116
    typename Graph::template NodeMap<double> dm(cm); //Copy from another type
alpar@503
   117
    int v;
alpar@503
   118
    v=m[k]; m[k]=v; m.set(k,v);
alpar@503
   119
    v=cm[k];
alpar@503
   120
    
alpar@503
   121
    m=cm;  
alpar@503
   122
    dm=cm; //Copy from another type
alpar@503
   123
  }  
alpar@503
   124
  { //bool NodeMap
alpar@503
   125
    Node k;
alpar@515
   126
    typename Graph::template NodeMap<bool> m(G);
alpar@515
   127
    typename Graph::template NodeMap<bool> const &cm = m;  //Const map
alpar@515
   128
    //Inicialize with default value
alpar@515
   129
    typename Graph::template NodeMap<bool> mdef(G,12);
alpar@515
   130
    typename Graph::template NodeMap<bool> mm(cm);   //Copy
alpar@515
   131
    typename Graph::template NodeMap<int> dm(cm); //Copy from another type
alpar@503
   132
    bool v;
alpar@503
   133
    v=m[k]; m[k]=v; m.set(k,v);
alpar@503
   134
    v=cm[k];
alpar@503
   135
    
alpar@503
   136
    m=cm;  
alpar@503
   137
    dm=cm; //Copy from another type
alpar@504
   138
    m=dm; //Copy to another type
alpar@503
   139
  }
alpar@503
   140
  //EdgeMap tests
alpar@503
   141
  {
alpar@503
   142
    Edge k;
alpar@515
   143
    typename Graph::template EdgeMap<int> m(G);
alpar@515
   144
    typename Graph::template EdgeMap<int> const &cm = m;  //Const map
alpar@515
   145
    //Inicialize with default value
alpar@515
   146
    typename Graph::template EdgeMap<int> mdef(G,12);
alpar@515
   147
    typename Graph::template EdgeMap<int> mm(cm);   //Copy
alpar@515
   148
    typename Graph::template EdgeMap<double> dm(cm); //Copy from another type
alpar@503
   149
    int v;
alpar@503
   150
    v=m[k]; m[k]=v; m.set(k,v);
alpar@503
   151
    v=cm[k];
alpar@503
   152
    
alpar@503
   153
    m=cm;  
alpar@503
   154
    dm=cm; //Copy from another type
alpar@503
   155
  }  
alpar@503
   156
  { //bool EdgeMap
alpar@503
   157
    Edge k;
alpar@515
   158
    typename Graph::template EdgeMap<bool> m(G);
alpar@515
   159
    typename Graph::template EdgeMap<bool> const &cm = m;  //Const map
alpar@515
   160
    //Inicialize with default value
alpar@515
   161
    typename Graph::template EdgeMap<bool> mdef(G,12);
alpar@515
   162
    typename Graph::template EdgeMap<bool> mm(cm);   //Copy
alpar@515
   163
    typename Graph::template EdgeMap<int> dm(cm); //Copy from another type
alpar@503
   164
    bool v;
alpar@503
   165
    v=m[k]; m[k]=v; m.set(k,v);
alpar@503
   166
    v=cm[k];
alpar@503
   167
    
alpar@503
   168
    m=cm;  
alpar@503
   169
    dm=cm; //Copy from another type
alpar@504
   170
    m=dm; //Copy to another type
alpar@503
   171
  }
alpar@503
   172
  
alpar@503
   173
}
alpar@503
   174
alpar@503
   175
alpar@503
   176
alpar@503
   177
template<class Graph> void addPetersen(Graph &G)
alpar@503
   178
{
alpar@503
   179
  std::vector<typename Graph::Node> outer, inner;
alpar@503
   180
  
alpar@503
   181
  for(int i=0;i<5;i++) {
alpar@503
   182
    outer.push_back(G.addNode());
alpar@503
   183
    inner.push_back(G.addNode());
alpar@503
   184
  }
alpar@503
   185
alpar@503
   186
 for(int i=0;i<5;i++) {
alpar@503
   187
    G.addEdge(outer[i],inner[i]);
alpar@503
   188
    G.addEdge(outer[i],outer[(i+1)%5]);
alpar@503
   189
    G.addEdge(inner[i],inner[(i+2)%5]);
alpar@503
   190
  }
alpar@503
   191
}
alpar@503
   192
alpar@503
   193
template<class Graph> void checkNodeList(Graph &G, int nn)
alpar@503
   194
{
alpar@503
   195
  typename Graph::NodeIt n(G);
alpar@503
   196
  for(int i=0;i<nn;i++) {
alpar@503
   197
    check(G.valid(n),"Wrong Node list linking.");
alpar@503
   198
    G.next(n);
alpar@503
   199
  }
alpar@503
   200
  check(!G.valid(n),"Wrong Node list linking.");
alpar@503
   201
}
alpar@503
   202
alpar@503
   203
template<class Graph> void checkEdgeList(Graph &G, int nn)
alpar@503
   204
{
alpar@503
   205
  typedef typename Graph::EdgeIt EdgeIt;
alpar@503
   206
alpar@503
   207
  EdgeIt e(G);
alpar@503
   208
  for(int i=0;i<nn;i++) {
alpar@503
   209
    check(G.valid(e),"Wrong Edge list linking.");
alpar@503
   210
    G.next(e);
alpar@503
   211
  }
alpar@503
   212
  check(!G.valid(e),"Wrong Edge list linking.");
alpar@503
   213
}
alpar@503
   214
alpar@503
   215
template<class Graph> void checkOutEdgeList(Graph &G,
alpar@503
   216
					    typename Graph::Node n,
alpar@503
   217
					    int nn)
alpar@503
   218
{
alpar@503
   219
  typename Graph::OutEdgeIt e(G,n);
alpar@503
   220
  for(int i=0;i<nn;i++) {
alpar@503
   221
    check(G.valid(e),"Wrong OutEdge list linking.");
alpar@503
   222
    G.next(e);
alpar@503
   223
  }
alpar@503
   224
  check(!G.valid(e),"Wrong OutEdge list linking.");
alpar@503
   225
}
alpar@503
   226
alpar@503
   227
template<class Graph> void checkInEdgeList(Graph &G,
alpar@503
   228
					    typename Graph::Node n,
alpar@503
   229
					    int nn)
alpar@503
   230
{
alpar@503
   231
  typename Graph::InEdgeIt e(G,n);
alpar@503
   232
  for(int i=0;i<nn;i++) {
alpar@503
   233
    check(G.valid(e),"Wrong InEdge list linking.");
alpar@503
   234
    G.next(e);
alpar@503
   235
  }
alpar@503
   236
  check(!G.valid(e),"Wrong InEdge list linking.");
alpar@503
   237
}
alpar@503
   238
alpar@503
   239
//Checks head(), tail() as well;
alpar@503
   240
template<class Graph> void bidirPetersen(Graph &G)
alpar@503
   241
{
alpar@503
   242
  typedef typename Graph::Edge Edge;
alpar@503
   243
  typedef typename Graph::EdgeIt EdgeIt;
alpar@503
   244
  
alpar@503
   245
  checkEdgeList(G,15);
alpar@503
   246
  
alpar@503
   247
  std::vector<Edge> ee;
alpar@503
   248
  
alpar@503
   249
  for(EdgeIt e(G);G.valid(e);G.next(e)) ee.push_back(e);
alpar@503
   250
alpar@503
   251
  for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
alpar@503
   252
    G.addEdge(G.head(*p),G.tail(*p));
alpar@503
   253
}
alpar@503
   254
alpar@503
   255
template<class Graph> void checkPetersen(Graph &G)
alpar@503
   256
{
alpar@503
   257
  typedef typename Graph::Node Node;
alpar@503
   258
alpar@503
   259
  typedef typename Graph::EdgeIt EdgeIt;
alpar@503
   260
  typedef typename Graph::NodeIt NodeIt;
alpar@503
   261
alpar@503
   262
  checkNodeList(G,10);
alpar@503
   263
  checkEdgeList(G,30);
alpar@503
   264
alpar@503
   265
  for(NodeIt n(G);G.valid(n);G.next(n)) {
alpar@503
   266
    checkInEdgeList(G,n,3);
alpar@503
   267
    checkOutEdgeList(G,n,3);
alpar@503
   268
    G.next(n);
alpar@503
   269
  }  
alpar@503
   270
}
alpar@503
   271
alpar@503
   272
template void checkCompile<GraphSkeleton>(GraphSkeleton &);
alpar@503
   273
template void checkCompile<SmartGraph>(SmartGraph &);
alpar@503
   274
template void checkCompile<SymSmartGraph>(SymSmartGraph &);
alpar@503
   275
template void checkCompile<ListGraph>(ListGraph &);
alpar@503
   276
template void checkCompile<SymListGraph>(SymListGraph &);
alpar@503
   277
//Due to some mysterious and some conceptual problems it does not work.
alpar@503
   278
//template void checkCompile<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
alpar@503
   279
alpar@503
   280
int main() 
alpar@503
   281
{
alpar@503
   282
  {
alpar@503
   283
    SmartGraph G;
alpar@503
   284
    addPetersen(G);
alpar@503
   285
    bidirPetersen(G);
alpar@503
   286
    checkPetersen(G);
alpar@503
   287
  }
alpar@503
   288
  {
alpar@503
   289
    ListGraph G;
alpar@503
   290
    addPetersen(G);
alpar@503
   291
    bidirPetersen(G);
alpar@503
   292
    checkPetersen(G);
alpar@503
   293
  }
alpar@503
   294
  {
alpar@503
   295
    SymSmartGraph G;
alpar@503
   296
    addPetersen(G);
alpar@503
   297
    checkPetersen(G);
alpar@503
   298
  }
alpar@503
   299
  {
alpar@503
   300
    SymListGraph G;
alpar@503
   301
    addPetersen(G);
alpar@503
   302
    checkPetersen(G);
alpar@503
   303
  }
alpar@503
   304
alpar@503
   305
  //\todo map tests.
alpar@503
   306
  //\todo copy constr tests.
alpar@503
   307
alpar@503
   308
  std::cout << __FILE__ ": All tests passed.\n";
alpar@503
   309
alpar@503
   310
}