COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/graph_test.cc @ 733:240003bddaff

Last change on this file since 733:240003bddaff was 733:240003bddaff, checked in by Alpar Juttner, 17 years ago

Check StaticGraphSkeleton?, as well.

File size: 7.1 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/*
10This test makes consistency checks of list graph structures.
11
12G.addNode(), G.addEdge(), G.valid(), G.tail(), G.head()
13
14\todo Checks for empty graphs and isolated points.
15*/
16
17using namespace hugo;
18using namespace hugo::skeleton;
19
20template<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;
28 
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  }
83
84  Node n,m;
85  n=m=INVALID;
86  Edge e;
87  e=INVALID;
88  n=G.tail(e);
89  n=G.head(e);
90
91  //aNode, bNode ?
92
93  // id tests
94  { int i=G.id(n); i=i; }
95  { int i=G.id(e); i=i; }
96 
97  //  G.clear();
98
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];
111   
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];
126   
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];
143   
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];
158   
159    m=cm; 
160    dm=cm; //Copy from another type
161    m=dm; //Copy to another type
162  }
163 
164}
165
166template<class Graph> void checkCompile(Graph &G)
167{
168  checkCompileStaticGraph(G);
169
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;
176 
177  Node n,m;
178  n=G.addNode();
179  m=G.addNode();
180 
181  G.addEdge(n,m);
182}
183
184
185template<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}
194
195template<class Graph> void checkEdgeList(Graph &G, int nn)
196{
197  typedef typename Graph::EdgeIt EdgeIt;
198
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}
206
207template<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}
218
219template<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}
230
231//Checks head(), tail() as well;
232template<class Graph> void bidirPetersen(Graph &G)
233{
234  typedef typename Graph::Edge Edge;
235  typedef typename Graph::EdgeIt EdgeIt;
236 
237  checkEdgeList(G,15);
238 
239  std::vector<Edge> ee;
240 
241  for(EdgeIt e(G);G.valid(e);G.next(e)) ee.push_back(e);
242
243  for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
244    G.addEdge(G.head(*p),G.tail(*p));
245}
246
247template<class Graph> void checkPetersen(Graph &G)
248{
249  typedef typename Graph::Node Node;
250
251  typedef typename Graph::EdgeIt EdgeIt;
252  typedef typename Graph::NodeIt NodeIt;
253
254  checkNodeList(G,10);
255  checkEdgeList(G,30);
256
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}
263
264template
265void checkCompileStaticGraph<StaticGraphSkeleton>(StaticGraphSkeleton &);
266template void checkCompile<GraphSkeleton>(GraphSkeleton &);
267
268template void checkCompile<SmartGraph>(SmartGraph &);
269template void checkCompile<SymSmartGraph>(SymSmartGraph &);
270template void checkCompile<ListGraph>(ListGraph &);
271template void checkCompile<SymListGraph>(SymListGraph &);
272template void checkCompileStaticGraph<FullGraph>(FullGraph &);
273
274template void checkCompile<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
275template void checkCompile<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
276
277int 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  }
301
302  //\todo map tests.
303  //\todo copy constr tests.
304
305  std::cout << __FILE__ ": All tests passed.\n";
306
307  return 0;
308}
Note: See TracBrowser for help on using the repository browser.