test/dim_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 12 Nov 2009 23:26:13 +0100
changeset 806 fa6f37d7a25b
parent 253 dbe309b5e855
permissions -rw-r--r--
Entirely rework CapacityScaling (#180)

- Use the new interface similarly to NetworkSimplex.
- Rework the implementation using an efficient internal structure
for handling the residual network. This improvement made the
code much faster (up to 2-5 times faster on large graphs).
- Handle GEQ supply type (LEQ is not supported).
- Handle negative costs for arcs of finite capacity.
(Note that this algorithm cannot handle arcs of negative cost
and infinite upper bound, thus it returns UNBOUNDED if such
an arc exists.)
- Extend the documentation.
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@8
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@8
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
alpar@8
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@8
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@8
     8
 *
alpar@8
     9
 * Permission to use, modify and distribute this software is granted
alpar@8
    10
 * provided that this copyright notice appears in all copies. For
alpar@8
    11
 * precise terms see the accompanying LICENSE file.
alpar@8
    12
 *
alpar@8
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@8
    14
 * express or implied, and with no claim as to its suitability for any
alpar@8
    15
 * purpose.
alpar@8
    16
 *
alpar@8
    17
 */
alpar@8
    18
alpar@8
    19
#include <lemon/dim2.h>
alpar@8
    20
#include <iostream>
alpar@8
    21
#include "test_tools.h"
alpar@8
    22
alpar@8
    23
using namespace std;
alpar@8
    24
using namespace lemon;
kpeter@14
    25
alpar@8
    26
int main()
alpar@8
    27
{
alpar@8
    28
  typedef dim2::Point<int> Point;
kpeter@14
    29
kpeter@14
    30
  Point p;
kpeter@171
    31
  check(p.size()==2, "Wrong dim2::Point initialization.");
alpar@8
    32
alpar@8
    33
  Point a(1,2);
alpar@8
    34
  Point b(3,4);
kpeter@171
    35
  check(a[0]==1 && a[1]==2, "Wrong dim2::Point initialization.");
alpar@8
    36
kpeter@14
    37
  p = a+b;
kpeter@171
    38
  check(p.x==4 && p.y==6, "Wrong dim2::Point addition.");
alpar@8
    39
kpeter@14
    40
  p = a-b;
kpeter@171
    41
  check(p.x==-2 && p.y==-2, "Wrong dim2::Point subtraction.");
alpar@8
    42
kpeter@171
    43
  check(a.normSquare()==5,"Wrong dim2::Point norm calculation.");
kpeter@171
    44
  check(a*b==11, "Wrong dim2::Point scalar product.");
alpar@8
    45
alpar@8
    46
  int l=2;
kpeter@14
    47
  p = a*l;
kpeter@171
    48
  check(p.x==2 && p.y==4, "Wrong dim2::Point multiplication by a scalar.");
alpar@8
    49
kpeter@14
    50
  p = b/l;
kpeter@171
    51
  check(p.x==1 && p.y==2, "Wrong dim2::Point division by a scalar.");
alpar@8
    52
kpeter@253
    53
  typedef dim2::Box<int> Box;
kpeter@253
    54
  Box box1;
kpeter@253
    55
  check(box1.empty(), "Wrong empty() in dim2::Box.");
alpar@8
    56
kpeter@14
    57
  box1.add(a);
kpeter@253
    58
  check(!box1.empty(), "Wrong empty() in dim2::Box.");
kpeter@14
    59
  box1.add(b);
alpar@8
    60
kpeter@242
    61
  check(box1.left()==1 && box1.bottom()==2 &&
kpeter@242
    62
        box1.right()==3 && box1.top()==4,
kpeter@253
    63
        "Wrong addition of points to dim2::Box.");
alpar@8
    64
kpeter@253
    65
  check(box1.inside(Point(2,3)), "Wrong inside() in dim2::Box.");
kpeter@253
    66
  check(box1.inside(Point(1,3)), "Wrong inside() in dim2::Box.");
kpeter@253
    67
  check(!box1.inside(Point(0,3)), "Wrong inside() in dim2::Box.");
alpar@8
    68
kpeter@253
    69
  Box box2(Point(2,2));
kpeter@253
    70
  check(!box2.empty(), "Wrong empty() in dim2::Box.");
kpeter@253
    71
kpeter@242
    72
  box2.bottomLeft(Point(2,0));
kpeter@242
    73
  box2.topRight(Point(5,3));
kpeter@253
    74
  Box box3 = box1 & box2;
kpeter@242
    75
  check(!box3.empty() &&
kpeter@253
    76
        box3.left()==2 && box3.bottom()==2 &&
kpeter@242
    77
        box3.right()==3 && box3.top()==3,
kpeter@253
    78
        "Wrong intersection of two dim2::Box objects.");
kpeter@253
    79
kpeter@242
    80
  box1.add(box2);
kpeter@242
    81
  check(!box1.empty() &&
kpeter@242
    82
        box1.left()==1 && box1.bottom()==0 &&
kpeter@242
    83
        box1.right()==5 && box1.top()==4,
kpeter@253
    84
        "Wrong addition of two dim2::Box objects.");
kpeter@14
    85
kpeter@14
    86
  return 0;
alpar@8
    87
}