COIN-OR::LEMON - Graph Library

source: lemon-main/test/path_test.cc @ 1202:4fd76139b69e

tip
Last change on this file since 1202:4fd76139b69e was 1202:4fd76139b69e, checked in by Peter Kovacs <kpeter@…>, 3 years ago

Add operator[] to Path structures (#250)

File size: 11.6 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2013
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#include <string>
20#include <iostream>
21
22#include <lemon/concepts/path.h>
23#include <lemon/concepts/digraph.h>
24#include <lemon/concept_check.h>
25
26#include <lemon/path.h>
27#include <lemon/list_graph.h>
28
29#include "test_tools.h"
30
31using namespace std;
32using namespace lemon;
33
34template <typename GR>
35void checkConcepts() {
36  checkConcept<concepts::Path<GR>, concepts::Path<GR> >();
37  checkConcept<concepts::Path<GR>, Path<GR> >();
38  checkConcept<concepts::Path<GR>, SimplePath<GR> >();
39  checkConcept<concepts::Path<GR>, StaticPath<GR> >();
40  checkConcept<concepts::Path<GR>, ListPath<GR> >();
41}
42
43// Conecpt checking for path structures
44void checkPathConcepts() {
45  checkConcepts<concepts::Digraph>();
46  checkConcepts<ListDigraph>();
47}
48
49// Check if proper copy consructor is called (use valgrind for testing)
50template <typename GR, typename P1, typename P2>
51void checkCopy(typename GR::Arc a) {
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
63void checkPathCopy() {
64  ListDigraph g;
65  ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode());
66
67  typedef Path<ListDigraph> Path1;
68  typedef SimplePath<ListDigraph> Path2;
69  typedef ListPath<ListDigraph> Path3;
70  typedef StaticPath<ListDigraph> Path4;
71  checkCopy<ListDigraph, Path1, Path2>(a);
72  checkCopy<ListDigraph, Path1, Path3>(a);
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
83class 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
93public:
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    checkSubscriptOperator<Path<GR> >();
112    checkSubscriptOperator<SimplePath<GR> >();
113    checkSubscriptOperator<StaticPath<GR> >();
114    checkSubscriptOperator<ListPath<GR> >();
115
116    checkListPathSplitAndSplice();
117  }
118
119private:
120
121  template <typename P>
122  void checkBackInsertablePath() {
123
124    // Create and check empty path
125    P p;
126    const P& cp = p;
127    check(cp.empty(), "The path is not empty");
128    check(cp.length() == 0, "The path is not empty");
129//    check(cp.front() == INVALID, "Wrong front()");
130//    check(cp.back() == INVALID, "Wrong back()");
131    typename P::ArcIt ai(cp);
132    check(ai == INVALID, "Wrong ArcIt");
133    check(pathSource(cgr, cp) == INVALID, "Wrong pathSource()");
134    check(pathTarget(cgr, cp) == INVALID, "Wrong pathTarget()");
135    check(checkPath(cgr, cp), "Wrong checkPath()");
136    PathNodeIt<P> ni(cgr, cp);
137    check(ni == INVALID, "Wrong PathNodeIt");
138
139    // Check single-arc path
140    p.addBack(a1);
141    check(!cp.empty(), "Wrong empty()");
142    check(cp.length() == 1, "Wrong length");
143    check(cp.front() == a1, "Wrong front()");
144    check(cp.back() == a1, "Wrong back()");
145    check(cp.nth(0) == a1, "Wrong nth()");
146    ai = cp.nthIt(0);
147    check((tmp_a = ai) == a1, "Wrong nthIt()");
148    check(++ai == INVALID, "Wrong nthIt()");
149    typename P::ArcIt ai2(cp);
150    check((tmp_a = ai2) == a1, "Wrong ArcIt");
151    check(++ai2 == INVALID, "Wrong ArcIt");
152    check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
153    check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
154    check(checkPath(cgr, cp), "Wrong checkPath()");
155    PathNodeIt<P> ni2(cgr, cp);
156    check((tmp_n = ni2) == n1, "Wrong PathNodeIt");
157    check((tmp_n = ++ni2) == n2, "Wrong PathNodeIt");
158    check(++ni2 == INVALID, "Wrong PathNodeIt");
159
160    // Check adding more arcs
161    p.addBack(a2);
162    p.addBack(a3);
163    check(!cp.empty(), "Wrong empty()");
164    check(cp.length() == 3, "Wrong length");
165    check(cp.front() == a1, "Wrong front()");
166    check(cp.back() == a3, "Wrong back()");
167    check(cp.nth(0) == a1, "Wrong nth()");
168    check(cp.nth(1) == a2, "Wrong nth()");
169    check(cp.nth(2) == a3, "Wrong nth()");
170    typename P::ArcIt ai3(cp);
171    check((tmp_a = ai3) == a1, "Wrong ArcIt");
172    check((tmp_a = ++ai3) == a2, "Wrong nthIt()");
173    check((tmp_a = ++ai3) == a3, "Wrong nthIt()");
174    check(++ai3 == INVALID, "Wrong nthIt()");
175    ai = cp.nthIt(0);
176    check((tmp_a = ai) == a1, "Wrong nthIt()");
177    check((tmp_a = ++ai) == a2, "Wrong nthIt()");
178    ai = cp.nthIt(2);
179    check((tmp_a = ai) == a3, "Wrong nthIt()");
180    check(++ai == INVALID, "Wrong nthIt()");
181    check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
182    check(pathTarget(cgr, cp) == n4, "Wrong pathTarget()");
183    check(checkPath(cgr, cp), "Wrong checkPath()");
184    PathNodeIt<P> ni3(cgr, cp);
185    check((tmp_n = ni3) == n1, "Wrong PathNodeIt");
186    check((tmp_n = ++ni3) == n2, "Wrong PathNodeIt");
187    check((tmp_n = ++ni3) == n3, "Wrong PathNodeIt");
188    check((tmp_n = ++ni3) == n4, "Wrong PathNodeIt");
189    check(++ni3 == INVALID, "Wrong PathNodeIt");
190
191    // Check arc removal and addition
192    p.eraseBack();
193    p.eraseBack();
194    p.addBack(a2);
195    check(!cp.empty(), "Wrong empty()");
196    check(cp.length() == 2, "Wrong length");
197    check(cp.front() == a1, "Wrong front()");
198    check(cp.back() == a2, "Wrong back()");
199    check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
200    check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()");
201    check(checkPath(cgr, cp), "Wrong checkPath()");
202
203    // Check clear()
204    p.clear();
205    check(cp.empty(), "The path is not empty");
206    check(cp.length() == 0, "The path is not empty");
207
208    // Check inconsistent path
209    p.addBack(a4);
210    p.addBack(a2);
211    p.addBack(a1);
212    check(!cp.empty(), "Wrong empty()");
213    check(cp.length() == 3, "Wrong length");
214    check(cp.front() == a4, "Wrong front()");
215    check(cp.back() == a1, "Wrong back()");
216    check(pathSource(cgr, cp) == n4, "Wrong pathSource()");
217    check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
218    check(!checkPath(cgr, cp), "Wrong checkPath()");
219  }
220
221  template <typename P>
222  void checkBackAndFrontInsertablePath() {
223
224    // Include back insertable test cases
225    checkBackInsertablePath<P>();
226
227    // Check front and back insertion
228    P p;
229    const P& cp = p;
230    p.addFront(a4);
231    p.addBack(a1);
232    p.addFront(a3);
233    check(!cp.empty(), "Wrong empty()");
234    check(cp.length() == 3, "Wrong length");
235    check(cp.front() == a3, "Wrong front()");
236    check(cp.back() == a1, "Wrong back()");
237    check(cp.nth(0) == a3, "Wrong nth()");
238    check(cp.nth(1) == a4, "Wrong nth()");
239    check(cp.nth(2) == a1, "Wrong nth()");
240    typename P::ArcIt ai(cp);
241    check((tmp_a = ai) == a3, "Wrong ArcIt");
242    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
243    check((tmp_a = ++ai) == a1, "Wrong nthIt()");
244    check(++ai == INVALID, "Wrong nthIt()");
245    ai = cp.nthIt(0);
246    check((tmp_a = ai) == a3, "Wrong nthIt()");
247    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
248    ai = cp.nthIt(2);
249    check((tmp_a = ai) == a1, "Wrong nthIt()");
250    check(++ai == INVALID, "Wrong nthIt()");
251    check(pathSource(cgr, cp) == n3, "Wrong pathSource()");
252    check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
253    check(checkPath(cgr, cp), "Wrong checkPath()");
254
255    // Check eraseFront()
256    p.eraseFront();
257    p.addBack(a2);
258    check(!cp.empty(), "Wrong empty()");
259    check(cp.length() == 3, "Wrong length");
260    check(cp.front() == a4, "Wrong front()");
261    check(cp.back() == a2, "Wrong back()");
262    check(cp.nth(0) == a4, "Wrong nth()");
263    check(cp.nth(1) == a1, "Wrong nth()");
264    check(cp.nth(2) == a2, "Wrong nth()");
265    typename P::ArcIt ai2(cp);
266    check((tmp_a = ai2) == a4, "Wrong ArcIt");
267    check((tmp_a = ++ai2) == a1, "Wrong nthIt()");
268    check((tmp_a = ++ai2) == a2, "Wrong nthIt()");
269    check(++ai2 == INVALID, "Wrong nthIt()");
270    ai = cp.nthIt(0);
271    check((tmp_a = ai) == a4, "Wrong nthIt()");
272    check((tmp_a = ++ai) == a1, "Wrong nthIt()");
273    ai = cp.nthIt(2);
274    check((tmp_a = ai) == a2, "Wrong nthIt()");
275    check(++ai == INVALID, "Wrong nthIt()");
276    check(pathSource(cgr, cp) == n4, "Wrong pathSource()");
277    check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()");
278    check(checkPath(cgr, cp), "Wrong checkPath()");
279  }
280
281  template <typename P>
282  void checkSubscriptOperator() {
283    SimplePath<GR> p0;
284    p0.addBack(a1);
285    p0.addBack(a3);
286    p0.addBack(a2);
287    P p = p0;
288    check(!p.empty(), "Wrong empty()");
289    check(p.length() == 3, "Wrong length");
290    check(p.front() == a1, "Wrong front()");
291    check(p.back() == a2, "Wrong back()");
292    check(p.nth(0) == a1, "Wrong nth()");
293    check(p.nth(1) == a3, "Wrong nth()");
294    check(p.nth(2) == a2, "Wrong nth()");
295    check(p[0] == a1, "Wrong operator[]");
296    check(p[1] == a3, "Wrong operator[]");
297    check(p[2] == a2, "Wrong operator[]");
298  }
299
300  void checkListPathSplitAndSplice() {
301
302    // Build a path with spliceFront() and spliceBack()
303    ListPath<GR> p1, p2, p3, p4;
304    p1.addBack(a3);
305    p1.addFront(a2);
306    p2.addBack(a1);
307    p1.spliceFront(p2);
308    p3.addFront(a4);
309    p1.spliceBack(p3);
310    check(p1.length() == 4, "Wrong length");
311    check(p1.front() == a1, "Wrong front()");
312    check(p1.back() == a4, "Wrong back()");
313    ListPath<GR>::ArcIt ai(p1);
314    check((tmp_a = ai) == a1, "Wrong ArcIt");
315    check((tmp_a = ++ai) == a2, "Wrong nthIt()");
316    check((tmp_a = ++ai) == a3, "Wrong nthIt()");
317    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
318    check(++ai == INVALID, "Wrong nthIt()");
319    check(checkPath(cgr, p1), "Wrong checkPath()");
320
321    // Check split()
322    p1.split(p1.nthIt(2), p2);
323    check(p1.length() == 2, "Wrong length");
324    ai = p1.nthIt(0);
325    check((tmp_a = ai) == a1, "Wrong ArcIt");
326    check((tmp_a = ++ai) == a2, "Wrong nthIt()");
327    check(++ai == INVALID, "Wrong nthIt()");
328    check(checkPath(cgr, p1), "Wrong checkPath()");
329    check(p2.length() == 2, "Wrong length");
330    ai = p2.nthIt(0);
331    check((tmp_a = ai) == a3, "Wrong ArcIt");
332    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
333    check(++ai == INVALID, "Wrong nthIt()");
334    check(checkPath(cgr, p2), "Wrong checkPath()");
335
336    // Check split() and splice()
337    p1.spliceFront(p2);
338    p1.split(p1.nthIt(2), p2);
339    p2.split(p2.nthIt(1), p3);
340    p2.spliceBack(p1);
341    p2.splice(p2.nthIt(1), p3);
342    check(p2.length() == 4, "Wrong length");
343    check(p2.front() == a1, "Wrong front()");
344    check(p2.back() == a4, "Wrong back()");
345    ai = p2.nthIt(0);
346    check((tmp_a = ai) == a1, "Wrong ArcIt");
347    check((tmp_a = ++ai) == a2, "Wrong nthIt()");
348    check((tmp_a = ++ai) == a3, "Wrong nthIt()");
349    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
350    check(++ai == INVALID, "Wrong nthIt()");
351    check(checkPath(cgr, p2), "Wrong checkPath()");
352  }
353
354};
355
356int main() {
357  checkPathConcepts();
358  checkPathCopy();
359  CheckPathFunctions cpf;
360  cpf.run();
361
362  return 0;
363}
Note: See TracBrowser for help on using the repository browser.