test/heap_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 651 8c3112a66878
parent 293 47fbc814aa31
child 728 532697c9fa53
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@100
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@100
     4
 *
alpar@463
     5
 * Copyright (C) 2003-2009
alpar@100
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@100
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@100
     8
 *
alpar@100
     9
 * Permission to use, modify and distribute this software is granted
alpar@100
    10
 * provided that this copyright notice appears in all copies. For
alpar@100
    11
 * precise terms see the accompanying LICENSE file.
alpar@100
    12
 *
alpar@100
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@100
    14
 * express or implied, and with no claim as to its suitability for any
alpar@100
    15
 * purpose.
alpar@100
    16
 *
alpar@100
    17
 */
alpar@100
    18
alpar@100
    19
#include <iostream>
alpar@100
    20
#include <fstream>
alpar@100
    21
#include <string>
alpar@100
    22
#include <vector>
alpar@100
    23
alpar@100
    24
#include <lemon/concept_check.h>
alpar@100
    25
#include <lemon/concepts/heap.h>
alpar@100
    26
deba@203
    27
#include <lemon/smart_graph.h>
alpar@100
    28
deba@203
    29
#include <lemon/lgf_reader.h>
deba@203
    30
#include <lemon/dijkstra.h>
deba@203
    31
#include <lemon/maps.h>
alpar@100
    32
alpar@100
    33
#include <lemon/bin_heap.h>
alpar@100
    34
alpar@100
    35
#include "test_tools.h"
alpar@100
    36
alpar@100
    37
using namespace lemon;
alpar@100
    38
using namespace lemon::concepts;
alpar@100
    39
deba@203
    40
typedef ListDigraph Digraph;
deba@203
    41
DIGRAPH_TYPEDEFS(Digraph);
deba@203
    42
alpar@209
    43
char test_lgf[] =
alpar@209
    44
  "@nodes\n"
alpar@209
    45
  "label\n"
alpar@209
    46
  "0\n"
alpar@209
    47
  "1\n"
alpar@209
    48
  "2\n"
alpar@209
    49
  "3\n"
alpar@209
    50
  "4\n"
alpar@209
    51
  "5\n"
alpar@209
    52
  "6\n"
alpar@209
    53
  "7\n"
alpar@209
    54
  "8\n"
alpar@209
    55
  "9\n"
alpar@209
    56
  "@arcs\n"
kpeter@212
    57
  "                label   capacity\n"
kpeter@212
    58
  "0       5       0       94\n"
kpeter@212
    59
  "3       9       1       11\n"
kpeter@212
    60
  "8       7       2       83\n"
kpeter@212
    61
  "1       2       3       94\n"
kpeter@212
    62
  "5       7       4       35\n"
kpeter@212
    63
  "7       4       5       84\n"
kpeter@212
    64
  "9       5       6       38\n"
kpeter@212
    65
  "0       4       7       96\n"
kpeter@212
    66
  "6       7       8       6\n"
kpeter@212
    67
  "3       1       9       27\n"
kpeter@212
    68
  "5       2       10      77\n"
kpeter@212
    69
  "5       6       11      69\n"
kpeter@212
    70
  "6       5       12      41\n"
kpeter@212
    71
  "4       6       13      70\n"
kpeter@212
    72
  "3       2       14      45\n"
kpeter@212
    73
  "7       9       15      93\n"
kpeter@212
    74
  "5       9       16      50\n"
kpeter@212
    75
  "9       0       17      94\n"
kpeter@212
    76
  "9       6       18      67\n"
kpeter@212
    77
  "0       9       19      86\n"
alpar@209
    78
  "@attributes\n"
deba@203
    79
  "source 3\n";
deba@203
    80
deba@203
    81
int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26,  1,  9,  4, 34};
deba@203
    82
int test_inc[] = {20, 28, 34, 16,  0, 46, 44,  0, 42, 32, 14,  8,  6, 37};
deba@203
    83
deba@203
    84
int test_len = sizeof(test_seq) / sizeof(test_seq[0]);
deba@203
    85
deba@203
    86
template <typename Heap>
deba@203
    87
void heapSortTest() {
deba@203
    88
  RangeMap<int> map(test_len, -1);
deba@203
    89
deba@203
    90
  Heap heap(map);
alpar@209
    91
deba@203
    92
  std::vector<int> v(test_len);
deba@203
    93
deba@203
    94
  for (int i = 0; i < test_len; ++i) {
deba@203
    95
    v[i] = test_seq[i];
deba@203
    96
    heap.push(i, v[i]);
deba@203
    97
  }
deba@203
    98
  std::sort(v.begin(), v.end());
deba@203
    99
  for (int i = 0; i < test_len; ++i) {
deba@203
   100
    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
deba@203
   101
    heap.pop();
deba@203
   102
  }
deba@203
   103
}
deba@203
   104
deba@203
   105
template <typename Heap>
deba@203
   106
void heapIncreaseTest() {
deba@203
   107
  RangeMap<int> map(test_len, -1);
deba@203
   108
deba@203
   109
  Heap heap(map);
alpar@209
   110
deba@203
   111
  std::vector<int> v(test_len);
deba@203
   112
deba@203
   113
  for (int i = 0; i < test_len; ++i) {
deba@203
   114
    v[i] = test_seq[i];
deba@203
   115
    heap.push(i, v[i]);
deba@203
   116
  }
deba@203
   117
  for (int i = 0; i < test_len; ++i) {
deba@203
   118
    v[i] += test_inc[i];
deba@203
   119
    heap.increase(i, v[i]);
deba@203
   120
  }
deba@203
   121
  std::sort(v.begin(), v.end());
deba@203
   122
  for (int i = 0; i < test_len; ++i) {
deba@203
   123
    check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
deba@203
   124
    heap.pop();
deba@203
   125
  }
deba@203
   126
}
deba@203
   127
deba@203
   128
deba@203
   129
deba@203
   130
template <typename Heap>
alpar@209
   131
void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
alpar@209
   132
                      Node source) {
alpar@209
   133
kpeter@257
   134
  typename Dijkstra<Digraph, IntArcMap>::template SetStandardHeap<Heap>::
deba@203
   135
    Create dijkstra(digraph, length);
deba@203
   136
deba@203
   137
  dijkstra.run(source);
deba@203
   138
deba@203
   139
  for(ArcIt a(digraph); a != INVALID; ++a) {
alpar@209
   140
    Node s = digraph.source(a);
deba@203
   141
    Node t = digraph.target(a);
deba@203
   142
    if (dijkstra.reached(s)) {
deba@203
   143
      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
kpeter@212
   144
             "Error in a shortest path tree!");
deba@203
   145
    }
deba@203
   146
  }
deba@203
   147
deba@203
   148
  for(NodeIt n(digraph); n != INVALID; ++n) {
deba@203
   149
    if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
deba@203
   150
      Arc a = dijkstra.predArc(n);
deba@203
   151
      Node s = digraph.source(a);
deba@203
   152
      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
alpar@209
   153
             "Error in a shortest path tree!");
deba@203
   154
    }
deba@203
   155
  }
deba@203
   156
deba@203
   157
}
deba@203
   158
alpar@100
   159
int main() {
alpar@100
   160
alpar@100
   161
  typedef int Item;
alpar@100
   162
  typedef int Prio;
deba@203
   163
  typedef RangeMap<int> ItemIntMap;
alpar@209
   164
deba@203
   165
  Digraph digraph;
deba@203
   166
  IntArcMap length(digraph);
deba@203
   167
  Node source;
alpar@100
   168
deba@203
   169
  std::istringstream input(test_lgf);
kpeter@293
   170
  digraphReader(digraph, input).
deba@203
   171
    arcMap("capacity", length).
deba@203
   172
    node("source", source).
alpar@209
   173
    run();
alpar@209
   174
alpar@100
   175
  {
alpar@100
   176
    typedef BinHeap<Prio, ItemIntMap> IntHeap;
alpar@100
   177
    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
deba@203
   178
    heapSortTest<IntHeap>();
deba@203
   179
    heapIncreaseTest<IntHeap>();
alpar@209
   180
deba@203
   181
    typedef BinHeap<Prio, IntNodeMap > NodeHeap;
deba@203
   182
    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
deba@203
   183
    dijkstraHeapTest<NodeHeap>(digraph, length, source);
alpar@100
   184
  }
alpar@100
   185
alpar@100
   186
  return 0;
alpar@100
   187
}