lemon-main: test/path_test.cc@c6aa2cc1af04

     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  */

    19 #include <string>

    20 #include <iostream>

    22 #include <lemon/concepts/path.h>

    23 #include <lemon/concepts/digraph.h>

    24 #include <lemon/concept_check.h>

    26 #include <lemon/path.h>

    27 #include <lemon/list_graph.h>

    29 #include "test_tools.h"

    31 using namespace std;

    32 using namespace lemon;

    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 }

    43 // Conecpt checking for path structures

    44 void checkPathConcepts() {

    45   checkConcepts<concepts::Digraph>();

    46   checkConcepts<ListDigraph>();

    47 }

    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 }

    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());

    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 }

    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;

    93 public:

    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   }

   106   void run() {

   107     checkBackAndFrontInsertablePath<Path<GR> >();

   108     checkBackAndFrontInsertablePath<ListPath<GR> >();

   109     checkBackInsertablePath<SimplePath<GR> >();

   111     checkSubscriptOperator<Path<GR> >();

   112     checkSubscriptOperator<SimplePath<GR> >();

   113     checkSubscriptOperator<StaticPath<GR> >();

   114     checkSubscriptOperator<ListPath<GR> >();

   116     checkListPathSplitAndSplice();

   117   }

   119 private:

   121   template <typename P>

   122   void checkBackInsertablePath() {

   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");

   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");

   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");

   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()");

   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");

   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   }

   221   template <typename P>

   222   void checkBackAndFrontInsertablePath() {

   224     // Include back insertable test cases

   225     checkBackInsertablePath<P>();

   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()");

   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   }

   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   }

   300   void checkListPathSplitAndSplice() {

   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()");

   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()");

   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   }

   354 };

   356 int main() {

   357   checkPathConcepts();

   358   checkPathCopy();

   359   CheckPathFunctions cpf;

   360   cpf.run();

   362   return 0;

   363 }

author	Balazs Dezso <deba@google.com>
	Fri, 22 Jan 2021 10:55:32 +0100
changeset 1208	c6aa2cc1af04
parent 1092	dceba191c00d
permissions	-rw-r--r--