test/heap_test.cc
author hegyi
Mon, 07 Apr 2008 16:28:20 +0000
changeset 2600 e5530c0a018c
parent 2553 bfced05fa852
permissions -rw-r--r--
NEWS file updated for Release 0.7
alpar@1956
     1
/* -*- C++ -*-
alpar@1956
     2
 *
alpar@1956
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@1956
     4
 *
alpar@2553
     5
 * Copyright (C) 2003-2008
alpar@1956
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1956
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@1956
     8
 *
alpar@1956
     9
 * Permission to use, modify and distribute this software is granted
alpar@1956
    10
 * provided that this copyright notice appears in all copies. For
alpar@1956
    11
 * precise terms see the accompanying LICENSE file.
alpar@1956
    12
 *
alpar@1956
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@1956
    14
 * express or implied, and with no claim as to its suitability for any
alpar@1956
    15
 * purpose.
alpar@1956
    16
 *
alpar@1956
    17
 */
deba@1187
    18
deba@1187
    19
#include <iostream>
deba@1187
    20
#include <fstream>
alpar@1215
    21
#include <string>
deba@1187
    22
#include <vector>
deba@1187
    23
deba@1187
    24
#include <lemon/concept_check.h>
alpar@2260
    25
#include <lemon/concepts/heap.h>
deba@1187
    26
deba@1206
    27
#include <lemon/smart_graph.h>
deba@1206
    28
deba@1206
    29
#include <lemon/graph_reader.h>
deba@1206
    30
deba@1187
    31
#include <lemon/bin_heap.h>
deba@1187
    32
#include <lemon/fib_heap.h>
deba@1187
    33
#include <lemon/radix_heap.h>
deba@2038
    34
#include <lemon/bucket_heap.h>
deba@1187
    35
deba@1206
    36
#include "test_tools.h"
deba@1187
    37
deba@1187
    38
#include "heap_test.h"
deba@1187
    39
deba@1728
    40
#include <lemon/time_measure.h>
deba@1187
    41
deba@1187
    42
using namespace lemon;
alpar@2260
    43
using namespace lemon::concepts;
deba@1187
    44
deba@1187
    45
deba@1187
    46
int main() {
deba@1187
    47
deba@1187
    48
  typedef int Item;
deba@1187
    49
  typedef int Prio;
deba@1187
    50
  typedef IntIntMap ItemIntMap;
deba@1187
    51
deba@1187
    52
  typedef ListGraph Graph;
deba@1187
    53
deba@1187
    54
  typedef Graph::Edge Edge;
deba@1187
    55
  typedef Graph::Node Node;
deba@1187
    56
  typedef Graph::EdgeIt EdgeIt;
deba@1187
    57
  typedef Graph::NodeIt NodeIt;
deba@1187
    58
  typedef Graph::EdgeMap<int> LengthMap;
deba@1187
    59
deba@1187
    60
  Graph graph;
deba@1187
    61
  LengthMap length(graph);
deba@1187
    62
  Node start;
deba@1187
    63
deba@1206
    64
  /// \todo create own test graph
alpar@1215
    65
alpar@1215
    66
  std::string f_name;
alpar@1215
    67
  if( getenv("srcdir") )
alpar@1215
    68
    f_name = std::string(getenv("srcdir"));
alpar@1215
    69
  else f_name = ".";
ladanyi@2108
    70
  f_name += "/test/dijkstra_test.lgf";
alpar@1215
    71
  
alpar@1215
    72
  std::ifstream input(f_name.c_str());
alpar@1215
    73
  check(input, "Input file '" << f_name << "' not found.");
deba@1744
    74
  GraphReader<Graph>(input, graph).
deba@1845
    75
    readEdgeMap("capacity", length).
deba@1744
    76
    readNode("source", start).
deba@1744
    77
    run();  
deba@1187
    78
 
deba@1187
    79
  {
kpeter@2565
    80
    std::cout << "Checking Bin Heap" << std::endl;
deba@1187
    81
deba@2269
    82
    typedef BinHeap<Prio, ItemIntMap> IntHeap;
deba@2269
    83
    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
deba@1206
    84
    heapSortTest<IntHeap>(100);
deba@1206
    85
    heapIncreaseTest<IntHeap>(100);
deba@1187
    86
    
kpeter@2565
    87
    typedef BinHeap<Prio, Graph::NodeMap<int> > NodeHeap;
deba@2269
    88
    checkConcept<Heap<Prio, Graph::NodeMap<int> >, NodeHeap>();
deba@1728
    89
    Timer timer;
deba@1187
    90
    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
deba@1728
    91
    std::cout << timer << std::endl;
deba@1187
    92
  }
deba@1187
    93
  {
kpeter@2565
    94
    std::cout << "Checking Fib Heap" << std::endl;
deba@1187
    95
deba@2269
    96
    typedef FibHeap<Prio, ItemIntMap> IntHeap;
deba@2269
    97
    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
deba@1206
    98
    heapSortTest<IntHeap>(100);
deba@1206
    99
    heapIncreaseTest<IntHeap>(100);
deba@1187
   100
deba@2269
   101
    typedef FibHeap<Prio, Graph::NodeMap<int> > NodeHeap;
deba@2269
   102
    checkConcept<Heap<Prio, Graph::NodeMap<int> >, NodeHeap>();
deba@1728
   103
    Timer timer;
deba@1187
   104
    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
deba@1728
   105
    std::cout << timer << std::endl;
deba@1187
   106
  }
deba@1187
   107
  {
kpeter@2565
   108
    std::cout << "Checking Radix Heap" << std::endl;
deba@1187
   109
deba@2269
   110
    typedef RadixHeap<ItemIntMap> IntHeap;
deba@2269
   111
    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
deba@1206
   112
    heapSortTest<IntHeap>(100);
deba@1206
   113
    heapIncreaseTest<IntHeap>(100);
deba@1187
   114
deba@2269
   115
    typedef RadixHeap<Graph::NodeMap<int> > NodeHeap;
deba@2269
   116
    checkConcept<Heap<Prio, Graph::NodeMap<int> >, NodeHeap>();
deba@1728
   117
    Timer timer;
deba@1187
   118
    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
deba@1728
   119
    std::cout << timer << std::endl;
deba@1728
   120
  }
deba@1728
   121
deba@1728
   122
  {
kpeter@2565
   123
    std::cout << "Checking Bucket Heap" << std::endl;
deba@1728
   124
deba@2269
   125
    typedef BucketHeap<ItemIntMap> IntHeap;
deba@2269
   126
    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
deba@1728
   127
    heapSortTest<IntHeap>(100);
deba@1728
   128
    heapIncreaseTest<IntHeap>(100);
deba@1728
   129
deba@2269
   130
    typedef BucketHeap<Graph::NodeMap<int> > NodeHeap;
deba@2269
   131
    checkConcept<Heap<Prio, Graph::NodeMap<int> >, NodeHeap>();
deba@1728
   132
    Timer timer;
deba@1728
   133
    dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
deba@1728
   134
    std::cout << timer << std::endl;
deba@1187
   135
  }
deba@1187
   136
deba@1187
   137
  std::cout << __FILE__ ": All tests passed.\n";
deba@1187
   138
deba@1187
   139
  return 0;
deba@1187
   140
}