lemon-0.x: src/test/graph_test.cc@cfa6c2ea48e5

     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>

     7 #include"test_tools.h"

     9 /**

    10 \file

    11 This test makes consistency checks of list graph structures.

    13 G.addNode(), G.addEdge(), G.tail(), G.head()

    15 \todo Checks for empty graphs and isolated points.

    16 \todo Checks for Node->NodeIt, Edge->{EdgeIt,InEdgeIt,OutEdgeIt}

    17 conversion.

    18 */

    20 using namespace hugo;

    22 template<class Graph> void checkCompileStaticGraph(Graph &G)

    23 {

    24   typedef typename Graph::Node Node;

    25   typedef typename Graph::NodeIt NodeIt;

    26   typedef typename Graph::Edge Edge;

    27   typedef typename Graph::EdgeIt EdgeIt;

    28   typedef typename Graph::InEdgeIt InEdgeIt;

    29   typedef typename Graph::OutEdgeIt OutEdgeIt;

    31   {

    32     Node i; Node j(i); Node k(INVALID);

    33     i=j;

    34     //    bool b=G.valid(i); b=b;

    35     bool b; b=b;

    36     b=(i==INVALID); b=(i!=INVALID);

    37     b=(i==j); b=(i!=j); b=(i<j);

    38   }

    39   {

    40     NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);

    41     i=j;

    42     j=G.first(i);

    43     j=++i;

    44     //    bool b=G.valid(i); b=b;

    45     bool b; b=b;

    46     b=(i==INVALID); b=(i!=INVALID);

    47     Node n(i);

    48     n=i;

    49     b=(i==j); b=(i!=j); b=(i<j);

    50     //Node ->NodeIt conversion

    51     NodeIt ni(G,n);

    52   }

    53   {

    54     Edge i; Edge j(i); Edge k(INVALID);

    55     i=j;

    56     //    bool b=G.valid(i); b=b;

    57     bool b; b=b;

    58     b=(i==INVALID); b=(i!=INVALID);

    59     b=(i==j); b=(i!=j); b=(i<j);

    60   }

    61   {

    62     EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);

    63     i=j;

    64     j=G.first(i);

    65     j=++i;

    66     //    bool b=G.valid(i); b=b;

    67     bool b; b=b;

    68     b=(i==INVALID); b=(i!=INVALID);

    69     Edge e(i);

    70     e=i;

    71     b=(i==j); b=(i!=j); b=(i<j);

    72     //Edge ->EdgeIt conversion

    73     EdgeIt ei(G,e);

    74   }

    75   {

    76     Node n;

    77     InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);

    78     i=j;

    79     j=G.first(i,n);

    80     j=++i;

    81     //    bool b=G.valid(i); b=b;

    82     bool b; b=b;

    83     b=(i==INVALID); b=(i!=INVALID);

    84     Edge e(i);

    85     e=i;

    86     b=(i==j); b=(i!=j); b=(i<j);

    87     //Edge ->InEdgeIt conversion

    88     InEdgeIt ei(G,e);

    89   }

    90   {

    91     Node n;

    92     OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);

    93     i=j;

    94     j=G.first(i,n);

    95     j=++i;

    96     //    bool b=G.valid(i); b=b;

    97     bool b; b=b;

    98     b=(i==INVALID); b=(i!=INVALID);

    99     Edge e(i);

   100     e=i;

   101     b=(i==j); b=(i!=j); b=(i<j);

   102     //Edge ->OutEdgeIt conversion

   103     OutEdgeIt ei(G,e);

   104   }

   105   {

   106     Node n,m;

   107     n=m=INVALID;

   108     Edge e;

   109     e=INVALID;

   110     n=G.tail(e);

   111     n=G.head(e);

   112   }

   113   // id tests

   114   { Node n; int i=G.id(n); i=i; }

   115   { Edge e; int i=G.id(e); i=i; }

   116   //NodeMap tests

   117   {

   118     Node k;

   119     typename Graph::template NodeMap<int> m(G);

   120     //Const map

   121     typename Graph::template NodeMap<int> const &cm = m;

   122     //Inicialize with default value

   123     typename Graph::template NodeMap<int> mdef(G,12);

   124     //Copy

   125     typename Graph::template NodeMap<int> mm(cm);

   126     //Copy from another type

   127     typename Graph::template NodeMap<double> dm(cm);

   128     int v;

   129     v=m[k]; m[k]=v; m.set(k,v);

   130     v=cm[k];

   132     m=cm;

   133     dm=cm; //Copy from another type

   134     {

   135       //Check the typedef's

   136       typename Graph::template NodeMap<int>::ValueType val;

   137       val=1;

   138       typename Graph::template NodeMap<int>::KeyType key;

   139       key = typename Graph::NodeIt(G);

   140     }

   141   }

   142   { //bool NodeMap

   143     Node k;

   144     typename Graph::template NodeMap<bool> m(G);

   145     typename Graph::template NodeMap<bool> const &cm = m;  //Const map

   146     //Inicialize with default value

   147     typename Graph::template NodeMap<bool> mdef(G,12);

   148     typename Graph::template NodeMap<bool> mm(cm);   //Copy

   149     typename Graph::template NodeMap<int> dm(cm); //Copy from another type

   150     bool v;

   151     v=m[k]; m[k]=v; m.set(k,v);

   152     v=cm[k];

   154     m=cm;

   155     dm=cm; //Copy from another type

   156     m=dm; //Copy to another type

   158     {

   159       //Check the typedef's

   160       typename Graph::template NodeMap<bool>::ValueType val;

   161       val=true;

   162       typename Graph::template NodeMap<bool>::KeyType key;

   163       key= typename Graph::NodeIt(G);

   164     }

   165   }

   166   //EdgeMap tests

   167   {

   168     Edge k;

   169     typename Graph::template EdgeMap<int> m(G);

   170     typename Graph::template EdgeMap<int> const &cm = m;  //Const map

   171     //Inicialize with default value

   172     typename Graph::template EdgeMap<int> mdef(G,12);

   173     typename Graph::template EdgeMap<int> mm(cm);   //Copy

   174     typename Graph::template EdgeMap<double> dm(cm); //Copy from another type

   175     int v;

   176     v=m[k]; m[k]=v; m.set(k,v);

   177     v=cm[k];

   179     m=cm;

   180     dm=cm; //Copy from another type

   181     {

   182       //Check the typedef's

   183       typename Graph::template EdgeMap<int>::ValueType val;

   184       val=1;

   185       typename Graph::template EdgeMap<int>::KeyType key;

   186       key= typename Graph::EdgeIt(G);

   187     }

   188   }

   189   { //bool EdgeMap

   190     Edge k;

   191     typename Graph::template EdgeMap<bool> m(G);

   192     typename Graph::template EdgeMap<bool> const &cm = m;  //Const map

   193     //Inicialize with default value

   194     typename Graph::template EdgeMap<bool> mdef(G,12);

   195     typename Graph::template EdgeMap<bool> mm(cm);   //Copy

   196     typename Graph::template EdgeMap<int> dm(cm); //Copy from another type

   197     bool v;

   198     v=m[k]; m[k]=v; m.set(k,v);

   199     v=cm[k];

   201     m=cm;

   202     dm=cm; //Copy from another type

   203     m=dm; //Copy to another type

   204     {

   205       //Check the typedef's

   206       typename Graph::template EdgeMap<bool>::ValueType val;

   207       val=true;

   208       typename Graph::template EdgeMap<bool>::KeyType key;

   209       key= typename Graph::EdgeIt(G);

   210     }

   211   }

   212 }

   214 template<class Graph> void checkCompile(Graph &G)

   215 {

   216   checkCompileStaticGraph(G);

   218   typedef typename Graph::Node Node;

   219   typedef typename Graph::NodeIt NodeIt;

   220   typedef typename Graph::Edge Edge;

   221   typedef typename Graph::EdgeIt EdgeIt;

   222   typedef typename Graph::InEdgeIt InEdgeIt;

   223   typedef typename Graph::OutEdgeIt OutEdgeIt;

   225   Node n,m;

   226   n=G.addNode();

   227   m=G.addNode();

   228   Edge e;

   229   e=G.addEdge(n,m);

   231   //  G.clear();

   232 }

   234 template<class Graph> void checkCompileErase(Graph &G)

   235 {

   236   typedef typename Graph::Node Node;

   237   typedef typename Graph::Edge Edge;

   238   Node n;

   239   Edge e;

   240   G.erase(n);

   241   G.erase(e);

   242 }

   244 template<class Graph> void checkCompileEraseEdge(Graph &G)

   245 {

   246   typedef typename Graph::Edge Edge;

   247   Edge e;

   248   G.erase(e);

   249 }

   251 template<class Graph> void checkCompileFindEdge(Graph &G)

   252 {

   253   typedef typename Graph::NodeIt Node;

   254   typedef typename Graph::NodeIt NodeIt;

   256   G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));

   257   G.findEdge(Node(),Node(),G.findEdge(Node(),Node()));

   258 }

   261 template<class Graph> void checkNodeList(Graph &G, int nn)

   262 {

   263   typename Graph::NodeIt n(G);

   264   for(int i=0;i<nn;i++) {

   265     check(n!=INVALID,"Wrong Node list linking.");

   266     ++n;

   267   }

   268   check(n==INVALID,"Wrong Node list linking.");

   269 }

   271 template<class Graph> void checkEdgeList(Graph &G, int nn)

   272 {

   273   typedef typename Graph::EdgeIt EdgeIt;

   275   EdgeIt e(G);

   276   for(int i=0;i<nn;i++) {

   277     check(e!=INVALID,"Wrong Edge list linking.");

   278     ++e;

   279   }

   280   check(e==INVALID,"Wrong Edge list linking.");

   281 }

   283 template<class Graph> void checkOutEdgeList(Graph &G,

   284 					    typename Graph::Node n,

   285 					    int nn)

   286 {

   287   typename Graph::OutEdgeIt e(G,n);

   288   for(int i=0;i<nn;i++) {

   289     check(e!=INVALID,"Wrong OutEdge list linking.");

   290     ++e;

   291   }

   292   check(e==INVALID,"Wrong OutEdge list linking.");

   293 }

   295 template<class Graph> void checkInEdgeList(Graph &G,

   296 					   typename Graph::Node n,

   297 					   int nn)

   298 {

   299   typename Graph::InEdgeIt e(G,n);

   300   for(int i=0;i<nn;i++) {

   301     check(e!=INVALID,"Wrong InEdge list linking.");

   302     ++e;

   303   }

   304   check(e==INVALID,"Wrong InEdge list linking.");

   305 }

   307 ///\file

   308 ///\todo Checks head(), tail() as well;

   310 template<class Graph> void bidirPetersen(Graph &G)

   311 {

   312   typedef typename Graph::Edge Edge;

   313   typedef typename Graph::EdgeIt EdgeIt;

   315   checkEdgeList(G,15);

   317   std::vector<Edge> ee;

   319   for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e);

   321   for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)

   322     G.addEdge(G.head(*p),G.tail(*p));

   323 }

   325 template<class Graph> void checkPetersen(Graph &G)

   326 {

   327   typedef typename Graph::Node Node;

   329   typedef typename Graph::EdgeIt EdgeIt;

   330   typedef typename Graph::NodeIt NodeIt;

   332   checkNodeList(G,10);

   333   checkEdgeList(G,30);

   335   for(NodeIt n(G);n!=INVALID;++n) {

   336     checkInEdgeList(G,n,3);

   337     checkOutEdgeList(G,n,3);

   338     ++n;

   339   }

   340 }

   342 //Compile GraphSkeleton

   343 template void checkCompileStaticGraph<skeleton::StaticGraphSkeleton>

   344 (skeleton::StaticGraphSkeleton &);

   346 template void checkCompile<skeleton::GraphSkeleton>(skeleton::GraphSkeleton &);

   348 template void checkCompileErase<skeleton::EraseableGraphSkeleton>

   349 (skeleton::EraseableGraphSkeleton &);

   351 //Compile SmartGraph

   352 template void checkCompile<SmartGraph>(SmartGraph &);

   354 //Compile SymSmartGraph

   355 template void checkCompile<SymSmartGraph>(SymSmartGraph &);

   357 //Compile ListGraph

   358 template void checkCompile<ListGraph>(ListGraph &);

   359 template void checkCompileErase<ListGraph>(ListGraph &);

   360 template void checkCompileFindEdge<ListGraph>(ListGraph &);

   363 //Compile SymListGraph

   364 template void checkCompile<SymListGraph>(SymListGraph &);

   365 template void checkCompileErase<SymListGraph>(SymListGraph &);

   366 template void checkCompileFindEdge<SymListGraph>(SymListGraph &);

   368 //Compile FullGraph

   369 template void checkCompileStaticGraph<FullGraph>(FullGraph &);

   370 template void checkCompileFindEdge<FullGraph>(FullGraph &);

   372 //Compile EdgeSet <ListGraph>

   373 template void checkCompile<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);

   374 template

   375 void checkCompileEraseEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);

   376 template

   377 void checkCompileFindEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);

   379 //Compile EdgeSet <NodeSet>

   380 template void checkCompile<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);

   381 template

   382 void checkCompileEraseEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);

   383 template void checkCompileFindEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);

   386 int main()

   387 {

   388   {

   389     SmartGraph G;

   390     addPetersen(G);

   391     bidirPetersen(G);

   392     checkPetersen(G);

   393   }

   394   {

   395     ListGraph G;

   396     addPetersen(G);

   397     bidirPetersen(G);

   398     checkPetersen(G);

   399   }

   400   {

   401     SymSmartGraph G;

   402     addPetersen(G);

   403     checkPetersen(G);

   404   }

   405   {

   406     SymListGraph G;

   407     addPetersen(G);

   408     checkPetersen(G);

   409   }

   411   ///\file

   412   ///\todo map tests.

   413   ///\todo copy constr tests.

   415   std::cout << __FILE__ ": All tests passed.\n";

   417   return 0;

   418 }

author	alpar
	Fri, 03 Sep 2004 10:43:22 +0000
changeset 795	cfa6c2ea48e5
parent 787	584270fba752
child 800	b70a494b4912
permissions	-rw-r--r--