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

     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;

    21 using namespace hugo::skeleton;

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

    24 {

    25   typedef typename Graph::Node Node;

    26   typedef typename Graph::NodeIt NodeIt;

    27   typedef typename Graph::Edge Edge;

    28   typedef typename Graph::EdgeIt EdgeIt;

    29   typedef typename Graph::InEdgeIt InEdgeIt;

    30   typedef typename Graph::OutEdgeIt OutEdgeIt;

    32   {

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

    34     i=j;

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

    36     bool b; b=b;

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

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

    39   }

    40   {

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

    42     i=j;

    43     j=G.first(i);

    44     j=++i;

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

    46     bool b; b=b;

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

    48     Node n(i);

    49     n=i;

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

    51     //Node ->NodeIt conversion

    52     NodeIt ni(G,n);

    53   }

    54   {

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

    56     i=j;

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

    58     bool b; b=b;

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

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

    61   }

    62   {

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

    64     i=j;

    65     j=G.first(i);

    66     j=++i;

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

    68     bool b; b=b;

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

    70     Edge e(i);

    71     e=i;

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

    73     //Edge ->EdgeIt conversion

    74     EdgeIt ei(G,e);

    75   }

    76   {

    77     Node n;

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

    79     i=j;

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

    81     j=++i;

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

    83     bool b; b=b;

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

    85     Edge e(i);

    86     e=i;

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

    88     //Edge ->InEdgeIt conversion

    89     InEdgeIt ei(G,e);

    90   }

    91   {

    92     Node n;

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

    94     i=j;

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

    96     j=++i;

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

    98     bool b; b=b;

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

   100     Edge e(i);

   101     e=i;

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

   103     //Edge ->OutEdgeIt conversion

   104     OutEdgeIt ei(G,e);

   105   }

   106   {

   107     Node n,m;

   108     n=m=INVALID;

   109     Edge e;

   110     e=INVALID;

   111     n=G.tail(e);

   112     n=G.head(e);

   113   }

   114   // id tests

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

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

   117   //NodeMap tests

   118   {

   119     Node k;

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

   121     //Const map

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

   123     //Inicialize with default value

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

   125     //Copy

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

   127     //Copy from another type

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

   129     int v;

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

   131     v=cm[k];

   133     m=cm;

   134     dm=cm; //Copy from another type

   135     {

   136       //Check the typedef's

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

   138       val=1;

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

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

   141     }

   142   }

   143   { //bool NodeMap

   144     Node k;

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

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

   147     //Inicialize with default value

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

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

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

   151     bool v;

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

   153     v=cm[k];

   155     m=cm;

   156     dm=cm; //Copy from another type

   157     m=dm; //Copy to another type

   159     {

   160       //Check the typedef's

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

   162       val=true;

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

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

   165     }

   166   }

   167   //EdgeMap tests

   168   {

   169     Edge k;

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

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

   172     //Inicialize with default value

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

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

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

   176     int v;

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

   178     v=cm[k];

   180     m=cm;

   181     dm=cm; //Copy from another type

   182     {

   183       //Check the typedef's

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

   185       val=1;

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

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

   188     }

   189   }

   190   { //bool EdgeMap

   191     Edge k;

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

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

   194     //Inicialize with default value

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

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

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

   198     bool v;

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

   200     v=cm[k];

   202     m=cm;

   203     dm=cm; //Copy from another type

   204     m=dm; //Copy to another type

   205     {

   206       //Check the typedef's

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

   208       val=true;

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

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

   211     }

   212   }

   213 }

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

   216 {

   217   checkCompileStaticGraph(G);

   219   typedef typename Graph::Node Node;

   220   typedef typename Graph::NodeIt NodeIt;

   221   typedef typename Graph::Edge Edge;

   222   typedef typename Graph::EdgeIt EdgeIt;

   223   typedef typename Graph::InEdgeIt InEdgeIt;

   224   typedef typename Graph::OutEdgeIt OutEdgeIt;

   226   Node n,m;

   227   n=G.addNode();

   228   m=G.addNode();

   229   Edge e;

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

   232   //  G.clear();

   233 }

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

   236 {

   237   typedef typename Graph::Node Node;

   238   typedef typename Graph::Edge Edge;

   239   Node n;

   240   Edge e;

   241   G.erase(n);

   242   G.erase(e);

   243 }

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

   246 {

   247   typedef typename Graph::Edge Edge;

   248   Edge e;

   249   G.erase(e);

   250 }

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

   253 {

   254   typedef typename Graph::NodeIt Node;

   255   typedef typename Graph::NodeIt NodeIt;

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

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

   259 }

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

   263 {

   264   typename Graph::NodeIt n(G);

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

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

   267     ++n;

   268   }

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

   270 }

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

   273 {

   274   typedef typename Graph::EdgeIt EdgeIt;

   276   EdgeIt e(G);

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

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

   279     ++e;

   280   }

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

   282 }

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

   285 					    typename Graph::Node n,

   286 					    int nn)

   287 {

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

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

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

   291     ++e;

   292   }

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

   294 }

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

   297 					   typename Graph::Node n,

   298 					   int nn)

   299 {

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

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

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

   303     ++e;

   304   }

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

   306 }

   308 ///\file

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

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

   312 {

   313   typedef typename Graph::Edge Edge;

   314   typedef typename Graph::EdgeIt EdgeIt;

   316   checkEdgeList(G,15);

   318   std::vector<Edge> ee;

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

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

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

   324 }

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

   327 {

   328   typedef typename Graph::Node Node;

   330   typedef typename Graph::EdgeIt EdgeIt;

   331   typedef typename Graph::NodeIt NodeIt;

   333   checkNodeList(G,10);

   334   checkEdgeList(G,30);

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

   337     checkInEdgeList(G,n,3);

   338     checkOutEdgeList(G,n,3);

   339     ++n;

   340   }

   341 }

   343 //Compile GraphSkeleton

   344 template

   345 void checkCompileStaticGraph<StaticGraphSkeleton>(StaticGraphSkeleton &);

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

   347 template

   348 void checkCompileErase<EraseableGraphSkeleton>(EraseableGraphSkeleton &);

   350 //Compile SmartGraph

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

   353 //Compile SymSmartGraph

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

   356 //Compile ListGraph

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

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

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

   362 //Compile SymListGraph

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

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

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

   367 //Compile FullGraph

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

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

   371 //Compile EdgeSet <ListGraph>

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

   373 template

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

   375 template

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

   378 //Compile EdgeSet <NodeSet>

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

   380 template

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

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

   385 int main()

   386 {

   387   {

   388     SmartGraph G;

   389     addPetersen(G);

   390     bidirPetersen(G);

   391     checkPetersen(G);

   392   }

   393   {

   394     ListGraph G;

   395     addPetersen(G);

   396     bidirPetersen(G);

   397     checkPetersen(G);

   398   }

   399   {

   400     SymSmartGraph G;

   401     addPetersen(G);

   402     checkPetersen(G);

   403   }

   404   {

   405     SymListGraph G;

   406     addPetersen(G);

   407     checkPetersen(G);

   408   }

   410   ///\file

   411   ///\todo map tests.

   412   ///\todo copy constr tests.

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

   416   return 0;

   417 }

author	alpar
	Thu, 02 Sep 2004 15:30:50 +0000
changeset 787	584270fba752
parent 783	81bf2d766164
child 793	9cd0aeea47b0
permissions	-rw-r--r--