4 #include<hugo/list_graph.h> |
4 #include<hugo/list_graph.h> |
5 #include<hugo/full_graph.h> |
5 #include<hugo/full_graph.h> |
6 |
6 |
7 #include"test_tools.h" |
7 #include"test_tools.h" |
8 |
8 |
9 /* |
9 /** |
|
10 \file |
10 This test makes consistency checks of list graph structures. |
11 This test makes consistency checks of list graph structures. |
11 |
12 |
12 G.addNode(), G.addEdge(), G.valid(), G.tail(), G.head() |
13 G.addNode(), G.addEdge(), G.tail(), G.head() |
13 |
14 |
14 \todo Checks for empty graphs and isolated points. |
15 \todo Checks for empty graphs and isolated points. |
|
16 \todo Checks for Node->NodeIt, Edge->{EdgeIt,InEdgeIt,OutEdgeIt} |
|
17 conversion. |
15 */ |
18 */ |
16 |
19 |
17 using namespace hugo; |
20 using namespace hugo; |
18 using namespace hugo::skeleton; |
21 using namespace hugo::skeleton; |
19 |
22 |
27 typedef typename Graph::OutEdgeIt OutEdgeIt; |
30 typedef typename Graph::OutEdgeIt OutEdgeIt; |
28 |
31 |
29 { |
32 { |
30 Node i; Node j(i); Node k(INVALID); |
33 Node i; Node j(i); Node k(INVALID); |
31 i=j; |
34 i=j; |
32 bool b=G.valid(i); b=b; |
35 // bool b=G.valid(i); b=b; |
|
36 bool b; b=b; |
|
37 b=(i==INVALID); b=(i!=INVALID); |
33 b=(i==j); b=(i!=j); b=(i<j); |
38 b=(i==j); b=(i!=j); b=(i<j); |
34 } |
39 } |
35 { |
40 { |
36 NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G); |
41 NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G); |
37 i=j; |
42 i=j; |
38 j=G.first(i); |
43 j=G.first(i); |
39 j=G.next(i); |
44 j=++i; |
40 bool b=G.valid(i); b=b; |
45 // bool b=G.valid(i); b=b; |
|
46 bool b; b=b; |
|
47 b=(i==INVALID); b=(i!=INVALID); |
41 Node n(i); |
48 Node n(i); |
42 n=i; |
49 n=i; |
43 b=(i==j); b=(i!=j); b=(i<j); |
50 b=(i==j); b=(i!=j); b=(i<j); |
|
51 //Node ->NodeIt conversion |
|
52 NodeIt ni(G,n); |
44 } |
53 } |
45 { |
54 { |
46 Edge i; Edge j(i); Edge k(INVALID); |
55 Edge i; Edge j(i); Edge k(INVALID); |
47 i=j; |
56 i=j; |
48 bool b=G.valid(i); b=b; |
57 // bool b=G.valid(i); b=b; |
|
58 bool b; b=b; |
|
59 b=(i==INVALID); b=(i!=INVALID); |
49 b=(i==j); b=(i!=j); b=(i<j); |
60 b=(i==j); b=(i!=j); b=(i<j); |
50 } |
61 } |
51 { |
62 { |
52 EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G); |
63 EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G); |
53 i=j; |
64 i=j; |
54 j=G.first(i); |
65 j=G.first(i); |
55 j=G.next(i); |
66 j=++i; |
56 bool b=G.valid(i); b=b; |
67 // bool b=G.valid(i); b=b; |
|
68 bool b; b=b; |
|
69 b=(i==INVALID); b=(i!=INVALID); |
57 Edge e(i); |
70 Edge e(i); |
58 e=i; |
71 e=i; |
59 b=(i==j); b=(i!=j); b=(i<j); |
72 b=(i==j); b=(i!=j); b=(i<j); |
|
73 //Edge ->EdgeIt conversion |
|
74 EdgeIt ei(G,e); |
60 } |
75 } |
61 { |
76 { |
62 Node n; |
77 Node n; |
63 InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n); |
78 InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n); |
64 i=j; |
79 i=j; |
65 j=G.first(i,n); |
80 j=G.first(i,n); |
66 j=G.next(i); |
81 j=++i; |
67 bool b=G.valid(i); b=b; |
82 // bool b=G.valid(i); b=b; |
|
83 bool b; b=b; |
|
84 b=(i==INVALID); b=(i!=INVALID); |
68 Edge e(i); |
85 Edge e(i); |
69 e=i; |
86 e=i; |
70 b=(i==j); b=(i!=j); b=(i<j); |
87 b=(i==j); b=(i!=j); b=(i<j); |
|
88 //Edge ->InEdgeIt conversion |
|
89 InEdgeIt ei(G,e); |
71 } |
90 } |
72 { |
91 { |
73 Node n; |
92 Node n; |
74 OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n); |
93 OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n); |
75 i=j; |
94 i=j; |
76 j=G.first(i,n); |
95 j=G.first(i,n); |
77 j=G.next(i); |
96 j=++i; |
78 bool b=G.valid(i); b=b; |
97 // bool b=G.valid(i); b=b; |
|
98 bool b; b=b; |
|
99 b=(i==INVALID); b=(i!=INVALID); |
79 Edge e(i); |
100 Edge e(i); |
80 e=i; |
101 e=i; |
81 b=(i==j); b=(i!=j); b=(i<j); |
102 b=(i==j); b=(i!=j); b=(i<j); |
82 } |
103 //Edge ->OutEdgeIt conversion |
83 |
104 OutEdgeIt ei(G,e); |
84 Node n,m; |
105 } |
85 n=m=INVALID; |
106 { |
86 Edge e; |
107 Node n,m; |
87 e=INVALID; |
108 n=m=INVALID; |
88 n=G.tail(e); |
109 Edge e; |
89 n=G.head(e); |
110 e=INVALID; |
90 |
111 n=G.tail(e); |
91 //aNode, bNode ? |
112 n=G.head(e); |
92 |
113 } |
93 // id tests |
114 // id tests |
94 { int i=G.id(n); i=i; } |
115 { Node n; int i=G.id(n); i=i; } |
95 { int i=G.id(e); i=i; } |
116 { Edge e; int i=G.id(e); i=i; } |
96 |
|
97 // G.clear(); |
|
98 |
|
99 //NodeMap tests |
117 //NodeMap tests |
100 { |
118 { |
101 Node k; |
119 Node k; |
102 typename Graph::template NodeMap<int> m(G); |
120 typename Graph::template NodeMap<int> m(G); |
103 typename Graph::template NodeMap<int> const &cm = m; //Const map |
121 //Const map |
|
122 typename Graph::template NodeMap<int> const &cm = m; |
104 //Inicialize with default value |
123 //Inicialize with default value |
105 typename Graph::template NodeMap<int> mdef(G,12); |
124 typename Graph::template NodeMap<int> mdef(G,12); |
106 typename Graph::template NodeMap<int> mm(cm); //Copy |
125 //Copy |
107 typename Graph::template NodeMap<double> dm(cm); //Copy from another type |
126 typename Graph::template NodeMap<int> mm(cm); |
|
127 //Copy from another type |
|
128 typename Graph::template NodeMap<double> dm(cm); |
108 int v; |
129 int v; |
109 v=m[k]; m[k]=v; m.set(k,v); |
130 v=m[k]; m[k]=v; m.set(k,v); |
110 v=cm[k]; |
131 v=cm[k]; |
111 |
132 |
112 m=cm; |
133 m=cm; |
175 typedef typename Graph::OutEdgeIt OutEdgeIt; |
195 typedef typename Graph::OutEdgeIt OutEdgeIt; |
176 |
196 |
177 Node n,m; |
197 Node n,m; |
178 n=G.addNode(); |
198 n=G.addNode(); |
179 m=G.addNode(); |
199 m=G.addNode(); |
180 |
200 Edge e; |
181 G.addEdge(n,m); |
201 e=G.addEdge(n,m); |
|
202 |
|
203 // G.clear(); |
|
204 } |
|
205 |
|
206 template<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 |
|
216 template<class Graph> void checkCompileEraseEdge(Graph &G) |
|
217 { |
|
218 typedef typename Graph::Edge Edge; |
|
219 Edge e; |
|
220 G.erase(e); |
|
221 } |
|
222 |
|
223 template<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())); |
182 } |
230 } |
183 |
231 |
184 |
232 |
185 template<class Graph> void checkNodeList(Graph &G, int nn) |
233 template<class Graph> void checkNodeList(Graph &G, int nn) |
186 { |
234 { |
187 typename Graph::NodeIt n(G); |
235 typename Graph::NodeIt n(G); |
188 for(int i=0;i<nn;i++) { |
236 for(int i=0;i<nn;i++) { |
189 check(G.valid(n),"Wrong Node list linking."); |
237 check(n!=INVALID,"Wrong Node list linking."); |
190 G.next(n); |
238 ++n; |
191 } |
239 } |
192 check(!G.valid(n),"Wrong Node list linking."); |
240 check(n==INVALID,"Wrong Node list linking."); |
193 } |
241 } |
194 |
242 |
195 template<class Graph> void checkEdgeList(Graph &G, int nn) |
243 template<class Graph> void checkEdgeList(Graph &G, int nn) |
196 { |
244 { |
197 typedef typename Graph::EdgeIt EdgeIt; |
245 typedef typename Graph::EdgeIt EdgeIt; |
198 |
246 |
199 EdgeIt e(G); |
247 EdgeIt e(G); |
200 for(int i=0;i<nn;i++) { |
248 for(int i=0;i<nn;i++) { |
201 check(G.valid(e),"Wrong Edge list linking."); |
249 check(e!=INVALID,"Wrong Edge list linking."); |
202 G.next(e); |
250 ++e; |
203 } |
251 } |
204 check(!G.valid(e),"Wrong Edge list linking."); |
252 check(e==INVALID,"Wrong Edge list linking."); |
205 } |
253 } |
206 |
254 |
207 template<class Graph> void checkOutEdgeList(Graph &G, |
255 template<class Graph> void checkOutEdgeList(Graph &G, |
208 typename Graph::Node n, |
256 typename Graph::Node n, |
209 int nn) |
257 int nn) |
210 { |
258 { |
211 typename Graph::OutEdgeIt e(G,n); |
259 typename Graph::OutEdgeIt e(G,n); |
212 for(int i=0;i<nn;i++) { |
260 for(int i=0;i<nn;i++) { |
213 check(G.valid(e),"Wrong OutEdge list linking."); |
261 check(e!=INVALID,"Wrong OutEdge list linking."); |
214 G.next(e); |
262 ++e; |
215 } |
263 } |
216 check(!G.valid(e),"Wrong OutEdge list linking."); |
264 check(e==INVALID,"Wrong OutEdge list linking."); |
217 } |
265 } |
218 |
266 |
219 template<class Graph> void checkInEdgeList(Graph &G, |
267 template<class Graph> void checkInEdgeList(Graph &G, |
220 typename Graph::Node n, |
268 typename Graph::Node n, |
221 int nn) |
269 int nn) |
222 { |
270 { |
223 typename Graph::InEdgeIt e(G,n); |
271 typename Graph::InEdgeIt e(G,n); |
224 for(int i=0;i<nn;i++) { |
272 for(int i=0;i<nn;i++) { |
225 check(G.valid(e),"Wrong InEdge list linking."); |
273 check(e!=INVALID,"Wrong InEdge list linking."); |
226 G.next(e); |
274 ++e; |
227 } |
275 } |
228 check(!G.valid(e),"Wrong InEdge list linking."); |
276 check(e==INVALID,"Wrong InEdge list linking."); |
229 } |
277 } |
230 |
278 |
231 //Checks head(), tail() as well; |
279 ///\file |
|
280 ///\todo Checks head(), tail() as well; |
|
281 |
232 template<class Graph> void bidirPetersen(Graph &G) |
282 template<class Graph> void bidirPetersen(Graph &G) |
233 { |
283 { |
234 typedef typename Graph::Edge Edge; |
284 typedef typename Graph::Edge Edge; |
235 typedef typename Graph::EdgeIt EdgeIt; |
285 typedef typename Graph::EdgeIt EdgeIt; |
236 |
286 |
237 checkEdgeList(G,15); |
287 checkEdgeList(G,15); |
238 |
288 |
239 std::vector<Edge> ee; |
289 std::vector<Edge> ee; |
240 |
290 |
241 for(EdgeIt e(G);G.valid(e);G.next(e)) ee.push_back(e); |
291 for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e); |
242 |
292 |
243 for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++) |
293 for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++) |
244 G.addEdge(G.head(*p),G.tail(*p)); |
294 G.addEdge(G.head(*p),G.tail(*p)); |
245 } |
295 } |
246 |
296 |
252 typedef typename Graph::NodeIt NodeIt; |
302 typedef typename Graph::NodeIt NodeIt; |
253 |
303 |
254 checkNodeList(G,10); |
304 checkNodeList(G,10); |
255 checkEdgeList(G,30); |
305 checkEdgeList(G,30); |
256 |
306 |
257 for(NodeIt n(G);G.valid(n);G.next(n)) { |
307 for(NodeIt n(G);n!=INVALID;++n) { |
258 checkInEdgeList(G,n,3); |
308 checkInEdgeList(G,n,3); |
259 checkOutEdgeList(G,n,3); |
309 checkOutEdgeList(G,n,3); |
260 G.next(n); |
310 ++n; |
261 } |
311 } |
262 } |
312 } |
263 |
313 |
264 template |
314 //Compile GraphSkeleton |
|
315 template |
265 void checkCompileStaticGraph<StaticGraphSkeleton>(StaticGraphSkeleton &); |
316 void checkCompileStaticGraph<StaticGraphSkeleton>(StaticGraphSkeleton &); |
266 template void checkCompile<GraphSkeleton>(GraphSkeleton &); |
317 template void checkCompile<GraphSkeleton>(GraphSkeleton &); |
267 |
318 template |
|
319 void checkCompileErase<EraseableGraphSkeleton>(EraseableGraphSkeleton &); |
|
320 |
|
321 //Compile SmartGraph |
268 template void checkCompile<SmartGraph>(SmartGraph &); |
322 template void checkCompile<SmartGraph>(SmartGraph &); |
|
323 //Compile SymSmartGraph |
269 template void checkCompile<SymSmartGraph>(SymSmartGraph &); |
324 template void checkCompile<SymSmartGraph>(SymSmartGraph &); |
|
325 |
|
326 //Compile ListGraph |
270 template void checkCompile<ListGraph>(ListGraph &); |
327 template void checkCompile<ListGraph>(ListGraph &); |
|
328 template void checkCompileErase<ListGraph>(ListGraph &); |
|
329 template void checkCompileFindEdge<ListGraph>(ListGraph &); |
|
330 |
|
331 //Compile SymListGraph |
271 template void checkCompile<SymListGraph>(SymListGraph &); |
332 template void checkCompile<SymListGraph>(SymListGraph &); |
|
333 template void checkCompileErase<SymListGraph>(SymListGraph &); |
|
334 template void checkCompileFindEdge<SymListGraph>(SymListGraph &); |
|
335 |
|
336 //Compile FullGraph |
272 template void checkCompileStaticGraph<FullGraph>(FullGraph &); |
337 template void checkCompileStaticGraph<FullGraph>(FullGraph &); |
273 |
338 template void checkCompileFindEdge<FullGraph>(FullGraph &); |
|
339 |
|
340 //Compile EdgeSet <ListGraph> |
274 template void checkCompile<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &); |
341 template void checkCompile<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &); |
|
342 template |
|
343 void checkCompileEraseEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &); |
|
344 template |
|
345 void checkCompileFindEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &); |
|
346 |
|
347 //Compile EdgeSet <NodeSet> |
275 template void checkCompile<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &); |
348 template void checkCompile<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &); |
|
349 template |
|
350 void checkCompileEraseEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &); |
|
351 template void checkCompileFindEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &); |
|
352 |
276 |
353 |
277 int main() |
354 int main() |
278 { |
355 { |
279 { |
356 { |
280 SmartGraph G; |
357 SmartGraph G; |