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

     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>

    19 #include "test_tools.h"

    21 #include "heap_test.h"

    24 using namespace lemon;

    25 using namespace lemon::concept;

    28 int main() {

    30   typedef int Item;

    31   typedef int Prio;

    32   typedef IntIntMap ItemIntMap;

    34   typedef ListGraph Graph;

    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;

    42   Graph graph;

    43   LengthMap length(graph);

    44   Node start;

    46   /// \todo create own test graph

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

    54   std::ifstream input(f_name.c_str());

    55   check(input, "Input file '" << f_name << "' not found.");

    56   readGraph(input, graph, length, start);

    58   {

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

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

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

    63     heapSortTest<IntHeap>(100);

    64     heapIncreaseTest<IntHeap>(100);

    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;

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

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

    75     heapSortTest<IntHeap>(100);

    76     heapIncreaseTest<IntHeap>(100);

    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;

    85     typedef RadixHeap<Item, ItemIntMap> IntHeap;

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

    87     heapSortTest<IntHeap>(100);

    88     heapIncreaseTest<IntHeap>(100);

    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   }

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

    97   return 0;

    98 }

author	alpar
	Mon, 04 Jul 2005 17:16:05 +0000
changeset 1537	0d9f1a71be27
parent 1330	52ef02524468
child 1728	eb8bb91ba9e2
permissions	-rw-r--r--