COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/graph_test.cc @ 776:f2994a2b10b2

Last change on this file since 776:f2994a2b10b2 was 774:4297098d9677, checked in by Alpar Juttner, 20 years ago

Merge back the whole branches/hugo++ to trunk.

File size: 9.2 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  { //bool NodeMap
137    Node k;
138    typename Graph::template NodeMap<bool> m(G);
139    typename Graph::template NodeMap<bool> const &cm = m;  //Const map
140    //Inicialize with default value
141    typename Graph::template NodeMap<bool> mdef(G,12);
142    typename Graph::template NodeMap<bool> mm(cm);   //Copy
143    typename Graph::template NodeMap<int> dm(cm); //Copy from another type
144    bool v;
145    v=m[k]; m[k]=v; m.set(k,v);
146    v=cm[k];
147   
148    m=cm; 
149    dm=cm; //Copy from another type
150    m=dm; //Copy to another type
151  }
152  //EdgeMap tests
153  {
154    Edge k;
155    typename Graph::template EdgeMap<int> m(G);
156    typename Graph::template EdgeMap<int> const &cm = m;  //Const map
157    //Inicialize with default value
158    typename Graph::template EdgeMap<int> mdef(G,12);
159    typename Graph::template EdgeMap<int> mm(cm);   //Copy
160    typename Graph::template EdgeMap<double> dm(cm); //Copy from another type
161    int v;
162    v=m[k]; m[k]=v; m.set(k,v);
163    v=cm[k];
164   
165    m=cm; 
166    dm=cm; //Copy from another type
167  } 
168  { //bool EdgeMap
169    Edge k;
170    typename Graph::template EdgeMap<bool> m(G);
171    typename Graph::template EdgeMap<bool> const &cm = m;  //Const map
172    //Inicialize with default value
173    typename Graph::template EdgeMap<bool> mdef(G,12);
174    typename Graph::template EdgeMap<bool> mm(cm);   //Copy
175    typename Graph::template EdgeMap<int> dm(cm); //Copy from another type
176    bool 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    m=dm; //Copy to another type
183  }
184}
185
186template<class Graph> void checkCompile(Graph &G)
187{
188  checkCompileStaticGraph(G);
189
190  typedef typename Graph::Node Node;
191  typedef typename Graph::NodeIt NodeIt;
192  typedef typename Graph::Edge Edge;
193  typedef typename Graph::EdgeIt EdgeIt;
194  typedef typename Graph::InEdgeIt InEdgeIt;
195  typedef typename Graph::OutEdgeIt OutEdgeIt;
196 
197  Node n,m;
198  n=G.addNode();
199  m=G.addNode();
200  Edge e;
201  e=G.addEdge(n,m);
202 
203  //  G.clear();
204}
205
206template<class Graph> void checkCompileErase(Graph &G)
207{
208  typedef typename Graph::Node Node;
209  typedef typename Graph::Edge Edge;
210  Node n;
211  Edge e;
212  G.erase(n);
213  G.erase(e);
214}
215
216template<class Graph> void checkCompileEraseEdge(Graph &G)
217{
218  typedef typename Graph::Edge Edge;
219  Edge e;
220  G.erase(e);
221}
222
223template<class Graph> void checkCompileFindEdge(Graph &G)
224{
225  typedef typename Graph::NodeIt Node;
226  typedef typename Graph::NodeIt NodeIt;
227
228  G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
229  G.findEdge(Node(),Node(),G.findEdge(Node(),Node())); 
230}
231
232
233template<class Graph> void checkNodeList(Graph &G, int nn)
234{
235  typename Graph::NodeIt n(G);
236  for(int i=0;i<nn;i++) {
237    check(n!=INVALID,"Wrong Node list linking.");
238    ++n;
239  }
240  check(n==INVALID,"Wrong Node list linking.");
241}
242
243template<class Graph> void checkEdgeList(Graph &G, int nn)
244{
245  typedef typename Graph::EdgeIt EdgeIt;
246
247  EdgeIt e(G);
248  for(int i=0;i<nn;i++) {
249    check(e!=INVALID,"Wrong Edge list linking.");
250    ++e;
251  }
252  check(e==INVALID,"Wrong Edge list linking.");
253}
254
255template<class Graph> void checkOutEdgeList(Graph &G,
256                                            typename Graph::Node n,
257                                            int nn)
258{
259  typename Graph::OutEdgeIt e(G,n);
260  for(int i=0;i<nn;i++) {
261    check(e!=INVALID,"Wrong OutEdge list linking.");
262    ++e;
263  }
264  check(e==INVALID,"Wrong OutEdge list linking.");
265}
266
267template<class Graph> void checkInEdgeList(Graph &G,
268                                           typename Graph::Node n,
269                                           int nn)
270{
271  typename Graph::InEdgeIt e(G,n);
272  for(int i=0;i<nn;i++) {
273    check(e!=INVALID,"Wrong InEdge list linking.");
274    ++e;
275  }
276  check(e==INVALID,"Wrong InEdge list linking.");
277}
278
279///\file
280///\todo Checks head(), tail() as well;
281
282template<class Graph> void bidirPetersen(Graph &G)
283{
284  typedef typename Graph::Edge Edge;
285  typedef typename Graph::EdgeIt EdgeIt;
286 
287  checkEdgeList(G,15);
288 
289  std::vector<Edge> ee;
290 
291  for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e);
292
293  for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
294    G.addEdge(G.head(*p),G.tail(*p));
295}
296
297template<class Graph> void checkPetersen(Graph &G)
298{
299  typedef typename Graph::Node Node;
300
301  typedef typename Graph::EdgeIt EdgeIt;
302  typedef typename Graph::NodeIt NodeIt;
303
304  checkNodeList(G,10);
305  checkEdgeList(G,30);
306
307  for(NodeIt n(G);n!=INVALID;++n) {
308    checkInEdgeList(G,n,3);
309    checkOutEdgeList(G,n,3);
310    ++n;
311  } 
312}
313
314//Compile GraphSkeleton
315template
316void checkCompileStaticGraph<StaticGraphSkeleton>(StaticGraphSkeleton &);
317template void checkCompile<GraphSkeleton>(GraphSkeleton &);
318template
319void checkCompileErase<EraseableGraphSkeleton>(EraseableGraphSkeleton &);
320
321//Compile SmartGraph
322template void checkCompile<SmartGraph>(SmartGraph &);
323//Compile SymSmartGraph
324template void checkCompile<SymSmartGraph>(SymSmartGraph &);
325
326//Compile ListGraph
327template void checkCompile<ListGraph>(ListGraph &);
328template void checkCompileErase<ListGraph>(ListGraph &);
329template void checkCompileFindEdge<ListGraph>(ListGraph &);
330
331//Compile SymListGraph
332template void checkCompile<SymListGraph>(SymListGraph &);
333template void checkCompileErase<SymListGraph>(SymListGraph &);
334template void checkCompileFindEdge<SymListGraph>(SymListGraph &);
335
336//Compile FullGraph
337template void checkCompileStaticGraph<FullGraph>(FullGraph &);
338template void checkCompileFindEdge<FullGraph>(FullGraph &);
339
340//Compile EdgeSet <ListGraph>
341template void checkCompile<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
342template
343void checkCompileEraseEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
344template
345void checkCompileFindEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
346
347//Compile EdgeSet <NodeSet>
348template void checkCompile<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
349template
350void checkCompileEraseEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
351template void checkCompileFindEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
352
353
354int main()
355{
356  {
357    SmartGraph G;
358    addPetersen(G);
359    bidirPetersen(G);
360    checkPetersen(G);
361  }
362  {
363    ListGraph G;
364    addPetersen(G);
365    bidirPetersen(G);
366    checkPetersen(G);
367  }
368  {
369    SymSmartGraph G;
370    addPetersen(G);
371    checkPetersen(G);
372  }
373  {
374    SymListGraph G;
375    addPetersen(G);
376    checkPetersen(G);
377  }
378
379  ///\file
380  ///\todo map tests.
381  ///\todo copy constr tests.
382
383  std::cout << __FILE__ ": All tests passed.\n";
384
385  return 0;
386}
Note: See TracBrowser for help on using the repository browser.