src/test/heap_test.cc
author deba
Sat, 09 Apr 2005 19:27:48 +0000
changeset 1330 52ef02524468
parent 1325 916ec8699dc3
permissions -rw-r--r--
Heap concept moved to namespace concept.
     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 
    19 #include "test_tools.h"
    20 
    21 #include "heap_test.h"
    22 
    23 
    24 using namespace lemon;
    25 using namespace lemon::concept;
    26 
    27 
    28 int main() {
    29 
    30   typedef int Item;
    31   typedef int Prio;
    32   typedef IntIntMap ItemIntMap;
    33 
    34   typedef ListGraph Graph;
    35 
    36   typedef Graph::Edge Edge;
    37   typedef Graph::Node Node;
    38   typedef Graph::EdgeIt EdgeIt;
    39   typedef Graph::NodeIt NodeIt;
    40   typedef Graph::EdgeMap<int> LengthMap;
    41 
    42   Graph graph;
    43   LengthMap length(graph);
    44   Node start;
    45 
    46   /// \todo create own test graph
    47 
    48   std::string f_name;
    49   if( getenv("srcdir") )
    50     f_name = std::string(getenv("srcdir"));
    51   else f_name = ".";
    52   f_name += "/dijkstra_test.lgf";
    53   
    54   std::ifstream input(f_name.c_str());
    55   check(input, "Input file '" << f_name << "' not found.");
    56   readGraph(input, graph, length, start);  
    57  
    58   {
    59     std::cerr << "Checking Bin Heap" << std::endl;
    60 
    61     typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;
    62     checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
    63     heapSortTest<IntHeap>(100);
    64     heapIncreaseTest<IntHeap>(100);
    65     
    66     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
    67     checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
    68     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
    69   }
    70   {
    71     std::cerr << "Checking Fib Heap" << std::endl;
    72 
    73     typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;
    74     checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
    75     heapSortTest<IntHeap>(100);
    76     heapIncreaseTest<IntHeap>(100);
    77 
    78     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
    79     checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
    80     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
    81   }
    82   {
    83     std::cerr << "Checking Radix Heap" << std::endl;
    84 
    85     typedef RadixHeap<Item, ItemIntMap> IntHeap;
    86     checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
    87     heapSortTest<IntHeap>(100);
    88     heapIncreaseTest<IntHeap>(100);
    89 
    90     typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;
    91     checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
    92     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
    93   }
    94 
    95   std::cout << __FILE__ ": All tests passed.\n";
    96 
    97   return 0;
    98 }