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