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 } |
|