test/path_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 09 Aug 2013 11:28:17 +0200
changeset 1270 dceba191c00d
parent 1212 15d7c5eadaca
child 1421 4fd76139b69e
permissions -rw-r--r--
Apply unify-sources.sh to the source tree
     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 
    31 using namespace std;
    32 using namespace lemon;
    33 
    34 template <typename GR>
    35 void 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
    44 void checkPathConcepts() {
    45   checkConcepts<concepts::Digraph>();
    46   checkConcepts<ListDigraph>();
    47 }
    48 
    49 // Check if proper copy consructor is called (use valgrind for testing)
    50 template <typename GR, typename P1, typename P2>
    51 void 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
    63 void 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
    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 
   332 int main() {
   333   checkPathConcepts();
   334   checkPathCopy();
   335   CheckPathFunctions cpf;
   336   cpf.run();
   337 
   338   return 0;
   339 }