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

     1 #include<iostream>

     2 #include<smart_graph.h>

     3 #include<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::NodeMap<int> m(G);

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

   113     typename Graph::NodeMap<int> mdef(G,12); //Inicialize with default value

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

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

   116     int v;

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

   118     v=cm[k];

   120     m=cm;

   121     dm=cm; //Copy from another type

   122   }

   123   { //bool NodeMap

   124     Node k;

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

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

   127     typename Graph::NodeMap<bool> mdef(G,12); //Inicialize with default value

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

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

   130     bool v;

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

   132     v=cm[k];

   134     m=cm;

   135     dm=cm; //Copy from another type

   136   }

   137   //EdgeMap tests

   138   {

   139     Edge k;

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

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

   142     typename Graph::EdgeMap<int> mdef(G,12); //Inicialize with default value

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

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

   145     int v;

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

   147     v=cm[k];

   149     m=cm;

   150     dm=cm; //Copy from another type

   151   }

   152   { //bool EdgeMap

   153     Edge k;

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

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

   156     typename Graph::EdgeMap<bool> mdef(G,12); //Inicialize with default value

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

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

   159     bool v;

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

   161     v=cm[k];

   163     m=cm;

   164     dm=cm; //Copy from another type

   165   }

   167 }

   171 template<class Graph> void addPetersen(Graph &G)

   172 {

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

   175   for(int i=0;i<5;i++) {

   176     outer.push_back(G.addNode());

   177     inner.push_back(G.addNode());

   178   }

   180  for(int i=0;i<5;i++) {

   181     G.addEdge(outer[i],inner[i]);

   182     G.addEdge(outer[i],outer[(i+1)%5]);

   183     G.addEdge(inner[i],inner[(i+2)%5]);

   184   }

   185 }

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

   188 {

   189   typename Graph::NodeIt n(G);

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

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

   192     G.next(n);

   193   }

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

   195 }

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

   198 {

   199   typedef typename Graph::EdgeIt EdgeIt;

   201   EdgeIt e(G);

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

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

   204     G.next(e);

   205   }

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

   207 }

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

   210 					    typename Graph::Node n,

   211 					    int nn)

   212 {

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

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

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

   216     G.next(e);

   217   }

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

   219 }

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

   222 					    typename Graph::Node n,

   223 					    int nn)

   224 {

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

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

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

   228     G.next(e);

   229   }

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

   231 }

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

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

   235 {

   236   typedef typename Graph::Edge Edge;

   237   typedef typename Graph::EdgeIt EdgeIt;

   239   checkEdgeList(G,15);

   241   std::vector<Edge> ee;

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

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

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

   247 }

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

   250 {

   251   typedef typename Graph::Node Node;

   253   typedef typename Graph::EdgeIt EdgeIt;

   254   typedef typename Graph::NodeIt NodeIt;

   256   checkNodeList(G,10);

   257   checkEdgeList(G,30);

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

   260     checkInEdgeList(G,n,3);

   261     checkOutEdgeList(G,n,3);

   262     G.next(n);

   263   }

   264 }

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

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

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

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

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

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

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

   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 }

author	alpar
	Mon, 03 May 2004 07:27:29 +0000
changeset 503	769f31e9f7b0
child 504	6ef30329dd50
permissions	-rw-r--r--