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

     1 #include<iostream>

     2 #include<hugo/smart_graph.h>

     3 #include<hugo/skeletons/graph.h>

     4 //#include<../work/alpar/list_graph.h>

     6 /*

     7 This test makes consistency checks of list graph structures.

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

    11 */

    13 using namespace hugo;

    15 // void check(bool rc, const char *msg) {

    16 //   if(!rc) {

    17 //     std::cerr << msg << std::endl;

    18 //     exit(1);

    19 //   }

    20 // }

    22 #define check(rc, msg) \

    23   if(!rc) { \

    24     std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \

    25     exit(1); \

    26   } else { } \

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

    30 {

    31   typedef typename Graph::Node Node;

    32   typedef typename Graph::NodeIt NodeIt;

    33   typedef typename Graph::Edge Edge;

    34   typedef typename Graph::EdgeIt EdgeIt;

    35   typedef typename Graph::InEdgeIt InEdgeIt;

    36   typedef typename Graph::OutEdgeIt OutEdgeIt;

    38   {

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

    40     i=j;

    41     bool b=G.valid(i); b=b;

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

    43   }

    44   {

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

    46     i=j;

    47     j=G.first(i);

    48     j=G.next(i);

    49     bool b=G.valid(i); b=b;

    50     Node n(i);

    51     n=i;

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

    53   }

    54   {

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

    56     i=j;

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

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

    59   }

    60   {

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

    62     i=j;

    63     j=G.first(i);

    64     j=G.next(i);

    65     bool b=G.valid(i); b=b;

    66     Edge e(i);

    67     e=i;

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

    69   }

    70   {

    71     Node n;

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

    73     i=j;

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

    75     j=G.next(i);

    76     bool b=G.valid(i); b=b;

    77     Edge e(i);

    78     e=i;

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

    80   }

    81   {

    82     Node n;

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

    84     i=j;

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

    86     j=G.next(i);

    87     bool b=G.valid(i); b=b;

    88     Edge e(i);

    89     e=i;

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

    91   }

    93   Node n,m;

    94   n=G.addNode();

    95   Edge e;

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

    97   n=G.tail(e);

    98   n=G.head(e);

   100   //aNode, bNode ?

   102   // id tests

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

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

   106   G.clear();

   108   //NodeMap tests

   109   {

   110     Node k;

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

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

   113     //Inicialize with default value

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

   115     typename Graph::template NodeMap<int> mm(cm);   //Copy

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

   117     int v;

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

   119     v=cm[k];

   121     m=cm;

   122     dm=cm; //Copy from another type

   123   }

   124   { //bool NodeMap

   125     Node k;

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

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

   128     //Inicialize with default value

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

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

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

   132     bool v;

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

   134     v=cm[k];

   136     m=cm;

   137     dm=cm; //Copy from another type

   138     m=dm; //Copy to another type

   139   }

   140   //EdgeMap tests

   141   {

   142     Edge k;

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

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

   145     //Inicialize with default value

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

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

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

   149     int v;

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

   151     v=cm[k];

   153     m=cm;

   154     dm=cm; //Copy from another type

   155   }

   156   { //bool EdgeMap

   157     Edge k;

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

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

   160     //Inicialize with default value

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

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

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

   164     bool v;

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

   166     v=cm[k];

   168     m=cm;

   169     dm=cm; //Copy from another type

   170     m=dm; //Copy to another type

   171   }

   173 }

   175 template<class Graph> struct PetNodes

   176 {

   177   std::vector<typename Graph::Node> outer, inner;

   178   std::vector<typename Graph::Edge> outcir, incir, cons;

   179 };

   181 template<class Graph> PetNodes<Graph> addPetersen(Graph &G,int num=5)

   182 {

   183   //std::vector<typename Graph::Node> outer, inner;

   185   PetNodes<Graph> n;

   187   for(int i=0;i<num;i++) {

   188     n.outer.push_back(G.addNode());

   189     n.inner.push_back(G.addNode());

   190   }

   192  for(int i=0;i<num;i++) {

   193    n.cons.push_back(G.addEdge(n.outer[i],n.inner[i]));

   194    n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%5]));

   195    n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%5]));

   196   }

   197  return n;

   198 }

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

   201 {

   202   typename Graph::NodeIt n(G);

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

   204     check(G.valid(n),"Wrong Node list linking.");

   205     G.next(n);

   206   }

   207   check(!G.valid(n),"Wrong Node list linking.");

   208 }

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

   211 {

   212   typedef typename Graph::EdgeIt EdgeIt;

   214   EdgeIt e(G);

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

   216     check(G.valid(e),"Wrong Edge list linking.");

   217     G.next(e);

   218   }

   219   check(!G.valid(e),"Wrong Edge list linking.");

   220 }

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

   223 					    typename Graph::Node n,

   224 					    int nn)

   225 {

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

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

   228     check(G.valid(e),"Wrong OutEdge list linking.");

   229     G.next(e);

   230   }

   231   check(!G.valid(e),"Wrong OutEdge list linking.");

   232 }

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

   235 					    typename Graph::Node n,

   236 					    int nn)

   237 {

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

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

   240     check(G.valid(e),"Wrong InEdge list linking.");

   241     G.next(e);

   242   }

   243   check(!G.valid(e),"Wrong InEdge list linking.");

   244 }

   246 //Checks head(), tail() as well;

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

   248 {

   249   typedef typename Graph::Edge Edge;

   250   typedef typename Graph::EdgeIt EdgeIt;

   252   checkEdgeList(G,15);

   254   std::vector<Edge> ee;

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

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

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

   260 }

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

   263 {

   264   typedef typename Graph::Node Node;

   266   typedef typename Graph::EdgeIt EdgeIt;

   267   typedef typename Graph::NodeIt NodeIt;

   269   checkNodeList(G,10);

   270   checkEdgeList(G,30);

   272   for(NodeIt n(G);G.valid(n);G.next(n)) {

   273     checkInEdgeList(G,n,3);

   274     checkOutEdgeList(G,n,3);

   275     G.next(n);

   276   }

   277 }

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

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

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

   282 //template void checkCompile<ListGraph>(ListGraph &);

   283 //template void checkCompile<SymListGraph>(SymListGraph &);

   285 //Due to some mysterious and some conceptual problems it does not work.

   286 //template void checkCompile<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);

   288 int main()

   289 {

   290   {

   291     SmartGraph G;

   292     addPetersen(G);

   293     bidirPetersen(G);

   294     checkPetersen(G);

   295   }

   296 //   {

   297 //     ListGraph G;

   298 //     addPetersen(G);

   299 //     bidirPetersen(G);

   300 //     checkPetersen(G);

   301 //   }

   302   {

   303     SymSmartGraph G;

   304     addPetersen(G);

   305     checkPetersen(G);

   306   }

   307 //   {

   308 //     SymListGraph G;

   309 //     addPetersen(G);

   310 //     checkPetersen(G);

   311 //   }

   313   //\todo map tests.

   314   //\todo copy constr tests.

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

   318 }

author	marci
	Fri, 07 May 2004 06:33:02 +0000
changeset 565	18787f6db0db
parent 550	9e7613fa6d27
child 567	efaa79ee8d14
permissions	-rw-r--r--