test/heap_test.cc
author klao
Thu, 02 Feb 2006 17:09:09 +0000
changeset 1945 e5c0c5cc477f
parent 1744 51d5d41e15b1
child 1956 a055123339d5
permissions -rw-r--r--
NEWS: major changes since 0.4 added
     1 // -*- c++ -*-
     2 
     3 #include <iostream>
     4 #include <fstream>
     5 #include <string>
     6 #include <vector>
     7 
     8 #include <lemon/concept_check.h>
     9 #include <lemon/concept/heap.h>
    10 
    11 #include <lemon/smart_graph.h>
    12 
    13 #include <lemon/graph_reader.h>
    14 
    15 #include <lemon/bin_heap.h>
    16 #include <lemon/fib_heap.h>
    17 #include <lemon/radix_heap.h>
    18 #include <lemon/linear_heap.h>
    19 
    20 #include "test_tools.h"
    21 
    22 #include "heap_test.h"
    23 
    24 #include <lemon/time_measure.h>
    25 
    26 using namespace lemon;
    27 using namespace lemon::concept;
    28 
    29 
    30 int main() {
    31 
    32   typedef int Item;
    33   typedef int Prio;
    34   typedef IntIntMap ItemIntMap;
    35 
    36   typedef ListGraph Graph;
    37 
    38   typedef Graph::Edge Edge;
    39   typedef Graph::Node Node;
    40   typedef Graph::EdgeIt EdgeIt;
    41   typedef Graph::NodeIt NodeIt;
    42   typedef Graph::EdgeMap<int> LengthMap;
    43 
    44   Graph graph;
    45   LengthMap length(graph);
    46   Node start;
    47 
    48   /// \todo create own test graph
    49 
    50   std::string f_name;
    51   if( getenv("srcdir") )
    52     f_name = std::string(getenv("srcdir"));
    53   else f_name = ".";
    54   f_name += "/dijkstra_test.lgf";
    55   
    56   std::ifstream input(f_name.c_str());
    57   check(input, "Input file '" << f_name << "' not found.");
    58   GraphReader<Graph>(input, graph).
    59     readEdgeMap("capacity", length).
    60     readNode("source", start).
    61     run();  
    62  
    63   {
    64     std::cerr << "Checking Bin Heap" << std::endl;
    65 
    66     typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;
    67     checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
    68     heapSortTest<IntHeap>(100);
    69     heapIncreaseTest<IntHeap>(100);
    70     
    71     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
    72     checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
    73     Timer timer;
    74     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
    75     std::cout << timer << std::endl;
    76   }
    77   {
    78     std::cerr << "Checking Fib Heap" << std::endl;
    79 
    80     typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;
    81     checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
    82     heapSortTest<IntHeap>(100);
    83     heapIncreaseTest<IntHeap>(100);
    84 
    85     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
    86     checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
    87     Timer timer;
    88     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
    89     std::cout << timer << std::endl;
    90   }
    91   {
    92     std::cerr << "Checking Radix Heap" << std::endl;
    93 
    94     typedef RadixHeap<Item, ItemIntMap> IntHeap;
    95     checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
    96     heapSortTest<IntHeap>(100);
    97     heapIncreaseTest<IntHeap>(100);
    98 
    99     typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;
   100     checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
   101     Timer timer;
   102     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
   103     std::cout << timer << std::endl;
   104   }
   105 
   106   {
   107     std::cerr << "Checking Linear Heap" << std::endl;
   108 
   109     typedef LinearHeap<Item, ItemIntMap> IntHeap;
   110     checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
   111     heapSortTest<IntHeap>(100);
   112     heapIncreaseTest<IntHeap>(100);
   113 
   114     typedef LinearHeap<Node, Graph::NodeMap<int> > NodeHeap;
   115     checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
   116     Timer timer;
   117     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
   118     std::cout << timer << std::endl;
   119   }
   120 
   121   std::cout << __FILE__ ": All tests passed.\n";
   122 
   123   return 0;
   124 }