1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/jacint/bin_heap.hh Thu Mar 11 18:17:20 2004 +0000
1.3 @@ -0,0 +1,232 @@
1.4 +/* FIXME: Copyright ...
1.5 + *
1.6 + * This implementation is heavily based on STL's heap functions and
1.7 + * the similar class by Alpar Juttner in IKTA...
1.8 + */
1.9 +
1.10 +/******
1.11 + *
1.12 + * BinHeap<KeyType, ValueType, KeyIntMap, [ValueCompare]>
1.13 + *
1.14 + * Ez az osztaly kulcs-ertek parok tarolasara alkalmas binaris kupacot
1.15 + * valosit meg.
1.16 + * A kupacban legfolul mindig az a par talalhato, amiben az _ertek_ a
1.17 + * legkisebb. (Gondolj a Dijkstra pont-tavolsag kupacara; igazabol ahhoz
1.18 + * lett keszitve...)
1.19 + *
1.20 + * Megjegyzes: egy kicsit gyanus nekem, hogy a kupacos temakorben nem
1.21 + * azt hivjak kulcsnak, amit most en annak nevezek. :) En olyan
1.22 + * property_map -os ertelemben hasznalom.
1.23 + *
1.24 + * A hasznalatahoz szukseg van egy irhato/olvashato property_map-re, ami
1.25 + * a kulcsokhoz egy int-et tud tarolni (ezzel tudom megkeresni az illeto
1.26 + * elemet a kupacban a csokkentes es hasonlo muveletekhez).
1.27 + * A map-re csak referenciat tarol, ugy hogy a kupac elete folyan a map-nek
1.28 + * is elnie kell. (???)
1.29 + *
1.30 + * Ketfele modon hasznalhato:
1.31 + * Lusta mod:
1.32 + * put(Key, Value) metodussal pakolunk a kupacba,
1.33 + * aztan o majd eldonti, hogy ez az elem mar benne van-e es ha igen, akkor
1.34 + * csokkentettunk-e rajta, vagy noveltunk.
1.35 + * Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
1.36 + * minden szobajovo kulcs ertekre, -1 -es ertekkel!
1.37 + * Es ilyen esetben a kulcsokrol lekerdezheto az allapotuk a state metodussal:
1.38 + * (nem jart meg a kupacban PRE_HEAP=-1, epp a kupacban van IN_HEAP=0,
1.39 + * mar kikerult a kupacbol POST_HEAP=-2).
1.40 + * Szoval ebben a modban a kupac nagyjabol hasznalhato property_map-kent, csak
1.41 + * meg meg tudja mondani a "legkisebb" erteku elemet. De csak nagyjabol,
1.42 + * hiszen a kupacbol kikerult elemeknek elvesz az ertekuk...
1.43 + *
1.44 + * Kozvetlen mod:
1.45 + * push(Key, Value) metodussal belerakunk a kupacba (ha az illeto kulcs mar
1.46 + * benn volt, akkor gaz).
1.47 + * increase/decrease(Key k, Value new_value) metodusokkal lehet
1.48 + * novelni/csokkenteni az illeto kulcshoz tartozo erteket. (Ha nem volt meg
1.49 + * benne a kupacban az illeto kulcs, vagy nem abba az iranyba valtoztattad
1.50 + * az erteket, amerre mondtad -- gaz).
1.51 + *
1.52 + * Termeszetesen a fenti ket modot ertelemszeruen lehet keverni.
1.53 + * Ja es mindig nagyon gaz, ha belepiszkalsz a map-be, amit a kupac
1.54 + * hasznal. :-))
1.55 + *
1.56 + *
1.57 + * Bocs, most faradt vagyok, majd egyszer leforditom. (Misi)
1.58 + *
1.59 + */
1.60 +
1.61 +
1.62 +#ifndef BIN_HEAP_HH
1.63 +#define BIN_HEAP_HH
1.64 +
1.65 +#include <vector>
1.66 +#include <utility>
1.67 +#include <functional>
1.68 +
1.69 +namespace hugo {
1.70 +
1.71 + template <typename Key, typename Val, typename KeyIntMap,
1.72 + typename Compare = std::less<Val> >
1.73 + class BinHeap {
1.74 +
1.75 + public:
1.76 + typedef Key KeyType;
1.77 + // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
1.78 + typedef Val ValueType;
1.79 + typedef std::pair<KeyType,ValueType> PairType;
1.80 + typedef KeyIntMap KeyIntMapType;
1.81 + typedef Compare ValueCompare;
1.82 +
1.83 + /**
1.84 + * Each Key element have a state associated to it. It may be "in heap",
1.85 + * "pre heap" or "post heap". The later two are indifferent from the
1.86 + * heap's point of view, but may be useful to the user.
1.87 + *
1.88 + * The KeyIntMap _should_ be initialized in such way, that it maps
1.89 + * PRE_HEAP (-1) to any element to be put in the heap...
1.90 + */
1.91 + enum state_enum {
1.92 + IN_HEAP = 0,
1.93 + PRE_HEAP = -1,
1.94 + POST_HEAP = -2
1.95 + };
1.96 +
1.97 + private:
1.98 + std::vector<PairType> data;
1.99 + Compare comp;
1.100 + // FIXME: jo ez igy???
1.101 + KeyIntMap &kim;
1.102 +
1.103 + public:
1.104 + BinHeap(KeyIntMap &_kim) : kim(_kim) {}
1.105 + BinHeap(KeyIntMap &_kim, const Compare &_comp) : comp(_comp), kim(_kim) {}
1.106 +
1.107 +
1.108 + int size() const { return data.size(); }
1.109 + bool empty() const { return data.empty(); }
1.110 +
1.111 + private:
1.112 + static int parent(int i) { return (i-1)/2; }
1.113 + static int second_child(int i) { return 2*i+2; }
1.114 + bool less(const PairType &p1, const PairType &p2) {
1.115 + return comp(p1.second, p2.second);
1.116 + }
1.117 +
1.118 + int bubble_up(int hole, PairType p);
1.119 + int bubble_down(int hole, PairType p, int length);
1.120 +
1.121 + void move(const PairType &p, int i) {
1.122 + data[i] = p;
1.123 + kim.set(p.first, i);
1.124 + }
1.125 +
1.126 + void rmidx(int h) {
1.127 + int n = data.size()-1;
1.128 + if( h>=0 && h<=n ) {
1.129 + kim.set(data[h].first, POST_HEAP);
1.130 + if ( h<n ) {
1.131 + bubble_down(h, data[n], n);
1.132 + }
1.133 + data.pop_back();
1.134 + }
1.135 + }
1.136 +
1.137 + public:
1.138 + void push(const PairType &p) {
1.139 + int n = data.size();
1.140 + data.resize(n+1);
1.141 + bubble_up(n, p);
1.142 + }
1.143 + void push(const Key &k, const Val &v) { push(PairType(k,v)); }
1.144 +
1.145 + Key top() const {
1.146 + // FIXME: test size>0 ?
1.147 + return data[0].first;
1.148 + }
1.149 + Val topValue() const {
1.150 + // FIXME: test size>0 ?
1.151 + return data[0].second;
1.152 + }
1.153 +
1.154 + void pop() {
1.155 + rmidx(0);
1.156 + }
1.157 +
1.158 + void erase(const Key &k) {
1.159 + rmidx(kim.get(k));
1.160 + }
1.161 +
1.162 + const Val get(const Key &k) const {
1.163 + int idx = kim.get(k);
1.164 + return data[idx].second;
1.165 + }
1.166 + void put(const Key &k, const Val &v) {
1.167 + int idx = kim.get(k);
1.168 + if( idx < 0 ) {
1.169 + push(k,v);
1.170 + }
1.171 + else if( comp(v, data[idx].second) ) {
1.172 + bubble_up(idx, PairType(k,v));
1.173 + }
1.174 + else {
1.175 + bubble_down(idx, PairType(k,v), data.size());
1.176 + }
1.177 + }
1.178 +
1.179 + void decrease(const Key &k, const Val &v) {
1.180 + int idx = kim.get(k);
1.181 + bubble_up(idx, PairType(k,v));
1.182 + }
1.183 + void increase(const Key &k, const Val &v) {
1.184 + int idx = kim.get(k);
1.185 + bubble_down(idx, PairType(k,v), data.size());
1.186 + }
1.187 +
1.188 + state_enum state(const Key &k) const {
1.189 + int s = kim.get(k);
1.190 + if( s>=0 )
1.191 + s=0;
1.192 + return state_enum(s);
1.193 + }
1.194 +
1.195 + }; // class BinHeap
1.196 +
1.197 +
1.198 + template <typename K, typename V, typename M, typename C>
1.199 + int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
1.200 + int par = parent(hole);
1.201 + while( hole>0 && less(p,data[par]) ) {
1.202 + move(data[par],hole);
1.203 + hole = par;
1.204 + par = parent(hole);
1.205 + }
1.206 + move(p, hole);
1.207 + return hole;
1.208 + }
1.209 +
1.210 + template <typename K, typename V, typename M, typename C>
1.211 + int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
1.212 + int child = second_child(hole);
1.213 + while(child < length) {
1.214 + if( less(data[child-1], data[child]) ) {
1.215 + --child;
1.216 + }
1.217 + if( !less(data[child], p) )
1.218 + goto ok;
1.219 + move(data[child], hole);
1.220 + hole = child;
1.221 + child = second_child(hole);
1.222 + }
1.223 + child--;
1.224 + if( child<length && less(data[child], p) ) {
1.225 + move(data[child], hole);
1.226 + hole=child;
1.227 + }
1.228 + ok:
1.229 + move(p, hole);
1.230 + return hole;
1.231 + }
1.232 +
1.233 +} // namespace hugo
1.234 +
1.235 +#endif // BIN_HEAP_HH
2.1 --- a/src/work/jacint/dijkstra.cc Thu Mar 11 15:57:17 2004 +0000
2.2 +++ b/src/work/jacint/dijkstra.cc Thu Mar 11 18:17:20 2004 +0000
2.3 @@ -6,11 +6,15 @@
2.4 #include <dijkstra.h>
2.5 #include <time_measure.h>
2.6
2.7 +#include <bin_heap.hh>
2.8 +#include <fib_heap.h>
2.9 +
2.10 using namespace hugo;
2.11
2.12 int main(int, char **) {
2.13 typedef ListGraph::NodeIt NodeIt;
2.14 - typedef ListGraph::EachEdgeIt EachEdgeIt;
2.15 + typedef ListGraph::EachNodeIt EachNodeIt;
2.16 + typedef ListGraph::InEdgeIt InEdgeIt;
2.17
2.18 ListGraph G;
2.19 NodeIt s, t;
2.20 @@ -20,24 +24,65 @@
2.21 std::cout << "dijkstra demo ..." << std::endl;
2.22
2.23 double pre_time=currTime();
2.24 - Dijkstra<ListGraph, int> dijkstra_test(G, s, cap);
2.25 + Dijkstra<ListGraph, int, FibHeap<ListGraph::NodeIt, int,
2.26 + ListGraph::NodeMap<int> > > dijkstra_test(G, s, cap);
2.27 dijkstra_test.run();
2.28 double post_time=currTime();
2.29
2.30 - std::cout << "running time: " << post_time-pre_time << " sec"<< std::endl;
2.31 + std::cout << "running time with fib_heap: "
2.32 + << post_time-pre_time << " sec"<< std::endl;
2.33
2.34 - int hiba=0;
2.35 - EachEdgeIt e;
2.36 - for ( G.getFirst(e) ; G.valid(e); G.next(e) ) {
2.37 - NodeIt u=G.tail(e);
2.38 - NodeIt v=G.head(e);
2.39 - if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap.get(e) ) {
2.40 - std::cout<<"Hiba: "<<dijkstra_test.dist(v) - dijkstra_test.dist(u) - cap.get(e)<<std::endl;
2.41 - ++hiba;
2.42 + pre_time=currTime();
2.43 + Dijkstra<ListGraph, int, BinHeap<ListGraph::NodeIt, int,
2.44 + ListGraph::NodeMap<int> > > dijkstra_test2(G, s, cap);
2.45 + dijkstra_test2.run();
2.46 + post_time=currTime();
2.47 +
2.48 + std::cout << "running time with bin_heap: "
2.49 + << post_time-pre_time << " sec"<< std::endl;
2.50 +
2.51 +
2.52 + int hiba_fib=0;
2.53 + int hiba_bin=0;
2.54 + EachNodeIt u;
2.55 + for ( G.getFirst(u) ; G.valid(u); G.next(u) ) {
2.56 + InEdgeIt e;
2.57 + for ( G.getFirst(e,u); G.valid(e); G.next(e) ) {
2.58 + NodeIt v=G.tail(e);
2.59 + if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap.get(e) )
2.60 + {
2.61 + std::cout<<"Hibas el a fibonaccis Dijkstraban: "
2.62 + << dijkstra_test.dist(u) - dijkstra_test.dist(v) -
2.63 + cap.get(e)<<std::endl;
2.64 + ++hiba_fib;
2.65 + }
2.66 + if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap.get(e) )
2.67 + {
2.68 + std::cout<<"Hibas el a binarisos Dijkstraban: "
2.69 + << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) -
2.70 + cap.get(e)<<std::endl;
2.71 + ++hiba_bin;
2.72 + }
2.73 + if ( e==dijkstra_test.pred(u) &&
2.74 + dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap.get(e) )
2.75 + {
2.76 + std::cout<<"Hibas fael a fibonaccis Dijkstraban!"<<std::endl;
2.77 + ++hiba_fib;
2.78 + }
2.79 + if ( e==dijkstra_test2.pred(u) &&
2.80 + dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap.get(e) )
2.81 + {
2.82 + std::cout<<"Hibas fael a binarisos Dijkstraban!"<<std::endl;
2.83 + ++hiba_bin;
2.84 + }
2.85 }
2.86 }
2.87
2.88 - std::cout << "Hibas elek szama: " << hiba << " a " << G.edgeNum() <<"-bol."<< std::endl;
2.89 + std::cout << "Hibas elek szama a fibonaccis Dijkstraban: "
2.90 + << hiba_fib << " a " << G.edgeNum() <<"-bol."<< std::endl;
2.91 +
2.92 + std::cout << "Hibas elek szama a binarisos Dijkstraban: "
2.93 + << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl;
2.94
2.95 return 0;
2.96 }
3.1 --- a/src/work/jacint/dijkstra.h Thu Mar 11 15:57:17 2004 +0000
3.2 +++ b/src/work/jacint/dijkstra.h Thu Mar 11 18:17:20 2004 +0000
3.3 @@ -1,4 +1,8 @@
3.4 // -*- C++ -*-
3.5 +
3.6 +//ha predecessor az elejen nem invalid, akkor hagyd csak ugy
3.7 +//scanned mutatja hogy jo ertek van-e benne vagy szemet
3.8 +
3.9 /*
3.10 *template <Graph, T, Heap=FibHeap>
3.11 *
3.12 @@ -24,8 +28,8 @@
3.13 *
3.14 */
3.15
3.16 -#ifndef DIJKSTRA_HH
3.17 -#define DIJKSTRA_HH
3.18 +#ifndef DIJKSTRA_H
3.19 +#define DIJKSTRA_H
3.20
3.21 #include <fib_heap.h>
3.22
4.1 --- a/src/work/jacint/makefile Thu Mar 11 15:57:17 2004 +0000
4.2 +++ b/src/work/jacint/makefile Thu Mar 11 18:17:20 2004 +0000
4.3 @@ -16,6 +16,9 @@
4.4 dijkstra:
4.5 $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -o dijkstra dijkstra.cc
4.6
4.7 +prim:
4.8 + $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -o prim prim.cc
4.9 +
4.10 clean:
4.11 $(RM) *.o $(BINARIES) .depend
4.12