19 #include <string> |
19 #include <string> |
20 #include <iostream> |
20 #include <iostream> |
21 |
21 |
22 #include <lemon/concepts/path.h> |
22 #include <lemon/concepts/path.h> |
23 #include <lemon/concepts/digraph.h> |
23 #include <lemon/concepts/digraph.h> |
|
24 #include <lemon/concept_check.h> |
24 |
25 |
25 #include <lemon/path.h> |
26 #include <lemon/path.h> |
26 #include <lemon/list_graph.h> |
27 #include <lemon/list_graph.h> |
27 |
28 |
28 #include "test_tools.h" |
29 #include "test_tools.h" |
29 |
30 |
30 using namespace std; |
31 using namespace std; |
31 using namespace lemon; |
32 using namespace lemon; |
32 |
33 |
33 void check_concepts() { |
34 template <typename GR> |
34 checkConcept<concepts::Path<ListDigraph>, concepts::Path<ListDigraph> >(); |
35 void checkConcepts() { |
35 checkConcept<concepts::Path<ListDigraph>, Path<ListDigraph> >(); |
36 checkConcept<concepts::Path<GR>, concepts::Path<GR> >(); |
36 checkConcept<concepts::Path<ListDigraph>, SimplePath<ListDigraph> >(); |
37 checkConcept<concepts::Path<GR>, Path<GR> >(); |
37 checkConcept<concepts::Path<ListDigraph>, StaticPath<ListDigraph> >(); |
38 checkConcept<concepts::Path<GR>, SimplePath<GR> >(); |
38 checkConcept<concepts::Path<ListDigraph>, ListPath<ListDigraph> >(); |
39 checkConcept<concepts::Path<GR>, StaticPath<GR> >(); |
|
40 checkConcept<concepts::Path<GR>, ListPath<GR> >(); |
|
41 } |
|
42 |
|
43 // Conecpt checking for path structures |
|
44 void checkPathConcepts() { |
|
45 checkConcepts<concepts::Digraph>(); |
|
46 checkConcepts<ListDigraph>(); |
39 } |
47 } |
40 |
48 |
41 // Check if proper copy consructor is called (use valgrind for testing) |
49 // Check if proper copy consructor is called (use valgrind for testing) |
42 template<class _Path> |
50 template <typename GR, typename P1, typename P2> |
43 void checkCopy() |
51 void checkCopy(typename GR::Arc a) { |
44 { |
52 P1 p; |
|
53 p.addBack(a); |
|
54 P1 q; |
|
55 q = p; |
|
56 P1 r(p); |
|
57 P2 q2; |
|
58 q2 = p; |
|
59 P2 r2(p); |
|
60 } |
|
61 |
|
62 // Tests for copy constructors and assignment operators of paths |
|
63 void checkPathCopy() { |
45 ListDigraph g; |
64 ListDigraph g; |
46 ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode()); |
65 ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode()); |
47 |
66 |
48 _Path p,q; |
67 typedef Path<ListDigraph> Path1; |
49 p.addBack(a); |
68 typedef SimplePath<ListDigraph> Path2; |
50 q=p; |
69 typedef ListPath<ListDigraph> Path3; |
51 _Path r(p); |
70 typedef StaticPath<ListDigraph> Path4; |
52 StaticPath<ListDigraph> s(r); |
71 checkCopy<ListDigraph, Path1, Path2>(a); |
53 } |
72 checkCopy<ListDigraph, Path1, Path3>(a); |
54 |
73 checkCopy<ListDigraph, Path1, Path4>(a); |
|
74 checkCopy<ListDigraph, Path2, Path1>(a); |
|
75 checkCopy<ListDigraph, Path2, Path3>(a); |
|
76 checkCopy<ListDigraph, Path2, Path4>(a); |
|
77 checkCopy<ListDigraph, Path3, Path1>(a); |
|
78 checkCopy<ListDigraph, Path3, Path2>(a); |
|
79 checkCopy<ListDigraph, Path3, Path4>(a); |
|
80 } |
|
81 |
|
82 // Class for testing path functions |
|
83 class CheckPathFunctions { |
|
84 typedef ListDigraph GR; |
|
85 DIGRAPH_TYPEDEFS(GR); |
|
86 GR gr; |
|
87 const GR& cgr; |
|
88 Node n1, n2, n3, n4; |
|
89 Node tmp_n; |
|
90 Arc a1, a2, a3, a4; |
|
91 Arc tmp_a; |
|
92 |
|
93 public: |
|
94 |
|
95 CheckPathFunctions() : cgr(gr) { |
|
96 n1 = gr.addNode(); |
|
97 n2 = gr.addNode(); |
|
98 n3 = gr.addNode(); |
|
99 n4 = gr.addNode(); |
|
100 a1 = gr.addArc(n1, n2); |
|
101 a2 = gr.addArc(n2, n3); |
|
102 a3 = gr.addArc(n3, n4); |
|
103 a4 = gr.addArc(n4, n1); |
|
104 } |
|
105 |
|
106 void run() { |
|
107 checkBackAndFrontInsertablePath<Path<GR> >(); |
|
108 checkBackAndFrontInsertablePath<ListPath<GR> >(); |
|
109 checkBackInsertablePath<SimplePath<GR> >(); |
|
110 |
|
111 checkListPathSplitAndSplice(); |
|
112 } |
|
113 |
|
114 private: |
|
115 |
|
116 template <typename P> |
|
117 void checkBackInsertablePath() { |
|
118 |
|
119 // Create and check empty path |
|
120 P p; |
|
121 const P& cp = p; |
|
122 check(cp.empty(), "The path is not empty"); |
|
123 check(cp.length() == 0, "The path is not empty"); |
|
124 // check(cp.front() == INVALID, "Wrong front()"); |
|
125 // check(cp.back() == INVALID, "Wrong back()"); |
|
126 typename P::ArcIt ai(cp); |
|
127 check(ai == INVALID, "Wrong ArcIt"); |
|
128 check(pathSource(cgr, cp) == INVALID, "Wrong pathSource()"); |
|
129 check(pathTarget(cgr, cp) == INVALID, "Wrong pathTarget()"); |
|
130 check(checkPath(cgr, cp), "Wrong checkPath()"); |
|
131 PathNodeIt<P> ni(cgr, cp); |
|
132 check(ni == INVALID, "Wrong PathNodeIt"); |
|
133 |
|
134 // Check single-arc path |
|
135 p.addBack(a1); |
|
136 check(!cp.empty(), "Wrong empty()"); |
|
137 check(cp.length() == 1, "Wrong length"); |
|
138 check(cp.front() == a1, "Wrong front()"); |
|
139 check(cp.back() == a1, "Wrong back()"); |
|
140 check(cp.nth(0) == a1, "Wrong nth()"); |
|
141 ai = cp.nthIt(0); |
|
142 check((tmp_a = ai) == a1, "Wrong nthIt()"); |
|
143 check(++ai == INVALID, "Wrong nthIt()"); |
|
144 typename P::ArcIt ai2(cp); |
|
145 check((tmp_a = ai2) == a1, "Wrong ArcIt"); |
|
146 check(++ai2 == INVALID, "Wrong ArcIt"); |
|
147 check(pathSource(cgr, cp) == n1, "Wrong pathSource()"); |
|
148 check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()"); |
|
149 check(checkPath(cgr, cp), "Wrong checkPath()"); |
|
150 PathNodeIt<P> ni2(cgr, cp); |
|
151 check((tmp_n = ni2) == n1, "Wrong PathNodeIt"); |
|
152 check((tmp_n = ++ni2) == n2, "Wrong PathNodeIt"); |
|
153 check(++ni2 == INVALID, "Wrong PathNodeIt"); |
|
154 |
|
155 // Check adding more arcs |
|
156 p.addBack(a2); |
|
157 p.addBack(a3); |
|
158 check(!cp.empty(), "Wrong empty()"); |
|
159 check(cp.length() == 3, "Wrong length"); |
|
160 check(cp.front() == a1, "Wrong front()"); |
|
161 check(cp.back() == a3, "Wrong back()"); |
|
162 check(cp.nth(0) == a1, "Wrong nth()"); |
|
163 check(cp.nth(1) == a2, "Wrong nth()"); |
|
164 check(cp.nth(2) == a3, "Wrong nth()"); |
|
165 typename P::ArcIt ai3(cp); |
|
166 check((tmp_a = ai3) == a1, "Wrong ArcIt"); |
|
167 check((tmp_a = ++ai3) == a2, "Wrong nthIt()"); |
|
168 check((tmp_a = ++ai3) == a3, "Wrong nthIt()"); |
|
169 check(++ai3 == INVALID, "Wrong nthIt()"); |
|
170 ai = cp.nthIt(0); |
|
171 check((tmp_a = ai) == a1, "Wrong nthIt()"); |
|
172 check((tmp_a = ++ai) == a2, "Wrong nthIt()"); |
|
173 ai = cp.nthIt(2); |
|
174 check((tmp_a = ai) == a3, "Wrong nthIt()"); |
|
175 check(++ai == INVALID, "Wrong nthIt()"); |
|
176 check(pathSource(cgr, cp) == n1, "Wrong pathSource()"); |
|
177 check(pathTarget(cgr, cp) == n4, "Wrong pathTarget()"); |
|
178 check(checkPath(cgr, cp), "Wrong checkPath()"); |
|
179 PathNodeIt<P> ni3(cgr, cp); |
|
180 check((tmp_n = ni3) == n1, "Wrong PathNodeIt"); |
|
181 check((tmp_n = ++ni3) == n2, "Wrong PathNodeIt"); |
|
182 check((tmp_n = ++ni3) == n3, "Wrong PathNodeIt"); |
|
183 check((tmp_n = ++ni3) == n4, "Wrong PathNodeIt"); |
|
184 check(++ni3 == INVALID, "Wrong PathNodeIt"); |
|
185 |
|
186 // Check arc removal and addition |
|
187 p.eraseBack(); |
|
188 p.eraseBack(); |
|
189 p.addBack(a2); |
|
190 check(!cp.empty(), "Wrong empty()"); |
|
191 check(cp.length() == 2, "Wrong length"); |
|
192 check(cp.front() == a1, "Wrong front()"); |
|
193 check(cp.back() == a2, "Wrong back()"); |
|
194 check(pathSource(cgr, cp) == n1, "Wrong pathSource()"); |
|
195 check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()"); |
|
196 check(checkPath(cgr, cp), "Wrong checkPath()"); |
|
197 |
|
198 // Check clear() |
|
199 p.clear(); |
|
200 check(cp.empty(), "The path is not empty"); |
|
201 check(cp.length() == 0, "The path is not empty"); |
|
202 |
|
203 // Check inconsistent path |
|
204 p.addBack(a4); |
|
205 p.addBack(a2); |
|
206 p.addBack(a1); |
|
207 check(!cp.empty(), "Wrong empty()"); |
|
208 check(cp.length() == 3, "Wrong length"); |
|
209 check(cp.front() == a4, "Wrong front()"); |
|
210 check(cp.back() == a1, "Wrong back()"); |
|
211 check(pathSource(cgr, cp) == n4, "Wrong pathSource()"); |
|
212 check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()"); |
|
213 check(!checkPath(cgr, cp), "Wrong checkPath()"); |
|
214 } |
|
215 |
|
216 template <typename P> |
|
217 void checkBackAndFrontInsertablePath() { |
|
218 |
|
219 // Include back insertable test cases |
|
220 checkBackInsertablePath<P>(); |
|
221 |
|
222 // Check front and back insertion |
|
223 P p; |
|
224 const P& cp = p; |
|
225 p.addFront(a4); |
|
226 p.addBack(a1); |
|
227 p.addFront(a3); |
|
228 check(!cp.empty(), "Wrong empty()"); |
|
229 check(cp.length() == 3, "Wrong length"); |
|
230 check(cp.front() == a3, "Wrong front()"); |
|
231 check(cp.back() == a1, "Wrong back()"); |
|
232 check(cp.nth(0) == a3, "Wrong nth()"); |
|
233 check(cp.nth(1) == a4, "Wrong nth()"); |
|
234 check(cp.nth(2) == a1, "Wrong nth()"); |
|
235 typename P::ArcIt ai(cp); |
|
236 check((tmp_a = ai) == a3, "Wrong ArcIt"); |
|
237 check((tmp_a = ++ai) == a4, "Wrong nthIt()"); |
|
238 check((tmp_a = ++ai) == a1, "Wrong nthIt()"); |
|
239 check(++ai == INVALID, "Wrong nthIt()"); |
|
240 ai = cp.nthIt(0); |
|
241 check((tmp_a = ai) == a3, "Wrong nthIt()"); |
|
242 check((tmp_a = ++ai) == a4, "Wrong nthIt()"); |
|
243 ai = cp.nthIt(2); |
|
244 check((tmp_a = ai) == a1, "Wrong nthIt()"); |
|
245 check(++ai == INVALID, "Wrong nthIt()"); |
|
246 check(pathSource(cgr, cp) == n3, "Wrong pathSource()"); |
|
247 check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()"); |
|
248 check(checkPath(cgr, cp), "Wrong checkPath()"); |
|
249 |
|
250 // Check eraseFront() |
|
251 p.eraseFront(); |
|
252 p.addBack(a2); |
|
253 check(!cp.empty(), "Wrong empty()"); |
|
254 check(cp.length() == 3, "Wrong length"); |
|
255 check(cp.front() == a4, "Wrong front()"); |
|
256 check(cp.back() == a2, "Wrong back()"); |
|
257 check(cp.nth(0) == a4, "Wrong nth()"); |
|
258 check(cp.nth(1) == a1, "Wrong nth()"); |
|
259 check(cp.nth(2) == a2, "Wrong nth()"); |
|
260 typename P::ArcIt ai2(cp); |
|
261 check((tmp_a = ai2) == a4, "Wrong ArcIt"); |
|
262 check((tmp_a = ++ai2) == a1, "Wrong nthIt()"); |
|
263 check((tmp_a = ++ai2) == a2, "Wrong nthIt()"); |
|
264 check(++ai2 == INVALID, "Wrong nthIt()"); |
|
265 ai = cp.nthIt(0); |
|
266 check((tmp_a = ai) == a4, "Wrong nthIt()"); |
|
267 check((tmp_a = ++ai) == a1, "Wrong nthIt()"); |
|
268 ai = cp.nthIt(2); |
|
269 check((tmp_a = ai) == a2, "Wrong nthIt()"); |
|
270 check(++ai == INVALID, "Wrong nthIt()"); |
|
271 check(pathSource(cgr, cp) == n4, "Wrong pathSource()"); |
|
272 check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()"); |
|
273 check(checkPath(cgr, cp), "Wrong checkPath()"); |
|
274 } |
|
275 |
|
276 void checkListPathSplitAndSplice() { |
|
277 |
|
278 // Build a path with spliceFront() and spliceBack() |
|
279 ListPath<GR> p1, p2, p3, p4; |
|
280 p1.addBack(a3); |
|
281 p1.addFront(a2); |
|
282 p2.addBack(a1); |
|
283 p1.spliceFront(p2); |
|
284 p3.addFront(a4); |
|
285 p1.spliceBack(p3); |
|
286 check(p1.length() == 4, "Wrong length"); |
|
287 check(p1.front() == a1, "Wrong front()"); |
|
288 check(p1.back() == a4, "Wrong back()"); |
|
289 ListPath<GR>::ArcIt ai(p1); |
|
290 check((tmp_a = ai) == a1, "Wrong ArcIt"); |
|
291 check((tmp_a = ++ai) == a2, "Wrong nthIt()"); |
|
292 check((tmp_a = ++ai) == a3, "Wrong nthIt()"); |
|
293 check((tmp_a = ++ai) == a4, "Wrong nthIt()"); |
|
294 check(++ai == INVALID, "Wrong nthIt()"); |
|
295 check(checkPath(cgr, p1), "Wrong checkPath()"); |
|
296 |
|
297 // Check split() |
|
298 p1.split(p1.nthIt(2), p2); |
|
299 check(p1.length() == 2, "Wrong length"); |
|
300 ai = p1.nthIt(0); |
|
301 check((tmp_a = ai) == a1, "Wrong ArcIt"); |
|
302 check((tmp_a = ++ai) == a2, "Wrong nthIt()"); |
|
303 check(++ai == INVALID, "Wrong nthIt()"); |
|
304 check(checkPath(cgr, p1), "Wrong checkPath()"); |
|
305 check(p2.length() == 2, "Wrong length"); |
|
306 ai = p2.nthIt(0); |
|
307 check((tmp_a = ai) == a3, "Wrong ArcIt"); |
|
308 check((tmp_a = ++ai) == a4, "Wrong nthIt()"); |
|
309 check(++ai == INVALID, "Wrong nthIt()"); |
|
310 check(checkPath(cgr, p2), "Wrong checkPath()"); |
|
311 |
|
312 // Check split() and splice() |
|
313 p1.spliceFront(p2); |
|
314 p1.split(p1.nthIt(2), p2); |
|
315 p2.split(p2.nthIt(1), p3); |
|
316 p2.spliceBack(p1); |
|
317 p2.splice(p2.nthIt(1), p3); |
|
318 check(p2.length() == 4, "Wrong length"); |
|
319 check(p2.front() == a1, "Wrong front()"); |
|
320 check(p2.back() == a4, "Wrong back()"); |
|
321 ai = p2.nthIt(0); |
|
322 check((tmp_a = ai) == a1, "Wrong ArcIt"); |
|
323 check((tmp_a = ++ai) == a2, "Wrong nthIt()"); |
|
324 check((tmp_a = ++ai) == a3, "Wrong nthIt()"); |
|
325 check((tmp_a = ++ai) == a4, "Wrong nthIt()"); |
|
326 check(++ai == INVALID, "Wrong nthIt()"); |
|
327 check(checkPath(cgr, p2), "Wrong checkPath()"); |
|
328 } |
|
329 |
|
330 }; |
|
331 |
55 int main() { |
332 int main() { |
56 check_concepts(); |
333 checkPathConcepts(); |
57 |
334 checkPathCopy(); |
58 checkCopy<Path<ListDigraph> >(); |
335 CheckPathFunctions cpf; |
59 checkCopy<SimplePath<ListDigraph> >(); |
336 cpf.run(); |
60 checkCopy<ListPath<ListDigraph> >(); |
|
61 |
|
62 ListDigraph g; |
|
63 ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode()); |
|
64 |
|
65 Path<ListDigraph> p; |
|
66 StaticPath<ListDigraph> q,r; |
|
67 p.addBack(a); |
|
68 q=p; |
|
69 r=q; |
|
70 StaticPath<ListDigraph> s(q); |
|
71 |
337 |
72 return 0; |
338 return 0; |
73 } |
339 } |