test/heap_test.cc
changeset 109 abddaa08b507
child 171 02f4d5d9bfd7
equal deleted inserted replaced
-1:000000000000 0:b1ee61b64c5a
       
     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 
       
    46 int main() {
       
    47 
       
    48   typedef int Item;
       
    49   typedef int Prio;
       
    50   typedef IntIntMap ItemIntMap;
       
    51 
       
    52   typedef ListDigraph Digraph;
       
    53 
       
    54   typedef Digraph::Arc Arc;
       
    55   typedef Digraph::Node Node;
       
    56   typedef Digraph::ArcIt ArcIt;
       
    57   typedef Digraph::NodeIt NodeIt;
       
    58   typedef Digraph::ArcMap<int> LengthMap;
       
    59 
       
    60   Digraph digraph;
       
    61   LengthMap length(digraph);
       
    62   Node start;
       
    63 
       
    64   /// \todo create own test digraph
       
    65 
       
    66   std::string f_name;
       
    67   if( getenv("srcdir") )
       
    68     f_name = std::string(getenv("srcdir"));
       
    69   else f_name = ".";
       
    70   f_name += "/test/dijkstra_test.lgf";
       
    71   
       
    72   std::ifstream input(f_name.c_str());
       
    73   check(input, "Input file '" << f_name << "' not found.");
       
    74   DigraphReader<Digraph>(input, digraph).
       
    75     readArcMap("capacity", length).
       
    76     readNode("source", start).
       
    77     run();  
       
    78  
       
    79   {
       
    80     std::cerr << "Checking Bin Heap" << std::endl;
       
    81 
       
    82     typedef BinHeap<Prio, ItemIntMap> IntHeap;
       
    83     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
       
    84     heapSortTest<IntHeap>(100);
       
    85     heapIncreaseTest<IntHeap>(100);
       
    86     
       
    87     typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
       
    88     checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
       
    89     Timer timer;
       
    90     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
       
    91     std::cout << timer << std::endl;
       
    92   }
       
    93   {
       
    94     std::cerr << "Checking Fib Heap" << std::endl;
       
    95 
       
    96     typedef FibHeap<Prio, ItemIntMap> IntHeap;
       
    97     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
       
    98     heapSortTest<IntHeap>(100);
       
    99     heapIncreaseTest<IntHeap>(100);
       
   100 
       
   101     typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
       
   102     checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
       
   103     Timer timer;
       
   104     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
       
   105     std::cout << timer << std::endl;
       
   106   }
       
   107   {
       
   108     std::cerr << "Checking Radix Heap" << std::endl;
       
   109 
       
   110     typedef RadixHeap<ItemIntMap> IntHeap;
       
   111     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
       
   112     heapSortTest<IntHeap>(100);
       
   113     heapIncreaseTest<IntHeap>(100);
       
   114 
       
   115     typedef RadixHeap<Digraph::NodeMap<int> > NodeHeap;
       
   116     checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
       
   117     Timer timer;
       
   118     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
       
   119     std::cout << timer << std::endl;
       
   120   }
       
   121 
       
   122   {
       
   123     std::cerr << "Checking Bucket Heap" << std::endl;
       
   124 
       
   125     typedef BucketHeap<ItemIntMap> IntHeap;
       
   126     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
       
   127     heapSortTest<IntHeap>(100);
       
   128     heapIncreaseTest<IntHeap>(100);
       
   129 
       
   130     typedef BucketHeap<Digraph::NodeMap<int> > NodeHeap;
       
   131     checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
       
   132     Timer timer;
       
   133     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
       
   134     std::cout << timer << std::endl;
       
   135   }
       
   136 
       
   137   std::cout << __FILE__ ": All tests passed.\n";
       
   138 
       
   139   return 0;
       
   140 }