Changeset 203:215bfc30b14f in lemon for test/heap_test.cc
 Timestamp:
 07/11/08 15:01:49 (13 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

test/heap_test.cc
r171 r203 25 25 #include <lemon/concepts/heap.h> 26 26 27 #include <lemon/ list_graph.h>27 #include <lemon/smart_graph.h> 28 28 29 #include <lemon/digraph_reader.h> 29 #include <lemon/lgf_reader.h> 30 #include <lemon/dijkstra.h> 31 #include <lemon/maps.h> 30 32 31 33 #include <lemon/bin_heap.h> 32 #include <lemon/fib_heap.h>33 #include <lemon/radix_heap.h>34 #include <lemon/bucket_heap.h>35 34 36 35 #include "test_tools.h" 37 36 38 #include "heap_test.h"39 40 #include <lemon/time_measure.h>41 42 37 using namespace lemon; 43 38 using namespace lemon::concepts; 39 40 typedef ListDigraph Digraph; 41 DIGRAPH_TYPEDEFS(Digraph); 42 43 char test_lgf[] = 44 "@nodes\n" 45 "label\n" 46 "0\n" 47 "1\n" 48 "2\n" 49 "3\n" 50 "4\n" 51 "5\n" 52 "6\n" 53 "7\n" 54 "8\n" 55 "9\n" 56 "@arcs\n" 57 " label capacity\n" 58 "0 5 0 94\n" 59 "3 9 1 11\n" 60 "8 7 2 83\n" 61 "1 2 3 94\n" 62 "5 7 4 35\n" 63 "7 4 5 84\n" 64 "9 5 6 38\n" 65 "0 4 7 96\n" 66 "6 7 8 6\n" 67 "3 1 9 27\n" 68 "5 2 10 77\n" 69 "5 6 11 69\n" 70 "6 5 12 41\n" 71 "4 6 13 70\n" 72 "3 2 14 45\n" 73 "7 9 15 93\n" 74 "5 9 16 50\n" 75 "9 0 17 94\n" 76 "9 6 18 67\n" 77 "0 9 19 86\n" 78 "@attributes\n" 79 "source 3\n"; 80 81 int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26, 1, 9, 4, 34}; 82 int test_inc[] = {20, 28, 34, 16, 0, 46, 44, 0, 42, 32, 14, 8, 6, 37}; 83 84 int test_len = sizeof(test_seq) / sizeof(test_seq[0]); 85 86 template <typename Heap> 87 void heapSortTest() { 88 RangeMap<int> map(test_len, 1); 89 90 Heap heap(map); 91 92 std::vector<int> v(test_len); 93 94 for (int i = 0; i < test_len; ++i) { 95 v[i] = test_seq[i]; 96 heap.push(i, v[i]); 97 } 98 std::sort(v.begin(), v.end()); 99 for (int i = 0; i < test_len; ++i) { 100 check(v[i] == heap.prio() ,"Wrong order in heap sort."); 101 heap.pop(); 102 } 103 } 104 105 template <typename Heap> 106 void heapIncreaseTest() { 107 RangeMap<int> map(test_len, 1); 108 109 Heap heap(map); 110 111 std::vector<int> v(test_len); 112 113 for (int i = 0; i < test_len; ++i) { 114 v[i] = test_seq[i]; 115 heap.push(i, v[i]); 116 } 117 for (int i = 0; i < test_len; ++i) { 118 v[i] += test_inc[i]; 119 heap.increase(i, v[i]); 120 } 121 std::sort(v.begin(), v.end()); 122 for (int i = 0; i < test_len; ++i) { 123 check(v[i] == heap.prio() ,"Wrong order in heap increase test."); 124 heap.pop(); 125 } 126 } 127 128 129 130 template <typename Heap> 131 void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length, 132 Node source) { 133 134 typename Dijkstra<Digraph, IntArcMap>::template DefStandardHeap<Heap>:: 135 Create dijkstra(digraph, length); 136 137 dijkstra.run(source); 138 139 for(ArcIt a(digraph); a != INVALID; ++a) { 140 Node s = digraph.source(a); 141 Node t = digraph.target(a); 142 if (dijkstra.reached(s)) { 143 check( dijkstra.dist(t)  dijkstra.dist(s) <= length[a], 144 "Error in a shortest path tree!"); 145 } 146 } 147 148 for(NodeIt n(digraph); n != INVALID; ++n) { 149 if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) { 150 Arc a = dijkstra.predArc(n); 151 Node s = digraph.source(a); 152 check( dijkstra.dist(n)  dijkstra.dist(s) == length[a], 153 "Error in a shortest path tree!"); 154 } 155 } 156 157 } 44 158 45 159 int main() { … … 47 161 typedef int Item; 48 162 typedef int Prio; 49 typedef IntIntMap ItemIntMap; 163 typedef RangeMap<int> ItemIntMap; 164 165 Digraph digraph; 166 IntArcMap length(digraph); 167 Node source; 50 168 51 typedef ListDigraph Digraph; 52 53 typedef Digraph::Arc Arc; 54 typedef Digraph::Node Node; 55 typedef Digraph::ArcIt ArcIt; 56 typedef Digraph::NodeIt NodeIt; 57 typedef Digraph::ArcMap<int> LengthMap; 58 59 Digraph digraph; 60 LengthMap length(digraph); 61 Node start; 62 63 /// \todo create own test digraph 64 65 std::string f_name; 66 if( getenv("srcdir") ) 67 f_name = std::string(getenv("srcdir")); 68 else f_name = "."; 69 f_name += "/test/dijkstra_test.lgf"; 70 71 std::ifstream input(f_name.c_str()); 72 check(input, "Input file '" << f_name << "' not found."); 73 DigraphReader<Digraph>(input, digraph). 74 readArcMap("capacity", length). 75 readNode("source", start). 169 std::istringstream input(test_lgf); 170 digraphReader(input, digraph). 171 arcMap("capacity", length). 172 node("source", source). 76 173 run(); 77 174 78 175 { 79 std::cout << "Checking Bin Heap" << std::endl;80 81 176 typedef BinHeap<Prio, ItemIntMap> IntHeap; 82 177 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 83 heapSortTest<IntHeap>( 100);84 heapIncreaseTest<IntHeap>( 100);178 heapSortTest<IntHeap>(); 179 heapIncreaseTest<IntHeap>(); 85 180 86 typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap; 87 checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>(); 88 Timer timer; 89 dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start); 90 std::cout << timer << std::endl; 91 } 92 { 93 std::cout << "Checking Fib Heap" << std::endl; 94 95 typedef FibHeap<Prio, ItemIntMap> IntHeap; 96 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 97 heapSortTest<IntHeap>(100); 98 heapIncreaseTest<IntHeap>(100); 99 100 typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap; 101 checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>(); 102 Timer timer; 103 dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start); 104 std::cout << timer << std::endl; 105 } 106 { 107 std::cout << "Checking Radix Heap" << std::endl; 108 109 typedef RadixHeap<ItemIntMap> IntHeap; 110 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 111 heapSortTest<IntHeap>(100); 112 heapIncreaseTest<IntHeap>(100); 113 114 typedef RadixHeap<Digraph::NodeMap<int> > NodeHeap; 115 checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>(); 116 Timer timer; 117 dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start); 118 std::cout << timer << std::endl; 119 } 120 121 { 122 std::cout << "Checking Bucket Heap" << std::endl; 123 124 typedef BucketHeap<ItemIntMap> IntHeap; 125 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>(); 126 heapSortTest<IntHeap>(100); 127 heapIncreaseTest<IntHeap>(100); 128 129 typedef BucketHeap<Digraph::NodeMap<int> > NodeHeap; 130 checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>(); 131 Timer timer; 132 dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start); 133 std::cout << timer << std::endl; 181 typedef BinHeap<Prio, IntNodeMap > NodeHeap; 182 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>(); 183 dijkstraHeapTest<NodeHeap>(digraph, length, source); 134 184 } 135 185
Note: See TracChangeset
for help on using the changeset viewer.