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