test/path_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 08 Mar 2013 10:47:38 +0100
changeset 1212 15d7c5eadaca
parent 1144 7440937d154b
child 1270 dceba191c00d
permissions -rw-r--r--
Greatly extend path_test.cc + fix compiler warning (#408)
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@96
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@96
     4
 *
alpar@463
     5
 * Copyright (C) 2003-2009
alpar@96
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@96
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@96
     8
 *
alpar@96
     9
 * Permission to use, modify and distribute this software is granted
alpar@96
    10
 * provided that this copyright notice appears in all copies. For
alpar@96
    11
 * precise terms see the accompanying LICENSE file.
alpar@96
    12
 *
alpar@96
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@96
    14
 * express or implied, and with no claim as to its suitability for any
alpar@96
    15
 * purpose.
alpar@96
    16
 *
alpar@96
    17
 */
alpar@96
    18
alpar@96
    19
#include <string>
alpar@96
    20
#include <iostream>
alpar@96
    21
alpar@96
    22
#include <lemon/concepts/path.h>
alpar@96
    23
#include <lemon/concepts/digraph.h>
kpeter@1212
    24
#include <lemon/concept_check.h>
alpar@96
    25
alpar@96
    26
#include <lemon/path.h>
alpar@96
    27
#include <lemon/list_graph.h>
alpar@96
    28
alpar@96
    29
#include "test_tools.h"
alpar@96
    30
alpar@96
    31
using namespace std;
alpar@96
    32
using namespace lemon;
alpar@96
    33
kpeter@1212
    34
template <typename GR>
kpeter@1212
    35
void checkConcepts() {
kpeter@1212
    36
  checkConcept<concepts::Path<GR>, concepts::Path<GR> >();
kpeter@1212
    37
  checkConcept<concepts::Path<GR>, Path<GR> >();
kpeter@1212
    38
  checkConcept<concepts::Path<GR>, SimplePath<GR> >();
kpeter@1212
    39
  checkConcept<concepts::Path<GR>, StaticPath<GR> >();
kpeter@1212
    40
  checkConcept<concepts::Path<GR>, ListPath<GR> >();
kpeter@1212
    41
}
kpeter@1212
    42
kpeter@1212
    43
// Conecpt checking for path structures
kpeter@1212
    44
void checkPathConcepts() {
kpeter@1212
    45
  checkConcepts<concepts::Digraph>();
kpeter@1212
    46
  checkConcepts<ListDigraph>();
alpar@96
    47
}
alpar@96
    48
alpar@1144
    49
// Check if proper copy consructor is called (use valgrind for testing)
kpeter@1212
    50
template <typename GR, typename P1, typename P2>
kpeter@1212
    51
void checkCopy(typename GR::Arc a) {
kpeter@1212
    52
  P1 p;
kpeter@1212
    53
  p.addBack(a);
kpeter@1212
    54
  P1 q;
kpeter@1212
    55
  q = p;
kpeter@1212
    56
  P1 r(p);
kpeter@1212
    57
  P2 q2;
kpeter@1212
    58
  q2 = p;
kpeter@1212
    59
  P2 r2(p);
kpeter@1212
    60
}
kpeter@1212
    61
kpeter@1212
    62
// Tests for copy constructors and assignment operators of paths
kpeter@1212
    63
void checkPathCopy() {
alpar@1144
    64
  ListDigraph g;
kpeter@1212
    65
  ListDigraph::Arc a = g.addArc(g.addNode(), g.addNode());
kpeter@1212
    66
kpeter@1212
    67
  typedef Path<ListDigraph> Path1;
kpeter@1212
    68
  typedef SimplePath<ListDigraph> Path2;
kpeter@1212
    69
  typedef ListPath<ListDigraph> Path3;
kpeter@1212
    70
  typedef StaticPath<ListDigraph> Path4;
kpeter@1212
    71
  checkCopy<ListDigraph, Path1, Path2>(a);
kpeter@1212
    72
  checkCopy<ListDigraph, Path1, Path3>(a);
kpeter@1212
    73
  checkCopy<ListDigraph, Path1, Path4>(a);
kpeter@1212
    74
  checkCopy<ListDigraph, Path2, Path1>(a);
kpeter@1212
    75
  checkCopy<ListDigraph, Path2, Path3>(a);
kpeter@1212
    76
  checkCopy<ListDigraph, Path2, Path4>(a);
kpeter@1212
    77
  checkCopy<ListDigraph, Path3, Path1>(a);
kpeter@1212
    78
  checkCopy<ListDigraph, Path3, Path2>(a);
kpeter@1212
    79
  checkCopy<ListDigraph, Path3, Path4>(a);
alpar@1144
    80
}
kpeter@1212
    81
kpeter@1212
    82
// Class for testing path functions
kpeter@1212
    83
class CheckPathFunctions {
kpeter@1212
    84
  typedef ListDigraph GR;
kpeter@1212
    85
  DIGRAPH_TYPEDEFS(GR);
kpeter@1212
    86
  GR gr;
kpeter@1212
    87
  const GR& cgr;
kpeter@1212
    88
  Node n1, n2, n3, n4;
kpeter@1212
    89
  Node tmp_n;
kpeter@1212
    90
  Arc a1, a2, a3, a4;
kpeter@1212
    91
  Arc tmp_a;
kpeter@1212
    92
kpeter@1212
    93
public:
kpeter@1212
    94
kpeter@1212
    95
  CheckPathFunctions() : cgr(gr) {
kpeter@1212
    96
    n1 = gr.addNode();
kpeter@1212
    97
    n2 = gr.addNode();
kpeter@1212
    98
    n3 = gr.addNode();
kpeter@1212
    99
    n4 = gr.addNode();
kpeter@1212
   100
    a1 = gr.addArc(n1, n2);
kpeter@1212
   101
    a2 = gr.addArc(n2, n3);
kpeter@1212
   102
    a3 = gr.addArc(n3, n4);
kpeter@1212
   103
    a4 = gr.addArc(n4, n1);
kpeter@1212
   104
  }
kpeter@1212
   105
kpeter@1212
   106
  void run() {
kpeter@1212
   107
    checkBackAndFrontInsertablePath<Path<GR> >();
kpeter@1212
   108
    checkBackAndFrontInsertablePath<ListPath<GR> >();
kpeter@1212
   109
    checkBackInsertablePath<SimplePath<GR> >();
kpeter@1212
   110
kpeter@1212
   111
    checkListPathSplitAndSplice();
kpeter@1212
   112
  }
kpeter@1212
   113
kpeter@1212
   114
private:
kpeter@1212
   115
kpeter@1212
   116
  template <typename P>
kpeter@1212
   117
  void checkBackInsertablePath() {
kpeter@1212
   118
kpeter@1212
   119
    // Create and check empty path
kpeter@1212
   120
    P p;
kpeter@1212
   121
    const P& cp = p;
kpeter@1212
   122
    check(cp.empty(), "The path is not empty");
kpeter@1212
   123
    check(cp.length() == 0, "The path is not empty");
kpeter@1212
   124
//    check(cp.front() == INVALID, "Wrong front()");
kpeter@1212
   125
//    check(cp.back() == INVALID, "Wrong back()");
kpeter@1212
   126
    typename P::ArcIt ai(cp);
kpeter@1212
   127
    check(ai == INVALID, "Wrong ArcIt");
kpeter@1212
   128
    check(pathSource(cgr, cp) == INVALID, "Wrong pathSource()");
kpeter@1212
   129
    check(pathTarget(cgr, cp) == INVALID, "Wrong pathTarget()");
kpeter@1212
   130
    check(checkPath(cgr, cp), "Wrong checkPath()");
kpeter@1212
   131
    PathNodeIt<P> ni(cgr, cp);
kpeter@1212
   132
    check(ni == INVALID, "Wrong PathNodeIt");
kpeter@1212
   133
kpeter@1212
   134
    // Check single-arc path
kpeter@1212
   135
    p.addBack(a1);
kpeter@1212
   136
    check(!cp.empty(), "Wrong empty()");
kpeter@1212
   137
    check(cp.length() == 1, "Wrong length");
kpeter@1212
   138
    check(cp.front() == a1, "Wrong front()");
kpeter@1212
   139
    check(cp.back() == a1, "Wrong back()");
kpeter@1212
   140
    check(cp.nth(0) == a1, "Wrong nth()");
kpeter@1212
   141
    ai = cp.nthIt(0);
kpeter@1212
   142
    check((tmp_a = ai) == a1, "Wrong nthIt()");
kpeter@1212
   143
    check(++ai == INVALID, "Wrong nthIt()");
kpeter@1212
   144
    typename P::ArcIt ai2(cp);
kpeter@1212
   145
    check((tmp_a = ai2) == a1, "Wrong ArcIt");
kpeter@1212
   146
    check(++ai2 == INVALID, "Wrong ArcIt");
kpeter@1212
   147
    check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
kpeter@1212
   148
    check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
kpeter@1212
   149
    check(checkPath(cgr, cp), "Wrong checkPath()");
kpeter@1212
   150
    PathNodeIt<P> ni2(cgr, cp);
kpeter@1212
   151
    check((tmp_n = ni2) == n1, "Wrong PathNodeIt");
kpeter@1212
   152
    check((tmp_n = ++ni2) == n2, "Wrong PathNodeIt");
kpeter@1212
   153
    check(++ni2 == INVALID, "Wrong PathNodeIt");
kpeter@1212
   154
kpeter@1212
   155
    // Check adding more arcs
kpeter@1212
   156
    p.addBack(a2);
kpeter@1212
   157
    p.addBack(a3);
kpeter@1212
   158
    check(!cp.empty(), "Wrong empty()");
kpeter@1212
   159
    check(cp.length() == 3, "Wrong length");
kpeter@1212
   160
    check(cp.front() == a1, "Wrong front()");
kpeter@1212
   161
    check(cp.back() == a3, "Wrong back()");
kpeter@1212
   162
    check(cp.nth(0) == a1, "Wrong nth()");
kpeter@1212
   163
    check(cp.nth(1) == a2, "Wrong nth()");
kpeter@1212
   164
    check(cp.nth(2) == a3, "Wrong nth()");
kpeter@1212
   165
    typename P::ArcIt ai3(cp);
kpeter@1212
   166
    check((tmp_a = ai3) == a1, "Wrong ArcIt");
kpeter@1212
   167
    check((tmp_a = ++ai3) == a2, "Wrong nthIt()");
kpeter@1212
   168
    check((tmp_a = ++ai3) == a3, "Wrong nthIt()");
kpeter@1212
   169
    check(++ai3 == INVALID, "Wrong nthIt()");
kpeter@1212
   170
    ai = cp.nthIt(0);
kpeter@1212
   171
    check((tmp_a = ai) == a1, "Wrong nthIt()");
kpeter@1212
   172
    check((tmp_a = ++ai) == a2, "Wrong nthIt()");
kpeter@1212
   173
    ai = cp.nthIt(2);
kpeter@1212
   174
    check((tmp_a = ai) == a3, "Wrong nthIt()");
kpeter@1212
   175
    check(++ai == INVALID, "Wrong nthIt()");
kpeter@1212
   176
    check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
kpeter@1212
   177
    check(pathTarget(cgr, cp) == n4, "Wrong pathTarget()");
kpeter@1212
   178
    check(checkPath(cgr, cp), "Wrong checkPath()");
kpeter@1212
   179
    PathNodeIt<P> ni3(cgr, cp);
kpeter@1212
   180
    check((tmp_n = ni3) == n1, "Wrong PathNodeIt");
kpeter@1212
   181
    check((tmp_n = ++ni3) == n2, "Wrong PathNodeIt");
kpeter@1212
   182
    check((tmp_n = ++ni3) == n3, "Wrong PathNodeIt");
kpeter@1212
   183
    check((tmp_n = ++ni3) == n4, "Wrong PathNodeIt");
kpeter@1212
   184
    check(++ni3 == INVALID, "Wrong PathNodeIt");
kpeter@1212
   185
kpeter@1212
   186
    // Check arc removal and addition
kpeter@1212
   187
    p.eraseBack();
kpeter@1212
   188
    p.eraseBack();
kpeter@1212
   189
    p.addBack(a2);
kpeter@1212
   190
    check(!cp.empty(), "Wrong empty()");
kpeter@1212
   191
    check(cp.length() == 2, "Wrong length");
kpeter@1212
   192
    check(cp.front() == a1, "Wrong front()");
kpeter@1212
   193
    check(cp.back() == a2, "Wrong back()");
kpeter@1212
   194
    check(pathSource(cgr, cp) == n1, "Wrong pathSource()");
kpeter@1212
   195
    check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()");
kpeter@1212
   196
    check(checkPath(cgr, cp), "Wrong checkPath()");
kpeter@1212
   197
kpeter@1212
   198
    // Check clear()
kpeter@1212
   199
    p.clear();
kpeter@1212
   200
    check(cp.empty(), "The path is not empty");
kpeter@1212
   201
    check(cp.length() == 0, "The path is not empty");
kpeter@1212
   202
kpeter@1212
   203
    // Check inconsistent path
kpeter@1212
   204
    p.addBack(a4);
kpeter@1212
   205
    p.addBack(a2);
kpeter@1212
   206
    p.addBack(a1);
kpeter@1212
   207
    check(!cp.empty(), "Wrong empty()");
kpeter@1212
   208
    check(cp.length() == 3, "Wrong length");
kpeter@1212
   209
    check(cp.front() == a4, "Wrong front()");
kpeter@1212
   210
    check(cp.back() == a1, "Wrong back()");
kpeter@1212
   211
    check(pathSource(cgr, cp) == n4, "Wrong pathSource()");
kpeter@1212
   212
    check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
kpeter@1212
   213
    check(!checkPath(cgr, cp), "Wrong checkPath()");
kpeter@1212
   214
  }
kpeter@1212
   215
kpeter@1212
   216
  template <typename P>
kpeter@1212
   217
  void checkBackAndFrontInsertablePath() {
kpeter@1212
   218
kpeter@1212
   219
    // Include back insertable test cases
kpeter@1212
   220
    checkBackInsertablePath<P>();
kpeter@1212
   221
kpeter@1212
   222
    // Check front and back insertion
kpeter@1212
   223
    P p;
kpeter@1212
   224
    const P& cp = p;
kpeter@1212
   225
    p.addFront(a4);
kpeter@1212
   226
    p.addBack(a1);
kpeter@1212
   227
    p.addFront(a3);
kpeter@1212
   228
    check(!cp.empty(), "Wrong empty()");
kpeter@1212
   229
    check(cp.length() == 3, "Wrong length");
kpeter@1212
   230
    check(cp.front() == a3, "Wrong front()");
kpeter@1212
   231
    check(cp.back() == a1, "Wrong back()");
kpeter@1212
   232
    check(cp.nth(0) == a3, "Wrong nth()");
kpeter@1212
   233
    check(cp.nth(1) == a4, "Wrong nth()");
kpeter@1212
   234
    check(cp.nth(2) == a1, "Wrong nth()");
kpeter@1212
   235
    typename P::ArcIt ai(cp);
kpeter@1212
   236
    check((tmp_a = ai) == a3, "Wrong ArcIt");
kpeter@1212
   237
    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
kpeter@1212
   238
    check((tmp_a = ++ai) == a1, "Wrong nthIt()");
kpeter@1212
   239
    check(++ai == INVALID, "Wrong nthIt()");
kpeter@1212
   240
    ai = cp.nthIt(0);
kpeter@1212
   241
    check((tmp_a = ai) == a3, "Wrong nthIt()");
kpeter@1212
   242
    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
kpeter@1212
   243
    ai = cp.nthIt(2);
kpeter@1212
   244
    check((tmp_a = ai) == a1, "Wrong nthIt()");
kpeter@1212
   245
    check(++ai == INVALID, "Wrong nthIt()");
kpeter@1212
   246
    check(pathSource(cgr, cp) == n3, "Wrong pathSource()");
kpeter@1212
   247
    check(pathTarget(cgr, cp) == n2, "Wrong pathTarget()");
kpeter@1212
   248
    check(checkPath(cgr, cp), "Wrong checkPath()");
kpeter@1212
   249
kpeter@1212
   250
    // Check eraseFront()
kpeter@1212
   251
    p.eraseFront();
kpeter@1212
   252
    p.addBack(a2);
kpeter@1212
   253
    check(!cp.empty(), "Wrong empty()");
kpeter@1212
   254
    check(cp.length() == 3, "Wrong length");
kpeter@1212
   255
    check(cp.front() == a4, "Wrong front()");
kpeter@1212
   256
    check(cp.back() == a2, "Wrong back()");
kpeter@1212
   257
    check(cp.nth(0) == a4, "Wrong nth()");
kpeter@1212
   258
    check(cp.nth(1) == a1, "Wrong nth()");
kpeter@1212
   259
    check(cp.nth(2) == a2, "Wrong nth()");
kpeter@1212
   260
    typename P::ArcIt ai2(cp);
kpeter@1212
   261
    check((tmp_a = ai2) == a4, "Wrong ArcIt");
kpeter@1212
   262
    check((tmp_a = ++ai2) == a1, "Wrong nthIt()");
kpeter@1212
   263
    check((tmp_a = ++ai2) == a2, "Wrong nthIt()");
kpeter@1212
   264
    check(++ai2 == INVALID, "Wrong nthIt()");
kpeter@1212
   265
    ai = cp.nthIt(0);
kpeter@1212
   266
    check((tmp_a = ai) == a4, "Wrong nthIt()");
kpeter@1212
   267
    check((tmp_a = ++ai) == a1, "Wrong nthIt()");
kpeter@1212
   268
    ai = cp.nthIt(2);
kpeter@1212
   269
    check((tmp_a = ai) == a2, "Wrong nthIt()");
kpeter@1212
   270
    check(++ai == INVALID, "Wrong nthIt()");
kpeter@1212
   271
    check(pathSource(cgr, cp) == n4, "Wrong pathSource()");
kpeter@1212
   272
    check(pathTarget(cgr, cp) == n3, "Wrong pathTarget()");
kpeter@1212
   273
    check(checkPath(cgr, cp), "Wrong checkPath()");
kpeter@1212
   274
  }
kpeter@1212
   275
kpeter@1212
   276
  void checkListPathSplitAndSplice() {
kpeter@1212
   277
kpeter@1212
   278
    // Build a path with spliceFront() and spliceBack()
kpeter@1212
   279
    ListPath<GR> p1, p2, p3, p4;
kpeter@1212
   280
    p1.addBack(a3);
kpeter@1212
   281
    p1.addFront(a2);
kpeter@1212
   282
    p2.addBack(a1);
kpeter@1212
   283
    p1.spliceFront(p2);
kpeter@1212
   284
    p3.addFront(a4);
kpeter@1212
   285
    p1.spliceBack(p3);
kpeter@1212
   286
    check(p1.length() == 4, "Wrong length");
kpeter@1212
   287
    check(p1.front() == a1, "Wrong front()");
kpeter@1212
   288
    check(p1.back() == a4, "Wrong back()");
kpeter@1212
   289
    ListPath<GR>::ArcIt ai(p1);
kpeter@1212
   290
    check((tmp_a = ai) == a1, "Wrong ArcIt");
kpeter@1212
   291
    check((tmp_a = ++ai) == a2, "Wrong nthIt()");
kpeter@1212
   292
    check((tmp_a = ++ai) == a3, "Wrong nthIt()");
kpeter@1212
   293
    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
kpeter@1212
   294
    check(++ai == INVALID, "Wrong nthIt()");
kpeter@1212
   295
    check(checkPath(cgr, p1), "Wrong checkPath()");
kpeter@1212
   296
kpeter@1212
   297
    // Check split()
kpeter@1212
   298
    p1.split(p1.nthIt(2), p2);
kpeter@1212
   299
    check(p1.length() == 2, "Wrong length");
kpeter@1212
   300
    ai = p1.nthIt(0);
kpeter@1212
   301
    check((tmp_a = ai) == a1, "Wrong ArcIt");
kpeter@1212
   302
    check((tmp_a = ++ai) == a2, "Wrong nthIt()");
kpeter@1212
   303
    check(++ai == INVALID, "Wrong nthIt()");
kpeter@1212
   304
    check(checkPath(cgr, p1), "Wrong checkPath()");
kpeter@1212
   305
    check(p2.length() == 2, "Wrong length");
kpeter@1212
   306
    ai = p2.nthIt(0);
kpeter@1212
   307
    check((tmp_a = ai) == a3, "Wrong ArcIt");
kpeter@1212
   308
    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
kpeter@1212
   309
    check(++ai == INVALID, "Wrong nthIt()");
kpeter@1212
   310
    check(checkPath(cgr, p2), "Wrong checkPath()");
kpeter@1212
   311
kpeter@1212
   312
    // Check split() and splice()
kpeter@1212
   313
    p1.spliceFront(p2);
kpeter@1212
   314
    p1.split(p1.nthIt(2), p2);
kpeter@1212
   315
    p2.split(p2.nthIt(1), p3);
kpeter@1212
   316
    p2.spliceBack(p1);
kpeter@1212
   317
    p2.splice(p2.nthIt(1), p3);
kpeter@1212
   318
    check(p2.length() == 4, "Wrong length");
kpeter@1212
   319
    check(p2.front() == a1, "Wrong front()");
kpeter@1212
   320
    check(p2.back() == a4, "Wrong back()");
kpeter@1212
   321
    ai = p2.nthIt(0);
kpeter@1212
   322
    check((tmp_a = ai) == a1, "Wrong ArcIt");
kpeter@1212
   323
    check((tmp_a = ++ai) == a2, "Wrong nthIt()");
kpeter@1212
   324
    check((tmp_a = ++ai) == a3, "Wrong nthIt()");
kpeter@1212
   325
    check((tmp_a = ++ai) == a4, "Wrong nthIt()");
kpeter@1212
   326
    check(++ai == INVALID, "Wrong nthIt()");
kpeter@1212
   327
    check(checkPath(cgr, p2), "Wrong checkPath()");
kpeter@1212
   328
  }
kpeter@1212
   329
kpeter@1212
   330
};
kpeter@1212
   331
alpar@96
   332
int main() {
kpeter@1212
   333
  checkPathConcepts();
kpeter@1212
   334
  checkPathCopy();
kpeter@1212
   335
  CheckPathFunctions cpf;
kpeter@1212
   336
  cpf.run();
alpar@1144
   337
alpar@96
   338
  return 0;
alpar@96
   339
}