lemon-0.x: test/heap_test.cc@e5c0c5cc477f

     1 // -*- c++ -*-

     3 #include <iostream>

     4 #include <fstream>

     5 #include <string>

     6 #include <vector>

     8 #include <lemon/concept_check.h>

     9 #include <lemon/concept/heap.h>

    11 #include <lemon/smart_graph.h>

    13 #include <lemon/graph_reader.h>

    15 #include <lemon/bin_heap.h>

    16 #include <lemon/fib_heap.h>

    17 #include <lemon/radix_heap.h>

    18 #include <lemon/linear_heap.h>

    20 #include "test_tools.h"

    22 #include "heap_test.h"

    24 #include <lemon/time_measure.h>

    26 using namespace lemon;

    27 using namespace lemon::concept;

    30 int main() {

    32   typedef int Item;

    33   typedef int Prio;

    34   typedef IntIntMap ItemIntMap;

    36   typedef ListGraph Graph;

    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;

    44   Graph graph;

    45   LengthMap length(graph);

    46   Node start;

    48   /// \todo create own test graph

    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";

    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();

    63   {

    64     std::cerr << "Checking Bin Heap" << std::endl;

    66     typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;

    67     checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();

    68     heapSortTest<IntHeap>(100);

    69     heapIncreaseTest<IntHeap>(100);

    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;

    80     typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;

    81     checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();

    82     heapSortTest<IntHeap>(100);

    83     heapIncreaseTest<IntHeap>(100);

    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;

    94     typedef RadixHeap<Item, ItemIntMap> IntHeap;

    95     checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();

    96     heapSortTest<IntHeap>(100);

    97     heapIncreaseTest<IntHeap>(100);

    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   }

   106   {

   107     std::cerr << "Checking Linear Heap" << std::endl;

   109     typedef LinearHeap<Item, ItemIntMap> IntHeap;

   110     checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();

   111     heapSortTest<IntHeap>(100);

   112     heapIncreaseTest<IntHeap>(100);

   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   }

   121   std::cout << __FILE__ ": All tests passed.\n";

   123   return 0;

   124 }

author	klao
	Thu, 02 Feb 2006 17:09:09 +0000
changeset 1945	e5c0c5cc477f
parent 1744	51d5d41e15b1
child 1956	a055123339d5
permissions	-rw-r--r--