test/heap_test.cc
changeset 180 4b9ab1324c3b
parent 100 4f754b4cf82b
child 203 215bfc30b14f
equal deleted inserted replaced
0:b1ee61b64c5a 1:3ef28713bbba
    40 #include <lemon/time_measure.h>
    40 #include <lemon/time_measure.h>
    41 
    41 
    42 using namespace lemon;
    42 using namespace lemon;
    43 using namespace lemon::concepts;
    43 using namespace lemon::concepts;
    44 
    44 
    45 
       
    46 int main() {
    45 int main() {
    47 
    46 
    48   typedef int Item;
    47   typedef int Item;
    49   typedef int Prio;
    48   typedef int Prio;
    50   typedef IntIntMap ItemIntMap;
    49   typedef IntIntMap ItemIntMap;
    75     readArcMap("capacity", length).
    74     readArcMap("capacity", length).
    76     readNode("source", start).
    75     readNode("source", start).
    77     run();  
    76     run();  
    78  
    77  
    79   {
    78   {
    80     std::cerr << "Checking Bin Heap" << std::endl;
    79     std::cout << "Checking Bin Heap" << std::endl;
    81 
    80 
    82     typedef BinHeap<Prio, ItemIntMap> IntHeap;
    81     typedef BinHeap<Prio, ItemIntMap> IntHeap;
    83     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    82     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    84     heapSortTest<IntHeap>(100);
    83     heapSortTest<IntHeap>(100);
    85     heapIncreaseTest<IntHeap>(100);
    84     heapIncreaseTest<IntHeap>(100);
    89     Timer timer;
    88     Timer timer;
    90     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
    89     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
    91     std::cout << timer << std::endl;
    90     std::cout << timer << std::endl;
    92   }
    91   }
    93   {
    92   {
    94     std::cerr << "Checking Fib Heap" << std::endl;
    93     std::cout << "Checking Fib Heap" << std::endl;
    95 
    94 
    96     typedef FibHeap<Prio, ItemIntMap> IntHeap;
    95     typedef FibHeap<Prio, ItemIntMap> IntHeap;
    97     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    96     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    98     heapSortTest<IntHeap>(100);
    97     heapSortTest<IntHeap>(100);
    99     heapIncreaseTest<IntHeap>(100);
    98     heapIncreaseTest<IntHeap>(100);
   103     Timer timer;
   102     Timer timer;
   104     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
   103     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
   105     std::cout << timer << std::endl;
   104     std::cout << timer << std::endl;
   106   }
   105   }
   107   {
   106   {
   108     std::cerr << "Checking Radix Heap" << std::endl;
   107     std::cout << "Checking Radix Heap" << std::endl;
   109 
   108 
   110     typedef RadixHeap<ItemIntMap> IntHeap;
   109     typedef RadixHeap<ItemIntMap> IntHeap;
   111     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   110     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   112     heapSortTest<IntHeap>(100);
   111     heapSortTest<IntHeap>(100);
   113     heapIncreaseTest<IntHeap>(100);
   112     heapIncreaseTest<IntHeap>(100);
   118     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
   117     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
   119     std::cout << timer << std::endl;
   118     std::cout << timer << std::endl;
   120   }
   119   }
   121 
   120 
   122   {
   121   {
   123     std::cerr << "Checking Bucket Heap" << std::endl;
   122     std::cout << "Checking Bucket Heap" << std::endl;
   124 
   123 
   125     typedef BucketHeap<ItemIntMap> IntHeap;
   124     typedef BucketHeap<ItemIntMap> IntHeap;
   126     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   125     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   127     heapSortTest<IntHeap>(100);
   126     heapSortTest<IntHeap>(100);
   128     heapIncreaseTest<IntHeap>(100);
   127     heapIncreaseTest<IntHeap>(100);
   132     Timer timer;
   131     Timer timer;
   133     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
   132     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
   134     std::cout << timer << std::endl;
   133     std::cout << timer << std::endl;
   135   }
   134   }
   136 
   135 
   137   std::cout << __FILE__ ": All tests passed.\n";
       
   138 
       
   139   return 0;
   136   return 0;
   140 }
   137 }