Changeset 173:de9849252e78 in lemon-0.x
- Timestamp:
- 03/12/04 00:31:13 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@246
- Location:
- src/work/jacint
- Files:
-
- 2 added
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/jacint/dijkstra.cc
r170 r173 67 67 dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap.get(e) ) 68 68 { 69 std::cout<<"Hibas fael a fibonaccis Dijkstraban!"<<std::endl; 69 std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<< 70 dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap.get(e)<<std::endl; 70 71 ++hiba_fib; 71 72 } … … 73 74 dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap.get(e) ) 74 75 { 75 std::cout<<"Hibas fael a binarisos Dijkstraban!"<<std::endl; 76 std::cout<<"Hibas fael a binarisos Dijkstraban: "<< 77 dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap.get(e)<<std::endl; 76 78 ++hiba_bin; 77 79 } 78 80 } 79 } 81 82 if ( dijkstra_test.dist(u) != dijkstra_test2.dist(u) ) 83 std::cout << "Nem egyezik meg a tavolsag!"<<std::endl; 84 85 86 } 80 87 81 88 std::cout << "Hibas elek szama a fibonaccis Dijkstraban: " … … 85 92 << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl; 86 93 94 95 96 87 97 return 0; 88 98 } -
src/work/jacint/fib_heap.h
r167 r173 22 22 * mustn't be in the heap. 23 23 * 24 *Item top() : returns the Item with least Prio 24 *Item top() : returns the Item with least Prio. 25 * Must be called only if heap is nonempty. 25 26 * 26 27 *Prio prio() : returns the least Prio 27 * 28 * Must be called only if heap is nonempty. 29 * 28 30 *Prio get(Item) : returns Prio of Item 31 * Must be called only if Item is in heap. 29 32 * 30 33 *void pop() : deletes the Item with least Prio … … 66 69 std::vector<store> container; 67 70 int minimum; 68 bool blank;69 71 ItemIntMap &iimap; 70 72 Compare comp; 73 int num_items; 71 74 72 75 enum state_enum { … … 78 81 public : 79 82 80 FibHeap(ItemIntMap &_iimap) : minimum(), blank(true), iimap(_iimap) {}83 FibHeap(ItemIntMap &_iimap) : minimum(), iimap(_iimap), num_items() {} 81 84 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(), 82 blank(true), iimap(_iimap), comp(_comp) {}85 iimap(_iimap), comp(_comp), num_items() {} 83 86 84 87 85 88 int size() const { 86 int s=0; 87 for ( unsigned int i=0; i!=container.size(); ++i ) 88 if ( container[i].in ) ++s; 89 return s; 90 } 91 92 93 bool empty() const { return blank; } 89 return num_items; 90 } 91 92 93 bool empty() const { return num_items==0; } 94 94 95 95 … … 97 97 int i=iimap.get(it); 98 98 if ( i >= 0 && container[i].in ) { 99 if ( !comp(container[i].prio, value) ) decrease(it, value);99 if ( comp(value, container[i].prio) ) decrease(it, value); 100 100 if ( comp(container[i].prio, value) ) increase(it, value); 101 101 } else push(it, value); … … 119 119 } 120 120 121 if ( !blank) {121 if ( num_items ) { 122 122 container[container[minimum].right_neighbor].left_neighbor=i; 123 123 container[i].right_neighbor=container[minimum].right_neighbor; 124 124 container[minimum].right_neighbor=i; 125 125 container[i].left_neighbor=minimum; 126 if ( !comp( container[minimum].prio, value) ) minimum=i;126 if ( comp( value, container[minimum].prio) ) minimum=i; 127 127 } else { 128 128 container[i].right_neighbor=container[i].left_neighbor=i; 129 129 minimum=i; 130 blank=false;131 130 } 132 131 container[i].prio=value; 132 ++num_items; 133 133 } 134 134 135 135 136 136 Item top() const { 137 if ( !blank ) { 138 return container[minimum].name; 139 } else { 140 return Item(); 141 } 137 return container[minimum].name; 142 138 } 143 139 144 140 145 141 PrioType prio() const { 146 if ( !blank ) { 147 return container[minimum].prio; 148 } else { 149 return PrioType(); 150 } 142 return container[minimum].prio; 151 143 } 152 144 153 145 154 146 const PrioType get(const Item& it) const { 155 int i=iimap.get(it); 156 157 if ( i >= 0 && container[i].in ) { 158 return container[i].prio; 159 } else { 160 return PrioType(); 161 } 162 } 163 164 147 return container[iimap.get(it)].prio; 148 } 165 149 166 150 … … 169 153 if ( container[minimum].left_neighbor==minimum ) { 170 154 container[minimum].in=false; 171 if ( container[minimum].degree==0 ) blank=true; 172 else { 155 if ( container[minimum].degree!=0 ) { 173 156 makeroot(container[minimum].child); 174 157 minimum=container[minimum].child; 175 158 balance(); 176 } 159 } 177 160 } else { 178 161 int right=container[minimum].right_neighbor; … … 194 177 balance(); 195 178 } // the case where there are more roots 179 --num_items; 196 180 } 197 181 … … 200 184 int i=iimap.get(it); 201 185 202 if ( i >= 0 && container[i].in ) { 203 204 if ( container[i].parent!=-1 ) { 205 int p=container[i].parent; 206 cut(i,p); 207 cascade(p); 208 minimum=i; //As if its prio would be -infinity 209 } 210 pop(); 211 } 212 } 186 if ( i >= 0 && container[i].in ) { 187 if ( container[i].parent!=-1 ) { 188 int p=container[i].parent; 189 cut(i,p); 190 cascade(p); 191 } 192 minimum=i; //As if its prio would be -infinity 193 pop(); 194 } 195 } 213 196 214 197 … … 221 204 cut(i,p); 222 205 cascade(p); 223 if ( comp(value, container[minimum].prio) ) minimum=i;224 }206 } 207 if ( comp(value, container[minimum].prio) ) minimum=i; 225 208 } 226 209 … … 311 294 312 295 313 /*Lacing ito the roots.*/296 /*Lacing a to the roots.*/ 314 297 int right=container[minimum].right_neighbor; 315 298 container[minimum].right_neighbor=a; … … 393 376 } //namespace hugo 394 377 #endif 395 396 397 398 399 400 -
src/work/jacint/makefile
r170 r173 4 4 LEDAROOT = /ledasrc/LEDA-4.1 5 5 6 BINARIES = dijkstra6 BINARIES = prim 7 7 8 8 all: $(BINARIES)
Note: See TracChangeset
for help on using the changeset viewer.