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