3 #include<hugo/skeletons/graph.h> |
3 #include<hugo/skeletons/graph.h> |
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 #include"graph_test.h" |
8 |
9 |
9 /** |
10 /** |
10 \file |
11 \file |
11 This test makes consistency checks of list graph structures. |
12 This test makes consistency checks of list graph structures. |
12 |
13 |
13 G.addNode(), G.addEdge(), G.tail(), G.head() |
14 G.addNode(), G.addEdge(), G.tail(), G.head() |
14 |
15 |
15 \todo Checks for empty graphs and isolated points. |
16 \todo Checks for empty graphs and isolated points. |
16 \todo Checks for Node->NodeIt, Edge->{EdgeIt,InEdgeIt,OutEdgeIt} |
|
17 conversion. |
17 conversion. |
18 */ |
18 */ |
19 |
19 |
20 using namespace hugo; |
20 using namespace hugo; |
21 |
|
22 template<class Graph> void checkCompileStaticGraph(Graph &G) |
|
23 { |
|
24 typedef typename Graph::Node Node; |
|
25 typedef typename Graph::NodeIt NodeIt; |
|
26 typedef typename Graph::Edge Edge; |
|
27 typedef typename Graph::EdgeIt EdgeIt; |
|
28 typedef typename Graph::InEdgeIt InEdgeIt; |
|
29 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
30 |
|
31 { |
|
32 Node i; Node j(i); Node k(INVALID); |
|
33 i=j; |
|
34 // bool b=G.valid(i); b=b; |
|
35 bool b; b=b; |
|
36 b=(i==INVALID); b=(i!=INVALID); |
|
37 b=(i==j); b=(i!=j); b=(i<j); |
|
38 } |
|
39 { |
|
40 NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G); |
|
41 i=j; |
|
42 j=G.first(i); |
|
43 j=++i; |
|
44 // bool b=G.valid(i); b=b; |
|
45 bool b; b=b; |
|
46 b=(i==INVALID); b=(i!=INVALID); |
|
47 Node n(i); |
|
48 n=i; |
|
49 b=(i==j); b=(i!=j); b=(i<j); |
|
50 //Node ->NodeIt conversion |
|
51 NodeIt ni(G,n); |
|
52 } |
|
53 { |
|
54 Edge i; Edge j(i); Edge k(INVALID); |
|
55 i=j; |
|
56 // bool b=G.valid(i); b=b; |
|
57 bool b; b=b; |
|
58 b=(i==INVALID); b=(i!=INVALID); |
|
59 b=(i==j); b=(i!=j); b=(i<j); |
|
60 } |
|
61 { |
|
62 EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G); |
|
63 i=j; |
|
64 j=G.first(i); |
|
65 j=++i; |
|
66 // bool b=G.valid(i); b=b; |
|
67 bool b; b=b; |
|
68 b=(i==INVALID); b=(i!=INVALID); |
|
69 Edge e(i); |
|
70 e=i; |
|
71 b=(i==j); b=(i!=j); b=(i<j); |
|
72 //Edge ->EdgeIt conversion |
|
73 EdgeIt ei(G,e); |
|
74 } |
|
75 { |
|
76 Node n; |
|
77 InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n); |
|
78 i=j; |
|
79 j=G.first(i,n); |
|
80 j=++i; |
|
81 // bool b=G.valid(i); b=b; |
|
82 bool b; b=b; |
|
83 b=(i==INVALID); b=(i!=INVALID); |
|
84 Edge e(i); |
|
85 e=i; |
|
86 b=(i==j); b=(i!=j); b=(i<j); |
|
87 //Edge ->InEdgeIt conversion |
|
88 InEdgeIt ei(G,e); |
|
89 } |
|
90 { |
|
91 Node n; |
|
92 OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n); |
|
93 i=j; |
|
94 j=G.first(i,n); |
|
95 j=++i; |
|
96 // bool b=G.valid(i); b=b; |
|
97 bool b; b=b; |
|
98 b=(i==INVALID); b=(i!=INVALID); |
|
99 Edge e(i); |
|
100 e=i; |
|
101 b=(i==j); b=(i!=j); b=(i<j); |
|
102 //Edge ->OutEdgeIt conversion |
|
103 OutEdgeIt ei(G,e); |
|
104 } |
|
105 { |
|
106 Node n,m; |
|
107 n=m=INVALID; |
|
108 Edge e; |
|
109 e=INVALID; |
|
110 n=G.tail(e); |
|
111 n=G.head(e); |
|
112 } |
|
113 // id tests |
|
114 { Node n; int i=G.id(n); i=i; } |
|
115 { Edge e; int i=G.id(e); i=i; } |
|
116 //NodeMap tests |
|
117 { |
|
118 Node k; |
|
119 typename Graph::template NodeMap<int> m(G); |
|
120 //Const map |
|
121 typename Graph::template NodeMap<int> const &cm = m; |
|
122 //Inicialize with default value |
|
123 typename Graph::template NodeMap<int> mdef(G,12); |
|
124 //Copy |
|
125 typename Graph::template NodeMap<int> mm(cm); |
|
126 //Copy from another type |
|
127 typename Graph::template NodeMap<double> dm(cm); |
|
128 int v; |
|
129 v=m[k]; m[k]=v; m.set(k,v); |
|
130 v=cm[k]; |
|
131 |
|
132 m=cm; |
|
133 dm=cm; //Copy from another type |
|
134 { |
|
135 //Check the typedef's |
|
136 typename Graph::template NodeMap<int>::ValueType val; |
|
137 val=1; |
|
138 typename Graph::template NodeMap<int>::KeyType key; |
|
139 key = typename Graph::NodeIt(G); |
|
140 } |
|
141 } |
|
142 { //bool NodeMap |
|
143 Node k; |
|
144 typename Graph::template NodeMap<bool> m(G); |
|
145 typename Graph::template NodeMap<bool> const &cm = m; //Const map |
|
146 //Inicialize with default value |
|
147 typename Graph::template NodeMap<bool> mdef(G,12); |
|
148 typename Graph::template NodeMap<bool> mm(cm); //Copy |
|
149 typename Graph::template NodeMap<int> dm(cm); //Copy from another type |
|
150 bool v; |
|
151 v=m[k]; m[k]=v; m.set(k,v); |
|
152 v=cm[k]; |
|
153 |
|
154 m=cm; |
|
155 dm=cm; //Copy from another type |
|
156 m=dm; //Copy to another type |
|
157 |
|
158 { |
|
159 //Check the typedef's |
|
160 typename Graph::template NodeMap<bool>::ValueType val; |
|
161 val=true; |
|
162 typename Graph::template NodeMap<bool>::KeyType key; |
|
163 key= typename Graph::NodeIt(G); |
|
164 } |
|
165 } |
|
166 //EdgeMap tests |
|
167 { |
|
168 Edge k; |
|
169 typename Graph::template EdgeMap<int> m(G); |
|
170 typename Graph::template EdgeMap<int> const &cm = m; //Const map |
|
171 //Inicialize with default value |
|
172 typename Graph::template EdgeMap<int> mdef(G,12); |
|
173 typename Graph::template EdgeMap<int> mm(cm); //Copy |
|
174 typename Graph::template EdgeMap<double> dm(cm); //Copy from another type |
|
175 int v; |
|
176 v=m[k]; m[k]=v; m.set(k,v); |
|
177 v=cm[k]; |
|
178 |
|
179 m=cm; |
|
180 dm=cm; //Copy from another type |
|
181 { |
|
182 //Check the typedef's |
|
183 typename Graph::template EdgeMap<int>::ValueType val; |
|
184 val=1; |
|
185 typename Graph::template EdgeMap<int>::KeyType key; |
|
186 key= typename Graph::EdgeIt(G); |
|
187 } |
|
188 } |
|
189 { //bool EdgeMap |
|
190 Edge k; |
|
191 typename Graph::template EdgeMap<bool> m(G); |
|
192 typename Graph::template EdgeMap<bool> const &cm = m; //Const map |
|
193 //Inicialize with default value |
|
194 typename Graph::template EdgeMap<bool> mdef(G,12); |
|
195 typename Graph::template EdgeMap<bool> mm(cm); //Copy |
|
196 typename Graph::template EdgeMap<int> dm(cm); //Copy from another type |
|
197 bool v; |
|
198 v=m[k]; m[k]=v; m.set(k,v); |
|
199 v=cm[k]; |
|
200 |
|
201 m=cm; |
|
202 dm=cm; //Copy from another type |
|
203 m=dm; //Copy to another type |
|
204 { |
|
205 //Check the typedef's |
|
206 typename Graph::template EdgeMap<bool>::ValueType val; |
|
207 val=true; |
|
208 typename Graph::template EdgeMap<bool>::KeyType key; |
|
209 key= typename Graph::EdgeIt(G); |
|
210 } |
|
211 } |
|
212 } |
|
213 |
|
214 template<class Graph> void checkCompile(Graph &G) |
|
215 { |
|
216 checkCompileStaticGraph(G); |
|
217 |
|
218 typedef typename Graph::Node Node; |
|
219 typedef typename Graph::NodeIt NodeIt; |
|
220 typedef typename Graph::Edge Edge; |
|
221 typedef typename Graph::EdgeIt EdgeIt; |
|
222 typedef typename Graph::InEdgeIt InEdgeIt; |
|
223 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
224 |
|
225 Node n,m; |
|
226 n=G.addNode(); |
|
227 m=G.addNode(); |
|
228 Edge e; |
|
229 e=G.addEdge(n,m); |
|
230 |
|
231 // G.clear(); |
|
232 } |
|
233 |
|
234 template<class Graph> void checkCompileErase(Graph &G) |
|
235 { |
|
236 typedef typename Graph::Node Node; |
|
237 typedef typename Graph::Edge Edge; |
|
238 Node n; |
|
239 Edge e; |
|
240 G.erase(n); |
|
241 G.erase(e); |
|
242 } |
|
243 |
|
244 template<class Graph> void checkCompileEraseEdge(Graph &G) |
|
245 { |
|
246 typedef typename Graph::Edge Edge; |
|
247 Edge e; |
|
248 G.erase(e); |
|
249 } |
|
250 |
|
251 template<class Graph> void checkCompileFindEdge(Graph &G) |
|
252 { |
|
253 typedef typename Graph::NodeIt Node; |
|
254 typedef typename Graph::NodeIt NodeIt; |
|
255 |
|
256 G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G))); |
|
257 G.findEdge(Node(),Node(),G.findEdge(Node(),Node())); |
|
258 } |
|
259 |
|
260 |
|
261 template<class Graph> void checkNodeList(Graph &G, int nn) |
|
262 { |
|
263 typename Graph::NodeIt n(G); |
|
264 for(int i=0;i<nn;i++) { |
|
265 check(n!=INVALID,"Wrong Node list linking."); |
|
266 ++n; |
|
267 } |
|
268 check(n==INVALID,"Wrong Node list linking."); |
|
269 } |
|
270 |
|
271 template<class Graph> void checkEdgeList(Graph &G, int nn) |
|
272 { |
|
273 typedef typename Graph::EdgeIt EdgeIt; |
|
274 |
|
275 EdgeIt e(G); |
|
276 for(int i=0;i<nn;i++) { |
|
277 check(e!=INVALID,"Wrong Edge list linking."); |
|
278 ++e; |
|
279 } |
|
280 check(e==INVALID,"Wrong Edge list linking."); |
|
281 } |
|
282 |
|
283 template<class Graph> void checkOutEdgeList(Graph &G, |
|
284 typename Graph::Node n, |
|
285 int nn) |
|
286 { |
|
287 typename Graph::OutEdgeIt e(G,n); |
|
288 for(int i=0;i<nn;i++) { |
|
289 check(e!=INVALID,"Wrong OutEdge list linking."); |
|
290 ++e; |
|
291 } |
|
292 check(e==INVALID,"Wrong OutEdge list linking."); |
|
293 } |
|
294 |
|
295 template<class Graph> void checkInEdgeList(Graph &G, |
|
296 typename Graph::Node n, |
|
297 int nn) |
|
298 { |
|
299 typename Graph::InEdgeIt e(G,n); |
|
300 for(int i=0;i<nn;i++) { |
|
301 check(e!=INVALID,"Wrong InEdge list linking."); |
|
302 ++e; |
|
303 } |
|
304 check(e==INVALID,"Wrong InEdge list linking."); |
|
305 } |
|
306 |
|
307 ///\file |
|
308 ///\todo Checks head(), tail() as well; |
|
309 |
21 |
310 template<class Graph> void bidirPetersen(Graph &G) |
22 template<class Graph> void bidirPetersen(Graph &G) |
311 { |
23 { |
312 typedef typename Graph::Edge Edge; |
24 typedef typename Graph::Edge Edge; |
313 typedef typename Graph::EdgeIt EdgeIt; |
25 typedef typename Graph::EdgeIt EdgeIt; |
314 |
26 |
315 checkEdgeList(G,15); |
27 checkGraphEdgeList(G,15); |
316 |
28 |
317 std::vector<Edge> ee; |
29 std::vector<Edge> ee; |
318 |
30 |
319 for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e); |
31 for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e); |
320 |
32 |
327 typedef typename Graph::Node Node; |
39 typedef typename Graph::Node Node; |
328 |
40 |
329 typedef typename Graph::EdgeIt EdgeIt; |
41 typedef typename Graph::EdgeIt EdgeIt; |
330 typedef typename Graph::NodeIt NodeIt; |
42 typedef typename Graph::NodeIt NodeIt; |
331 |
43 |
332 checkNodeList(G,10); |
44 checkGraphNodeList(G,10); |
333 checkEdgeList(G,30); |
45 checkGraphEdgeList(G,30); |
334 |
46 |
335 for(NodeIt n(G);n!=INVALID;++n) { |
47 for(NodeIt n(G);n!=INVALID;++n) { |
336 checkInEdgeList(G,n,3); |
48 checkGraphInEdgeList(G,n,3); |
337 checkOutEdgeList(G,n,3); |
49 checkGraphOutEdgeList(G,n,3); |
338 ++n; |
50 ++n; |
339 } |
51 } |
340 } |
52 } |
341 |
53 |
342 //Compile GraphSkeleton |
54 //Compile GraphSkeleton |
343 template void checkCompileStaticGraph<skeleton::StaticGraphSkeleton> |
55 template void checkCompileStaticGraph<skeleton::StaticGraphSkeleton> |
344 (skeleton::StaticGraphSkeleton &); |
56 (skeleton::StaticGraphSkeleton &); |
345 |
57 |
346 template void checkCompile<skeleton::GraphSkeleton>(skeleton::GraphSkeleton &); |
58 template void checkCompileGraph<skeleton::GraphSkeleton> |
|
59 (skeleton::GraphSkeleton &); |
347 |
60 |
348 template void checkCompileErase<skeleton::EraseableGraphSkeleton> |
61 template void checkCompileErasableGraph<skeleton::EraseableGraphSkeleton> |
349 (skeleton::EraseableGraphSkeleton &); |
62 (skeleton::EraseableGraphSkeleton &); |
350 |
63 |
351 //Compile SmartGraph |
64 //Compile SmartGraph |
352 template void checkCompile<SmartGraph>(SmartGraph &); |
65 template void checkCompileGraph<SmartGraph>(SmartGraph &); |
|
66 template void checkCompileGraphFindEdge<SmartGraph>(SmartGraph &); |
353 |
67 |
354 //Compile SymSmartGraph |
68 //Compile SymSmartGraph |
355 template void checkCompile<SymSmartGraph>(SymSmartGraph &); |
69 template void checkCompileGraph<SymSmartGraph>(SymSmartGraph &); |
|
70 template void checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &); |
356 |
71 |
357 //Compile ListGraph |
72 //Compile ListGraph |
358 template void checkCompile<ListGraph>(ListGraph &); |
73 template void checkCompileGraph<ListGraph>(ListGraph &); |
359 template void checkCompileErase<ListGraph>(ListGraph &); |
74 template void checkCompileErasableGraph<ListGraph>(ListGraph &); |
360 template void checkCompileFindEdge<ListGraph>(ListGraph &); |
75 template void checkCompileGraphFindEdge<ListGraph>(ListGraph &); |
361 |
76 |
362 |
77 |
363 //Compile SymListGraph |
78 //Compile SymListGraph |
364 template void checkCompile<SymListGraph>(SymListGraph &); |
79 template void checkCompileGraph<SymListGraph>(SymListGraph &); |
365 template void checkCompileErase<SymListGraph>(SymListGraph &); |
80 template void checkCompileErasableGraph<SymListGraph>(SymListGraph &); |
366 template void checkCompileFindEdge<SymListGraph>(SymListGraph &); |
81 template void checkCompileGraphFindEdge<SymListGraph>(SymListGraph &); |
367 |
82 |
368 //Compile FullGraph |
83 //Compile FullGraph |
369 template void checkCompileStaticGraph<FullGraph>(FullGraph &); |
84 template void checkCompileStaticGraph<FullGraph>(FullGraph &); |
370 template void checkCompileFindEdge<FullGraph>(FullGraph &); |
85 template void checkCompileGraphFindEdge<FullGraph>(FullGraph &); |
371 |
86 |
372 //Compile EdgeSet <ListGraph> |
87 //Compile EdgeSet <ListGraph> |
373 template void checkCompile<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &); |
88 template void checkCompileGraph<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &); |
374 template |
89 template void checkCompileGraphEraseEdge<EdgeSet <ListGraph> > |
375 void checkCompileEraseEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &); |
90 (EdgeSet <ListGraph> &); |
376 template |
91 template void checkCompileGraphFindEdge<EdgeSet <ListGraph> > |
377 void checkCompileFindEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &); |
92 (EdgeSet <ListGraph> &); |
378 |
93 |
379 //Compile EdgeSet <NodeSet> |
94 //Compile EdgeSet <NodeSet> |
380 template void checkCompile<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &); |
95 template void checkCompileGraph<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &); |
381 template |
96 template void checkCompileGraphEraseEdge<EdgeSet <NodeSet> > |
382 void checkCompileEraseEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &); |
97 (EdgeSet <NodeSet> &); |
383 template void checkCompileFindEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &); |
98 template void checkCompileGraphFindEdge<EdgeSet <NodeSet> > |
|
99 (EdgeSet <NodeSet> &); |
384 |
100 |
385 |
101 |
386 int main() |
102 int main() |
387 { |
103 { |
388 { |
104 { |