1.1 --- a/src/work/jacint/bin_heap.hh Sat Mar 20 16:10:26 2004 +0000
1.2 +++ b/src/work/jacint/bin_heap.hh Sat Mar 20 16:13:19 2004 +0000
1.3 @@ -153,15 +153,16 @@
1.4 }
1.5
1.6 void erase(const Key &k) {
1.7 - rmidx(kim.get(k));
1.8 + rmidx(kim[k]);
1.9 }
1.10
1.11 - const Val get(const Key &k) const {
1.12 - int idx = kim.get(k);
1.13 + Val operator[](const Key &k) const {
1.14 + int idx = kim[k];
1.15 return data[idx].second;
1.16 }
1.17 +
1.18 void put(const Key &k, const Val &v) {
1.19 - int idx = kim.get(k);
1.20 + int idx = kim[k];
1.21 if( idx < 0 ) {
1.22 push(k,v);
1.23 }
1.24 @@ -174,16 +175,16 @@
1.25 }
1.26
1.27 void decrease(const Key &k, const Val &v) {
1.28 - int idx = kim.get(k);
1.29 + int idx = kim[k];
1.30 bubble_up(idx, PairType(k,v));
1.31 }
1.32 void increase(const Key &k, const Val &v) {
1.33 - int idx = kim.get(k);
1.34 + int idx = kim[k];
1.35 bubble_down(idx, PairType(k,v), data.size());
1.36 }
1.37
1.38 state_enum state(const Key &k) const {
1.39 - int s = kim.get(k);
1.40 + int s = kim[k];
1.41 if( s>=0 )
1.42 s=0;
1.43 return state_enum(s);
2.1 --- a/src/work/jacint/dijkstra.cc Sat Mar 20 16:10:26 2004 +0000
2.2 +++ b/src/work/jacint/dijkstra.cc Sat Mar 20 16:13:19 2004 +0000
2.3 @@ -25,12 +25,12 @@
2.4 std::cout << "dijkstra demo ..." << std::endl;
2.5
2.6 double pre_time=currTime();
2.7 - Dijkstra<SmartGraph, int, FibHeap<SmartGraph::Node, int,
2.8 + Dijkstra<SmartGraph, int, FibHeap<SmartGraph::Node, int,
2.9 SmartGraph::NodeMap<int> > > dijkstra_test(G, cap);
2.10 - dijkstra_test.run(s);
2.11 + dijkstra_test.run(s);
2.12 double post_time=currTime();
2.13
2.14 - std::cout << "running time with fib_heap: "
2.15 + std::cout << "running time with fib_heap: "
2.16 << post_time-pre_time << " sec"<< std::endl;
2.17
2.18 pre_time=currTime();
2.19 @@ -50,32 +50,32 @@
2.20 InEdgeIt e;
2.21 for ( G.first(e,u); G.valid(e); G.next(e) ) {
2.22 Node v=G.tail(e);
2.23 - if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap.get(e) )
2.24 + if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap[e] )
2.25 {
2.26 std::cout<<"Hibas el a fibonaccis Dijkstraban: "
2.27 << dijkstra_test.dist(u) - dijkstra_test.dist(v) -
2.28 - cap.get(e)<<std::endl;
2.29 + cap[e]<<std::endl;
2.30 ++hiba_fib;
2.31 }
2.32 - if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap.get(e) )
2.33 + if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap[e] )
2.34 {
2.35 std::cout<<"Hibas el a binarisos Dijkstraban: "
2.36 << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) -
2.37 - cap.get(e)<<std::endl;
2.38 + cap[e]<<std::endl;
2.39 ++hiba_bin;
2.40 }
2.41 if ( e==dijkstra_test.pred(u) &&
2.42 - dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap.get(e) )
2.43 + dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap[e] )
2.44 {
2.45 std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<<
2.46 - dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap.get(e)<<std::endl;
2.47 + dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap[e]<<std::endl;
2.48 ++hiba_fib;
2.49 }
2.50 if ( e==dijkstra_test2.pred(u) &&
2.51 - dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap.get(e) )
2.52 + dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap[e] )
2.53 {
2.54 std::cout<<"Hibas fael a binarisos Dijkstraban: "<<
2.55 - dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap.get(e)<<std::endl;
2.56 + dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap[e]<<std::endl;
2.57 ++hiba_bin;
2.58 }
2.59 }
3.1 --- a/src/work/jacint/dijkstra.h Sat Mar 20 16:10:26 2004 +0000
3.2 +++ b/src/work/jacint/dijkstra.h Sat Mar 20 16:13:19 2004 +0000
3.3 @@ -45,7 +45,9 @@
3.4 const LengthMap& length;
3.5 typename Graph::NodeMap<Edge> predecessor;
3.6 typename Graph::NodeMap<T> distance;
3.7 + //FIXME:
3.8 typename Graph::NodeMap<bool> reach;
3.9 + //typename Graph::NodeMap<int> reach;
3.10
3.11 public :
3.12
3.13 @@ -65,7 +67,9 @@
3.14 reach.set(u,false);
3.15 }
3.16
3.17 + //FIXME:
3.18 typename Graph::NodeMap<bool> scanned(G,false);
3.19 + //typename Graph::NodeMap<int> scanned(G,false);
3.20 typename Graph::NodeMap<int> heap_map(G,-1);
3.21
3.22 Heap heap(heap_map);
3.23 @@ -76,7 +80,7 @@
3.24 while ( !heap.empty() ) {
3.25
3.26 Node v=heap.top();
3.27 - T oldvalue=heap.get(v);
3.28 + T oldvalue=heap[v];
3.29 heap.pop();
3.30 distance.set(v, oldvalue);
3.31 scanned.set(v,true);
3.32 @@ -90,26 +94,23 @@
3.33 reach.set(w,true);
3.34 heap.push(w,oldvalue+length[e]);
3.35 predecessor.set(w,e);
3.36 - } else if ( oldvalue+length[e] < heap.get(w) ) {
3.37 + } else if ( oldvalue+length[e] < heap[w] ) {
3.38 predecessor.set(w,e);
3.39 heap.decrease(w, oldvalue+length[e]);
3.40 }
3.41 }
3.42 }
3.43 }
3.44 - }
3.45 + }
3.46
3.47 -
3.48 T dist(Node v) {
3.49 return distance[v];
3.50 }
3.51
3.52 -
3.53 Edge pred(Node v) {
3.54 return predecessor[v];
3.55 }
3.56
3.57 -
3.58 bool reached(Node v) {
3.59 return reach[v];
3.60 }
4.1 --- a/src/work/jacint/fib_heap.h Sat Mar 20 16:10:26 2004 +0000
4.2 +++ b/src/work/jacint/fib_heap.h Sat Mar 20 16:13:19 2004 +0000
4.3 @@ -94,7 +94,7 @@
4.4
4.5
4.6 void set (Item const it, PrioType const value) {
4.7 - int i=iimap.get(it);
4.8 + int i=iimap[it];
4.9 if ( i >= 0 && container[i].in ) {
4.10 if ( comp(value, container[i].prio) ) decrease(it, value);
4.11 if ( comp(container[i].prio, value) ) increase(it, value);
4.12 @@ -103,7 +103,7 @@
4.13
4.14
4.15 void push (Item const it, PrioType const value) {
4.16 - int i=iimap.get(it);
4.17 + int i=iimap[it];
4.18 if ( i < 0 ) {
4.19 int s=container.size();
4.20 iimap.set( it, s );
4.21 @@ -145,19 +145,17 @@
4.22
4.23
4.24
4.25 - PrioType& operator[](const Item& it) const {
4.26 - return container[iimap.get(it)].prio;
4.27 + PrioType& operator[](const Item& it) {
4.28 + return container[iimap[it]].prio;
4.29 }
4.30
4.31 const PrioType& operator[](const Item& it) const {
4.32 - return container[iimap.get(it)].prio;
4.33 + return container[iimap[it]].prio;
4.34 }
4.35
4.36 - const PrioType get(const Item& it) const {
4.37 - return container[iimap.get(it)].prio;
4.38 - }
4.39 -
4.40 -
4.41 +// const PrioType get(const Item& it) const {
4.42 +// return container[iimap[it]].prio;
4.43 +// }
4.44
4.45 void pop() {
4.46 /*The first case is that there are only one root.*/
4.47 @@ -192,7 +190,7 @@
4.48
4.49
4.50 void erase (const Item& it) {
4.51 - int i=iimap.get(it);
4.52 + int i=iimap[it];
4.53
4.54 if ( i >= 0 && container[i].in ) {
4.55 if ( container[i].parent!=-1 ) {
4.56 @@ -207,7 +205,7 @@
4.57
4.58
4.59 void decrease (Item it, PrioType const value) {
4.60 - int i=iimap.get(it);
4.61 + int i=iimap[it];
4.62 container[i].prio=value;
4.63 int p=container[i].parent;
4.64
4.65 @@ -226,7 +224,7 @@
4.66
4.67
4.68 state_enum state(const Item &it) const {
4.69 - int i=iimap.get(it);
4.70 + int i=iimap[it];
4.71 if( i>=0 ) {
4.72 if ( container[i].in ) i=0;
4.73 else i=-2;