COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/graph_test.cc @ 787:584270fba752

Last change on this file since 787:584270fba752 was 787:584270fba752, checked in by Alpar Juttner, 16 years ago

Tests for the existence of 'KeyType?' and 'ValueType?' in the graph maps.

File size: 10.0 KB
Line 
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>
6
7#include"test_tools.h"
8
9/**
10\file
11This test makes consistency checks of list graph structures.
12
13G.addNode(), G.addEdge(), G.tail(), G.head()
14
15\todo Checks for empty graphs and isolated points.
16\todo Checks for Node->NodeIt, Edge->{EdgeIt,InEdgeIt,OutEdgeIt}
17conversion.
18*/
19
20using namespace hugo;
21using namespace hugo::skeleton;
22
23template<class Graph> void checkCompileStaticGraph(Graph &G)
24{
25  typedef typename Graph::Node Node;
26  typedef typename Graph::NodeIt NodeIt;
27  typedef typename Graph::Edge Edge;
28  typedef typename Graph::EdgeIt EdgeIt;
29  typedef typename Graph::InEdgeIt InEdgeIt;
30  typedef typename Graph::OutEdgeIt OutEdgeIt;
31 
32  {
33    Node i; Node j(i); Node k(INVALID);
34    i=j;
35    //    bool b=G.valid(i); b=b;
36    bool b; b=b;
37    b=(i==INVALID); b=(i!=INVALID);
38    b=(i==j); b=(i!=j); b=(i<j);
39  }
40  {
41    NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);
42    i=j;
43    j=G.first(i);
44    j=++i;
45    //    bool b=G.valid(i); b=b;
46    bool b; b=b;
47    b=(i==INVALID); b=(i!=INVALID);
48    Node n(i);
49    n=i;
50    b=(i==j); b=(i!=j); b=(i<j);
51    //Node ->NodeIt conversion
52    NodeIt ni(G,n);
53  }
54  {
55    Edge i; Edge j(i); Edge k(INVALID);
56    i=j;
57    //    bool b=G.valid(i); b=b;
58    bool b; b=b;
59    b=(i==INVALID); b=(i!=INVALID);
60    b=(i==j); b=(i!=j); b=(i<j);
61  }
62  {
63    EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);
64    i=j;
65    j=G.first(i);
66    j=++i;
67    //    bool b=G.valid(i); b=b;
68    bool b; b=b;
69    b=(i==INVALID); b=(i!=INVALID);
70    Edge e(i);
71    e=i;
72    b=(i==j); b=(i!=j); b=(i<j);
73    //Edge ->EdgeIt conversion
74    EdgeIt ei(G,e);
75  }
76  {
77    Node n;
78    InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);
79    i=j;
80    j=G.first(i,n);
81    j=++i;
82    //    bool b=G.valid(i); b=b;
83    bool b; b=b;
84    b=(i==INVALID); b=(i!=INVALID);
85    Edge e(i);
86    e=i;
87    b=(i==j); b=(i!=j); b=(i<j);
88    //Edge ->InEdgeIt conversion
89    InEdgeIt ei(G,e);
90  }
91  {
92    Node n;
93    OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);
94    i=j;
95    j=G.first(i,n);
96    j=++i;
97    //    bool b=G.valid(i); b=b;
98    bool b; b=b;
99    b=(i==INVALID); b=(i!=INVALID);
100    Edge e(i);
101    e=i;
102    b=(i==j); b=(i!=j); b=(i<j);
103    //Edge ->OutEdgeIt conversion
104    OutEdgeIt ei(G,e);
105  }
106  {
107    Node n,m;
108    n=m=INVALID;
109    Edge e;
110    e=INVALID;
111    n=G.tail(e);
112    n=G.head(e);
113  }
114  // id tests
115  { Node n; int i=G.id(n); i=i; }
116  { Edge e; int i=G.id(e); i=i; }
117  //NodeMap tests
118  {
119    Node k;
120    typename Graph::template NodeMap<int> m(G);
121    //Const map
122    typename Graph::template NodeMap<int> const &cm = m;
123    //Inicialize with default value
124    typename Graph::template NodeMap<int> mdef(G,12);
125    //Copy
126    typename Graph::template NodeMap<int> mm(cm);
127    //Copy from another type
128    typename Graph::template NodeMap<double> dm(cm);
129    int v;
130    v=m[k]; m[k]=v; m.set(k,v);
131    v=cm[k];
132   
133    m=cm; 
134    dm=cm; //Copy from another type
135    {
136      //Check the typedef's
137      typename Graph::template NodeMap<int>::ValueType val;
138      val=1;
139      typename Graph::template NodeMap<int>::KeyType key;
140      key = typename Graph::NodeIt(G);
141    }
142  } 
143  { //bool NodeMap
144    Node k;
145    typename Graph::template NodeMap<bool> m(G);
146    typename Graph::template NodeMap<bool> const &cm = m;  //Const map
147    //Inicialize with default value
148    typename Graph::template NodeMap<bool> mdef(G,12);
149    typename Graph::template NodeMap<bool> mm(cm);   //Copy
150    typename Graph::template NodeMap<int> dm(cm); //Copy from another type
151    bool v;
152    v=m[k]; m[k]=v; m.set(k,v);
153    v=cm[k];
154   
155    m=cm; 
156    dm=cm; //Copy from another type
157    m=dm; //Copy to another type
158
159    {
160      //Check the typedef's
161      typename Graph::template NodeMap<bool>::ValueType val;
162      val=true;
163      typename Graph::template NodeMap<bool>::KeyType key;
164      key= typename Graph::NodeIt(G);
165    }
166  }
167  //EdgeMap tests
168  {
169    Edge k;
170    typename Graph::template EdgeMap<int> m(G);
171    typename Graph::template EdgeMap<int> const &cm = m;  //Const map
172    //Inicialize with default value
173    typename Graph::template EdgeMap<int> mdef(G,12);
174    typename Graph::template EdgeMap<int> mm(cm);   //Copy
175    typename Graph::template EdgeMap<double> dm(cm); //Copy from another type
176    int v;
177    v=m[k]; m[k]=v; m.set(k,v);
178    v=cm[k];
179   
180    m=cm; 
181    dm=cm; //Copy from another type
182    {
183      //Check the typedef's
184      typename Graph::template EdgeMap<int>::ValueType val;
185      val=1;
186      typename Graph::template EdgeMap<int>::KeyType key;
187      key= typename Graph::EdgeIt(G);
188    }
189  } 
190  { //bool EdgeMap
191    Edge k;
192    typename Graph::template EdgeMap<bool> m(G);
193    typename Graph::template EdgeMap<bool> const &cm = m;  //Const map
194    //Inicialize with default value
195    typename Graph::template EdgeMap<bool> mdef(G,12);
196    typename Graph::template EdgeMap<bool> mm(cm);   //Copy
197    typename Graph::template EdgeMap<int> dm(cm); //Copy from another type
198    bool v;
199    v=m[k]; m[k]=v; m.set(k,v);
200    v=cm[k];
201   
202    m=cm; 
203    dm=cm; //Copy from another type
204    m=dm; //Copy to another type
205    {
206      //Check the typedef's
207      typename Graph::template EdgeMap<bool>::ValueType val;
208      val=true;
209      typename Graph::template EdgeMap<bool>::KeyType key;
210      key= typename Graph::EdgeIt(G);
211    }
212  }
213}
214
215template<class Graph> void checkCompile(Graph &G)
216{
217  checkCompileStaticGraph(G);
218
219  typedef typename Graph::Node Node;
220  typedef typename Graph::NodeIt NodeIt;
221  typedef typename Graph::Edge Edge;
222  typedef typename Graph::EdgeIt EdgeIt;
223  typedef typename Graph::InEdgeIt InEdgeIt;
224  typedef typename Graph::OutEdgeIt OutEdgeIt;
225 
226  Node n,m;
227  n=G.addNode();
228  m=G.addNode();
229  Edge e;
230  e=G.addEdge(n,m);
231 
232  //  G.clear();
233}
234
235template<class Graph> void checkCompileErase(Graph &G)
236{
237  typedef typename Graph::Node Node;
238  typedef typename Graph::Edge Edge;
239  Node n;
240  Edge e;
241  G.erase(n);
242  G.erase(e);
243}
244
245template<class Graph> void checkCompileEraseEdge(Graph &G)
246{
247  typedef typename Graph::Edge Edge;
248  Edge e;
249  G.erase(e);
250}
251
252template<class Graph> void checkCompileFindEdge(Graph &G)
253{
254  typedef typename Graph::NodeIt Node;
255  typedef typename Graph::NodeIt NodeIt;
256
257  G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
258  G.findEdge(Node(),Node(),G.findEdge(Node(),Node())); 
259}
260
261
262template<class Graph> void checkNodeList(Graph &G, int nn)
263{
264  typename Graph::NodeIt n(G);
265  for(int i=0;i<nn;i++) {
266    check(n!=INVALID,"Wrong Node list linking.");
267    ++n;
268  }
269  check(n==INVALID,"Wrong Node list linking.");
270}
271
272template<class Graph> void checkEdgeList(Graph &G, int nn)
273{
274  typedef typename Graph::EdgeIt EdgeIt;
275
276  EdgeIt e(G);
277  for(int i=0;i<nn;i++) {
278    check(e!=INVALID,"Wrong Edge list linking.");
279    ++e;
280  }
281  check(e==INVALID,"Wrong Edge list linking.");
282}
283
284template<class Graph> void checkOutEdgeList(Graph &G,
285                                            typename Graph::Node n,
286                                            int nn)
287{
288  typename Graph::OutEdgeIt e(G,n);
289  for(int i=0;i<nn;i++) {
290    check(e!=INVALID,"Wrong OutEdge list linking.");
291    ++e;
292  }
293  check(e==INVALID,"Wrong OutEdge list linking.");
294}
295
296template<class Graph> void checkInEdgeList(Graph &G,
297                                           typename Graph::Node n,
298                                           int nn)
299{
300  typename Graph::InEdgeIt e(G,n);
301  for(int i=0;i<nn;i++) {
302    check(e!=INVALID,"Wrong InEdge list linking.");
303    ++e;
304  }
305  check(e==INVALID,"Wrong InEdge list linking.");
306}
307
308///\file
309///\todo Checks head(), tail() as well;
310
311template<class Graph> void bidirPetersen(Graph &G)
312{
313  typedef typename Graph::Edge Edge;
314  typedef typename Graph::EdgeIt EdgeIt;
315 
316  checkEdgeList(G,15);
317 
318  std::vector<Edge> ee;
319 
320  for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e);
321
322  for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
323    G.addEdge(G.head(*p),G.tail(*p));
324}
325
326template<class Graph> void checkPetersen(Graph &G)
327{
328  typedef typename Graph::Node Node;
329
330  typedef typename Graph::EdgeIt EdgeIt;
331  typedef typename Graph::NodeIt NodeIt;
332
333  checkNodeList(G,10);
334  checkEdgeList(G,30);
335
336  for(NodeIt n(G);n!=INVALID;++n) {
337    checkInEdgeList(G,n,3);
338    checkOutEdgeList(G,n,3);
339    ++n;
340  } 
341}
342
343//Compile GraphSkeleton
344template
345void checkCompileStaticGraph<StaticGraphSkeleton>(StaticGraphSkeleton &);
346template void checkCompile<GraphSkeleton>(GraphSkeleton &);
347template
348void checkCompileErase<EraseableGraphSkeleton>(EraseableGraphSkeleton &);
349
350//Compile SmartGraph
351template void checkCompile<SmartGraph>(SmartGraph &);
352
353//Compile SymSmartGraph
354template void checkCompile<SymSmartGraph>(SymSmartGraph &);
355
356//Compile ListGraph
357template void checkCompile<ListGraph>(ListGraph &);
358template void checkCompileErase<ListGraph>(ListGraph &);
359template void checkCompileFindEdge<ListGraph>(ListGraph &);
360
361
362//Compile SymListGraph
363template void checkCompile<SymListGraph>(SymListGraph &);
364template void checkCompileErase<SymListGraph>(SymListGraph &);
365template void checkCompileFindEdge<SymListGraph>(SymListGraph &);
366
367//Compile FullGraph
368template void checkCompileStaticGraph<FullGraph>(FullGraph &);
369template void checkCompileFindEdge<FullGraph>(FullGraph &);
370
371//Compile EdgeSet <ListGraph>
372template void checkCompile<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
373template
374void checkCompileEraseEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
375template
376void checkCompileFindEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
377
378//Compile EdgeSet <NodeSet>
379template void checkCompile<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
380template
381void checkCompileEraseEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
382template void checkCompileFindEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
383
384
385int main()
386{
387  {
388    SmartGraph G;
389    addPetersen(G);
390    bidirPetersen(G);
391    checkPetersen(G);
392  }
393  {
394    ListGraph G;
395    addPetersen(G);
396    bidirPetersen(G);
397    checkPetersen(G);
398  }
399  {
400    SymSmartGraph G;
401    addPetersen(G);
402    checkPetersen(G);
403  }
404  {
405    SymListGraph G;
406    addPetersen(G);
407    checkPetersen(G);
408  }
409
410  ///\file
411  ///\todo map tests.
412  ///\todo copy constr tests.
413
414  std::cout << __FILE__ ": All tests passed.\n";
415
416  return 0;
417}
Note: See TracBrowser for help on using the repository browser.