test/heap_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 02 Sep 2008 10:23:23 +0100
changeset 255 914c5432be97
parent 209 765619b7cbb2
child 257 8d76a7bf9961
permissions -rw-r--r--
Merge
     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-2008
     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 <iostream>
    20 #include <fstream>
    21 #include <string>
    22 #include <vector>
    23 
    24 #include <lemon/concept_check.h>
    25 #include <lemon/concepts/heap.h>
    26 
    27 #include <lemon/smart_graph.h>
    28 
    29 #include <lemon/lgf_reader.h>
    30 #include <lemon/dijkstra.h>
    31 #include <lemon/maps.h>
    32 
    33 #include <lemon/bin_heap.h>
    34 
    35 #include "test_tools.h"
    36 
    37 using namespace lemon;
    38 using namespace lemon::concepts;
    39 
    40 typedef ListDigraph Digraph;
    41 DIGRAPH_TYPEDEFS(Digraph);
    42 
    43 char test_lgf[] =
    44   "@nodes\n"
    45   "label\n"
    46   "0\n"
    47   "1\n"
    48   "2\n"
    49   "3\n"
    50   "4\n"
    51   "5\n"
    52   "6\n"
    53   "7\n"
    54   "8\n"
    55   "9\n"
    56   "@arcs\n"
    57   "                label   capacity\n"
    58   "0       5       0       94\n"
    59   "3       9       1       11\n"
    60   "8       7       2       83\n"
    61   "1       2       3       94\n"
    62   "5       7       4       35\n"
    63   "7       4       5       84\n"
    64   "9       5       6       38\n"
    65   "0       4       7       96\n"
    66   "6       7       8       6\n"
    67   "3       1       9       27\n"
    68   "5       2       10      77\n"
    69   "5       6       11      69\n"
    70   "6       5       12      41\n"
    71   "4       6       13      70\n"
    72   "3       2       14      45\n"
    73   "7       9       15      93\n"
    74   "5       9       16      50\n"
    75   "9       0       17      94\n"
    76   "9       6       18      67\n"
    77   "0       9       19      86\n"
    78   "@attributes\n"
    79   "source 3\n";
    80 
    81 int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26,  1,  9,  4, 34};
    82 int test_inc[] = {20, 28, 34, 16,  0, 46, 44,  0, 42, 32, 14,  8,  6, 37};
    83 
    84 int test_len = sizeof(test_seq) / sizeof(test_seq[0]);
    85 
    86 template <typename Heap>
    87 void heapSortTest() {
    88   RangeMap<int> map(test_len, -1);
    89 
    90   Heap heap(map);
    91 
    92   std::vector<int> v(test_len);
    93 
    94   for (int i = 0; i < test_len; ++i) {
    95     v[i] = test_seq[i];
    96     heap.push(i, v[i]);
    97   }
    98   std::sort(v.begin(), v.end());
    99   for (int i = 0; i < test_len; ++i) {
   100     check(v[i] == heap.prio() ,"Wrong order in heap sort.");
   101     heap.pop();
   102   }
   103 }
   104 
   105 template <typename Heap>
   106 void heapIncreaseTest() {
   107   RangeMap<int> map(test_len, -1);
   108 
   109   Heap heap(map);
   110 
   111   std::vector<int> v(test_len);
   112 
   113   for (int i = 0; i < test_len; ++i) {
   114     v[i] = test_seq[i];
   115     heap.push(i, v[i]);
   116   }
   117   for (int i = 0; i < test_len; ++i) {
   118     v[i] += test_inc[i];
   119     heap.increase(i, v[i]);
   120   }
   121   std::sort(v.begin(), v.end());
   122   for (int i = 0; i < test_len; ++i) {
   123     check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
   124     heap.pop();
   125   }
   126 }
   127 
   128 
   129 
   130 template <typename Heap>
   131 void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
   132                       Node source) {
   133 
   134   typename Dijkstra<Digraph, IntArcMap>::template DefStandardHeap<Heap>::
   135     Create dijkstra(digraph, length);
   136 
   137   dijkstra.run(source);
   138 
   139   for(ArcIt a(digraph); a != INVALID; ++a) {
   140     Node s = digraph.source(a);
   141     Node t = digraph.target(a);
   142     if (dijkstra.reached(s)) {
   143       check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
   144              "Error in a shortest path tree!");
   145     }
   146   }
   147 
   148   for(NodeIt n(digraph); n != INVALID; ++n) {
   149     if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
   150       Arc a = dijkstra.predArc(n);
   151       Node s = digraph.source(a);
   152       check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
   153              "Error in a shortest path tree!");
   154     }
   155   }
   156 
   157 }
   158 
   159 int main() {
   160 
   161   typedef int Item;
   162   typedef int Prio;
   163   typedef RangeMap<int> ItemIntMap;
   164 
   165   Digraph digraph;
   166   IntArcMap length(digraph);
   167   Node source;
   168 
   169   std::istringstream input(test_lgf);
   170   digraphReader(input, digraph).
   171     arcMap("capacity", length).
   172     node("source", source).
   173     run();
   174 
   175   {
   176     typedef BinHeap<Prio, ItemIntMap> IntHeap;
   177     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   178     heapSortTest<IntHeap>();
   179     heapIncreaseTest<IntHeap>();
   180 
   181     typedef BinHeap<Prio, IntNodeMap > NodeHeap;
   182     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
   183     dijkstraHeapTest<NodeHeap>(digraph, length, source);
   184   }
   185 
   186   return 0;
   187 }