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

     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;

    18 using namespace hugo::skeleton;

    20 template<class Graph> void checkCompileStaticGraph(Graph &G)

    21 {

    22   typedef typename Graph::Node Node;

    23   typedef typename Graph::NodeIt NodeIt;

    24   typedef typename Graph::Edge Edge;

    25   typedef typename Graph::EdgeIt EdgeIt;

    26   typedef typename Graph::InEdgeIt InEdgeIt;

    27   typedef typename Graph::OutEdgeIt OutEdgeIt;

    29   {

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

    31     i=j;

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

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

    34   }

    35   {

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

    37     i=j;

    38     j=G.first(i);

    39     j=G.next(i);

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

    41     Node n(i);

    42     n=i;

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

    44   }

    45   {

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

    47     i=j;

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

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

    50   }

    51   {

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

    53     i=j;

    54     j=G.first(i);

    55     j=G.next(i);

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

    57     Edge e(i);

    58     e=i;

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

    60   }

    61   {

    62     Node n;

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

    64     i=j;

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

    66     j=G.next(i);

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

    68     Edge e(i);

    69     e=i;

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

    71   }

    72   {

    73     Node n;

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

    75     i=j;

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

    77     j=G.next(i);

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

    79     Edge e(i);

    80     e=i;

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

    82   }

    84   Node n,m;

    85   n=m=INVALID;

    86   Edge e;

    87   e=INVALID;

    88   n=G.tail(e);

    89   n=G.head(e);

    91   //aNode, bNode ?

    93   // id tests

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

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

    97   //  G.clear();

    99   //NodeMap tests

   100   {

   101     Node k;

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

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

   104     //Inicialize with default value

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

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

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

   108     int v;

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

   110     v=cm[k];

   112     m=cm;

   113     dm=cm; //Copy from another type

   114   }

   115   { //bool NodeMap

   116     Node k;

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

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

   119     //Inicialize with default value

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

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

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

   123     bool v;

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

   125     v=cm[k];

   127     m=cm;

   128     dm=cm; //Copy from another type

   129     m=dm; //Copy to another type

   130   }

   131   //EdgeMap tests

   132   {

   133     Edge k;

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

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

   136     //Inicialize with default value

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

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

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

   140     int v;

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

   142     v=cm[k];

   144     m=cm;

   145     dm=cm; //Copy from another type

   146   }

   147   { //bool EdgeMap

   148     Edge k;

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

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

   151     //Inicialize with default value

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

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

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

   155     bool v;

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

   157     v=cm[k];

   159     m=cm;

   160     dm=cm; //Copy from another type

   161     m=dm; //Copy to another type

   162   }

   164 }

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

   167 {

   168   checkCompileStaticGraph(G);

   170   typedef typename Graph::Node Node;

   171   typedef typename Graph::NodeIt NodeIt;

   172   typedef typename Graph::Edge Edge;

   173   typedef typename Graph::EdgeIt EdgeIt;

   174   typedef typename Graph::InEdgeIt InEdgeIt;

   175   typedef typename Graph::OutEdgeIt OutEdgeIt;

   177   Node n,m;

   178   n=G.addNode();

   179   m=G.addNode();

   181   G.addEdge(n,m);

   182 }

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

   186 {

   187   typename Graph::NodeIt n(G);

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

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

   190     G.next(n);

   191   }

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

   193 }

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

   196 {

   197   typedef typename Graph::EdgeIt EdgeIt;

   199   EdgeIt e(G);

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

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

   202     G.next(e);

   203   }

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

   205 }

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

   208 					    typename Graph::Node n,

   209 					    int nn)

   210 {

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

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

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

   214     G.next(e);

   215   }

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

   217 }

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

   220 					    typename Graph::Node n,

   221 					    int nn)

   222 {

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

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

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

   226     G.next(e);

   227   }

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

   229 }

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

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

   233 {

   234   typedef typename Graph::Edge Edge;

   235   typedef typename Graph::EdgeIt EdgeIt;

   237   checkEdgeList(G,15);

   239   std::vector<Edge> ee;

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

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

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

   245 }

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

   248 {

   249   typedef typename Graph::Node Node;

   251   typedef typename Graph::EdgeIt EdgeIt;

   252   typedef typename Graph::NodeIt NodeIt;

   254   checkNodeList(G,10);

   255   checkEdgeList(G,30);

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

   258     checkInEdgeList(G,n,3);

   259     checkOutEdgeList(G,n,3);

   260     G.next(n);

   261   }

   262 }

   264 template

   265 void checkCompileStaticGraph<StaticGraphSkeleton>(StaticGraphSkeleton &);

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

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

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

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

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

   272 template void checkCompileStaticGraph<FullGraph>(FullGraph &);

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

   275 template void checkCompile<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);

   277 int main()

   278 {

   279   {

   280     SmartGraph G;

   281     addPetersen(G);

   282     bidirPetersen(G);

   283     checkPetersen(G);

   284   }

   285   {

   286     ListGraph G;

   287     addPetersen(G);

   288     bidirPetersen(G);

   289     checkPetersen(G);

   290   }

   291   {

   292     SymSmartGraph G;

   293     addPetersen(G);

   294     checkPetersen(G);

   295   }

   296   {

   297     SymListGraph G;

   298     addPetersen(G);

   299     checkPetersen(G);

   300   }

   302   //\todo map tests.

   303   //\todo copy constr tests.

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

   307   return 0;

   308 }

author	alpar
	Fri, 23 Jul 2004 16:58:02 +0000
changeset 736	ba76a7f56b23
parent 717	6874df3f61db
child 774	4297098d9677
permissions	-rw-r--r--