Mercuriallemon / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/heap_test.cc
changeset 216 6d7bfcf5b48e
parent 203 215bfc30b14f
child 212 1ae84dea7d09
equal deleted inserted replaced
2:7088136d4be2 3:8e576f772481 
     1 /* -*- C++ -*-
 
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
 
     2  *
 
     2  *
 
     3  * This file is a part of LEMON, a generic C++ optimization library
 
     3  * This file is a part of LEMON, a generic C++ optimization library.
 
     4  *
 
     4  *
 
     5  * Copyright (C) 2003-2008
 
     5  * Copyright (C) 2003-2008
 
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
 
     8  *
 
     8  *
 
    38 using namespace lemon::concepts;
 
    38 using namespace lemon::concepts;
 
    39 
    39 
    40 typedef ListDigraph Digraph;
 
    40 typedef ListDigraph Digraph;
 
    41 DIGRAPH_TYPEDEFS(Digraph);
 
    41 DIGRAPH_TYPEDEFS(Digraph);
 
    42 
    42 
    43 char test_lgf[] = 
    43 char test_lgf[] =
 
    44   "@nodes\n" 
    44   "@nodes\n"
 
    45   "label\n"	
    45   "label\n"
 
    46   "0\n"	
    46   "0\n"
 
    47   "1\n"	
    47   "1\n"
 
    48   "2\n"	
    48   "2\n"
 
    49   "3\n"	
    49   "3\n"
 
    50   "4\n"	
    50   "4\n"
 
    51   "5\n"	
    51   "5\n"
 
    52   "6\n"	
    52   "6\n"
 
    53   "7\n"	
    53   "7\n"
 
    54   "8\n"	
    54   "8\n"
 
    55   "9\n"	
    55   "9\n"
 
    56   "@arcs\n" 
    56   "@arcs\n"
 
    57   "		label	capacity\n"	
    57   "                label        capacity\n"
 
    58   "0	5	0	94\n"	
    58   "0        5        0        94\n"
 
    59   "3	9	1	11\n"	
    59   "3        9        1        11\n"
 
    60   "8	7	2	83\n"	
    60   "8        7        2        83\n"
 
    61   "1	2	3	94\n"	
    61   "1        2        3        94\n"
 
    62   "5	7	4	35\n"	
    62   "5        7        4        35\n"
 
    63   "7	4	5	84\n"	
    63   "7        4        5        84\n"
 
    64   "9	5	6	38\n"	
    64   "9        5        6        38\n"
 
    65   "0	4	7	96\n"	
    65   "0        4        7        96\n"
 
    66   "6	7	8	6\n"	
    66   "6        7        8        6\n"
 
    67   "3	1	9	27\n"	
    67   "3        1        9        27\n"
 
    68   "5	2	10	77\n"	
    68   "5        2        10        77\n"
 
    69   "5	6	11	69\n"	
    69   "5        6        11        69\n"
 
    70   "6	5	12	41\n"	
    70   "6        5        12        41\n"
 
    71   "4	6	13	70\n"	
    71   "4        6        13        70\n"
 
    72   "3	2	14	45\n"	
    72   "3        2        14        45\n"
 
    73   "7	9	15	93\n"	
    73   "7        9        15        93\n"
 
    74   "5	9	16	50\n"	
    74   "5        9        16        50\n"
 
    75   "9	0	17	94\n"	
    75   "9        0        17        94\n"
 
    76   "9	6	18	67\n"	
    76   "9        6        18        67\n"
 
    77   "0	9	19	86\n"	
    77   "0        9        19        86\n"
 
    78   "@attributes\n" 
    78   "@attributes\n"
 
    79   "source 3\n";
 
    79   "source 3\n";
 
    80 
    80 
    81 int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26,  1,  9,  4, 34};
 
    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};
 
    82 int test_inc[] = {20, 28, 34, 16,  0, 46, 44,  0, 42, 32, 14,  8,  6, 37};
 
    83 
    83 
    86 template <typename Heap>
 
    86 template <typename Heap>
 
    87 void heapSortTest() {
 
    87 void heapSortTest() {
 
    88   RangeMap<int> map(test_len, -1);
 
    88   RangeMap<int> map(test_len, -1);
 
    89 
    89 
    90   Heap heap(map);
 
    90   Heap heap(map);
 
    91   
    91 
    92   std::vector<int> v(test_len);
 
    92   std::vector<int> v(test_len);
 
    93 
    93 
    94   for (int i = 0; i < test_len; ++i) {
 
    94   for (int i = 0; i < test_len; ++i) {
 
    95     v[i] = test_seq[i];
 
    95     v[i] = test_seq[i];
 
    96     heap.push(i, v[i]);
 
    96     heap.push(i, v[i]);
 
   105 template <typename Heap>
 
   105 template <typename Heap>
 
   106 void heapIncreaseTest() {
 
   106 void heapIncreaseTest() {
 
   107   RangeMap<int> map(test_len, -1);
 
   107   RangeMap<int> map(test_len, -1);
 
   108 
   108 
   109   Heap heap(map);
 
   109   Heap heap(map);
 
   110   
   110 
   111   std::vector<int> v(test_len);
 
   111   std::vector<int> v(test_len);
 
   112 
   112 
   113   for (int i = 0; i < test_len; ++i) {
 
   113   for (int i = 0; i < test_len; ++i) {
 
   114     v[i] = test_seq[i];
 
   114     v[i] = test_seq[i];
 
   115     heap.push(i, v[i]);
 
   115     heap.push(i, v[i]);
 
   126 }
 
   126 }
 
   127 
   127 
   128 
   128 
   129 
   129 
   130 template <typename Heap>
 
   130 template <typename Heap>
 
   131 void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length, 
   131 void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
 
   132 		      Node source) {
 
   132                       Node source) {
 
   133   
   133 
   134   typename Dijkstra<Digraph, IntArcMap>::template DefStandardHeap<Heap>::
 
   134   typename Dijkstra<Digraph, IntArcMap>::template DefStandardHeap<Heap>::
 
   135     Create dijkstra(digraph, length);
 
   135     Create dijkstra(digraph, length);
 
   136 
   136 
   137   dijkstra.run(source);
 
   137   dijkstra.run(source);
 
   138 
   138 
   139   for(ArcIt a(digraph); a != INVALID; ++a) {
 
   139   for(ArcIt a(digraph); a != INVALID; ++a) {
 
   140     Node s = digraph.source(a); 
   140     Node s = digraph.source(a);
 
   141     Node t = digraph.target(a);
 
   141     Node t = digraph.target(a);
 
   142     if (dijkstra.reached(s)) {
 
   142     if (dijkstra.reached(s)) {
 
   143       check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
 
   143       check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
 
   144       	     "Error in a shortest path tree!");
 
   144                    "Error in a shortest path tree!");
 
   145     }
 
   145     }
 
   146   }
 
   146   }
 
   147 
   147 
   148   for(NodeIt n(digraph); n != INVALID; ++n) {
 
   148   for(NodeIt n(digraph); n != INVALID; ++n) {
 
   149     if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
 
   149     if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
 
   150       Arc a = dijkstra.predArc(n);
 
   150       Arc a = dijkstra.predArc(n);
 
   151       Node s = digraph.source(a);
 
   151       Node s = digraph.source(a);
 
   152       check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
 
   152       check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
 
   153 	     "Error in a shortest path tree!");
 
   153              "Error in a shortest path tree!");
 
   154     }
 
   154     }
 
   155   }
 
   155   }
 
   156 
   156 
   157 }
 
   157 }
 
   158 
   158 
   159 int main() {
 
   159 int main() {
 
   160 
   160 
   161   typedef int Item;
 
   161   typedef int Item;
 
   162   typedef int Prio;
 
   162   typedef int Prio;
 
   163   typedef RangeMap<int> ItemIntMap;
 
   163   typedef RangeMap<int> ItemIntMap;
 
   164   
   164 
   165   Digraph digraph;
 
   165   Digraph digraph;
 
   166   IntArcMap length(digraph);
 
   166   IntArcMap length(digraph);
 
   167   Node source;
 
   167   Node source;
 
   168 
   168 
   169   std::istringstream input(test_lgf);
 
   169   std::istringstream input(test_lgf);
 
   170   digraphReader(input, digraph).
 
   170   digraphReader(input, digraph).
 
   171     arcMap("capacity", length).
 
   171     arcMap("capacity", length).
 
   172     node("source", source).
 
   172     node("source", source).
 
   173     run();  
   173     run();
 
   174  
   174 
   175   {
 
   175   {
 
   176     typedef BinHeap<Prio, ItemIntMap> IntHeap;
 
   176     typedef BinHeap<Prio, ItemIntMap> IntHeap;
 
   177     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 
   177     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 
   178     heapSortTest<IntHeap>();
 
   178     heapSortTest<IntHeap>();
 
   179     heapIncreaseTest<IntHeap>();
 
   179     heapIncreaseTest<IntHeap>();
 
   180     
   180 
   181     typedef BinHeap<Prio, IntNodeMap > NodeHeap;
 
   181     typedef BinHeap<Prio, IntNodeMap > NodeHeap;
 
   182     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 
   182     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 
   183     dijkstraHeapTest<NodeHeap>(digraph, length, source);
 
   183     dijkstraHeapTest<NodeHeap>(digraph, length, source);
 
   184   }
 
   184   }
 
   185 
   185
lemon