src/test/graph_test.cc
author alpar
Mon, 30 Aug 2004 12:01:47 +0000
changeset 774 4297098d9677
parent 733 240003bddaff
child 783 81bf2d766164
permissions -rw-r--r--
Merge back the whole branches/hugo++ to trunk.
alpar@503
     1
#include<iostream>
ladanyi@542
     2
#include<hugo/smart_graph.h>
alpar@564
     3
#include<hugo/skeletons/graph.h>
alpar@578
     4
#include<hugo/list_graph.h>
alpar@592
     5
#include<hugo/full_graph.h>
alpar@578
     6
alpar@567
     7
#include"test_tools.h"
alpar@567
     8
alpar@774
     9
/**
alpar@774
    10
\file
alpar@503
    11
This test makes consistency checks of list graph structures.
alpar@503
    12
alpar@774
    13
G.addNode(), G.addEdge(), G.tail(), G.head()
alpar@503
    14
alpar@592
    15
\todo Checks for empty graphs and isolated points.
alpar@774
    16
\todo Checks for Node->NodeIt, Edge->{EdgeIt,InEdgeIt,OutEdgeIt}
alpar@774
    17
conversion.
alpar@503
    18
*/
alpar@503
    19
alpar@503
    20
using namespace hugo;
alpar@733
    21
using namespace hugo::skeleton;
alpar@503
    22
alpar@592
    23
template<class Graph> void checkCompileStaticGraph(Graph &G) 
alpar@503
    24
{
alpar@503
    25
  typedef typename Graph::Node Node;
alpar@503
    26
  typedef typename Graph::NodeIt NodeIt;
alpar@503
    27
  typedef typename Graph::Edge Edge;
alpar@503
    28
  typedef typename Graph::EdgeIt EdgeIt;
alpar@503
    29
  typedef typename Graph::InEdgeIt InEdgeIt;
alpar@503
    30
  typedef typename Graph::OutEdgeIt OutEdgeIt;
alpar@503
    31
  
alpar@503
    32
  {
alpar@503
    33
    Node i; Node j(i); Node k(INVALID);
alpar@503
    34
    i=j;
alpar@774
    35
    //    bool b=G.valid(i); b=b;
alpar@774
    36
    bool b; b=b;
alpar@774
    37
    b=(i==INVALID); b=(i!=INVALID);
alpar@503
    38
    b=(i==j); b=(i!=j); b=(i<j);
alpar@503
    39
  }
alpar@503
    40
  {
alpar@503
    41
    NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);
alpar@503
    42
    i=j;
alpar@503
    43
    j=G.first(i);
alpar@774
    44
    j=++i;
alpar@774
    45
    //    bool b=G.valid(i); b=b;
alpar@774
    46
    bool b; b=b;
alpar@774
    47
    b=(i==INVALID); b=(i!=INVALID);
alpar@503
    48
    Node n(i);
alpar@503
    49
    n=i;
alpar@503
    50
    b=(i==j); b=(i!=j); b=(i<j);
alpar@774
    51
    //Node ->NodeIt conversion
alpar@774
    52
    NodeIt ni(G,n);
alpar@503
    53
  }
alpar@503
    54
  {
alpar@503
    55
    Edge i; Edge j(i); Edge k(INVALID);
alpar@503
    56
    i=j;
alpar@774
    57
    //    bool b=G.valid(i); b=b;
alpar@774
    58
    bool b; b=b;
alpar@774
    59
    b=(i==INVALID); b=(i!=INVALID);
alpar@503
    60
    b=(i==j); b=(i!=j); b=(i<j);
alpar@503
    61
  }
alpar@503
    62
  {
alpar@503
    63
    EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);
alpar@503
    64
    i=j;
alpar@503
    65
    j=G.first(i);
alpar@774
    66
    j=++i;
alpar@774
    67
    //    bool b=G.valid(i); b=b;
alpar@774
    68
    bool b; b=b;
alpar@774
    69
    b=(i==INVALID); b=(i!=INVALID);
alpar@503
    70
    Edge e(i);
alpar@503
    71
    e=i;
alpar@503
    72
    b=(i==j); b=(i!=j); b=(i<j);
alpar@774
    73
    //Edge ->EdgeIt conversion
alpar@774
    74
    EdgeIt ei(G,e);
alpar@503
    75
  }
alpar@503
    76
  {
alpar@503
    77
    Node n;
alpar@503
    78
    InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);
alpar@503
    79
    i=j;
alpar@503
    80
    j=G.first(i,n);
alpar@774
    81
    j=++i;
alpar@774
    82
    //    bool b=G.valid(i); b=b;
alpar@774
    83
    bool b; b=b;
alpar@774
    84
    b=(i==INVALID); b=(i!=INVALID);
alpar@503
    85
    Edge e(i);
alpar@503
    86
    e=i;
alpar@503
    87
    b=(i==j); b=(i!=j); b=(i<j);
alpar@774
    88
    //Edge ->InEdgeIt conversion
alpar@774
    89
    InEdgeIt ei(G,e);
alpar@503
    90
  }
alpar@503
    91
  {
alpar@503
    92
    Node n;
alpar@503
    93
    OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);
alpar@503
    94
    i=j;
alpar@503
    95
    j=G.first(i,n);
alpar@774
    96
    j=++i;
alpar@774
    97
    //    bool b=G.valid(i); b=b;
alpar@774
    98
    bool b; b=b;
alpar@774
    99
    b=(i==INVALID); b=(i!=INVALID);
alpar@503
   100
    Edge e(i);
alpar@503
   101
    e=i;
alpar@503
   102
    b=(i==j); b=(i!=j); b=(i<j);
alpar@774
   103
    //Edge ->OutEdgeIt conversion
alpar@774
   104
    OutEdgeIt ei(G,e);
alpar@503
   105
  }
alpar@774
   106
  {
alpar@774
   107
    Node n,m;
alpar@774
   108
    n=m=INVALID;
alpar@774
   109
    Edge e;
alpar@774
   110
    e=INVALID;
alpar@774
   111
    n=G.tail(e);
alpar@774
   112
    n=G.head(e);
alpar@774
   113
  }
alpar@503
   114
  // id tests
alpar@774
   115
  { Node n; int i=G.id(n); i=i; }
alpar@774
   116
  { Edge e; int i=G.id(e); i=i; }
alpar@503
   117
  //NodeMap tests
alpar@503
   118
  {
alpar@503
   119
    Node k;
alpar@515
   120
    typename Graph::template NodeMap<int> m(G);
alpar@774
   121
    //Const map
alpar@774
   122
    typename Graph::template NodeMap<int> const &cm = m;
alpar@515
   123
    //Inicialize with default value
alpar@515
   124
    typename Graph::template NodeMap<int> mdef(G,12);
alpar@774
   125
    //Copy
alpar@774
   126
    typename Graph::template NodeMap<int> mm(cm);
alpar@774
   127
    //Copy from another type
alpar@774
   128
    typename Graph::template NodeMap<double> dm(cm);
alpar@503
   129
    int v;
alpar@503
   130
    v=m[k]; m[k]=v; m.set(k,v);
alpar@503
   131
    v=cm[k];
alpar@503
   132
    
alpar@503
   133
    m=cm;  
alpar@503
   134
    dm=cm; //Copy from another type
alpar@503
   135
  }  
alpar@503
   136
  { //bool NodeMap
alpar@503
   137
    Node k;
alpar@515
   138
    typename Graph::template NodeMap<bool> m(G);
alpar@515
   139
    typename Graph::template NodeMap<bool> const &cm = m;  //Const map
alpar@515
   140
    //Inicialize with default value
alpar@515
   141
    typename Graph::template NodeMap<bool> mdef(G,12);
alpar@515
   142
    typename Graph::template NodeMap<bool> mm(cm);   //Copy
alpar@515
   143
    typename Graph::template NodeMap<int> dm(cm); //Copy from another type
alpar@503
   144
    bool v;
alpar@503
   145
    v=m[k]; m[k]=v; m.set(k,v);
alpar@503
   146
    v=cm[k];
alpar@503
   147
    
alpar@503
   148
    m=cm;  
alpar@503
   149
    dm=cm; //Copy from another type
alpar@504
   150
    m=dm; //Copy to another type
alpar@503
   151
  }
alpar@503
   152
  //EdgeMap tests
alpar@503
   153
  {
alpar@503
   154
    Edge k;
alpar@515
   155
    typename Graph::template EdgeMap<int> m(G);
alpar@515
   156
    typename Graph::template EdgeMap<int> const &cm = m;  //Const map
alpar@515
   157
    //Inicialize with default value
alpar@515
   158
    typename Graph::template EdgeMap<int> mdef(G,12);
alpar@515
   159
    typename Graph::template EdgeMap<int> mm(cm);   //Copy
alpar@515
   160
    typename Graph::template EdgeMap<double> dm(cm); //Copy from another type
alpar@503
   161
    int v;
alpar@503
   162
    v=m[k]; m[k]=v; m.set(k,v);
alpar@503
   163
    v=cm[k];
alpar@503
   164
    
alpar@503
   165
    m=cm;  
alpar@503
   166
    dm=cm; //Copy from another type
alpar@503
   167
  }  
alpar@503
   168
  { //bool EdgeMap
alpar@503
   169
    Edge k;
alpar@515
   170
    typename Graph::template EdgeMap<bool> m(G);
alpar@515
   171
    typename Graph::template EdgeMap<bool> const &cm = m;  //Const map
alpar@515
   172
    //Inicialize with default value
alpar@515
   173
    typename Graph::template EdgeMap<bool> mdef(G,12);
alpar@515
   174
    typename Graph::template EdgeMap<bool> mm(cm);   //Copy
alpar@515
   175
    typename Graph::template EdgeMap<int> dm(cm); //Copy from another type
alpar@503
   176
    bool v;
alpar@503
   177
    v=m[k]; m[k]=v; m.set(k,v);
alpar@503
   178
    v=cm[k];
alpar@503
   179
    
alpar@503
   180
    m=cm;  
alpar@503
   181
    dm=cm; //Copy from another type
alpar@504
   182
    m=dm; //Copy to another type
alpar@503
   183
  }
alpar@503
   184
}
alpar@503
   185
alpar@592
   186
template<class Graph> void checkCompile(Graph &G) 
alpar@592
   187
{
alpar@592
   188
  checkCompileStaticGraph(G);
alpar@592
   189
alpar@592
   190
  typedef typename Graph::Node Node;
alpar@592
   191
  typedef typename Graph::NodeIt NodeIt;
alpar@592
   192
  typedef typename Graph::Edge Edge;
alpar@592
   193
  typedef typename Graph::EdgeIt EdgeIt;
alpar@592
   194
  typedef typename Graph::InEdgeIt InEdgeIt;
alpar@592
   195
  typedef typename Graph::OutEdgeIt OutEdgeIt;
alpar@592
   196
  
alpar@592
   197
  Node n,m;
alpar@592
   198
  n=G.addNode();
alpar@592
   199
  m=G.addNode();
alpar@774
   200
  Edge e;
alpar@774
   201
  e=G.addEdge(n,m); 
alpar@592
   202
  
alpar@774
   203
  //  G.clear();
alpar@774
   204
}
alpar@774
   205
alpar@774
   206
template<class Graph> void checkCompileErase(Graph &G) 
alpar@774
   207
{
alpar@774
   208
  typedef typename Graph::Node Node;
alpar@774
   209
  typedef typename Graph::Edge Edge;
alpar@774
   210
  Node n;
alpar@774
   211
  Edge e;
alpar@774
   212
  G.erase(n);
alpar@774
   213
  G.erase(e);
alpar@774
   214
}
alpar@774
   215
alpar@774
   216
template<class Graph> void checkCompileEraseEdge(Graph &G) 
alpar@774
   217
{
alpar@774
   218
  typedef typename Graph::Edge Edge;
alpar@774
   219
  Edge e;
alpar@774
   220
  G.erase(e);
alpar@774
   221
}
alpar@774
   222
alpar@774
   223
template<class Graph> void checkCompileFindEdge(Graph &G) 
alpar@774
   224
{
alpar@774
   225
  typedef typename Graph::NodeIt Node;
alpar@774
   226
  typedef typename Graph::NodeIt NodeIt;
alpar@774
   227
alpar@774
   228
  G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
alpar@774
   229
  G.findEdge(Node(),Node(),G.findEdge(Node(),Node()));  
alpar@592
   230
}
alpar@592
   231
alpar@592
   232
alpar@503
   233
template<class Graph> void checkNodeList(Graph &G, int nn)
alpar@503
   234
{
alpar@503
   235
  typename Graph::NodeIt n(G);
alpar@503
   236
  for(int i=0;i<nn;i++) {
alpar@774
   237
    check(n!=INVALID,"Wrong Node list linking.");
alpar@774
   238
    ++n;
alpar@503
   239
  }
alpar@774
   240
  check(n==INVALID,"Wrong Node list linking.");
alpar@503
   241
}
alpar@503
   242
alpar@503
   243
template<class Graph> void checkEdgeList(Graph &G, int nn)
alpar@503
   244
{
alpar@503
   245
  typedef typename Graph::EdgeIt EdgeIt;
alpar@503
   246
alpar@503
   247
  EdgeIt e(G);
alpar@503
   248
  for(int i=0;i<nn;i++) {
alpar@774
   249
    check(e!=INVALID,"Wrong Edge list linking.");
alpar@774
   250
    ++e;
alpar@503
   251
  }
alpar@774
   252
  check(e==INVALID,"Wrong Edge list linking.");
alpar@503
   253
}
alpar@503
   254
alpar@503
   255
template<class Graph> void checkOutEdgeList(Graph &G,
alpar@503
   256
					    typename Graph::Node n,
alpar@503
   257
					    int nn)
alpar@503
   258
{
alpar@503
   259
  typename Graph::OutEdgeIt e(G,n);
alpar@503
   260
  for(int i=0;i<nn;i++) {
alpar@774
   261
    check(e!=INVALID,"Wrong OutEdge list linking.");
alpar@774
   262
    ++e;
alpar@503
   263
  }
alpar@774
   264
  check(e==INVALID,"Wrong OutEdge list linking.");
alpar@503
   265
}
alpar@503
   266
alpar@503
   267
template<class Graph> void checkInEdgeList(Graph &G,
alpar@774
   268
					   typename Graph::Node n,
alpar@774
   269
					   int nn)
alpar@503
   270
{
alpar@503
   271
  typename Graph::InEdgeIt e(G,n);
alpar@503
   272
  for(int i=0;i<nn;i++) {
alpar@774
   273
    check(e!=INVALID,"Wrong InEdge list linking.");
alpar@774
   274
    ++e;
alpar@503
   275
  }
alpar@774
   276
  check(e==INVALID,"Wrong InEdge list linking.");
alpar@503
   277
}
alpar@503
   278
alpar@774
   279
///\file
alpar@774
   280
///\todo Checks head(), tail() as well;
alpar@774
   281
alpar@503
   282
template<class Graph> void bidirPetersen(Graph &G)
alpar@503
   283
{
alpar@503
   284
  typedef typename Graph::Edge Edge;
alpar@503
   285
  typedef typename Graph::EdgeIt EdgeIt;
alpar@503
   286
  
alpar@503
   287
  checkEdgeList(G,15);
alpar@503
   288
  
alpar@503
   289
  std::vector<Edge> ee;
alpar@503
   290
  
alpar@774
   291
  for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e);
alpar@503
   292
alpar@503
   293
  for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
alpar@503
   294
    G.addEdge(G.head(*p),G.tail(*p));
alpar@503
   295
}
alpar@503
   296
alpar@503
   297
template<class Graph> void checkPetersen(Graph &G)
alpar@503
   298
{
alpar@503
   299
  typedef typename Graph::Node Node;
alpar@503
   300
alpar@503
   301
  typedef typename Graph::EdgeIt EdgeIt;
alpar@503
   302
  typedef typename Graph::NodeIt NodeIt;
alpar@503
   303
alpar@503
   304
  checkNodeList(G,10);
alpar@503
   305
  checkEdgeList(G,30);
alpar@503
   306
alpar@774
   307
  for(NodeIt n(G);n!=INVALID;++n) {
alpar@503
   308
    checkInEdgeList(G,n,3);
alpar@503
   309
    checkOutEdgeList(G,n,3);
alpar@774
   310
    ++n;
alpar@503
   311
  }  
alpar@503
   312
}
alpar@503
   313
alpar@774
   314
//Compile GraphSkeleton
alpar@774
   315
template 
alpar@733
   316
void checkCompileStaticGraph<StaticGraphSkeleton>(StaticGraphSkeleton &);
alpar@564
   317
template void checkCompile<GraphSkeleton>(GraphSkeleton &);
alpar@774
   318
template
alpar@774
   319
void checkCompileErase<EraseableGraphSkeleton>(EraseableGraphSkeleton &);
alpar@733
   320
alpar@774
   321
//Compile SmartGraph
alpar@503
   322
template void checkCompile<SmartGraph>(SmartGraph &);
alpar@774
   323
//Compile SymSmartGraph
alpar@503
   324
template void checkCompile<SymSmartGraph>(SymSmartGraph &);
alpar@774
   325
alpar@774
   326
//Compile ListGraph
alpar@578
   327
template void checkCompile<ListGraph>(ListGraph &);
alpar@774
   328
template void checkCompileErase<ListGraph>(ListGraph &);
alpar@774
   329
template void checkCompileFindEdge<ListGraph>(ListGraph &);
alpar@774
   330
alpar@774
   331
//Compile SymListGraph
alpar@578
   332
template void checkCompile<SymListGraph>(SymListGraph &);
alpar@774
   333
template void checkCompileErase<SymListGraph>(SymListGraph &);
alpar@774
   334
template void checkCompileFindEdge<SymListGraph>(SymListGraph &);
alpar@774
   335
alpar@774
   336
//Compile FullGraph
alpar@592
   337
template void checkCompileStaticGraph<FullGraph>(FullGraph &);
alpar@774
   338
template void checkCompileFindEdge<FullGraph>(FullGraph &);
alpar@550
   339
alpar@774
   340
//Compile EdgeSet <ListGraph>
alpar@579
   341
template void checkCompile<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
alpar@774
   342
template
alpar@774
   343
void checkCompileEraseEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
alpar@774
   344
template
alpar@774
   345
void checkCompileFindEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
alpar@774
   346
alpar@774
   347
//Compile EdgeSet <NodeSet>
alpar@717
   348
template void checkCompile<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
alpar@774
   349
template
alpar@774
   350
void checkCompileEraseEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
alpar@774
   351
template void checkCompileFindEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
alpar@774
   352
alpar@503
   353
alpar@503
   354
int main() 
alpar@503
   355
{
alpar@503
   356
  {
alpar@503
   357
    SmartGraph G;
alpar@503
   358
    addPetersen(G);
alpar@503
   359
    bidirPetersen(G);
alpar@503
   360
    checkPetersen(G);
alpar@503
   361
  }
alpar@578
   362
  {
alpar@578
   363
    ListGraph G;
alpar@578
   364
    addPetersen(G);
alpar@578
   365
    bidirPetersen(G);
alpar@578
   366
    checkPetersen(G);
alpar@578
   367
  }
alpar@503
   368
  {
alpar@503
   369
    SymSmartGraph G;
alpar@503
   370
    addPetersen(G);
alpar@503
   371
    checkPetersen(G);
alpar@503
   372
  }
alpar@578
   373
  {
alpar@578
   374
    SymListGraph G;
alpar@578
   375
    addPetersen(G);
alpar@578
   376
    checkPetersen(G);
alpar@578
   377
  }
alpar@503
   378
alpar@774
   379
  ///\file
alpar@774
   380
  ///\todo map tests.
alpar@774
   381
  ///\todo copy constr tests.
alpar@503
   382
alpar@503
   383
  std::cout << __FILE__ ": All tests passed.\n";
alpar@503
   384
alpar@579
   385
  return 0;
alpar@503
   386
}