Changeset 217:fc549fac0dd0 in lemon0.x
 Timestamp:
 03/20/04 17:13:19 (21 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@312
 Location:
 src/work/jacint
 Files:

 4 edited
Legend:
 Unmodified
 Added
 Removed

src/work/jacint/bin_heap.hh
r170 r217 154 154 155 155 void erase(const Key &k) { 156 rmidx(kim .get(k));157 } 158 159 const Val get(const Key &k) const {160 int idx = kim .get(k);156 rmidx(kim[k]); 157 } 158 159 Val operator[](const Key &k) const { 160 int idx = kim[k]; 161 161 return data[idx].second; 162 162 } 163 163 164 void put(const Key &k, const Val &v) { 164 int idx = kim .get(k);165 int idx = kim[k]; 165 166 if( idx < 0 ) { 166 167 push(k,v); … … 175 176 176 177 void decrease(const Key &k, const Val &v) { 177 int idx = kim .get(k);178 int idx = kim[k]; 178 179 bubble_up(idx, PairType(k,v)); 179 180 } 180 181 void increase(const Key &k, const Val &v) { 181 int idx = kim .get(k);182 int idx = kim[k]; 182 183 bubble_down(idx, PairType(k,v), data.size()); 183 184 } 184 185 185 186 state_enum state(const Key &k) const { 186 int s = kim .get(k);187 int s = kim[k]; 187 188 if( s>=0 ) 188 189 s=0; 
src/work/jacint/dijkstra.cc
r211 r217 26 26 27 27 double pre_time=currTime(); 28 28 Dijkstra<SmartGraph, int, FibHeap<SmartGraph::Node, int, 29 29 SmartGraph::NodeMap<int> > > dijkstra_test(G, cap); 30 30 dijkstra_test.run(s); 31 31 double post_time=currTime(); 32 32 33 std::cout << "running time with fib_heap: "33 std::cout << "running time with fib_heap: " 34 34 << post_timepre_time << " sec"<< std::endl; 35 35 … … 51 51 for ( G.first(e,u); G.valid(e); G.next(e) ) { 52 52 Node v=G.tail(e); 53 if ( dijkstra_test.dist(u)  dijkstra_test.dist(v) > cap .get(e))53 if ( dijkstra_test.dist(u)  dijkstra_test.dist(v) > cap[e] ) 54 54 { 55 55 std::cout<<"Hibas el a fibonaccis Dijkstraban: " 56 56 << dijkstra_test.dist(u)  dijkstra_test.dist(v)  57 cap .get(e)<<std::endl;57 cap[e]<<std::endl; 58 58 ++hiba_fib; 59 59 } 60 if ( dijkstra_test2.dist(u)  dijkstra_test2.dist(v) > cap .get(e))60 if ( dijkstra_test2.dist(u)  dijkstra_test2.dist(v) > cap[e] ) 61 61 { 62 62 std::cout<<"Hibas el a binarisos Dijkstraban: " 63 63 << dijkstra_test2.dist(u)  dijkstra_test2.dist(v)  64 cap .get(e)<<std::endl;64 cap[e]<<std::endl; 65 65 ++hiba_bin; 66 66 } 67 67 if ( e==dijkstra_test.pred(u) && 68 dijkstra_test.dist(u)  dijkstra_test.dist(v) != cap .get(e))68 dijkstra_test.dist(u)  dijkstra_test.dist(v) != cap[e] ) 69 69 { 70 70 std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<< 71 dijkstra_test.dist(u)  dijkstra_test.dist(v) cap .get(e)<<std::endl;71 dijkstra_test.dist(u)  dijkstra_test.dist(v) cap[e]<<std::endl; 72 72 ++hiba_fib; 73 73 } 74 74 if ( e==dijkstra_test2.pred(u) && 75 dijkstra_test2.dist(u)  dijkstra_test2.dist(v) != cap .get(e))75 dijkstra_test2.dist(u)  dijkstra_test2.dist(v) != cap[e] ) 76 76 { 77 77 std::cout<<"Hibas fael a binarisos Dijkstraban: "<< 78 dijkstra_test2.dist(u)  dijkstra_test2.dist(v) cap .get(e)<<std::endl;78 dijkstra_test2.dist(u)  dijkstra_test2.dist(v) cap[e]<<std::endl; 79 79 ++hiba_bin; 80 80 } 
src/work/jacint/dijkstra.h
r211 r217 46 46 typename Graph::NodeMap<Edge> predecessor; 47 47 typename Graph::NodeMap<T> distance; 48 //FIXME: 48 49 typename Graph::NodeMap<bool> reach; 50 //typename Graph::NodeMap<int> reach; 49 51 50 52 public : … … 66 68 } 67 69 70 //FIXME: 68 71 typename Graph::NodeMap<bool> scanned(G,false); 72 //typename Graph::NodeMap<int> scanned(G,false); 69 73 typename Graph::NodeMap<int> heap_map(G,1); 70 74 … … 77 81 78 82 Node v=heap.top(); 79 T oldvalue=heap .get(v);83 T oldvalue=heap[v]; 80 84 heap.pop(); 81 85 distance.set(v, oldvalue); … … 91 95 heap.push(w,oldvalue+length[e]); 92 96 predecessor.set(w,e); 93 } else if ( oldvalue+length[e] < heap .get(w)) {97 } else if ( oldvalue+length[e] < heap[w] ) { 94 98 predecessor.set(w,e); 95 99 heap.decrease(w, oldvalue+length[e]); … … 98 102 } 99 103 } 100 } 104 } 101 105 102 103 106 T dist(Node v) { 104 107 return distance[v]; 105 108 } 106 107 109 108 110 Edge pred(Node v) { … … 110 112 } 111 113 112 113 114 bool reached(Node v) { 114 115 return reach[v]; 
src/work/jacint/fib_heap.h
r211 r217 95 95 96 96 void set (Item const it, PrioType const value) { 97 int i=iimap .get(it);97 int i=iimap[it]; 98 98 if ( i >= 0 && container[i].in ) { 99 99 if ( comp(value, container[i].prio) ) decrease(it, value); … … 104 104 105 105 void push (Item const it, PrioType const value) { 106 int i=iimap .get(it);106 int i=iimap[it]; 107 107 if ( i < 0 ) { 108 108 int s=container.size(); … … 146 146 147 147 148 PrioType& operator[](const Item& it) const{149 return container[iimap .get(it)].prio;148 PrioType& operator[](const Item& it) { 149 return container[iimap[it]].prio; 150 150 } 151 151 152 152 const PrioType& operator[](const Item& it) const { 153 return container[iimap.get(it)].prio; 154 } 155 156 const PrioType get(const Item& it) const { 157 return container[iimap.get(it)].prio; 158 } 159 160 153 return container[iimap[it]].prio; 154 } 155 156 // const PrioType get(const Item& it) const { 157 // return container[iimap[it]].prio; 158 // } 161 159 162 160 void pop() { … … 193 191 194 192 void erase (const Item& it) { 195 int i=iimap .get(it);193 int i=iimap[it]; 196 194 197 195 if ( i >= 0 && container[i].in ) { … … 208 206 209 207 void decrease (Item it, PrioType const value) { 210 int i=iimap .get(it);208 int i=iimap[it]; 211 209 container[i].prio=value; 212 210 int p=container[i].parent; … … 227 225 228 226 state_enum state(const Item &it) const { 229 int i=iimap .get(it);227 int i=iimap[it]; 230 228 if( i>=0 ) { 231 229 if ( container[i].in ) i=0;
Note: See TracChangeset
for help on using the changeset viewer.