test/dim_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 651 8c3112a66878
parent 253 dbe309b5e855
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
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@463
     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
}