test/counter_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 609 e6927fe719e6
parent 209 765619b7cbb2
child 558 f53d641aa967
permissions -rw-r--r--
Support >= and <= constraints in NetworkSimplex (#219, #234)

By default the same inequality constraints are supported as by
Circulation (the GEQ form), but the LEQ form can also be selected
using the problemType() function.

The documentation of the min. cost flow module is reworked and
extended with important notes and explanations about the different
variants of the problem and about the dual solution and optimality
conditions.
     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-2009
     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  */
    18 
    19 #include <lemon/counter.h>
    20 #include <vector>
    21 
    22 using namespace lemon;
    23 
    24 template <typename T>
    25 void bubbleSort(std::vector<T>& v) {
    26   Counter op("Bubble Sort - Operations: ");
    27   Counter::NoSubCounter as(op, "Assignments: ");
    28   Counter::NoSubCounter co(op, "Comparisons: ");
    29   for (int i = v.size()-1; i > 0; --i) {
    30     for (int j = 0; j < i; ++j) {
    31       if (v[j] > v[j+1]) {
    32         T tmp = v[j];
    33         v[j] = v[j+1];
    34         v[j+1] = tmp;
    35         as += 3;
    36       }
    37       ++co;
    38     }
    39   }
    40 }
    41 
    42 template <typename T>
    43 void insertionSort(std::vector<T>& v) {
    44   Counter op("Insertion Sort - Operations: ");
    45   Counter::NoSubCounter as(op, "Assignments: ");
    46   Counter::NoSubCounter co(op, "Comparisons: ");
    47   for (int i = 1; i < int(v.size()); ++i) {
    48     T value = v[i];
    49     ++as;
    50     int j = i;
    51     while (j > 0 && v[j-1] > value) {
    52       v[j] = v[j-1];
    53       --j;
    54       ++co; ++as;
    55     }
    56     v[j] = value;
    57     ++as;
    58   }
    59 }
    60 
    61 template <typename MyCounter>
    62 void counterTest() {
    63   MyCounter c("Main Counter: ");
    64   c++;
    65   typename MyCounter::SubCounter d(c, "SubCounter: ");
    66   d++;
    67   typename MyCounter::SubCounter::NoSubCounter e(d, "SubSubCounter: ");
    68   e++;
    69   d+=3;
    70   c-=4;
    71   e-=2;
    72   c.reset(2);
    73   c.reset();
    74 }
    75 
    76 void init(std::vector<int>& v) {
    77   v[0] = 10; v[1] = 60; v[2] = 20; v[3] = 90; v[4] = 100;
    78   v[5] = 80; v[6] = 40; v[7] = 30; v[8] = 50; v[9] = 70;
    79 }
    80 
    81 int main()
    82 {
    83   counterTest<Counter>();
    84   counterTest<NoCounter>();
    85 
    86   std::vector<int> x(10);
    87   init(x); bubbleSort(x);
    88   init(x); insertionSort(x);
    89 
    90   return 0;
    91 }