Completions.
8 #include <lemon/concept_check.h>
10 #include <lemon/smart_graph.h>
12 #include <lemon/graph_reader.h>
14 #include <lemon/bin_heap.h>
15 #include <lemon/fib_heap.h>
16 #include <lemon/radix_heap.h>
18 #include "test_tools.h"
20 #include "heap_test.h"
23 using namespace lemon;
25 template <typename Item, typename Prio, typename ItemIntMap>
29 template <typename _Heap>
37 ignore_unused_variable_warning(item);
38 ignore_unused_variable_warning(prio);
40 typedef typename _Heap::state_enum state_enum;
43 ignore_unused_variable_warning(state);
45 _Heap heap1 = _Heap(map);
47 ignore_unused_variable_warning(heap1);
49 heap.push(item, prio);
57 heap.decrease(item, prio);
58 heap.increase(item, prio);
63 state = heap.state(item);
65 state = _Heap::PRE_HEAP;
66 state = _Heap::IN_HEAP;
67 state = _Heap::POST_HEAP;
79 typedef IntIntMap ItemIntMap;
81 typedef ListGraph Graph;
83 typedef Graph::Edge Edge;
84 typedef Graph::Node Node;
85 typedef Graph::EdgeIt EdgeIt;
86 typedef Graph::NodeIt NodeIt;
87 typedef Graph::EdgeMap<int> LengthMap;
90 LengthMap length(graph);
93 /// \todo create own test graph
96 if( getenv("srcdir") )
97 f_name = std::string(getenv("srcdir"));
99 f_name += "/dijkstra_test.lgf";
101 std::ifstream input(f_name.c_str());
102 check(input, "Input file '" << f_name << "' not found.");
103 readGraph(input, graph, length, start);
106 std::cerr << "Checking Bin Heap" << std::endl;
108 typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;
109 checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
110 heapSortTest<IntHeap>(100);
111 heapIncreaseTest<IntHeap>(100);
113 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
114 checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
115 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
118 std::cerr << "Checking Fib Heap" << std::endl;
120 typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;
121 checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
122 heapSortTest<IntHeap>(100);
123 heapIncreaseTest<IntHeap>(100);
125 typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
126 checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
127 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
130 std::cerr << "Checking Radix Heap" << std::endl;
132 typedef RadixHeap<Item, ItemIntMap> IntHeap;
133 checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
134 heapSortTest<IntHeap>(100);
135 heapIncreaseTest<IntHeap>(100);
137 typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;
138 checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
139 dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
142 std::cout << __FILE__ ": All tests passed.\n";