1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/alpar/dijkstra/bin_heap.hh Sat Mar 20 21:38:16 2004 +0000
1.3 @@ -0,0 +1,235 @@
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 + ///\todo it is used nowhere
1.92 + ///
1.93 + enum state_enum {
1.94 + IN_HEAP = 0,
1.95 + PRE_HEAP = -1,
1.96 + POST_HEAP = -2
1.97 + };
1.98 +
1.99 + private:
1.100 + std::vector<PairType> data;
1.101 + Compare comp;
1.102 + // FIXME: jo ez igy???
1.103 + KeyIntMap &kim;
1.104 +
1.105 + public:
1.106 + BinHeap(KeyIntMap &_kim) : kim(_kim) {}
1.107 + BinHeap(KeyIntMap &_kim, const Compare &_comp) : comp(_comp), kim(_kim) {}
1.108 +
1.109 +
1.110 + int size() const { return data.size(); }
1.111 + bool empty() const { return data.empty(); }
1.112 +
1.113 + private:
1.114 + static int parent(int i) { return (i-1)/2; }
1.115 + static int second_child(int i) { return 2*i+2; }
1.116 + bool less(const PairType &p1, const PairType &p2) {
1.117 + return comp(p1.second, p2.second);
1.118 + }
1.119 +
1.120 + int bubble_up(int hole, PairType p);
1.121 + int bubble_down(int hole, PairType p, int length);
1.122 +
1.123 + void move(const PairType &p, int i) {
1.124 + data[i] = p;
1.125 + kim.set(p.first, i);
1.126 + }
1.127 +
1.128 + void rmidx(int h) {
1.129 + int n = data.size()-1;
1.130 + if( h>=0 && h<=n ) {
1.131 + kim.set(data[h].first, POST_HEAP);
1.132 + if ( h<n ) {
1.133 + bubble_down(h, data[n], n);
1.134 + }
1.135 + data.pop_back();
1.136 + }
1.137 + }
1.138 +
1.139 + public:
1.140 + void push(const PairType &p) {
1.141 + int n = data.size();
1.142 + data.resize(n+1);
1.143 + bubble_up(n, p);
1.144 + }
1.145 + void push(const Key &k, const Val &v) { push(PairType(k,v)); }
1.146 +
1.147 + Key top() const {
1.148 + // FIXME: test size>0 ?
1.149 + return data[0].first;
1.150 + }
1.151 + Val topValue() const {
1.152 + // FIXME: test size>0 ?
1.153 + return data[0].second;
1.154 + }
1.155 +
1.156 + void pop() {
1.157 + rmidx(0);
1.158 + }
1.159 +
1.160 + void erase(const Key &k) {
1.161 + rmidx(kim[k]);
1.162 + }
1.163 +
1.164 + Val operator[](const Key &k) const {
1.165 + int idx = kim[k];
1.166 + return data[idx].second;
1.167 + }
1.168 +
1.169 + void put(const Key &k, const Val &v) {
1.170 + int idx = kim[k];
1.171 + if( idx < 0 ) {
1.172 + push(k,v);
1.173 + }
1.174 + else if( comp(v, data[idx].second) ) {
1.175 + bubble_up(idx, PairType(k,v));
1.176 + }
1.177 + else {
1.178 + bubble_down(idx, PairType(k,v), data.size());
1.179 + }
1.180 + }
1.181 +
1.182 + void decrease(const Key &k, const Val &v) {
1.183 + int idx = kim[k];
1.184 + bubble_up(idx, PairType(k,v));
1.185 + }
1.186 + void increase(const Key &k, const Val &v) {
1.187 + int idx = kim[k];
1.188 + bubble_down(idx, PairType(k,v), data.size());
1.189 + }
1.190 +
1.191 + state_enum state(const Key &k) const {
1.192 + int s = kim[k];
1.193 + if( s>=0 )
1.194 + s=0;
1.195 + return state_enum(s);
1.196 + }
1.197 +
1.198 + }; // class BinHeap
1.199 +
1.200 +
1.201 + template <typename K, typename V, typename M, typename C>
1.202 + int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
1.203 + int par = parent(hole);
1.204 + while( hole>0 && less(p,data[par]) ) {
1.205 + move(data[par],hole);
1.206 + hole = par;
1.207 + par = parent(hole);
1.208 + }
1.209 + move(p, hole);
1.210 + return hole;
1.211 + }
1.212 +
1.213 + template <typename K, typename V, typename M, typename C>
1.214 + int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
1.215 + int child = second_child(hole);
1.216 + while(child < length) {
1.217 + if( less(data[child-1], data[child]) ) {
1.218 + --child;
1.219 + }
1.220 + if( !less(data[child], p) )
1.221 + goto ok;
1.222 + move(data[child], hole);
1.223 + hole = child;
1.224 + child = second_child(hole);
1.225 + }
1.226 + child--;
1.227 + if( child<length && less(data[child], p) ) {
1.228 + move(data[child], hole);
1.229 + hole=child;
1.230 + }
1.231 + ok:
1.232 + move(p, hole);
1.233 + return hole;
1.234 + }
1.235 +
1.236 +} // namespace hugo
1.237 +
1.238 +#endif // BIN_HEAP_HH
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/alpar/dijkstra/dijkstra.cc Sat Mar 20 21:38:16 2004 +0000
2.3 @@ -0,0 +1,114 @@
2.4 +#include <iostream>
2.5 +#include <fstream>
2.6 +
2.7 +#include <smart_graph.h>
2.8 +#include <list_graph.h>
2.9 +#include <dimacs.h>
2.10 +#include <dijkstra.h>
2.11 +#include <time_measure.h>
2.12 +
2.13 +#include <bin_heap.hh>
2.14 +#include <fib_heap.h>
2.15 +
2.16 +using namespace hugo;
2.17 +
2.18 +int main(int, char **) {
2.19 + typedef SmartGraph::Node Node;
2.20 + typedef SmartGraph::NodeIt NodeIt;
2.21 + typedef SmartGraph::InEdgeIt InEdgeIt;
2.22 +
2.23 + SmartGraph G;
2.24 + Node s, t;
2.25 + SmartGraph::EdgeMap<int> cap(G);
2.26 + Timer tim;
2.27 + std::cout << "DIMACS load ..." << std::endl;
2.28 + readDimacsMaxFlow(std::cin, G, s, t, cap);
2.29 + std::cout << " " << tim <<std::endl;
2.30 +
2.31 + std::cout << "dijkstra demo ..." << std::endl;
2.32 +
2.33 + //double pre_time=currTime();
2.34 + tim.reset();
2.35 + Dijkstra <SmartGraph,
2.36 + SmartGraph::EdgeMap<int>,
2.37 + FibHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> >
2.38 + > dijkstra_test(G, cap);
2.39 +
2.40 + dijkstra_test.run(s);
2.41 + //double post_time=currTime();
2.42 +
2.43 + std::cout << "running time with fib_heap: "
2.44 + // << post_time-pre_time << " sec"
2.45 + << tim
2.46 + << std::endl;
2.47 +
2.48 + //pre_time=currTime();
2.49 + tim.reset();
2.50 + Dijkstra < SmartGraph,
2.51 + SmartGraph::EdgeMap<int>,
2.52 + BinHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> > >
2.53 + dijkstra_test2(G, cap);
2.54 +
2.55 + dijkstra_test2.run(s);
2.56 + //post_time=currTime();
2.57 +
2.58 + std::cout << "running time with bin_heap: "
2.59 + // << post_time-pre_time << " sec"
2.60 + << tim
2.61 + << std::endl;
2.62 +
2.63 +
2.64 + int hiba_fib=0;
2.65 + int hiba_bin=0;
2.66 + NodeIt u;
2.67 + for ( G.first(u) ; G.valid(u); G.next(u) ) {
2.68 + InEdgeIt e;
2.69 + for ( G.first(e,u); G.valid(e); G.next(e) ) {
2.70 + Node v=G.tail(e);
2.71 + if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap[e] )
2.72 + {
2.73 + std::cout<<"Hibas el a fibonaccis Dijkstraban: "
2.74 + << dijkstra_test.dist(u) - dijkstra_test.dist(v) -
2.75 + cap[e]<<std::endl;
2.76 + ++hiba_fib;
2.77 + }
2.78 + if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap[e] )
2.79 + {
2.80 + std::cout<<"Hibas el a binarisos Dijkstraban: "
2.81 + << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) -
2.82 + cap[e]<<std::endl;
2.83 + ++hiba_bin;
2.84 + }
2.85 + if ( e==dijkstra_test.pred(u) &&
2.86 + dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap[e] )
2.87 + {
2.88 + std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<<
2.89 + dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap[e]<<std::endl;
2.90 + ++hiba_fib;
2.91 + }
2.92 + if ( e==dijkstra_test2.pred(u) &&
2.93 + dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap[e] )
2.94 + {
2.95 + std::cout<<"Hibas fael a binarisos Dijkstraban: "<<
2.96 + dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap[e]<<std::endl;
2.97 + ++hiba_bin;
2.98 + }
2.99 + }
2.100 +
2.101 + if ( dijkstra_test.dist(u) != dijkstra_test2.dist(u) )
2.102 + std::cout << "Nem egyezik meg a tavolsag!"<<std::endl;
2.103 +
2.104 +
2.105 + }
2.106 +
2.107 + std::cout << "Hibas elek szama a fibonaccis Dijkstraban: "
2.108 + << hiba_fib << " a " << G.edgeNum() <<"-bol."<< std::endl;
2.109 +
2.110 + std::cout << "Hibas elek szama a binarisos Dijkstraban: "
2.111 + << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl;
2.112 +
2.113 +
2.114 +
2.115 +
2.116 + return 0;
2.117 +}
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/alpar/dijkstra/dijkstra.h Sat Mar 20 21:38:16 2004 +0000
3.3 @@ -0,0 +1,150 @@
3.4 +// -*- C++ -*-
3.5 +/*
3.6 + *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
3.7 + *
3.8 + *Constructor:
3.9 + *
3.10 + *Dijkstra(Graph G, LengthMap length)
3.11 + *
3.12 + *
3.13 + *Methods:
3.14 + *
3.15 + *void run(Node s)
3.16 + *
3.17 + *T dist(Node v) : After run(s) was run, it returns the distance from s to v.
3.18 + * Returns T() if v is not reachable from s.
3.19 + *
3.20 + *Edge pred(Node v) : After run(s) was run, it returns the last
3.21 + * edge of a shortest s-v path. It is INVALID for s and for
3.22 + * the nodes not reachable from s.
3.23 + *
3.24 + *bool reached(Node v) : After run(s) was run, it is true iff v is
3.25 + * reachable from s
3.26 + *
3.27 + */
3.28 +
3.29 +#ifndef HUGO_DIJKSTRA_H
3.30 +#define HUGO_DIJKSTRA_H
3.31 +
3.32 +#include <fib_heap.h>
3.33 +#include <invalid.h>
3.34 +
3.35 +namespace hugo {
3.36 +
3.37 + //Alpar: Changed the order of the parameters
3.38 + template <typename Graph,
3.39 + typename LengthMap=typename Graph::EdgeMap<int>,
3.40 + typename Heap=FibHeap<typename Graph::Node,
3.41 + typename LengthMap::ValueType,
3.42 + typename Graph::NodeMap<int> > >
3.43 + class Dijkstra{
3.44 + public:
3.45 + typedef typename LengthMap::ValueType ValueType;
3.46 +
3.47 + private:
3.48 + typedef typename Graph::Node Node;
3.49 + typedef typename Graph::NodeIt NodeIt;
3.50 + typedef typename Graph::Edge Edge;
3.51 + typedef typename Graph::OutEdgeIt OutEdgeIt;
3.52 +
3.53 + const Graph& G;
3.54 + const LengthMap& length;
3.55 + typedef typename Graph::NodeMap<Edge> PredMap;
3.56 + PredMap predecessor;
3.57 + //In place of reach:
3.58 + typedef typename Graph::NodeMap<Node> PredNodeMap;
3.59 + PredNodeMap pred_node;
3.60 + typedef typename Graph::NodeMap<ValueType> DistMap;
3.61 + DistMap distance;
3.62 + //I don't like this:
3.63 + // //FIXME:
3.64 + // typename Graph::NodeMap<bool> reach;
3.65 + // //typename Graph::NodeMap<int> reach;
3.66 +
3.67 + public :
3.68 +
3.69 + /*
3.70 + The distance of the nodes is 0.
3.71 + */
3.72 + Dijkstra(Graph& _G, LengthMap& _length) :
3.73 + G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
3.74 +
3.75 +
3.76 + void run(Node s);
3.77 +
3.78 + ValueType dist(Node v) const { return distance[v]; }
3.79 + Edge pred(Node v) const { return predecessor[v]; }
3.80 + Node predNode(Node v) const { return pred_node[v]; }
3.81 +
3.82 + const DistMap &distMap() const { return distance;}
3.83 + const PredMap &predMap() const { return predecessor;}
3.84 + const PredNodeMap &predNodeMap() const { return pred_node;}
3.85 +
3.86 + // bool reached(Node v) { return reach[v]; }
3.87 + ///\warning \c s is not reached!
3.88 + ///
3.89 + bool reached(Node v) { return G.valid(predecessor[v]); }
3.90 +
3.91 + };
3.92 +
3.93 +
3.94 + // IMPLEMENTATIONS
3.95 +
3.96 + template <typename Graph, typename LengthMap, typename Heap >
3.97 + void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
3.98 +
3.99 + NodeIt u;
3.100 + for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
3.101 + predecessor.set(u,INVALID);
3.102 + // If a node is unreacheable, then why should be the dist=0?
3.103 + // distance.set(u,0);
3.104 + // reach.set(u,false);
3.105 + }
3.106 +
3.107 + //We don't need it at all.
3.108 + // //FIXME:
3.109 + // typename Graph::NodeMap<bool> scanned(G,false);
3.110 + // //typename Graph::NodeMap<int> scanned(G,false);
3.111 + typename Graph::NodeMap<int> heap_map(G,-1);
3.112 +
3.113 + Heap heap(heap_map);
3.114 +
3.115 + heap.push(s,0);
3.116 + // reach.set(s, true);
3.117 +
3.118 + while ( !heap.empty() ) {
3.119 +
3.120 + Node v=heap.top();
3.121 + ValueType oldvalue=heap[v];
3.122 + heap.pop();
3.123 + distance.set(v, oldvalue);
3.124 +
3.125 + for(OutEdgeIt e(G,v); G.valid(e); G.next(e)) {
3.126 + Node w=G.head(e);
3.127 +
3.128 + switch(heap.state(w)) {
3.129 + case Heap::PRE_HEAP:
3.130 + // reach.set(w,true);
3.131 + heap.push(w,oldvalue+length[e]);
3.132 + predecessor.set(w,e);
3.133 + pred_node.set(w,v);
3.134 + break;
3.135 + case Heap::IN_HEAP:
3.136 + if ( oldvalue+length[e] < heap[w] ) {
3.137 + heap.decrease(w, oldvalue+length[e]);
3.138 + predecessor.set(w,e);
3.139 + pred_node.set(w,v);
3.140 + }
3.141 + break;
3.142 + case Heap::POST_HEAP:
3.143 + break;
3.144 + }
3.145 + }
3.146 + }
3.147 + }
3.148 +
3.149 +} //END OF NAMESPACE HUGO
3.150 +
3.151 +#endif
3.152 +
3.153 +
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/work/alpar/dijkstra/fib_heap.h Sat Mar 20 21:38:16 2004 +0000
4.3 @@ -0,0 +1,389 @@
4.4 +// -*- C++ -*-
4.5 +/*
4.6 + *template <typename Item,
4.7 + * typename Prio,
4.8 + * typename ItemIntMap,
4.9 + * typename Compare = std::less<Prio> >
4.10 + *
4.11 + *constructors:
4.12 + *
4.13 + *FibHeap(ItemIntMap), FibHeap(ItemIntMap, Compare)
4.14 + *
4.15 + *Member functions:
4.16 + *
4.17 + *int size() : returns the number of elements in the heap
4.18 + *
4.19 + *bool empty() : true iff size()=0
4.20 + *
4.21 + *void set(Item, Prio) : calls push(Item, Prio) if Item is not
4.22 + * in the heap, and calls decrease/increase(Item, Prio) otherwise
4.23 + *
4.24 + *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item
4.25 + * mustn't be in the heap.
4.26 + *
4.27 + *Item top() : returns the Item with least Prio.
4.28 + * Must be called only if heap is nonempty.
4.29 + *
4.30 + *Prio prio() : returns the least Prio
4.31 + * Must be called only if heap is nonempty.
4.32 + *
4.33 + *Prio get(Item) : returns Prio of Item
4.34 + * Must be called only if Item is in heap.
4.35 + *
4.36 + *void pop() : deletes the Item with least Prio
4.37 + *
4.38 + *void erase(Item) : deletes Item from the heap if it was already there
4.39 + *
4.40 + *void decrease(Item, P) : decreases prio of Item to P.
4.41 + * Item must be in the heap with prio at least P.
4.42 + *
4.43 + *void increase(Item, P) : sets prio of Item to P.
4.44 + *
4.45 + *state_enum state(Item) : returns PRE_HEAP if Item has not been in the
4.46 + * heap until now, IN_HEAP if it is in the heap at the moment, and
4.47 + * POST_HEAP otherwise. In the latter case it is possible that Item
4.48 + * will get back to the heap again.
4.49 + *
4.50 + *In Fibonacci heaps, increase and erase are not efficient, in case of
4.51 + *many calls to these operations, it is better to use bin_heap.
4.52 + */
4.53 +
4.54 +#ifndef FIB_HEAP_H
4.55 +#define FIB_HEAP_H
4.56 +
4.57 +#include <vector>
4.58 +#include <functional>
4.59 +#include <math.h>
4.60 +
4.61 +namespace hugo {
4.62 +
4.63 + template <typename Item, typename Prio, typename ItemIntMap,
4.64 + typename Compare = std::less<Prio> >
4.65 +
4.66 + class FibHeap {
4.67 +
4.68 + typedef Prio PrioType;
4.69 +
4.70 + class store;
4.71 +
4.72 + std::vector<store> container;
4.73 + int minimum;
4.74 + ItemIntMap &iimap;
4.75 + Compare comp;
4.76 + int num_items;
4.77 +
4.78 + ///\todo It is use nowhere
4.79 + ///\todo It doesn't conforms to the naming conventions.
4.80 + public:
4.81 + enum state_enum {
4.82 + IN_HEAP = 0,
4.83 + PRE_HEAP = -1,
4.84 + POST_HEAP = -2
4.85 + };
4.86 +
4.87 + public :
4.88 +
4.89 + FibHeap(ItemIntMap &_iimap) : minimum(), iimap(_iimap), num_items() {}
4.90 + FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(),
4.91 + iimap(_iimap), comp(_comp), num_items() {}
4.92 +
4.93 +
4.94 + int size() const {
4.95 + return num_items;
4.96 + }
4.97 +
4.98 +
4.99 + bool empty() const { return num_items==0; }
4.100 +
4.101 +
4.102 + void set (Item const it, PrioType const value) {
4.103 + int i=iimap[it];
4.104 + if ( i >= 0 && container[i].in ) {
4.105 + if ( comp(value, container[i].prio) ) decrease(it, value);
4.106 + if ( comp(container[i].prio, value) ) increase(it, value);
4.107 + } else push(it, value);
4.108 + }
4.109 +
4.110 +
4.111 + void push (Item const it, PrioType const value) {
4.112 + int i=iimap[it];
4.113 + if ( i < 0 ) {
4.114 + int s=container.size();
4.115 + iimap.set( it, s );
4.116 + store st;
4.117 + st.name=it;
4.118 + container.push_back(st);
4.119 + i=s;
4.120 + } else {
4.121 + container[i].parent=container[i].child=-1;
4.122 + container[i].degree=0;
4.123 + container[i].in=true;
4.124 + container[i].marked=false;
4.125 + }
4.126 +
4.127 + if ( num_items ) {
4.128 + container[container[minimum].right_neighbor].left_neighbor=i;
4.129 + container[i].right_neighbor=container[minimum].right_neighbor;
4.130 + container[minimum].right_neighbor=i;
4.131 + container[i].left_neighbor=minimum;
4.132 + if ( comp( value, container[minimum].prio) ) minimum=i;
4.133 + } else {
4.134 + container[i].right_neighbor=container[i].left_neighbor=i;
4.135 + minimum=i;
4.136 + }
4.137 + container[i].prio=value;
4.138 + ++num_items;
4.139 + }
4.140 +
4.141 +
4.142 + Item top() const {
4.143 + return container[minimum].name;
4.144 + }
4.145 +
4.146 +
4.147 + PrioType prio() const {
4.148 + return container[minimum].prio;
4.149 + }
4.150 +
4.151 +
4.152 +
4.153 +
4.154 + PrioType& operator[](const Item& it) {
4.155 + return container[iimap[it]].prio;
4.156 + }
4.157 +
4.158 + const PrioType& operator[](const Item& it) const {
4.159 + return container[iimap[it]].prio;
4.160 + }
4.161 +
4.162 +// const PrioType get(const Item& it) const {
4.163 +// return container[iimap[it]].prio;
4.164 +// }
4.165 +
4.166 + void pop() {
4.167 + /*The first case is that there are only one root.*/
4.168 + if ( container[minimum].left_neighbor==minimum ) {
4.169 + container[minimum].in=false;
4.170 + if ( container[minimum].degree!=0 ) {
4.171 + makeroot(container[minimum].child);
4.172 + minimum=container[minimum].child;
4.173 + balance();
4.174 + }
4.175 + } else {
4.176 + int right=container[minimum].right_neighbor;
4.177 + unlace(minimum);
4.178 + container[minimum].in=false;
4.179 + if ( container[minimum].degree > 0 ) {
4.180 + int left=container[minimum].left_neighbor;
4.181 + int child=container[minimum].child;
4.182 + int last_child=container[child].left_neighbor;
4.183 +
4.184 + makeroot(child);
4.185 +
4.186 + container[left].right_neighbor=child;
4.187 + container[child].left_neighbor=left;
4.188 + container[right].left_neighbor=last_child;
4.189 + container[last_child].right_neighbor=right;
4.190 + }
4.191 + minimum=right;
4.192 + balance();
4.193 + } // the case where there are more roots
4.194 + --num_items;
4.195 + }
4.196 +
4.197 +
4.198 + void erase (const Item& it) {
4.199 + int i=iimap[it];
4.200 +
4.201 + if ( i >= 0 && container[i].in ) {
4.202 + if ( container[i].parent!=-1 ) {
4.203 + int p=container[i].parent;
4.204 + cut(i,p);
4.205 + cascade(p);
4.206 + }
4.207 + minimum=i; //As if its prio would be -infinity
4.208 + pop();
4.209 + }
4.210 + }
4.211 +
4.212 +
4.213 + void decrease (Item it, PrioType const value) {
4.214 + int i=iimap[it];
4.215 + container[i].prio=value;
4.216 + int p=container[i].parent;
4.217 +
4.218 + if ( p!=-1 && comp(value, container[p].prio) ) {
4.219 + cut(i,p);
4.220 + cascade(p);
4.221 + }
4.222 + if ( comp(value, container[minimum].prio) ) minimum=i;
4.223 + }
4.224 +
4.225 +
4.226 + void increase (Item it, PrioType const value) {
4.227 + erase(it);
4.228 + push(it, value);
4.229 + }
4.230 +
4.231 +
4.232 + state_enum state(const Item &it) const {
4.233 + int i=iimap[it];
4.234 + if( i>=0 ) {
4.235 + if ( container[i].in ) i=0;
4.236 + else i=-2;
4.237 + }
4.238 + return state_enum(i);
4.239 + }
4.240 +
4.241 +
4.242 + private:
4.243 +
4.244 + void balance() {
4.245 +
4.246 + int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
4.247 +
4.248 + std::vector<int> A(maxdeg,-1);
4.249 +
4.250 + /*
4.251 + *Recall that now minimum does not point to the minimum prio element.
4.252 + *We set minimum to this during balance().
4.253 + */
4.254 + int anchor=container[minimum].left_neighbor;
4.255 + int next=minimum;
4.256 + bool end=false;
4.257 +
4.258 + do {
4.259 + int active=next;
4.260 + if ( anchor==active ) end=true;
4.261 + int d=container[active].degree;
4.262 + next=container[active].right_neighbor;
4.263 +
4.264 + while (A[d]!=-1) {
4.265 + if( comp(container[active].prio, container[A[d]].prio) ) {
4.266 + fuse(active,A[d]);
4.267 + } else {
4.268 + fuse(A[d],active);
4.269 + active=A[d];
4.270 + }
4.271 + A[d]=-1;
4.272 + ++d;
4.273 + }
4.274 + A[d]=active;
4.275 + } while ( !end );
4.276 +
4.277 +
4.278 + while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
4.279 + int s=minimum;
4.280 + int m=minimum;
4.281 + do {
4.282 + if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
4.283 + s=container[s].right_neighbor;
4.284 + } while ( s != m );
4.285 + }
4.286 +
4.287 +
4.288 + void makeroot (int c) {
4.289 + int s=c;
4.290 + do {
4.291 + container[s].parent=-1;
4.292 + s=container[s].right_neighbor;
4.293 + } while ( s != c );
4.294 + }
4.295 +
4.296 +
4.297 + void cut (int a, int b) {
4.298 + /*
4.299 + *Replacing a from the children of b.
4.300 + */
4.301 + --container[b].degree;
4.302 +
4.303 + if ( container[b].degree !=0 ) {
4.304 + int child=container[b].child;
4.305 + if ( child==a )
4.306 + container[b].child=container[child].right_neighbor;
4.307 + unlace(a);
4.308 + }
4.309 +
4.310 +
4.311 + /*Lacing a to the roots.*/
4.312 + int right=container[minimum].right_neighbor;
4.313 + container[minimum].right_neighbor=a;
4.314 + container[a].left_neighbor=minimum;
4.315 + container[a].right_neighbor=right;
4.316 + container[right].left_neighbor=a;
4.317 +
4.318 + container[a].parent=-1;
4.319 + container[a].marked=false;
4.320 + }
4.321 +
4.322 +
4.323 + void cascade (int a)
4.324 + {
4.325 + if ( container[a].parent!=-1 ) {
4.326 + int p=container[a].parent;
4.327 +
4.328 + if ( container[a].marked==false ) container[a].marked=true;
4.329 + else {
4.330 + cut(a,p);
4.331 + cascade(p);
4.332 + }
4.333 + }
4.334 + }
4.335 +
4.336 +
4.337 + void fuse (int a, int b) {
4.338 + unlace(b);
4.339 +
4.340 + /*Lacing b under a.*/
4.341 + container[b].parent=a;
4.342 +
4.343 + if (container[a].degree==0) {
4.344 + container[b].left_neighbor=b;
4.345 + container[b].right_neighbor=b;
4.346 + container[a].child=b;
4.347 + } else {
4.348 + int child=container[a].child;
4.349 + int last_child=container[child].left_neighbor;
4.350 + container[child].left_neighbor=b;
4.351 + container[b].right_neighbor=child;
4.352 + container[last_child].right_neighbor=b;
4.353 + container[b].left_neighbor=last_child;
4.354 + }
4.355 +
4.356 + ++container[a].degree;
4.357 +
4.358 + container[b].marked=false;
4.359 + }
4.360 +
4.361 +
4.362 + /*
4.363 + *It is invoked only if a has siblings.
4.364 + */
4.365 + void unlace (int a) {
4.366 + int leftn=container[a].left_neighbor;
4.367 + int rightn=container[a].right_neighbor;
4.368 + container[leftn].right_neighbor=rightn;
4.369 + container[rightn].left_neighbor=leftn;
4.370 + }
4.371 +
4.372 +
4.373 + class store {
4.374 + friend class FibHeap;
4.375 +
4.376 + Item name;
4.377 + int parent;
4.378 + int left_neighbor;
4.379 + int right_neighbor;
4.380 + int child;
4.381 + int degree;
4.382 + bool marked;
4.383 + bool in;
4.384 + PrioType prio;
4.385 +
4.386 + store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
4.387 + };
4.388 +
4.389 + };
4.390 +
4.391 +} //namespace hugo
4.392 +#endif
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/src/work/alpar/dijkstra/makefile Sat Mar 20 21:38:16 2004 +0000
5.3 @@ -0,0 +1,19 @@
5.4 +CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
5.5 +CXX2 = g++-2.95
5.6 +CXXFLAGS = -W -Wall -ansi -pedantic
5.7 +LEDAROOT ?= /ledasrc/LEDA-4.1
5.8 +
5.9 +BINARIES = dijkstra prim preflow
5.10 +
5.11 +all: $(BINARIES)
5.12 +
5.13 +makefile: .depend
5.14 +sinclude .depend
5.15 +
5.16 +dijkstra:
5.17 + $(CXX3) $(CXXFLAGS) -O3 -I. -I../../jacint -I../.. -I../../marci -I../../alpar -o dijkstra dijkstra.cc
5.18 +
5.19 +clean:
5.20 + $(RM) *.o $(BINARIES) .depend
5.21 +
5.22 +.PHONY: all clean dep depend