COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/graph_test.cc @ 503:769f31e9f7b0

Last change on this file since 503:769f31e9f7b0 was 503:769f31e9f7b0, checked in by Alpar Juttner, 17 years ago

test/graph_test.cc added.
It discovered several bugs and warnings in 'include/smart_graph.h',
in 'include/skeletons/graph.h' and in 'work/alpar/list_graph.h'.
They have also been fixed.

File size: 6.8 KB
Line 
1#include<iostream>
2#include<smart_graph.h>
3#include<skeletons/graph.h>
4#include<../work/alpar/list_graph.h>
5
6/*
7This test makes consistency checks of list graph structures.
8
9G.addNode(), G.addEdge(), G.valid(), G.tail(), G.head()
10
11*/
12
13using namespace hugo;
14
15// void check(bool rc, const char *msg) {
16//   if(!rc) {
17//     std::cerr << msg << std::endl;
18//     exit(1);
19//   }
20// }
21
22#define check(rc, msg) \
23  if(!rc) { \
24    std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \
25    exit(1); \
26  } else { } \
27
28
29template<class Graph> void checkCompile(Graph &G)
30{
31  typedef typename Graph::Node Node;
32  typedef typename Graph::NodeIt NodeIt;
33  typedef typename Graph::Edge Edge;
34  typedef typename Graph::EdgeIt EdgeIt;
35  typedef typename Graph::InEdgeIt InEdgeIt;
36  typedef typename Graph::OutEdgeIt OutEdgeIt;
37 
38  {
39    Node i; Node j(i); Node k(INVALID);
40    i=j;
41    bool b=G.valid(i); b=b;
42    b=(i==j); b=(i!=j); b=(i<j);
43  }
44  {
45    NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);
46    i=j;
47    j=G.first(i);
48    j=G.next(i);
49    bool b=G.valid(i); b=b;
50    Node n(i);
51    n=i;
52    b=(i==j); b=(i!=j); b=(i<j);
53  }
54  {
55    Edge i; Edge j(i); Edge k(INVALID);
56    i=j;
57    bool b=G.valid(i); b=b;
58    b=(i==j); b=(i!=j); b=(i<j);
59  }
60  {
61    EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);
62    i=j;
63    j=G.first(i);
64    j=G.next(i);
65    bool b=G.valid(i); b=b;
66    Edge e(i);
67    e=i;
68    b=(i==j); b=(i!=j); b=(i<j);
69  }
70  {
71    Node n;
72    InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);
73    i=j;
74    j=G.first(i,n);
75    j=G.next(i);
76    bool b=G.valid(i); b=b;
77    Edge e(i);
78    e=i;
79    b=(i==j); b=(i!=j); b=(i<j);
80  }
81  {
82    Node n;
83    OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);
84    i=j;
85    j=G.first(i,n);
86    j=G.next(i);
87    bool b=G.valid(i); b=b;
88    Edge e(i);
89    e=i;
90    b=(i==j); b=(i!=j); b=(i<j);
91  }
92
93  Node n,m;
94  n=G.addNode();
95  Edge e;
96  e=G.addEdge(n,m);
97  n=G.tail(e);
98  n=G.head(e);
99
100  //aNode, bNode ?
101
102  // id tests
103  { int i=G.id(n); i=i; }
104  { int i=G.id(e); i=i; }
105 
106  G.clear();
107
108  //NodeMap tests
109  {
110    Node k;
111    typename Graph::NodeMap<int> m(G);
112    typename Graph::NodeMap<int> const &cm = m;  //Const map
113    typename Graph::NodeMap<int> mdef(G,12); //Inicialize with default value
114    typename Graph::NodeMap<int> mm(cm);   //Copy
115    typename Graph::NodeMap<double> dm(cm); //Copy from another type
116    int v;
117    v=m[k]; m[k]=v; m.set(k,v);
118    v=cm[k];
119   
120    m=cm; 
121    dm=cm; //Copy from another type
122  } 
123  { //bool NodeMap
124    Node k;
125    typename Graph::NodeMap<bool> m(G);
126    typename Graph::NodeMap<bool> const &cm = m;  //Const map
127    typename Graph::NodeMap<bool> mdef(G,12); //Inicialize with default value
128    typename Graph::NodeMap<bool> mm(cm);   //Copy
129    typename Graph::NodeMap<int> dm(cm); //Copy from another type
130    bool v;
131    v=m[k]; m[k]=v; m.set(k,v);
132    v=cm[k];
133   
134    m=cm; 
135    dm=cm; //Copy from another type
136  }
137  //EdgeMap tests
138  {
139    Edge k;
140    typename Graph::EdgeMap<int> m(G);
141    typename Graph::EdgeMap<int> const &cm = m;  //Const map
142    typename Graph::EdgeMap<int> mdef(G,12); //Inicialize with default value
143    typename Graph::EdgeMap<int> mm(cm);   //Copy
144    typename Graph::EdgeMap<double> dm(cm); //Copy from another type
145    int v;
146    v=m[k]; m[k]=v; m.set(k,v);
147    v=cm[k];
148   
149    m=cm; 
150    dm=cm; //Copy from another type
151  } 
152  { //bool EdgeMap
153    Edge k;
154    typename Graph::EdgeMap<bool> m(G);
155    typename Graph::EdgeMap<bool> const &cm = m;  //Const map
156    typename Graph::EdgeMap<bool> mdef(G,12); //Inicialize with default value
157    typename Graph::EdgeMap<bool> mm(cm);   //Copy
158    typename Graph::EdgeMap<int> dm(cm); //Copy from another type
159    bool v;
160    v=m[k]; m[k]=v; m.set(k,v);
161    v=cm[k];
162   
163    m=cm; 
164    dm=cm; //Copy from another type
165  }
166 
167}
168
169
170
171template<class Graph> void addPetersen(Graph &G)
172{
173  std::vector<typename Graph::Node> outer, inner;
174 
175  for(int i=0;i<5;i++) {
176    outer.push_back(G.addNode());
177    inner.push_back(G.addNode());
178  }
179
180 for(int i=0;i<5;i++) {
181    G.addEdge(outer[i],inner[i]);
182    G.addEdge(outer[i],outer[(i+1)%5]);
183    G.addEdge(inner[i],inner[(i+2)%5]);
184  }
185}
186
187template<class Graph> void checkNodeList(Graph &G, int nn)
188{
189  typename Graph::NodeIt n(G);
190  for(int i=0;i<nn;i++) {
191    check(G.valid(n),"Wrong Node list linking.");
192    G.next(n);
193  }
194  check(!G.valid(n),"Wrong Node list linking.");
195}
196
197template<class Graph> void checkEdgeList(Graph &G, int nn)
198{
199  typedef typename Graph::EdgeIt EdgeIt;
200
201  EdgeIt e(G);
202  for(int i=0;i<nn;i++) {
203    check(G.valid(e),"Wrong Edge list linking.");
204    G.next(e);
205  }
206  check(!G.valid(e),"Wrong Edge list linking.");
207}
208
209template<class Graph> void checkOutEdgeList(Graph &G,
210                                            typename Graph::Node n,
211                                            int nn)
212{
213  typename Graph::OutEdgeIt e(G,n);
214  for(int i=0;i<nn;i++) {
215    check(G.valid(e),"Wrong OutEdge list linking.");
216    G.next(e);
217  }
218  check(!G.valid(e),"Wrong OutEdge list linking.");
219}
220
221template<class Graph> void checkInEdgeList(Graph &G,
222                                            typename Graph::Node n,
223                                            int nn)
224{
225  typename Graph::InEdgeIt e(G,n);
226  for(int i=0;i<nn;i++) {
227    check(G.valid(e),"Wrong InEdge list linking.");
228    G.next(e);
229  }
230  check(!G.valid(e),"Wrong InEdge list linking.");
231}
232
233//Checks head(), tail() as well;
234template<class Graph> void bidirPetersen(Graph &G)
235{
236  typedef typename Graph::Edge Edge;
237  typedef typename Graph::EdgeIt EdgeIt;
238 
239  checkEdgeList(G,15);
240 
241  std::vector<Edge> ee;
242 
243  for(EdgeIt e(G);G.valid(e);G.next(e)) ee.push_back(e);
244
245  for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
246    G.addEdge(G.head(*p),G.tail(*p));
247}
248
249template<class Graph> void checkPetersen(Graph &G)
250{
251  typedef typename Graph::Node Node;
252
253  typedef typename Graph::EdgeIt EdgeIt;
254  typedef typename Graph::NodeIt NodeIt;
255
256  checkNodeList(G,10);
257  checkEdgeList(G,30);
258
259  for(NodeIt n(G);G.valid(n);G.next(n)) {
260    checkInEdgeList(G,n,3);
261    checkOutEdgeList(G,n,3);
262    G.next(n);
263  } 
264}
265
266template void checkCompile<GraphSkeleton>(GraphSkeleton &);
267template void checkCompile<SmartGraph>(SmartGraph &);
268template void checkCompile<SymSmartGraph>(SymSmartGraph &);
269template void checkCompile<ListGraph>(ListGraph &);
270template void checkCompile<SymListGraph>(SymListGraph &);
271//Due to some mysterious and some conceptual problems it does not work.
272//template void checkCompile<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
273
274int main()
275{
276  {
277    SmartGraph G;
278    addPetersen(G);
279    bidirPetersen(G);
280    checkPetersen(G);
281  }
282  {
283    ListGraph G;
284    addPetersen(G);
285    bidirPetersen(G);
286    checkPetersen(G);
287  }
288  {
289    SymSmartGraph G;
290    addPetersen(G);
291    checkPetersen(G);
292  }
293  {
294    SymListGraph G;
295    addPetersen(G);
296    checkPetersen(G);
297  }
298
299  //\todo map tests.
300  //\todo copy constr tests.
301
302  std::cout << __FILE__ ": All tests passed.\n";
303
304}
Note: See TracBrowser for help on using the repository browser.