lemon-0.x: test/heap_test.cc@06f939455cb1

     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   readGraph(input, graph, length, start);

    60   {

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

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

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

    65     heapSortTest<IntHeap>(100);

    66     heapIncreaseTest<IntHeap>(100);

    68     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;

    69     checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();

    70     Timer timer;

    71     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);

    72     std::cout << timer << std::endl;

    73   }

    74   {

    75     std::cerr << "Checking Fib Heap" << std::endl;

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

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

    79     heapSortTest<IntHeap>(100);

    80     heapIncreaseTest<IntHeap>(100);

    82     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;

    83     checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();

    84     Timer timer;

    85     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);

    86     std::cout << timer << std::endl;

    87   }

    88   {

    89     std::cerr << "Checking Radix Heap" << std::endl;

    91     typedef RadixHeap<Item, ItemIntMap> IntHeap;

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

    93     heapSortTest<IntHeap>(100);

    94     heapIncreaseTest<IntHeap>(100);

    96     typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;

    97     checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();

    98     Timer timer;

    99     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);

   100     std::cout << timer << std::endl;

   101   }

   103   {

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

   106     typedef LinearHeap<Item, ItemIntMap> IntHeap;

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

   108     heapSortTest<IntHeap>(100);

   109     heapIncreaseTest<IntHeap>(100);

   111     typedef LinearHeap<Node, Graph::NodeMap<int> > NodeHeap;

   112     checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();

   113     Timer timer;

   114     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);

   115     std::cout << timer << std::endl;

   116   }

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

   120   return 0;

   121 }

author	deba
	Mon, 17 Oct 2005 10:28:48 +0000
changeset 1729	06f939455cb1
parent 1435	8e85e6bbefdf
child 1744	51d5d41e15b1
permissions	-rw-r--r--