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

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

   137   }

   138   //EdgeMap tests

   139   {

   140     Edge k;

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

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

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

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

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

   146     int v;

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

   148     v=cm[k];

   150     m=cm;

   151     dm=cm; //Copy from another type

   152   }

   153   { //bool EdgeMap

   154     Edge k;

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

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

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

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

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

   160     bool v;

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

   162     v=cm[k];

   164     m=cm;

   165     dm=cm; //Copy from another type

   166     m=dm; //Copy to another type

   167   }

   169 }

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

   174 {

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

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

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

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

   180   }

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

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

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

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

   186   }

   187 }

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

   190 {

   191   typename Graph::NodeIt n(G);

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

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

   194     G.next(n);

   195   }

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

   197 }

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

   200 {

   201   typedef typename Graph::EdgeIt EdgeIt;

   203   EdgeIt e(G);

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

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

   206     G.next(e);

   207   }

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

   209 }

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

   212 					    typename Graph::Node n,

   213 					    int nn)

   214 {

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

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

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

   218     G.next(e);

   219   }

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

   221 }

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

   224 					    typename Graph::Node n,

   225 					    int nn)

   226 {

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

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

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

   230     G.next(e);

   231   }

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

   233 }

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

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

   237 {

   238   typedef typename Graph::Edge Edge;

   239   typedef typename Graph::EdgeIt EdgeIt;

   241   checkEdgeList(G,15);

   243   std::vector<Edge> ee;

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

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

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

   249 }

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

   252 {

   253   typedef typename Graph::Node Node;

   255   typedef typename Graph::EdgeIt EdgeIt;

   256   typedef typename Graph::NodeIt NodeIt;

   258   checkNodeList(G,10);

   259   checkEdgeList(G,30);

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

   262     checkInEdgeList(G,n,3);

   263     checkOutEdgeList(G,n,3);

   264     G.next(n);

   265   }

   266 }

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

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

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

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

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

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

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

   276 int main()

   277 {

   278   {

   279     SmartGraph G;

   280     addPetersen(G);

   281     bidirPetersen(G);

   282     checkPetersen(G);

   283   }

   284   {

   285     ListGraph G;

   286     addPetersen(G);

   287     bidirPetersen(G);

   288     checkPetersen(G);

   289   }

   290   {

   291     SymSmartGraph G;

   292     addPetersen(G);

   293     checkPetersen(G);

   294   }

   295   {

   296     SymListGraph G;

   297     addPetersen(G);

   298     checkPetersen(G);

   299   }

   301   //\todo map tests.

   302   //\todo copy constr tests.

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

   306 }

author	alpar
	Mon, 03 May 2004 08:13:41 +0000
changeset 504	6ef30329dd50
parent 503	769f31e9f7b0
child 515	a7eeb8af6b34
permissions	-rw-r--r--