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

     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   { //bool NodeMap

   137     Node k;

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

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

   140     //Inicialize with default value

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

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

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

   144     bool v;

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

   146     v=cm[k];

   148     m=cm;

   149     dm=cm; //Copy from another type

   150     m=dm; //Copy to another type

   151   }

   152   //EdgeMap tests

   153   {

   154     Edge k;

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

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

   157     //Inicialize with default value

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

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

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

   161     int v;

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

   163     v=cm[k];

   165     m=cm;

   166     dm=cm; //Copy from another type

   167   }

   168   { //bool EdgeMap

   169     Edge k;

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

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

   172     //Inicialize with default value

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

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

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

   176     bool 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     m=dm; //Copy to another type

   183   }

   184 }

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

   187 {

   188   checkCompileStaticGraph(G);

   190   typedef typename Graph::Node Node;

   191   typedef typename Graph::NodeIt NodeIt;

   192   typedef typename Graph::Edge Edge;

   193   typedef typename Graph::EdgeIt EdgeIt;

   194   typedef typename Graph::InEdgeIt InEdgeIt;

   195   typedef typename Graph::OutEdgeIt OutEdgeIt;

   197   Node n,m;

   198   n=G.addNode();

   199   m=G.addNode();

   200   Edge e;

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

   203   //  G.clear();

   204 }

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

   207 {

   208   typedef typename Graph::Node Node;

   209   typedef typename Graph::Edge Edge;

   210   Node n;

   211   Edge e;

   212   G.erase(n);

   213   G.erase(e);

   214 }

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

   217 {

   218   typedef typename Graph::Edge Edge;

   219   Edge e;

   220   G.erase(e);

   221 }

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

   224 {

   225   typedef typename Graph::NodeIt Node;

   226   typedef typename Graph::NodeIt NodeIt;

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

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

   230 }

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

   234 {

   235   typename Graph::NodeIt n(G);

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

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

   238     ++n;

   239   }

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

   241 }

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

   244 {

   245   typedef typename Graph::EdgeIt EdgeIt;

   247   EdgeIt e(G);

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

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

   250     ++e;

   251   }

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

   253 }

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

   256 					    typename Graph::Node n,

   257 					    int nn)

   258 {

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

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

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

   262     ++e;

   263   }

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

   265 }

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

   268 					   typename Graph::Node n,

   269 					   int nn)

   270 {

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

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

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

   274     ++e;

   275   }

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

   277 }

   279 ///\file

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

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

   283 {

   284   typedef typename Graph::Edge Edge;

   285   typedef typename Graph::EdgeIt EdgeIt;

   287   checkEdgeList(G,15);

   289   std::vector<Edge> ee;

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

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

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

   295 }

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

   298 {

   299   typedef typename Graph::Node Node;

   301   typedef typename Graph::EdgeIt EdgeIt;

   302   typedef typename Graph::NodeIt NodeIt;

   304   checkNodeList(G,10);

   305   checkEdgeList(G,30);

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

   308     checkInEdgeList(G,n,3);

   309     checkOutEdgeList(G,n,3);

   310     ++n;

   311   }

   312 }

   314 //Compile GraphSkeleton

   315 template

   316 void checkCompileStaticGraph<StaticGraphSkeleton>(StaticGraphSkeleton &);

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

   318 template

   319 void checkCompileErase<EraseableGraphSkeleton>(EraseableGraphSkeleton &);

   321 //Compile SmartGraph

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

   324 //Compile SymSmartGraph

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

   327 //Compile ListGraph

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

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

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

   333 //Compile SymListGraph

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

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

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

   338 //Compile FullGraph

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

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

   342 //Compile EdgeSet <ListGraph>

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

   344 template

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

   346 template

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

   349 //Compile EdgeSet <NodeSet>

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

   351 template

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

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

   356 int main()

   357 {

   358   {

   359     SmartGraph G;

   360     addPetersen(G);

   361     bidirPetersen(G);

   362     checkPetersen(G);

   363   }

   364   {

   365     ListGraph G;

   366     addPetersen(G);

   367     bidirPetersen(G);

   368     checkPetersen(G);

   369   }

   370   {

   371     SymSmartGraph G;

   372     addPetersen(G);

   373     checkPetersen(G);

   374   }

   375   {

   376     SymListGraph G;

   377     addPetersen(G);

   378     checkPetersen(G);

   379   }

   381   ///\file

   382   ///\todo map tests.

   383   ///\todo copy constr tests.

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

   387   return 0;

   388 }

author	deba
	Thu, 02 Sep 2004 10:54:26 +0000
changeset 783	81bf2d766164
parent 774	4297098d9677
child 787	584270fba752
permissions	-rw-r--r--