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

     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 This test makes consistency checks of list graph structures.

    12 G.addNode(), G.addEdge(), G.valid(), G.tail(), G.head()

    14 \todo Checks for empty graphs and isolated points.

    15 */

    17 using namespace hugo;

    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;

    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   }

    83   Node n,m;

    84   n=m=INVALID;

    85   Edge e;

    86   e=INVALID;

    87   n=G.tail(e);

    88   n=G.head(e);

    90   //aNode, bNode ?

    92   // id tests

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

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

    96   //  G.clear();

    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];

   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];

   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];

   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];

   158     m=cm;

   159     dm=cm; //Copy from another type

   160     m=dm; //Copy to another type

   161   }

   163 }

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

   166 {

   167   checkCompileStaticGraph(G);

   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;

   176   Node n,m;

   177   n=G.addNode();

   178   m=G.addNode();

   180   G.addEdge(n,m);

   181 }

   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 }

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

   195 {

   196   typedef typename Graph::EdgeIt EdgeIt;

   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 }

   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 }

   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 }

   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;

   236   checkEdgeList(G,15);

   238   std::vector<Edge> ee;

   240   for(EdgeIt e(G);G.valid(e);G.next(e)) ee.push_back(e);

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

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

   244 }

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

   247 {

   248   typedef typename Graph::Node Node;

   250   typedef typename Graph::EdgeIt EdgeIt;

   251   typedef typename Graph::NodeIt NodeIt;

   253   checkNodeList(G,10);

   254   checkEdgeList(G,30);

   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 }

   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 &);

   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> &);

   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   }

   299   //\todo map tests.

   300   //\todo copy constr tests.

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

   304   return 0;

   305 }

author	marci
	Fri, 21 May 2004 10:57:30 +0000
changeset 655	a9878222d5c8
parent 579	859f8c7e2a40
child 717	6874df3f61db
permissions	-rw-r--r--