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