COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/graph_test.cc @ 793:9cd0aeea47b0

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