COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/graph_test.cc @ 717:6874df3f61db

Last change on this file since 717:6874df3f61db was 717:6874df3f61db, checked in by Alpar Juttner, 20 years ago

Test EdgeSet/NodeSet? as well.

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