test/path_test.cc
changeset 1076 38c432e01489
parent 990 7440937d154b
child 1092 dceba191c00d
equal deleted inserted replaced
3:8d9bff0afcbd 4:98232257798f
    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 }