alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@100:  *
alpar@209:  * This file is a part of LEMON, a generic C++ optimization library.
alpar@100:  *
alpar@463:  * Copyright (C) 2003-2009
alpar@100:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@100:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@100:  *
alpar@100:  * Permission to use, modify and distribute this software is granted
alpar@100:  * provided that this copyright notice appears in all copies. For
alpar@100:  * precise terms see the accompanying LICENSE file.
alpar@100:  *
alpar@100:  * This software is provided "AS IS" with no warranty of any kind,
alpar@100:  * express or implied, and with no claim as to its suitability for any
alpar@100:  * purpose.
alpar@100:  *
alpar@100:  */
alpar@100: 
alpar@100: #include <iostream>
alpar@100: #include <fstream>
alpar@100: #include <string>
alpar@100: #include <vector>
alpar@100: 
alpar@100: #include <lemon/concept_check.h>
alpar@100: #include <lemon/concepts/heap.h>
alpar@100: 
deba@203: #include <lemon/smart_graph.h>
deba@203: #include <lemon/lgf_reader.h>
deba@203: #include <lemon/dijkstra.h>
deba@203: #include <lemon/maps.h>
alpar@100: 
alpar@100: #include <lemon/bin_heap.h>
kpeter@929: #include <lemon/quad_heap.h>
kpeter@929: #include <lemon/dheap.h>
deba@728: #include <lemon/fib_heap.h>
kpeter@748: #include <lemon/pairing_heap.h>
deba@728: #include <lemon/radix_heap.h>
kpeter@929: #include <lemon/binomial_heap.h>
deba@728: #include <lemon/bucket_heap.h>
alpar@100: 
alpar@100: #include "test_tools.h"
alpar@100: 
alpar@100: using namespace lemon;
alpar@100: using namespace lemon::concepts;
alpar@100: 
deba@203: typedef ListDigraph Digraph;
deba@203: DIGRAPH_TYPEDEFS(Digraph);
deba@203: 
alpar@209: char test_lgf[] =
alpar@209:   "@nodes\n"
alpar@209:   "label\n"
alpar@209:   "0\n"
alpar@209:   "1\n"
alpar@209:   "2\n"
alpar@209:   "3\n"
alpar@209:   "4\n"
alpar@209:   "5\n"
alpar@209:   "6\n"
alpar@209:   "7\n"
alpar@209:   "8\n"
alpar@209:   "9\n"
alpar@209:   "@arcs\n"
kpeter@212:   "                label   capacity\n"
kpeter@212:   "0       5       0       94\n"
kpeter@212:   "3       9       1       11\n"
kpeter@212:   "8       7       2       83\n"
kpeter@212:   "1       2       3       94\n"
kpeter@212:   "5       7       4       35\n"
kpeter@212:   "7       4       5       84\n"
kpeter@212:   "9       5       6       38\n"
kpeter@212:   "0       4       7       96\n"
kpeter@212:   "6       7       8       6\n"
kpeter@212:   "3       1       9       27\n"
kpeter@212:   "5       2       10      77\n"
kpeter@212:   "5       6       11      69\n"
kpeter@212:   "6       5       12      41\n"
kpeter@212:   "4       6       13      70\n"
kpeter@212:   "3       2       14      45\n"
kpeter@212:   "7       9       15      93\n"
kpeter@212:   "5       9       16      50\n"
kpeter@212:   "9       0       17      94\n"
kpeter@212:   "9       6       18      67\n"
kpeter@212:   "0       9       19      86\n"
alpar@209:   "@attributes\n"
deba@203:   "source 3\n";
deba@203: 
deba@203: int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26,  1,  9,  4, 34};
deba@203: int test_inc[] = {20, 28, 34, 16,  0, 46, 44,  0, 42, 32, 14,  8,  6, 37};
deba@203: 
deba@203: int test_len = sizeof(test_seq) / sizeof(test_seq[0]);
deba@203: 
deba@203: template <typename Heap>
deba@203: void heapSortTest() {
deba@203:   RangeMap<int> map(test_len, -1);
deba@203:   Heap heap(map);
alpar@209: 
deba@203:   std::vector<int> v(test_len);
deba@203:   for (int i = 0; i < test_len; ++i) {
deba@203:     v[i] = test_seq[i];
deba@203:     heap.push(i, v[i]);
deba@203:   }
deba@203:   std::sort(v.begin(), v.end());
deba@203:   for (int i = 0; i < test_len; ++i) {
kpeter@748:     check(v[i] == heap.prio(), "Wrong order in heap sort.");
deba@203:     heap.pop();
deba@203:   }
deba@203: }
deba@203: 
deba@203: template <typename Heap>
deba@203: void heapIncreaseTest() {
deba@203:   RangeMap<int> map(test_len, -1);
deba@203: 
deba@203:   Heap heap(map);
alpar@209: 
deba@203:   std::vector<int> v(test_len);
deba@203:   for (int i = 0; i < test_len; ++i) {
deba@203:     v[i] = test_seq[i];
deba@203:     heap.push(i, v[i]);
deba@203:   }
deba@203:   for (int i = 0; i < test_len; ++i) {
deba@203:     v[i] += test_inc[i];
deba@203:     heap.increase(i, v[i]);
deba@203:   }
deba@203:   std::sort(v.begin(), v.end());
deba@203:   for (int i = 0; i < test_len; ++i) {
kpeter@748:     check(v[i] == heap.prio(), "Wrong order in heap increase test.");
deba@203:     heap.pop();
deba@203:   }
deba@203: }
deba@203: 
deba@203: template <typename Heap>
alpar@209: void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
alpar@209:                       Node source) {
alpar@209: 
kpeter@257:   typename Dijkstra<Digraph, IntArcMap>::template SetStandardHeap<Heap>::
deba@203:     Create dijkstra(digraph, length);
deba@203: 
deba@203:   dijkstra.run(source);
deba@203: 
deba@203:   for(ArcIt a(digraph); a != INVALID; ++a) {
alpar@209:     Node s = digraph.source(a);
deba@203:     Node t = digraph.target(a);
deba@203:     if (dijkstra.reached(s)) {
deba@203:       check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
kpeter@748:              "Error in shortest path tree.");
deba@203:     }
deba@203:   }
deba@203: 
deba@203:   for(NodeIt n(digraph); n != INVALID; ++n) {
deba@203:     if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
deba@203:       Arc a = dijkstra.predArc(n);
deba@203:       Node s = digraph.source(a);
deba@203:       check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
kpeter@748:              "Error in shortest path tree.");
deba@203:     }
deba@203:   }
deba@203: 
deba@203: }
deba@203: 
alpar@100: int main() {
alpar@100: 
alpar@100:   typedef int Item;
alpar@100:   typedef int Prio;
deba@203:   typedef RangeMap<int> ItemIntMap;
alpar@209: 
deba@203:   Digraph digraph;
deba@203:   IntArcMap length(digraph);
deba@203:   Node source;
alpar@100: 
deba@203:   std::istringstream input(test_lgf);
kpeter@293:   digraphReader(digraph, input).
deba@203:     arcMap("capacity", length).
deba@203:     node("source", source).
alpar@209:     run();
alpar@209: 
kpeter@748:   // BinHeap
alpar@100:   {
alpar@100:     typedef BinHeap<Prio, ItemIntMap> IntHeap;
alpar@100:     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
deba@203:     heapSortTest<IntHeap>();
deba@203:     heapIncreaseTest<IntHeap>();
alpar@209: 
deba@203:     typedef BinHeap<Prio, IntNodeMap > NodeHeap;
deba@203:     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
deba@203:     dijkstraHeapTest<NodeHeap>(digraph, length, source);
alpar@100:   }
alpar@100: 
kpeter@929:   // QuadHeap
kpeter@748:   {
kpeter@929:     typedef QuadHeap<Prio, ItemIntMap> IntHeap;
kpeter@748:     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
kpeter@748:     heapSortTest<IntHeap>();
kpeter@748:     heapIncreaseTest<IntHeap>();
kpeter@748: 
kpeter@929:     typedef QuadHeap<Prio, IntNodeMap > NodeHeap;
kpeter@748:     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
kpeter@748:     dijkstraHeapTest<NodeHeap>(digraph, length, source);
kpeter@748:   }
kpeter@748: 
kpeter@929:   // DHeap
kpeter@748:   {
kpeter@929:     typedef DHeap<Prio, ItemIntMap> IntHeap;
kpeter@748:     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
kpeter@748:     heapSortTest<IntHeap>();
kpeter@748:     heapIncreaseTest<IntHeap>();
kpeter@748: 
kpeter@929:     typedef DHeap<Prio, IntNodeMap > NodeHeap;
kpeter@748:     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
kpeter@748:     dijkstraHeapTest<NodeHeap>(digraph, length, source);
kpeter@748:   }
kpeter@748: 
kpeter@748:   // FibHeap
deba@728:   {
deba@728:     typedef FibHeap<Prio, ItemIntMap> IntHeap;
deba@728:     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
deba@728:     heapSortTest<IntHeap>();
deba@728:     heapIncreaseTest<IntHeap>();
deba@728: 
deba@728:     typedef FibHeap<Prio, IntNodeMap > NodeHeap;
deba@728:     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
deba@728:     dijkstraHeapTest<NodeHeap>(digraph, length, source);
deba@728:   }
deba@728: 
kpeter@748:   // PairingHeap
kpeter@749:   {
kpeter@749:     typedef PairingHeap<Prio, ItemIntMap> IntHeap;
kpeter@749:     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
kpeter@749:     heapSortTest<IntHeap>();
kpeter@749:     heapIncreaseTest<IntHeap>();
kpeter@749: 
kpeter@749:     typedef PairingHeap<Prio, IntNodeMap > NodeHeap;
kpeter@749:     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
kpeter@749:     dijkstraHeapTest<NodeHeap>(digraph, length, source);
kpeter@749:   }
kpeter@748: 
kpeter@748:   // RadixHeap
deba@728:   {
deba@728:     typedef RadixHeap<ItemIntMap> IntHeap;
deba@728:     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
deba@728:     heapSortTest<IntHeap>();
deba@728:     heapIncreaseTest<IntHeap>();
deba@728: 
deba@728:     typedef RadixHeap<IntNodeMap > NodeHeap;
deba@728:     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
deba@728:     dijkstraHeapTest<NodeHeap>(digraph, length, source);
deba@728:   }
deba@728: 
kpeter@929:   // BinomialHeap
kpeter@748:   {
kpeter@929:     typedef BinomialHeap<Prio, ItemIntMap> IntHeap;
kpeter@748:     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
kpeter@748:     heapSortTest<IntHeap>();
kpeter@748:     heapIncreaseTest<IntHeap>();
kpeter@748: 
kpeter@929:     typedef BinomialHeap<Prio, IntNodeMap > NodeHeap;
kpeter@748:     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
kpeter@748:     dijkstraHeapTest<NodeHeap>(digraph, length, source);
kpeter@748:   }
kpeter@748: 
kpeter@748:   // BucketHeap, SimpleBucketHeap
deba@728:   {
deba@728:     typedef BucketHeap<ItemIntMap> IntHeap;
deba@728:     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
deba@728:     heapSortTest<IntHeap>();
deba@728:     heapIncreaseTest<IntHeap>();
deba@728: 
deba@728:     typedef BucketHeap<IntNodeMap > NodeHeap;
deba@728:     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
deba@728:     dijkstraHeapTest<NodeHeap>(digraph, length, source);
kpeter@748: 
kpeter@748:     typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;
kpeter@748:     heapSortTest<SimpleIntHeap>();
deba@728:   }
deba@728: 
alpar@1065:   {
alpar@1065:     typedef FibHeap<Prio, ItemIntMap> IntHeap;
alpar@1065:     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
alpar@1065:     heapSortTest<IntHeap>();
alpar@1065:     heapIncreaseTest<IntHeap>();
alpar@1065: 
alpar@1065:     typedef FibHeap<Prio, IntNodeMap > NodeHeap;
alpar@1065:     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
alpar@1065:     dijkstraHeapTest<NodeHeap>(digraph, length, source);
alpar@1065:   }
alpar@1065: 
alpar@1065:   {
alpar@1065:     typedef RadixHeap<ItemIntMap> IntHeap;
alpar@1065:     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
alpar@1065:     heapSortTest<IntHeap>();
alpar@1065:     heapIncreaseTest<IntHeap>();
alpar@1065: 
alpar@1065:     typedef RadixHeap<IntNodeMap > NodeHeap;
alpar@1065:     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
alpar@1065:     dijkstraHeapTest<NodeHeap>(digraph, length, source);
alpar@1065:   }
alpar@1065: 
alpar@1065:   {
alpar@1065:     typedef BucketHeap<ItemIntMap> IntHeap;
alpar@1065:     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
alpar@1065:     heapSortTest<IntHeap>();
alpar@1065:     heapIncreaseTest<IntHeap>();
alpar@1065: 
alpar@1065:     typedef BucketHeap<IntNodeMap > NodeHeap;
alpar@1065:     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
alpar@1065:     dijkstraHeapTest<NodeHeap>(digraph, length, source);
alpar@1065:   }
alpar@1065: 
alpar@1065: 
alpar@100:   return 0;
alpar@100: }