COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/graph_test.cc @ 574:7b0b12eb603b

Last change on this file since 574:7b0b12eb603b was 567:efaa79ee8d14, checked in by Alpar Juttner, 20 years ago

time_measure.cc was renamed to time_measure_test.cc
Add an alternative dijsktra_test.cc

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