1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/test/heap_test.cc	Thu Mar 20 12:12:24 2008 +0000
     1.3 @@ -0,0 +1,140 @@
     1.4 +/* -*- C++ -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library
     1.7 + *
     1.8 + * Copyright (C) 2003-2008
     1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 + *
    1.12 + * Permission to use, modify and distribute this software is granted
    1.13 + * provided that this copyright notice appears in all copies. For
    1.14 + * precise terms see the accompanying LICENSE file.
    1.15 + *
    1.16 + * This software is provided "AS IS" with no warranty of any kind,
    1.17 + * express or implied, and with no claim as to its suitability for any
    1.18 + * purpose.
    1.19 + *
    1.20 + */
    1.21 +
    1.22 +#include <iostream>
    1.23 +#include <fstream>
    1.24 +#include <string>
    1.25 +#include <vector>
    1.26 +
    1.27 +#include <lemon/concept_check.h>
    1.28 +#include <lemon/concepts/heap.h>
    1.29 +
    1.30 +#include <lemon/list_graph.h>
    1.31 +
    1.32 +#include <lemon/digraph_reader.h>
    1.33 +
    1.34 +#include <lemon/bin_heap.h>
    1.35 +#include <lemon/fib_heap.h>
    1.36 +#include <lemon/radix_heap.h>
    1.37 +#include <lemon/bucket_heap.h>
    1.38 +
    1.39 +#include "test_tools.h"
    1.40 +
    1.41 +#include "heap_test.h"
    1.42 +
    1.43 +#include <lemon/time_measure.h>
    1.44 +
    1.45 +using namespace lemon;
    1.46 +using namespace lemon::concepts;
    1.47 +
    1.48 +
    1.49 +int main() {
    1.50 +
    1.51 +  typedef int Item;
    1.52 +  typedef int Prio;
    1.53 +  typedef IntIntMap ItemIntMap;
    1.54 +
    1.55 +  typedef ListDigraph Digraph;
    1.56 +
    1.57 +  typedef Digraph::Arc Arc;
    1.58 +  typedef Digraph::Node Node;
    1.59 +  typedef Digraph::ArcIt ArcIt;
    1.60 +  typedef Digraph::NodeIt NodeIt;
    1.61 +  typedef Digraph::ArcMap<int> LengthMap;
    1.62 +
    1.63 +  Digraph digraph;
    1.64 +  LengthMap length(digraph);
    1.65 +  Node start;
    1.66 +
    1.67 +  /// \todo create own test digraph
    1.68 +
    1.69 +  std::string f_name;
    1.70 +  if( getenv("srcdir") )
    1.71 +    f_name = std::string(getenv("srcdir"));
    1.72 +  else f_name = ".";
    1.73 +  f_name += "/test/dijkstra_test.lgf";
    1.74 +  
    1.75 +  std::ifstream input(f_name.c_str());
    1.76 +  check(input, "Input file '" << f_name << "' not found.");
    1.77 +  DigraphReader<Digraph>(input, digraph).
    1.78 +    readArcMap("capacity", length).
    1.79 +    readNode("source", start).
    1.80 +    run();  
    1.81 + 
    1.82 +  {
    1.83 +    std::cerr << "Checking Bin Heap" << std::endl;
    1.84 +
    1.85 +    typedef BinHeap<Prio, ItemIntMap> IntHeap;
    1.86 +    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    1.87 +    heapSortTest<IntHeap>(100);
    1.88 +    heapIncreaseTest<IntHeap>(100);
    1.89 +    
    1.90 +    typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
    1.91 +    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
    1.92 +    Timer timer;
    1.93 +    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
    1.94 +    std::cout << timer << std::endl;
    1.95 +  }
    1.96 +  {
    1.97 +    std::cerr << "Checking Fib Heap" << std::endl;
    1.98 +
    1.99 +    typedef FibHeap<Prio, ItemIntMap> IntHeap;
   1.100 +    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   1.101 +    heapSortTest<IntHeap>(100);
   1.102 +    heapIncreaseTest<IntHeap>(100);
   1.103 +
   1.104 +    typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
   1.105 +    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
   1.106 +    Timer timer;
   1.107 +    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
   1.108 +    std::cout << timer << std::endl;
   1.109 +  }
   1.110 +  {
   1.111 +    std::cerr << "Checking Radix Heap" << std::endl;
   1.112 +
   1.113 +    typedef RadixHeap<ItemIntMap> IntHeap;
   1.114 +    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   1.115 +    heapSortTest<IntHeap>(100);
   1.116 +    heapIncreaseTest<IntHeap>(100);
   1.117 +
   1.118 +    typedef RadixHeap<Digraph::NodeMap<int> > NodeHeap;
   1.119 +    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
   1.120 +    Timer timer;
   1.121 +    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
   1.122 +    std::cout << timer << std::endl;
   1.123 +  }
   1.124 +
   1.125 +  {
   1.126 +    std::cerr << "Checking Bucket Heap" << std::endl;
   1.127 +
   1.128 +    typedef BucketHeap<ItemIntMap> IntHeap;
   1.129 +    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   1.130 +    heapSortTest<IntHeap>(100);
   1.131 +    heapIncreaseTest<IntHeap>(100);
   1.132 +
   1.133 +    typedef BucketHeap<Digraph::NodeMap<int> > NodeHeap;
   1.134 +    checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
   1.135 +    Timer timer;
   1.136 +    dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
   1.137 +    std::cout << timer << std::endl;
   1.138 +  }
   1.139 +
   1.140 +  std::cout << __FILE__ ": All tests passed.\n";
   1.141 +
   1.142 +  return 0;
   1.143 +}