1.1 --- a/src/include/dijkstra.h Thu Apr 22 14:11:28 2004 +0000
1.2 +++ b/src/include/dijkstra.h Thu Apr 22 14:50:24 2004 +0000
1.3 @@ -1,29 +1,5 @@
1.4 // -*- C++ -*-
1.5
1.6 -/*
1.7 - *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
1.8 - *
1.9 - *Constructor:
1.10 - *
1.11 - *Dijkstra(Graph G, LengthMap length)
1.12 - *
1.13 - *
1.14 - *Methods:
1.15 - *
1.16 - *void run(Node s)
1.17 - *
1.18 - *T dist(Node v) : After run(s) was run, it returns the distance from s to v.
1.19 - * Returns T() if v is not reachable from s.
1.20 - *
1.21 - *Edge pred(Node v) : After run(s) was run, it returns the last
1.22 - * edge of a shortest s-v path. It is INVALID for s and for
1.23 - * the nodes not reachable from s.
1.24 - *
1.25 - *bool reached(Node v) : After run(s) was run, it is true iff v is
1.26 - * reachable from s
1.27 - *
1.28 - */
1.29 -
1.30 #ifndef HUGO_DIJKSTRA_H
1.31 #define HUGO_DIJKSTRA_H
1.32
1.33 @@ -36,8 +12,6 @@
1.34
1.35 namespace hugo {
1.36
1.37 - //Alpar: Changed the order of the parameters
1.38 -
1.39 ///%Dijkstra algorithm class.
1.40
1.41 ///This class provides an efficient implementation of %Dijkstra algorithm.
1.42 @@ -49,17 +23,14 @@
1.43 ///
1.44 ///It is also possible to change the underlying priority heap.
1.45 ///
1.46 - ///\param Graph The graph type the algorithm runs on.
1.47 - ///\param LengthMap This read-only
1.48 - ///EdgeMap
1.49 - ///determines the
1.50 - ///lengths of the edges. It is read once for each edge, so the map
1.51 - ///may involve in relatively time consuming process to compute the edge
1.52 - ///length if it is necessary. The default map type is
1.53 - ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
1.54 - ///\param Heap The heap type used by the %Dijkstra
1.55 - ///algorithm. The default
1.56 - ///is using \ref BinHeap "binary heap".
1.57 + ///\param Graph The graph type the algorithm runs on.
1.58 + ///\param LengthMap This read-only EdgeMap determines the lengths of
1.59 + ///the edges. It is read once for each edge, so the map may involve
1.60 + ///in relatively time consuming process to compute the edge length
1.61 + ///if it is necessary. The default map type is \ref
1.62 + ///GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
1.63 + ///\param Heap The heap type used by the %Dijkstra algorithm. The
1.64 + ///default is using \ref BinHeap "binary heap".
1.65
1.66 #ifdef DOXYGEN
1.67 template <typename Graph,
1.68 @@ -103,6 +74,7 @@
1.69 ///\warning If node \c v in unreachable from the source the return value
1.70 ///of this funcion is undefined.
1.71 ValueType dist(Node v) const { return distance[v]; }
1.72 +
1.73 ///Returns the edges of the shortest path tree.
1.74
1.75 ///For a node \c v it returns the last edge of the shortest path
1.76 @@ -110,6 +82,7 @@
1.77 ///from the source.
1.78 ///\pre \ref run() must be called before using this function.
1.79 Edge pred(Node v) const { return predecessor[v]; }
1.80 +
1.81 ///Returns the nodes of the shortest paths.
1.82
1.83 ///For a node \c v it returns the last but one node of the shortest path
1.84 @@ -123,12 +96,14 @@
1.85 ///\pre \ref run() must be called before using this function.
1.86 ///
1.87 const DistMap &distMap() const { return distance;}
1.88 +
1.89 ///Returns a reference to the shortest path tree map.
1.90
1.91 ///Returns a reference to the NodeMap of the edges of the
1.92 ///shortest path tree.
1.93 ///\pre \ref run() must be called before using this function.
1.94 const PredMap &predMap() const { return predecessor;}
1.95 +
1.96 ///Returns a reference to the map of nodes of shortest paths.
1.97
1.98 ///Returns a reference to the NodeMap of the last but one nodes of the
1.99 @@ -142,7 +117,6 @@
1.100 ///\warning the source node is reported to be unreached!
1.101 ///\todo Is this what we want?
1.102 ///\pre \ref run() must be called before using this function.
1.103 - ///
1.104 bool reached(Node v) { return G.valid(predecessor[v]); }
1.105
1.106 };
1.107 @@ -152,14 +126,12 @@
1.108 // IMPLEMENTATIONS
1.109 // **********************************************************************
1.110
1.111 - ///Runs %Dijkstra algorithm from node the source.
1.112 + ///Runs %Dijkstra algorithm from source node \c s.
1.113
1.114 ///This method runs the %Dijkstra algorithm from a source node \c s
1.115 - ///in order to
1.116 - ///compute the
1.117 - ///shortest path to each node. The algorithm computes
1.118 - ///- The shortest path tree.
1.119 - ///- The distance of each node from the source.
1.120 + ///in order to compute the shortest path to each node. The algorithm
1.121 + ///computes - The shortest path tree. - The distance of each node
1.122 + ///from the source.
1.123 template <typename Graph, typename LengthMap,
1.124 template<class,class,class> class Heap >
1.125 void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
1.126 @@ -168,28 +140,23 @@
1.127 for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
1.128 predecessor.set(u,INVALID);
1.129 pred_node.set(u,INVALID);
1.130 - // If a node is unreacheable, then why should be the dist=0?
1.131 - // distance.set(u,0);
1.132 - // reach.set(u,false);
1.133 }
1.134
1.135 typename Graph::NodeMap<int> heap_map(G,-1);
1.136
1.137 Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map);
1.138 -
1.139 heap.push(s,0);
1.140
1.141 - while ( !heap.empty() ) {
1.142 + while ( !heap.empty() ) {
1.143 +
1.144 + Node v=heap.top();
1.145 + ValueType oldvalue=heap[v];
1.146 + heap.pop();
1.147 + distance.set(v, oldvalue);
1.148
1.149 - Node v=heap.top();
1.150 - ValueType oldvalue=heap[v];
1.151 - heap.pop();
1.152 - distance.set(v, oldvalue);
1.153 -
1.154 - { //FIXME this bracket is for e to be local
1.155 - OutEdgeIt e;
1.156 - for(G.first(e, v);
1.157 - G.valid(e); G.next(e)) {
1.158 + { //FIXME this bracket is for e to be local
1.159 + OutEdgeIt e;
1.160 + for(G.first(e, v); G.valid(e); G.next(e)) {
1.161 Node w=G.head(e);
1.162
1.163 switch(heap.state(w)) {
1.164 @@ -209,8 +176,8 @@
1.165 break;
1.166 }
1.167 }
1.168 - } //FIXME tis bracket
1.169 - }
1.170 + } //FIXME this bracket
1.171 + }
1.172 }
1.173
1.174 } //END OF NAMESPACE HUGO
2.1 --- a/src/include/fib_heap.h Thu Apr 22 14:11:28 2004 +0000
2.2 +++ b/src/include/fib_heap.h Thu Apr 22 14:50:24 2004 +0000
2.3 @@ -1,55 +1,7 @@
2.4 // -*- C++ -*-
2.5 -/*
2.6 - *template <typename Item,
2.7 - * typename Prio,
2.8 - * typename ItemIntMap,
2.9 - * typename Compare = std::less<Prio> >
2.10 - *
2.11 - *constructors:
2.12 - *
2.13 - *FibHeap(ItemIntMap), FibHeap(ItemIntMap, Compare)
2.14 - *
2.15 - *Member functions:
2.16 - *
2.17 - *int size() : returns the number of elements in the heap
2.18 - *
2.19 - *bool empty() : true iff size()=0
2.20 - *
2.21 - *void set(Item, Prio) : calls push(Item, Prio) if Item is not
2.22 - * in the heap, and calls decrease/increase(Item, Prio) otherwise
2.23 - *
2.24 - *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item
2.25 - * mustn't be in the heap.
2.26 - *
2.27 - *Item top() : returns the Item with least Prio.
2.28 - * Must be called only if heap is nonempty.
2.29 - *
2.30 - *Prio prio() : returns the least Prio
2.31 - * Must be called only if heap is nonempty.
2.32 - *
2.33 - *Prio get(Item) : returns Prio of Item
2.34 - * Must be called only if Item is in heap.
2.35 - *
2.36 - *void pop() : deletes the Item with least Prio
2.37 - *
2.38 - *void erase(Item) : deletes Item from the heap if it was already there
2.39 - *
2.40 - *void decrease(Item, P) : decreases prio of Item to P.
2.41 - * Item must be in the heap with prio at least P.
2.42 - *
2.43 - *void increase(Item, P) : sets prio of Item to P.
2.44 - *
2.45 - *state_enum state(Item) : returns PRE_HEAP if Item has not been in the
2.46 - * heap until now, IN_HEAP if it is in the heap at the moment, and
2.47 - * POST_HEAP otherwise. In the latter case it is possible that Item
2.48 - * will get back to the heap again.
2.49 - *
2.50 - *In Fibonacci heaps, increase and erase are not efficient, in case of
2.51 - *many calls to these operations, it is better to use bin_heap.
2.52 - */
2.53
2.54 -#ifndef FIB_HEAP_H
2.55 -#define FIB_HEAP_H
2.56 +#ifndef HUGO_FIB_HEAP_H
2.57 +#define HUGO_FIB_HEAP_H
2.58
2.59 ///\file
2.60 ///\brief Fibonacci Heap implementation.
2.61 @@ -60,13 +12,44 @@
2.62
2.63 namespace hugo {
2.64
2.65 - /// A Fibonacci Heap implementation.
2.66 - template <typename Item, typename Prio, typename ItemIntMap,
2.67 + /// An implementation of the Fibonacci Heap.
2.68 +
2.69 + /**
2.70 + This class implements the \e Fibonacci \e heap data structure. A \e
2.71 + heap is a data structure for storing items with specified priorities,
2.72 + such that finding the item with minimum priority is efficient. In a
2.73 + heap one can change the priority of an item, and to add or erase an
2.74 + item.
2.75 +
2.76 + The methods \ref increase and \ref erase are not efficient, in
2.77 + case of many calls to these operations, it is better to use
2.78 + a binary heap.
2.79 +
2.80 + /param Item The type of the items to be stored.
2.81 + /param Prio The type of the priority of the items.
2.82 + /param ItemIntMap A read and writable Item int map, for the usage of
2.83 + the heap.
2.84 + /param Compare A class for the comparison of the priorities. The
2.85 + default is \c std::less<Prio>.
2.86 +
2.87 + */
2.88 +
2.89 +#ifdef DOXYGEN
2.90 + template <typename Item,
2.91 + typename Prio,
2.92 + typename ItemIntMap,
2.93 + typename Compare>
2.94 +#else
2.95 + template <typename Item,
2.96 + typename Prio,
2.97 + typename ItemIntMap,
2.98 typename Compare = std::less<Prio> >
2.99 +#endif
2.100 class FibHeap {
2.101 -
2.102 + public:
2.103 typedef Prio PrioType;
2.104
2.105 + private:
2.106 class store;
2.107
2.108 std::vector<store> container;
2.109 @@ -74,7 +57,7 @@
2.110 ItemIntMap &iimap;
2.111 Compare comp;
2.112 int num_items;
2.113 -
2.114 +
2.115 ///\todo It is use nowhere
2.116 ///\todo It doesn't conform to the naming conventions.
2.117 public:
2.118 @@ -86,18 +69,137 @@
2.119
2.120 public :
2.121
2.122 - FibHeap(ItemIntMap &_iimap) : minimum(), iimap(_iimap), num_items() {}
2.123 - FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(),
2.124 + FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {}
2.125 + FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
2.126 iimap(_iimap), comp(_comp), num_items() {}
2.127
2.128 + ///The number of items stored in the heap.
2.129 +
2.130 + /**
2.131 + Returns the number of items stored in the heap.
2.132 + */
2.133 + int size() const { return num_items; }
2.134 +
2.135 + ///Checks if the heap stores no items.
2.136
2.137 - int size() const {
2.138 - return num_items;
2.139 + /**
2.140 + Returns true iff the heap stores no items.
2.141 + */
2.142 + bool empty() const { return num_items==0; }
2.143 +
2.144 + ///Item \c item gets to the heap with priority \c value independently if \c item was already there.
2.145 +
2.146 + /**
2.147 + This method calls \ref push(item, value) if \c item is not
2.148 + stored in the heap, and it calls \ref decrease(it, \c value) or
2.149 + \ref increase(it, \c value) otherwise.
2.150 + */
2.151 + void set (Item const item, PrioType const value); //vigyazat: az implementacioban it van
2.152 +
2.153 + ///Adds \c item to the heap with priority \c value.
2.154 +
2.155 + /**
2.156 + Adds \c item to the heap with priority \c value.
2.157 + \pre \c item must not be stored in the heap.
2.158 + */
2.159 + void push (Item const it, PrioType const value); /*vigyazat: az implementacioban it van*/
2.160 +
2.161 +
2.162 + ///Returns the item having the minimum priority w.r.t. Compare.
2.163 +
2.164 + /**
2.165 + This method returns the item having the minimum priority w.r.t. Compare.
2.166 + \pre The heap must be nonempty.
2.167 + */
2.168 + Item top() const { return container[minimum].name; }
2.169 +
2.170 +
2.171 + ///Returns the minimum priority w.r.t. Compare.
2.172 +
2.173 + /**
2.174 + It returns the minimum priority w.r.t. Compare.
2.175 + \pre The heap must be nonempty.
2.176 + */
2.177 + PrioType prio() const { return container[minimum].prio; }
2.178 +
2.179 +
2.180 + ///Returns the priority of \c item.
2.181 +
2.182 + /**
2.183 + It returns the priority of \c item.
2.184 + \pre \c item must be in the heap.
2.185 + */
2.186 + PrioType& operator[](const Item& it) { return container[iimap[it]].prio; }
2.187 +
2.188 + ///Returns the priority of \c item.
2.189 +
2.190 + /**
2.191 + It returns the priority of \c item.
2.192 + \pre \c item must be in the heap.
2.193 + */
2.194 + const PrioType& operator[](const Item& it) const {
2.195 + return container[iimap[it]].prio;
2.196 }
2.197
2.198
2.199 - bool empty() const { return num_items==0; }
2.200 + ///Deletes the item with minimum priority w.r.t. Compare.
2.201
2.202 + /**
2.203 + This method deletes the item with minimum priority w.r.t.
2.204 + Compare from the heap.
2.205 + \pre The heap must be non-empty.
2.206 + */
2.207 + void pop();
2.208 +
2.209 + ///Deletes \c item from the heap.
2.210 +
2.211 + /**
2.212 + This method deletes \c item from the heap, if \c item was already
2.213 + stored in the heap. It is quite inefficient in Fibonacci heaps.
2.214 + */
2.215 + void erase (const Item& item); /*vigyazat: az implementacioban it van*/
2.216 +
2.217 + ///Decreases the priority of \c item to \c value.
2.218 +
2.219 + /**
2.220 + This method decreases the priority of \c item to \c value.
2.221 + \pre \c item must be stored in the heap with priority at least \c
2.222 + value w.r.t. Compare.
2.223 + */
2.224 + void decrease (Item item, PrioType const value); /*vigyazat: az implementacioban it van*/
2.225 +
2.226 +
2.227 + ///Increases the priority of \c item to \c value.
2.228 +
2.229 + /**
2.230 + This method sets the priority of \c item to \c value. Though
2.231 + there is no precondition on the priority of \c item, this
2.232 + method should be used only if one wants to \e increase
2.233 + (w.r.t. Compare) the priority of \c item, because this
2.234 + method is inefficient.
2.235 + */
2.236 + void increase (Item it, PrioType const value) {
2.237 + erase(it);
2.238 + push(it, value);
2.239 + }
2.240 +
2.241 +
2.242 + ///Tells if \c item is in, was in, or has not been in the heap.
2.243 +
2.244 + /**
2.245 + This method returns PRE_HEAP if \c item has never been in the
2.246 + heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
2.247 + otherwise. In the latter case it is possible that \c item will
2.248 + get back to the heap again.
2.249 + */
2.250 + state_enum state(const Item &it); /*vigyazat: az implementacioban it van*/
2.251 +
2.252 +
2.253 +
2.254 + // **********************************************************************
2.255 + // IMPLEMENTATIONS
2.256 + // **********************************************************************
2.257 +
2.258
2.259 void set (Item const it, PrioType const value) {
2.260 int i=iimap[it];
2.261 @@ -139,30 +241,6 @@
2.262 }
2.263
2.264
2.265 - Item top() const {
2.266 - return container[minimum].name;
2.267 - }
2.268 -
2.269 -
2.270 - PrioType prio() const {
2.271 - return container[minimum].prio;
2.272 - }
2.273 -
2.274 -
2.275 -
2.276 -
2.277 - PrioType& operator[](const Item& it) {
2.278 - return container[iimap[it]].prio;
2.279 - }
2.280 -
2.281 - const PrioType& operator[](const Item& it) const {
2.282 - return container[iimap[it]].prio;
2.283 - }
2.284 -
2.285 -// const PrioType get(const Item& it) const {
2.286 -// return container[iimap[it]].prio;
2.287 -// }
2.288 -
2.289 void pop() {
2.290 /*The first case is that there are only one root.*/
2.291 if ( container[minimum].left_neighbor==minimum ) {
2.292 @@ -223,12 +301,6 @@
2.293 }
2.294
2.295
2.296 - void increase (Item it, PrioType const value) {
2.297 - erase(it);
2.298 - push(it, value);
2.299 - }
2.300 -
2.301 -
2.302 state_enum state(const Item &it) const {
2.303 int i=iimap[it];
2.304 if( i>=0 ) {