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

     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::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 }

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

   178 {

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

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

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

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

   184   }

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

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

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

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

   190   }

   191 }

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

   194 {

   195   typename Graph::NodeIt n(G);

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

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

   198     G.next(n);

   199   }

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

   201 }

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

   204 {

   205   typedef typename Graph::EdgeIt EdgeIt;

   207   EdgeIt e(G);

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

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

   210     G.next(e);

   211   }

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

   213 }

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

   216 					    typename Graph::Node n,

   217 					    int nn)

   218 {

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

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

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

   222     G.next(e);

   223   }

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

   225 }

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

   228 					    typename Graph::Node n,

   229 					    int nn)

   230 {

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

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

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

   234     G.next(e);

   235   }

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

   237 }

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

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

   241 {

   242   typedef typename Graph::Edge Edge;

   243   typedef typename Graph::EdgeIt EdgeIt;

   245   checkEdgeList(G,15);

   247   std::vector<Edge> ee;

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

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

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

   253 }

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

   256 {

   257   typedef typename Graph::Node Node;

   259   typedef typename Graph::EdgeIt EdgeIt;

   260   typedef typename Graph::NodeIt NodeIt;

   262   checkNodeList(G,10);

   263   checkEdgeList(G,30);

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

   266     checkInEdgeList(G,n,3);

   267     checkOutEdgeList(G,n,3);

   268     G.next(n);

   269   }

   270 }

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

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

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

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

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

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

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

   280 int main()

   281 {

   282   {

   283     SmartGraph G;

   284     addPetersen(G);

   285     bidirPetersen(G);

   286     checkPetersen(G);

   287   }

   288   {

   289     ListGraph G;

   290     addPetersen(G);

   291     bidirPetersen(G);

   292     checkPetersen(G);

   293   }

   294   {

   295     SymSmartGraph G;

   296     addPetersen(G);

   297     checkPetersen(G);

   298   }

   299   {

   300     SymListGraph G;

   301     addPetersen(G);

   302     checkPetersen(G);

   303   }

   305   //\todo map tests.

   306   //\todo copy constr tests.

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

   310 }

author	marci
	Thu, 06 May 2004 13:46:07 +0000
changeset 541	5c5d970ef2f0
parent 504	6ef30329dd50
child 542	69bde1d90c04
permissions	-rw-r--r--