1.1 --- a/lemon/path.h	Sat Mar 20 11:03:12 2010 +0100
     1.2 +++ b/lemon/path.h	Fri Mar 08 10:47:38 2013 +0100
     1.3 @@ -317,7 +317,7 @@
     1.4  
     1.5        /// Constructor with starting point
     1.6        ArcIt(const SimplePath &_path, int _idx)
     1.7 -        : idx(_idx), path(&_path) {}
     1.8 +        : path(&_path), idx(_idx) {}
     1.9  
    1.10      public:
    1.11  

     2.1 --- a/test/path_test.cc	Sat Mar 20 11:03:12 2010 +0100
     2.2 +++ b/test/path_test.cc	Fri Mar 08 10:47:38 2013 +0100
     2.3 @@ -21,6 +21,7 @@
     2.4  
     2.5  #include <lemon/concepts/path.h>
     2.6  #include <lemon/concepts/digraph.h>
     2.7 +#include <lemon/concept_check.h>
     2.8  
     2.9  #include <lemon/path.h>
    2.10  #include <lemon/list_graph.h>
    2.11 @@ -30,44 +31,309 @@
    2.12  using namespace std;
    2.13  using namespace lemon;
    2.14  
    2.15 -void check_concepts() {
    2.16 -  checkConcept<concepts::Path<ListDigraph>, concepts::Path<ListDigraph> >();
    2.17 -  checkConcept<concepts::Path<ListDigraph>, Path<ListDigraph> >();
    2.18 -  checkConcept<concepts::Path<ListDigraph>, SimplePath<ListDigraph> >();
    2.19 -  checkConcept<concepts::Path<ListDigraph>, StaticPath<ListDigraph> >();
    2.20 -  checkConcept<concepts::Path<ListDigraph>, ListPath<ListDigraph> >();
    2.21 +template <typename GR>
    2.22 +void checkConcepts() {
    2.23 +  checkConcept<concepts::Path<GR>, concepts::Path<GR> >();
    2.24 +  checkConcept<concepts::Path<GR>, Path<GR> >();
    2.25 +  checkConcept<concepts::Path<GR>, SimplePath<GR> >();
    2.26 +  checkConcept<concepts::Path<GR>, StaticPath<GR> >();
    2.27 +  checkConcept<concepts::Path<GR>, ListPath<GR> >();
    2.28 +}
    2.29 +
    2.30 +// Conecpt checking for path structures
    2.31 +void checkPathConcepts() {
    2.32 +  checkConcepts<concepts::Digraph>();
    2.33 +  checkConcepts<ListDigraph>();
    2.34  }
    2.35  
    2.36  // Check if proper copy consructor is called (use valgrind for testing)
    2.37 -template<class _Path>
    2.38 -void checkCopy()
    2.39 -{
    2.40 +template <typename GR, typename P1, typename P2>
    2.41 +void checkCopy(typename GR::Arc a) {
    2.42 +  P1 p;
    2.43 +  p.addBack(a);
    2.44 +  P1 q;
    2.45 +  q = p;
    2.46 +  P1 r(p);
    2.47 +  P2 q2;
    2.48 +  q2 = p;
    2.49 +  P2 r2(p);
    2.50 +}
    2.51 +
    2.52 +// Tests for copy constructors and assignment operators of paths
    2.53 +void checkPathCopy() {
    2.54    ListDigraph g;
    2.55 -  ListDigraph::Arc a  = g.addArc(g.addNode(), g.addNode());
    2.56 -  
    2.57 -  _Path p,q;
    2.58 -  p.addBack(a);
    2.59 -  q=p;
    2.60 -  _Path r(p);
    2.61 -  StaticPath<ListDigraph> s(r);
    2.62 +  ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode());
    2.63 +
    2.64 +  typedef Path<ListDigraph> Path1;
    2.65 +  typedef SimplePath<ListDigraph> Path2;
    2.66 +  typedef ListPath<ListDigraph> Path3;
    2.67 +  typedef StaticPath<ListDigraph> Path4;
    2.68 +  checkCopy<ListDigraph, Path1, Path2>(a);
    2.69 +  checkCopy<ListDigraph, Path1, Path3>(a);
    2.70 +  checkCopy<ListDigraph, Path1, Path4>(a);
    2.71 +  checkCopy<ListDigraph, Path2, Path1>(a);
    2.72 +  checkCopy<ListDigraph, Path2, Path3>(a);
    2.73 +  checkCopy<ListDigraph, Path2, Path4>(a);
    2.74 +  checkCopy<ListDigraph, Path3, Path1>(a);
    2.75 +  checkCopy<ListDigraph, Path3, Path2>(a);
    2.76 +  checkCopy<ListDigraph, Path3, Path4>(a);
    2.77  }
    2.78 -  
    2.79 +
    2.80 +// Class for testing path functions
    2.81 +class CheckPathFunctions {
    2.82 +  typedef ListDigraph GR;
    2.83 +  DIGRAPH_TYPEDEFS(GR);
    2.84 +  GR gr;
    2.85 +  const GR& cgr;
    2.86 +  Node n1, n2, n3, n4;
    2.87 +  Node tmp_n;
    2.88 +  Arc a1, a2, a3, a4;
    2.89 +  Arc tmp_a;
    2.90 +
    2.91 +public:
    2.92 +
    2.93 +  CheckPathFunctions() : cgr(gr) {
    2.94 +    n1 = gr.addNode();
    2.95 +    n2 = gr.addNode();
    2.96 +    n3 = gr.addNode();
    2.97 +    n4 = gr.addNode();
    2.98 +    a1 = gr.addArc(n1, n2);
    2.99 +    a2 = gr.addArc(n2, n3);
   2.100 +    a3 = gr.addArc(n3, n4);
   2.101 +    a4 = gr.addArc(n4, n1);
   2.102 +  }
   2.103 +
   2.104 +  void run() {
   2.105 +    checkBackAndFrontInsertablePath<Path<GR> >();
   2.106 +    checkBackAndFrontInsertablePath<ListPath<GR> >();
   2.107 +    checkBackInsertablePath<SimplePath<GR> >();
   2.108 +
   2.109 +    checkListPathSplitAndSplice();
   2.110 +  }
   2.111 +
   2.112 +private:
   2.113 +
   2.114 +  template <typename P>
   2.115 +  void checkBackInsertablePath() {
   2.116 +
   2.117 +    // Create and check empty path
   2.118 +    P p;
   2.119 +    const P& cp = p;
   2.120 +    check(cp.empty(), "The path is not empty");
   2.121 +    check(cp.length() == 0, "The path is not empty");
   2.122 +//    check(cp.front() == INVALID, "Wrong front()");
   2.123 +//    check(cp.back() == INVALID, "Wrong back()");
   2.124 +    typename P::ArcIt ai(cp);
   2.125 +    check(ai == INVALID, "Wrong ArcIt");
   2.126 +    check(pathSource(cgr, cp) == INVALID, "Wrong pathSource()");
   2.127 +    check(pathTarget(cgr, cp) == INVALID, "Wrong pathTarget()");
   2.128 +    check(checkPath(cgr, cp), "Wrong checkPath()");
   2.129 +    PathNodeIt<P> ni(cgr, cp);
   2.130 +    check(ni == INVALID, "Wrong PathNodeIt");
   2.131 +
   2.132 +    // Check single-arc path
   2.133 +    p.addBack(a1);
   2.134 +    check(!cp.empty(), "Wrong empty()");
   2.135 +    check(cp.length() == 1, "Wrong length");
   2.136 +    check(cp.front() == a1, "Wrong front()");
   2.137 +    check(cp.back() == a1, "Wrong back()");
   2.138 +    check(cp.nth(0) == a1, "Wrong nth()");
   2.139 +    ai = cp.nthIt(0);
   2.140 +    check((tmp_a = ai) == a1, "Wrong nthIt()");
   2.141 +    check(++ai == INVALID, "Wrong nthIt()");
   2.142 +    typename P::ArcIt ai2(cp);
   2.143 +    check((tmp_a = ai2) == a1, "Wrong ArcIt");
   2.144 +    check(++ai2 == INVALID, "Wrong ArcIt");
   2.145 +    check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
   2.146 +    check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
   2.147 +    check(checkPath(cgr, cp), "Wrong checkPath()");
   2.148 +    PathNodeIt<P> ni2(cgr, cp);
   2.149 +    check((tmp_n = ni2) == n1, "Wrong PathNodeIt");
   2.150 +    check((tmp_n = ++ni2) == n2, "Wrong PathNodeIt");
   2.151 +    check(++ni2 == INVALID, "Wrong PathNodeIt");
   2.152 +
   2.153 +    // Check adding more arcs
   2.154 +    p.addBack(a2);
   2.155 +    p.addBack(a3);
   2.156 +    check(!cp.empty(), "Wrong empty()");
   2.157 +    check(cp.length() == 3, "Wrong length");
   2.158 +    check(cp.front() == a1, "Wrong front()");
   2.159 +    check(cp.back() == a3, "Wrong back()");
   2.160 +    check(cp.nth(0) == a1, "Wrong nth()");
   2.161 +    check(cp.nth(1) == a2, "Wrong nth()");
   2.162 +    check(cp.nth(2) == a3, "Wrong nth()");
   2.163 +    typename P::ArcIt ai3(cp);
   2.164 +    check((tmp_a = ai3) == a1, "Wrong ArcIt");
   2.165 +    check((tmp_a = ++ai3) == a2, "Wrong nthIt()");
   2.166 +    check((tmp_a = ++ai3) == a3, "Wrong nthIt()");
   2.167 +    check(++ai3 == INVALID, "Wrong nthIt()");
   2.168 +    ai = cp.nthIt(0);
   2.169 +    check((tmp_a = ai) == a1, "Wrong nthIt()");
   2.170 +    check((tmp_a = ++ai) == a2, "Wrong nthIt()");
   2.171 +    ai = cp.nthIt(2);
   2.172 +    check((tmp_a = ai) == a3, "Wrong nthIt()");
   2.173 +    check(++ai == INVALID, "Wrong nthIt()");
   2.174 +    check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
   2.175 +    check(pathTarget(cgr, cp) == n4, "Wrong pathTarget()");
   2.176 +    check(checkPath(cgr, cp), "Wrong checkPath()");
   2.177 +    PathNodeIt<P> ni3(cgr, cp);
   2.178 +    check((tmp_n = ni3) == n1, "Wrong PathNodeIt");
   2.179 +    check((tmp_n = ++ni3) == n2, "Wrong PathNodeIt");
   2.180 +    check((tmp_n = ++ni3) == n3, "Wrong PathNodeIt");
   2.181 +    check((tmp_n = ++ni3) == n4, "Wrong PathNodeIt");
   2.182 +    check(++ni3 == INVALID, "Wrong PathNodeIt");
   2.183 +
   2.184 +    // Check arc removal and addition
   2.185 +    p.eraseBack();
   2.186 +    p.eraseBack();
   2.187 +    p.addBack(a2);
   2.188 +    check(!cp.empty(), "Wrong empty()");
   2.189 +    check(cp.length() == 2, "Wrong length");
   2.190 +    check(cp.front() == a1, "Wrong front()");
   2.191 +    check(cp.back() == a2, "Wrong back()");
   2.192 +    check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
   2.193 +    check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()");
   2.194 +    check(checkPath(cgr, cp), "Wrong checkPath()");
   2.195 +
   2.196 +    // Check clear()
   2.197 +    p.clear();
   2.198 +    check(cp.empty(), "The path is not empty");
   2.199 +    check(cp.length() == 0, "The path is not empty");
   2.200 +
   2.201 +    // Check inconsistent path
   2.202 +    p.addBack(a4);
   2.203 +    p.addBack(a2);
   2.204 +    p.addBack(a1);
   2.205 +    check(!cp.empty(), "Wrong empty()");
   2.206 +    check(cp.length() == 3, "Wrong length");
   2.207 +    check(cp.front() == a4, "Wrong front()");
   2.208 +    check(cp.back() == a1, "Wrong back()");
   2.209 +    check(pathSource(cgr, cp) == n4, "Wrong pathSource()");
   2.210 +    check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
   2.211 +    check(!checkPath(cgr, cp), "Wrong checkPath()");
   2.212 +  }
   2.213 +
   2.214 +  template <typename P>
   2.215 +  void checkBackAndFrontInsertablePath() {
   2.216 +
   2.217 +    // Include back insertable test cases
   2.218 +    checkBackInsertablePath<P>();
   2.219 +
   2.220 +    // Check front and back insertion
   2.221 +    P p;
   2.222 +    const P& cp = p;
   2.223 +    p.addFront(a4);
   2.224 +    p.addBack(a1);
   2.225 +    p.addFront(a3);
   2.226 +    check(!cp.empty(), "Wrong empty()");
   2.227 +    check(cp.length() == 3, "Wrong length");
   2.228 +    check(cp.front() == a3, "Wrong front()");
   2.229 +    check(cp.back() == a1, "Wrong back()");
   2.230 +    check(cp.nth(0) == a3, "Wrong nth()");
   2.231 +    check(cp.nth(1) == a4, "Wrong nth()");
   2.232 +    check(cp.nth(2) == a1, "Wrong nth()");
   2.233 +    typename P::ArcIt ai(cp);
   2.234 +    check((tmp_a = ai) == a3, "Wrong ArcIt");
   2.235 +    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
   2.236 +    check((tmp_a = ++ai) == a1, "Wrong nthIt()");
   2.237 +    check(++ai == INVALID, "Wrong nthIt()");
   2.238 +    ai = cp.nthIt(0);
   2.239 +    check((tmp_a = ai) == a3, "Wrong nthIt()");
   2.240 +    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
   2.241 +    ai = cp.nthIt(2);
   2.242 +    check((tmp_a = ai) == a1, "Wrong nthIt()");
   2.243 +    check(++ai == INVALID, "Wrong nthIt()");
   2.244 +    check(pathSource(cgr, cp) == n3, "Wrong pathSource()");
   2.245 +    check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
   2.246 +    check(checkPath(cgr, cp), "Wrong checkPath()");
   2.247 +
   2.248 +    // Check eraseFront()
   2.249 +    p.eraseFront();
   2.250 +    p.addBack(a2);
   2.251 +    check(!cp.empty(), "Wrong empty()");
   2.252 +    check(cp.length() == 3, "Wrong length");
   2.253 +    check(cp.front() == a4, "Wrong front()");
   2.254 +    check(cp.back() == a2, "Wrong back()");
   2.255 +    check(cp.nth(0) == a4, "Wrong nth()");
   2.256 +    check(cp.nth(1) == a1, "Wrong nth()");
   2.257 +    check(cp.nth(2) == a2, "Wrong nth()");
   2.258 +    typename P::ArcIt ai2(cp);
   2.259 +    check((tmp_a = ai2) == a4, "Wrong ArcIt");
   2.260 +    check((tmp_a = ++ai2) == a1, "Wrong nthIt()");
   2.261 +    check((tmp_a = ++ai2) == a2, "Wrong nthIt()");
   2.262 +    check(++ai2 == INVALID, "Wrong nthIt()");
   2.263 +    ai = cp.nthIt(0);
   2.264 +    check((tmp_a = ai) == a4, "Wrong nthIt()");
   2.265 +    check((tmp_a = ++ai) == a1, "Wrong nthIt()");
   2.266 +    ai = cp.nthIt(2);
   2.267 +    check((tmp_a = ai) == a2, "Wrong nthIt()");
   2.268 +    check(++ai == INVALID, "Wrong nthIt()");
   2.269 +    check(pathSource(cgr, cp) == n4, "Wrong pathSource()");
   2.270 +    check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()");
   2.271 +    check(checkPath(cgr, cp), "Wrong checkPath()");
   2.272 +  }
   2.273 +
   2.274 +  void checkListPathSplitAndSplice() {
   2.275 +
   2.276 +    // Build a path with spliceFront() and spliceBack()
   2.277 +    ListPath<GR> p1, p2, p3, p4;
   2.278 +    p1.addBack(a3);
   2.279 +    p1.addFront(a2);
   2.280 +    p2.addBack(a1);
   2.281 +    p1.spliceFront(p2);
   2.282 +    p3.addFront(a4);
   2.283 +    p1.spliceBack(p3);
   2.284 +    check(p1.length() == 4, "Wrong length");
   2.285 +    check(p1.front() == a1, "Wrong front()");
   2.286 +    check(p1.back() == a4, "Wrong back()");
   2.287 +    ListPath<GR>::ArcIt ai(p1);
   2.288 +    check((tmp_a = ai) == a1, "Wrong ArcIt");
   2.289 +    check((tmp_a = ++ai) == a2, "Wrong nthIt()");
   2.290 +    check((tmp_a = ++ai) == a3, "Wrong nthIt()");
   2.291 +    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
   2.292 +    check(++ai == INVALID, "Wrong nthIt()");
   2.293 +    check(checkPath(cgr, p1), "Wrong checkPath()");
   2.294 +
   2.295 +    // Check split()
   2.296 +    p1.split(p1.nthIt(2), p2);
   2.297 +    check(p1.length() == 2, "Wrong length");
   2.298 +    ai = p1.nthIt(0);
   2.299 +    check((tmp_a = ai) == a1, "Wrong ArcIt");
   2.300 +    check((tmp_a = ++ai) == a2, "Wrong nthIt()");
   2.301 +    check(++ai == INVALID, "Wrong nthIt()");
   2.302 +    check(checkPath(cgr, p1), "Wrong checkPath()");
   2.303 +    check(p2.length() == 2, "Wrong length");
   2.304 +    ai = p2.nthIt(0);
   2.305 +    check((tmp_a = ai) == a3, "Wrong ArcIt");
   2.306 +    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
   2.307 +    check(++ai == INVALID, "Wrong nthIt()");
   2.308 +    check(checkPath(cgr, p2), "Wrong checkPath()");
   2.309 +
   2.310 +    // Check split() and splice()
   2.311 +    p1.spliceFront(p2);
   2.312 +    p1.split(p1.nthIt(2), p2);
   2.313 +    p2.split(p2.nthIt(1), p3);
   2.314 +    p2.spliceBack(p1);
   2.315 +    p2.splice(p2.nthIt(1), p3);
   2.316 +    check(p2.length() == 4, "Wrong length");
   2.317 +    check(p2.front() == a1, "Wrong front()");
   2.318 +    check(p2.back() == a4, "Wrong back()");
   2.319 +    ai = p2.nthIt(0);
   2.320 +    check((tmp_a = ai) == a1, "Wrong ArcIt");
   2.321 +    check((tmp_a = ++ai) == a2, "Wrong nthIt()");
   2.322 +    check((tmp_a = ++ai) == a3, "Wrong nthIt()");
   2.323 +    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
   2.324 +    check(++ai == INVALID, "Wrong nthIt()");
   2.325 +    check(checkPath(cgr, p2), "Wrong checkPath()");
   2.326 +  }
   2.327 +
   2.328 +};
   2.329 +
   2.330  int main() {
   2.331 -  check_concepts();
   2.332 -
   2.333 -  checkCopy<Path<ListDigraph> >();
   2.334 -  checkCopy<SimplePath<ListDigraph> >();
   2.335 -  checkCopy<ListPath<ListDigraph> >();
   2.336 -
   2.337 -  ListDigraph g;
   2.338 -  ListDigraph::Arc a  = g.addArc(g.addNode(), g.addNode());
   2.339 -  
   2.340 -  Path<ListDigraph> p;
   2.341 -  StaticPath<ListDigraph> q,r;
   2.342 -  p.addBack(a);
   2.343 -  q=p;
   2.344 -  r=q;
   2.345 -  StaticPath<ListDigraph> s(q);
   2.346 +  checkPathConcepts();
   2.347 +  checkPathCopy();
   2.348 +  CheckPathFunctions cpf;
   2.349 +  cpf.run();
   2.350  
   2.351    return 0;
   2.352  }