7 //! \ingroup misc |
8 //! \ingroup misc |
8 //! \file |
9 //! \file |
9 //! \brief Some utility to test graph classes. |
10 //! \brief Some utility to test graph classes. |
10 namespace hugo { |
11 namespace hugo { |
11 |
12 |
12 |
13 struct DummyType { |
13 template<class Graph> void checkCompileStaticGraph(Graph &G) |
14 int value; |
14 { |
15 DummyType() {} |
15 typedef typename Graph::Node Node; |
16 DummyType(int p) : value(p) {} |
16 typedef typename Graph::NodeIt NodeIt; |
17 DummyType& operator=(int p) { value = p; return *this;} |
17 typedef typename Graph::Edge Edge; |
18 }; |
18 typedef typename Graph::EdgeIt EdgeIt; |
19 |
19 typedef typename Graph::InEdgeIt InEdgeIt; |
20 |
20 typedef typename Graph::OutEdgeIt OutEdgeIt; |
21 template<class Graph> void checkCompileStaticGraph(Graph &G) |
|
22 { |
|
23 typedef typename Graph::Node Node; |
|
24 typedef typename Graph::NodeIt NodeIt; |
|
25 typedef typename Graph::Edge Edge; |
|
26 typedef typename Graph::EdgeIt EdgeIt; |
|
27 typedef typename Graph::InEdgeIt InEdgeIt; |
|
28 typedef typename Graph::OutEdgeIt OutEdgeIt; |
21 |
29 |
22 { |
30 { |
23 Node i; Node j(i); Node k(INVALID); |
31 Node i; Node j(i); Node k(INVALID); |
24 i=j; |
32 i=j; |
25 bool b; b=true; |
33 bool b; b=true; |
26 b=(i==INVALID); b=(i!=INVALID); |
34 b=(i==INVALID); b=(i!=INVALID); |
27 b=(i==j); b=(i!=j); b=(i<j); |
35 b=(i==j); b=(i!=j); b=(i<j); |
28 } |
36 } |
29 { |
37 { |
30 NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G); |
38 NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G); |
31 i=j; |
39 i=j; |
32 j=G.first(i); |
40 j=G.first(i); |
33 j=++i; |
41 j=++i; |
34 bool b; b=true; |
42 bool b; b=true; |
35 b=(i==INVALID); b=(i!=INVALID); |
43 b=(i==INVALID); b=(i!=INVALID); |
36 Node n(i); |
44 Node n(i); |
37 n=i; |
45 n=i; |
38 b=(i==j); b=(i!=j); b=(i<j); |
46 b=(i==j); b=(i!=j); b=(i<j); |
39 //Node ->NodeIt conversion |
47 //Node ->NodeIt conversion |
40 NodeIt ni(G,n); |
48 NodeIt ni(G,n); |
41 } |
49 } |
42 { |
50 { |
43 Edge i; Edge j(i); Edge k(INVALID); |
51 Edge i; Edge j(i); Edge k(INVALID); |
44 i=j; |
52 i=j; |
45 bool b; b=true; |
53 bool b; b=true; |
46 b=(i==INVALID); b=(i!=INVALID); |
54 b=(i==INVALID); b=(i!=INVALID); |
47 b=(i==j); b=(i!=j); b=(i<j); |
55 b=(i==j); b=(i!=j); b=(i<j); |
48 } |
56 } |
49 { |
57 { |
50 EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G); |
58 EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G); |
51 i=j; |
59 i=j; |
52 j=G.first(i); |
60 j=G.first(i); |
53 j=++i; |
61 j=++i; |
54 bool b; b=true; |
62 bool b; b=true; |
55 b=(i==INVALID); b=(i!=INVALID); |
63 b=(i==INVALID); b=(i!=INVALID); |
56 Edge e(i); |
64 Edge e(i); |
57 e=i; |
65 e=i; |
58 b=(i==j); b=(i!=j); b=(i<j); |
66 b=(i==j); b=(i!=j); b=(i<j); |
59 //Edge ->EdgeIt conversion |
67 //Edge ->EdgeIt conversion |
60 EdgeIt ei(G,e); |
68 EdgeIt ei(G,e); |
61 } |
69 } |
62 { |
70 { |
63 Node n; |
71 Node n; |
64 InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n); |
72 InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n); |
65 i=j; |
73 i=j; |
66 j=G.first(i,n); |
74 j=G.first(i,n); |
67 j=++i; |
75 j=++i; |
68 bool b; b=true; |
76 bool b; b=true; |
69 b=(i==INVALID); b=(i!=INVALID); |
77 b=(i==INVALID); b=(i!=INVALID); |
70 Edge e(i); |
78 Edge e(i); |
71 e=i; |
79 e=i; |
72 b=(i==j); b=(i!=j); b=(i<j); |
80 b=(i==j); b=(i!=j); b=(i<j); |
73 //Edge ->InEdgeIt conversion |
81 //Edge ->InEdgeIt conversion |
74 InEdgeIt ei(G,e); |
82 InEdgeIt ei(G,e); |
75 } |
83 } |
76 { |
84 { |
77 Node n; |
85 Node n; |
78 OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n); |
86 OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n); |
79 i=j; |
87 i=j; |
80 j=G.first(i,n); |
88 j=G.first(i,n); |
81 j=++i; |
89 j=++i; |
82 bool b; b=true; |
90 bool b; b=true; |
83 b=(i==INVALID); b=(i!=INVALID); |
91 b=(i==INVALID); b=(i!=INVALID); |
84 Edge e(i); |
92 Edge e(i); |
85 e=i; |
93 e=i; |
86 b=(i==j); b=(i!=j); b=(i<j); |
94 b=(i==j); b=(i!=j); b=(i<j); |
87 //Edge ->OutEdgeIt conversion |
95 //Edge ->OutEdgeIt conversion |
88 OutEdgeIt ei(G,e); |
96 OutEdgeIt ei(G,e); |
89 } |
97 } |
90 { |
98 { |
91 Node n,m; |
99 Node n,m; |
92 n=m=INVALID; |
100 n=m=INVALID; |
93 Edge e; |
101 Edge e; |
94 e=INVALID; |
102 e=INVALID; |
95 n=G.tail(e); |
103 n=G.tail(e); |
96 n=G.head(e); |
104 n=G.head(e); |
97 } |
105 } |
98 // id tests |
106 // id tests |
99 { Node n; int i=G.id(n); i=i; } |
107 { Node n; int i=G.id(n); i=i; } |
100 { Edge e; int i=G.id(e); i=i; } |
108 { Edge e; int i=G.id(e); i=i; } |
101 //NodeMap tests |
109 //NodeMap tests |
102 { |
110 { |
103 Node k; |
111 Node k; |
104 typename Graph::template NodeMap<int> m(G); |
112 typename Graph::template NodeMap<int> m(G); |
105 //Const map |
113 //Const map |
106 typename Graph::template NodeMap<int> const &cm = m; |
114 typename Graph::template NodeMap<int> const &cm = m; |
107 //Inicialize with default value |
115 //Inicialize with default value |
108 typename Graph::template NodeMap<int> mdef(G,12); |
116 typename Graph::template NodeMap<int> mdef(G,12); |
109 //Copy |
117 //Copy |
110 typename Graph::template NodeMap<int> mm(cm); |
118 typename Graph::template NodeMap<int> mm(cm); |
111 //Copy from another type |
119 //Copy from another type |
112 typename Graph::template NodeMap<double> dm(cm); |
120 typename Graph::template NodeMap<double> dm(cm); |
113 int v; |
121 //Copy to more complex type |
114 v=m[k]; m[k]=v; m.set(k,v); |
122 typename Graph::template NodeMap<DummyType> em(cm); |
115 v=cm[k]; |
123 int v; |
|
124 v=m[k]; m[k]=v; m.set(k,v); |
|
125 v=cm[k]; |
116 |
126 |
117 m=cm; |
127 m=cm; |
118 dm=cm; //Copy from another type |
128 dm=cm; //Copy from another type |
119 { |
129 em=cm; //Copy to more complex type |
120 //Check the typedef's |
130 { |
121 typename Graph::template NodeMap<int>::ValueType val; |
131 //Check the typedef's |
122 val=1; |
132 typename Graph::template NodeMap<int>::ValueType val; |
123 typename Graph::template NodeMap<int>::KeyType key; |
133 val=1; |
124 key = typename Graph::NodeIt(G); |
134 typename Graph::template NodeMap<int>::KeyType key; |
125 } |
135 key = typename Graph::NodeIt(G); |
126 } |
136 } |
127 { //bool NodeMap |
137 } |
128 Node k; |
138 { //bool NodeMap |
129 typename Graph::template NodeMap<bool> m(G); |
139 Node k; |
130 typename Graph::template NodeMap<bool> const &cm = m; //Const map |
140 typename Graph::template NodeMap<bool> m(G); |
131 //Inicialize with default value |
141 typename Graph::template NodeMap<bool> const &cm = m; //Const map |
132 typename Graph::template NodeMap<bool> mdef(G,12); |
142 //Inicialize with default value |
133 typename Graph::template NodeMap<bool> mm(cm); //Copy |
143 typename Graph::template NodeMap<bool> mdef(G,12); |
134 typename Graph::template NodeMap<int> dm(cm); //Copy from another type |
144 typename Graph::template NodeMap<bool> mm(cm); //Copy |
135 bool v; |
145 typename Graph::template NodeMap<int> dm(cm); //Copy from another type |
136 v=m[k]; m[k]=v; m.set(k,v); |
146 bool v; |
137 v=cm[k]; |
147 v=m[k]; m[k]=v; m.set(k,v); |
|
148 v=cm[k]; |
138 |
149 |
139 m=cm; |
150 m=cm; |
140 dm=cm; //Copy from another type |
151 dm=cm; //Copy from another type |
141 m=dm; //Copy to another type |
152 m=dm; //Copy to another type |
142 |
153 |
143 { |
154 { |
144 //Check the typedef's |
155 //Check the typedef's |
145 typename Graph::template NodeMap<bool>::ValueType val; |
156 typename Graph::template NodeMap<bool>::ValueType val; |
146 val=true; |
157 val=true; |
147 typename Graph::template NodeMap<bool>::KeyType key; |
158 typename Graph::template NodeMap<bool>::KeyType key; |
148 key= typename Graph::NodeIt(G); |
159 key= typename Graph::NodeIt(G); |
149 } |
160 } |
150 } |
161 } |
151 //EdgeMap tests |
162 //EdgeMap tests |
152 { |
163 { |
153 Edge k; |
164 Edge k; |
154 typename Graph::template EdgeMap<int> m(G); |
165 typename Graph::template EdgeMap<int> m(G); |
155 typename Graph::template EdgeMap<int> const &cm = m; //Const map |
166 typename Graph::template EdgeMap<int> const &cm = m; //Const map |
156 //Inicialize with default value |
167 //Inicialize with default value |
157 typename Graph::template EdgeMap<int> mdef(G,12); |
168 typename Graph::template EdgeMap<int> mdef(G,12); |
158 typename Graph::template EdgeMap<int> mm(cm); //Copy |
169 typename Graph::template EdgeMap<int> mm(cm); //Copy |
159 typename Graph::template EdgeMap<double> dm(cm); //Copy from another type |
170 typename Graph::template EdgeMap<double> dm(cm); //Copy from another type |
160 int v; |
171 int v; |
161 v=m[k]; m[k]=v; m.set(k,v); |
172 v=m[k]; m[k]=v; m.set(k,v); |
162 v=cm[k]; |
173 v=cm[k]; |
163 |
174 |
164 m=cm; |
175 m=cm; |
165 dm=cm; //Copy from another type |
176 dm=cm; //Copy from another type |
166 { |
177 { |
167 //Check the typedef's |
178 //Check the typedef's |
168 typename Graph::template EdgeMap<int>::ValueType val; |
179 typename Graph::template EdgeMap<int>::ValueType val; |
169 val=1; |
180 val=1; |
170 typename Graph::template EdgeMap<int>::KeyType key; |
181 typename Graph::template EdgeMap<int>::KeyType key; |
171 key= typename Graph::EdgeIt(G); |
182 key= typename Graph::EdgeIt(G); |
172 } |
183 } |
173 } |
184 } |
174 { //bool EdgeMap |
185 { //bool EdgeMap |
175 Edge k; |
186 Edge k; |
176 typename Graph::template EdgeMap<bool> m(G); |
187 typename Graph::template EdgeMap<bool> m(G); |
177 typename Graph::template EdgeMap<bool> const &cm = m; //Const map |
188 typename Graph::template EdgeMap<bool> const &cm = m; //Const map |
178 //Inicialize with default value |
189 //Inicialize with default value |
179 typename Graph::template EdgeMap<bool> mdef(G,12); |
190 typename Graph::template EdgeMap<bool> mdef(G,12); |
180 typename Graph::template EdgeMap<bool> mm(cm); //Copy |
191 typename Graph::template EdgeMap<bool> mm(cm); //Copy |
181 typename Graph::template EdgeMap<int> dm(cm); //Copy from another type |
192 typename Graph::template EdgeMap<int> dm(cm); //Copy from another type |
182 bool v; |
193 bool v; |
183 v=m[k]; m[k]=v; m.set(k,v); |
194 v=m[k]; m[k]=v; m.set(k,v); |
184 v=cm[k]; |
195 v=cm[k]; |
185 |
196 |
186 m=cm; |
197 m=cm; |
187 dm=cm; //Copy from another type |
198 dm=cm; //Copy from another type |
188 m=dm; //Copy to another type |
199 m=dm; //Copy to another type |
189 { |
200 { |
190 //Check the typedef's |
201 //Check the typedef's |
191 typename Graph::template EdgeMap<bool>::ValueType val; |
202 typename Graph::template EdgeMap<bool>::ValueType val; |
192 val=true; |
203 val=true; |
193 typename Graph::template EdgeMap<bool>::KeyType key; |
204 typename Graph::template EdgeMap<bool>::KeyType key; |
194 key= typename Graph::EdgeIt(G); |
205 key= typename Graph::EdgeIt(G); |
195 } |
206 } |
196 } |
207 } |
197 } |
208 } |
198 |
209 |
199 template<class Graph> void checkCompileGraph(Graph &G) |
210 template<class Graph> void checkCompileGraph(Graph &G) |
200 { |
211 { |
201 checkCompileStaticGraph(G); |
212 checkCompileStaticGraph(G); |
202 |
213 |
203 typedef typename Graph::Node Node; |
214 typedef typename Graph::Node Node; |
204 typedef typename Graph::NodeIt NodeIt; |
215 typedef typename Graph::NodeIt NodeIt; |
205 typedef typename Graph::Edge Edge; |
216 typedef typename Graph::Edge Edge; |
206 typedef typename Graph::EdgeIt EdgeIt; |
217 typedef typename Graph::EdgeIt EdgeIt; |
207 typedef typename Graph::InEdgeIt InEdgeIt; |
218 typedef typename Graph::InEdgeIt InEdgeIt; |
208 typedef typename Graph::OutEdgeIt OutEdgeIt; |
219 typedef typename Graph::OutEdgeIt OutEdgeIt; |
209 |
220 |
210 Node n,m; |
221 Node n,m; |
211 n=G.addNode(); |
222 n=G.addNode(); |
212 m=G.addNode(); |
223 m=G.addNode(); |
213 Edge e; |
224 Edge e; |
214 e=G.addEdge(n,m); |
225 e=G.addEdge(n,m); |
215 |
226 |
216 // G.clear(); |
227 // G.clear(); |
217 } |
228 } |
218 |
229 |
219 template<class Graph> void checkCompileGraphEraseEdge(Graph &G) |
230 template<class Graph> void checkCompileGraphEraseEdge(Graph &G) |
220 { |
231 { |
221 typename Graph::Edge e; |
232 typename Graph::Edge e; |
222 G.erase(e); |
233 G.erase(e); |
223 } |
234 } |
224 |
235 |
225 template<class Graph> void checkCompileGraphEraseNode(Graph &G) |
236 template<class Graph> void checkCompileGraphEraseNode(Graph &G) |
226 { |
237 { |
227 typename Graph::Node n; |
238 typename Graph::Node n; |
228 G.erase(n); |
239 G.erase(n); |
229 } |
240 } |
230 |
241 |
231 template<class Graph> void checkCompileErasableGraph(Graph &G) |
242 template<class Graph> void checkCompileErasableGraph(Graph &G) |
232 { |
243 { |
233 checkCompileGraph(G); |
244 checkCompileGraph(G); |
234 checkCompileGraphEraseNode(G); |
245 checkCompileGraphEraseNode(G); |
235 checkCompileGraphEraseEdge(G); |
246 checkCompileGraphEraseEdge(G); |
236 } |
247 } |
237 |
248 |
238 template<class Graph> void checkCompileGraphFindEdge(Graph &G) |
249 template<class Graph> void checkCompileGraphFindEdge(Graph &G) |
239 { |
250 { |
240 typedef typename Graph::NodeIt Node; |
251 typedef typename Graph::NodeIt Node; |
241 typedef typename Graph::NodeIt NodeIt; |
252 typedef typename Graph::NodeIt NodeIt; |
242 |
253 |
243 G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G))); |
254 G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G))); |
244 G.findEdge(Node(),Node(),G.findEdge(Node(),Node())); |
255 G.findEdge(Node(),Node(),G.findEdge(Node(),Node())); |
245 } |
256 } |
246 |
257 |
247 template<class Graph> void checkGraphNodeList(Graph &G, int nn) |
258 template<class Graph> void checkGraphNodeList(Graph &G, int nn) |
248 { |
259 { |
249 typename Graph::NodeIt n(G); |
260 typename Graph::NodeIt n(G); |
250 for(int i=0;i<nn;i++) { |
261 for(int i=0;i<nn;i++) { |
251 check(n!=INVALID,"Wrong Node list linking."); |
262 check(n!=INVALID,"Wrong Node list linking."); |
252 ++n; |
263 ++n; |
253 } |
264 } |
254 check(n==INVALID,"Wrong Node list linking."); |
265 check(n==INVALID,"Wrong Node list linking."); |
255 } |
266 } |
256 |
267 |
257 template<class Graph> void checkGraphEdgeList(Graph &G, int nn) |
268 template<class Graph> void checkGraphEdgeList(Graph &G, int nn) |
258 { |
269 { |
259 typedef typename Graph::EdgeIt EdgeIt; |
270 typedef typename Graph::EdgeIt EdgeIt; |
260 |
271 |
261 EdgeIt e(G); |
272 EdgeIt e(G); |
262 for(int i=0;i<nn;i++) { |
273 for(int i=0;i<nn;i++) { |
263 check(e!=INVALID,"Wrong Edge list linking."); |
274 check(e!=INVALID,"Wrong Edge list linking."); |
264 ++e; |
275 ++e; |
265 } |
276 } |
266 check(e==INVALID,"Wrong Edge list linking."); |
277 check(e==INVALID,"Wrong Edge list linking."); |
267 } |
278 } |
268 |
279 |
269 template<class Graph> void checkGraphOutEdgeList(Graph &G, |
280 template<class Graph> void checkGraphOutEdgeList(Graph &G, |
270 typename Graph::Node n, |
281 typename Graph::Node n, |
271 int nn) |
282 int nn) |
272 { |
283 { |
273 typename Graph::OutEdgeIt e(G,n); |
284 typename Graph::OutEdgeIt e(G,n); |
274 for(int i=0;i<nn;i++) { |
285 for(int i=0;i<nn;i++) { |
275 check(e!=INVALID,"Wrong OutEdge list linking."); |
286 check(e!=INVALID,"Wrong OutEdge list linking."); |
276 ++e; |
287 ++e; |
277 } |
288 } |
278 check(e==INVALID,"Wrong OutEdge list linking."); |
289 check(e==INVALID,"Wrong OutEdge list linking."); |
279 } |
290 } |
280 |
291 |
281 template<class Graph> void checkGraphInEdgeList(Graph &G, |
292 template<class Graph> void checkGraphInEdgeList(Graph &G, |
282 typename Graph::Node n, |
293 typename Graph::Node n, |
283 int nn) |
294 int nn) |
284 { |
295 { |
285 typename Graph::InEdgeIt e(G,n); |
296 typename Graph::InEdgeIt e(G,n); |
286 for(int i=0;i<nn;i++) { |
297 for(int i=0;i<nn;i++) { |
287 check(e!=INVALID,"Wrong InEdge list linking."); |
298 check(e!=INVALID,"Wrong InEdge list linking."); |
288 ++e; |
299 ++e; |
289 } |
300 } |
290 check(e==INVALID,"Wrong InEdge list linking."); |
301 check(e==INVALID,"Wrong InEdge list linking."); |
291 } |
302 } |
292 |
303 |
293 ///\file |
304 ///\file |
294 ///\todo Check head(), tail() as well; |
305 ///\todo Check head(), tail() as well; |
295 |
306 |
296 |
307 |
297 } //namespace hugo |
308 } //namespace hugo |
298 |
309 |
299 |
310 |