Changeset 209:765619b7cbb2 in lemon1.2 for test/heap_test.cc
 Timestamp:
 07/13/08 20:51:02 (12 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

test/heap_test.cc
r203 r209 1 /* * C++*1 /* * mode: C++; indenttabsmode: nil; * 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 20032008 … … 41 41 DIGRAPH_TYPEDEFS(Digraph); 42 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" 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 79 "source 3\n"; 80 80 … … 89 89 90 90 Heap heap(map); 91 91 92 92 std::vector<int> v(test_len); 93 93 … … 108 108 109 109 Heap heap(map); 110 110 111 111 std::vector<int> v(test_len); 112 112 … … 129 129 130 130 template <typename Heap> 131 void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length, 132 133 131 void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length, 132 Node source) { 133 134 134 typename Dijkstra<Digraph, IntArcMap>::template DefStandardHeap<Heap>:: 135 135 Create dijkstra(digraph, length); … … 138 138 139 139 for(ArcIt a(digraph); a != INVALID; ++a) { 140 Node s = digraph.source(a); 140 Node s = digraph.source(a); 141 141 Node t = digraph.target(a); 142 142 if (dijkstra.reached(s)) { 143 143 check( dijkstra.dist(t)  dijkstra.dist(s) <= length[a], 144 144 "Error in a shortest path tree!"); 145 145 } 146 146 } … … 151 151 Node s = digraph.source(a); 152 152 check( dijkstra.dist(n)  dijkstra.dist(s) == length[a], 153 153 "Error in a shortest path tree!"); 154 154 } 155 155 } … … 162 162 typedef int Prio; 163 163 typedef RangeMap<int> ItemIntMap; 164 164 165 165 Digraph digraph; 166 166 IntArcMap length(digraph); … … 171 171 arcMap("capacity", length). 172 172 node("source", source). 173 run(); 174 173 run(); 174 175 175 { 176 176 typedef BinHeap<Prio, ItemIntMap> IntHeap; … … 178 178 heapSortTest<IntHeap>(); 179 179 heapIncreaseTest<IntHeap>(); 180 180 181 181 typedef BinHeap<Prio, IntNodeMap > NodeHeap; 182 182 checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
Note: See TracChangeset
for help on using the changeset viewer.