Changeset 373:259ea2d741a2 in lemon-0.x for src/include
- Timestamp:
- 04/22/04 16:50:24 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@503
- Location:
- src/include
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
src/include/dijkstra.h
r335 r373 1 1 // -*- C++ -*- 2 3 /*4 *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >5 *6 *Constructor:7 *8 *Dijkstra(Graph G, LengthMap length)9 *10 *11 *Methods:12 *13 *void run(Node s)14 *15 *T dist(Node v) : After run(s) was run, it returns the distance from s to v.16 * Returns T() if v is not reachable from s.17 *18 *Edge pred(Node v) : After run(s) was run, it returns the last19 * edge of a shortest s-v path. It is INVALID for s and for20 * the nodes not reachable from s.21 *22 *bool reached(Node v) : After run(s) was run, it is true iff v is23 * reachable from s24 *25 */26 2 27 3 #ifndef HUGO_DIJKSTRA_H … … 37 13 namespace hugo { 38 14 39 //Alpar: Changed the order of the parameters40 41 15 ///%Dijkstra algorithm class. 42 16 … … 50 24 ///It is also possible to change the underlying priority heap. 51 25 /// 52 ///\param Graph The graph type the algorithm runs on. 53 ///\param LengthMap This read-only 54 ///EdgeMap 55 ///determines the 56 ///lengths of the edges. It is read once for each edge, so the map 57 ///may involve in relatively time consuming process to compute the edge 58 ///length if it is necessary. The default map type is 59 ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>" 60 ///\param Heap The heap type used by the %Dijkstra 61 ///algorithm. The default 62 ///is using \ref BinHeap "binary heap". 26 ///\param Graph The graph type the algorithm runs on. 27 ///\param LengthMap This read-only EdgeMap determines the lengths of 28 ///the edges. It is read once for each edge, so the map may involve 29 ///in relatively time consuming process to compute the edge length 30 ///if it is necessary. The default map type is \ref 31 ///GraphSkeleton::EdgeMap "Graph::EdgeMap<int>" 32 ///\param Heap The heap type used by the %Dijkstra algorithm. The 33 ///default is using \ref BinHeap "binary heap". 63 34 64 35 #ifdef DOXYGEN … … 104 75 ///of this funcion is undefined. 105 76 ValueType dist(Node v) const { return distance[v]; } 77 106 78 ///Returns the edges of the shortest path tree. 107 79 … … 111 83 ///\pre \ref run() must be called before using this function. 112 84 Edge pred(Node v) const { return predecessor[v]; } 85 113 86 ///Returns the nodes of the shortest paths. 114 87 … … 124 97 /// 125 98 const DistMap &distMap() const { return distance;} 99 126 100 ///Returns a reference to the shortest path tree map. 127 101 … … 130 104 ///\pre \ref run() must be called before using this function. 131 105 const PredMap &predMap() const { return predecessor;} 106 132 107 ///Returns a reference to the map of nodes of shortest paths. 133 108 … … 143 118 ///\todo Is this what we want? 144 119 ///\pre \ref run() must be called before using this function. 145 ///146 120 bool reached(Node v) { return G.valid(predecessor[v]); } 147 121 … … 153 127 // ********************************************************************** 154 128 155 ///Runs %Dijkstra algorithm from node the source.129 ///Runs %Dijkstra algorithm from source node \c s. 156 130 157 131 ///This method runs the %Dijkstra algorithm from a source node \c s 158 ///in order to 159 ///compute the 160 ///shortest path to each node. The algorithm computes 161 ///- The shortest path tree. 162 ///- The distance of each node from the source. 132 ///in order to compute the shortest path to each node. The algorithm 133 ///computes - The shortest path tree. - The distance of each node 134 ///from the source. 163 135 template <typename Graph, typename LengthMap, 164 136 template<class,class,class> class Heap > … … 169 141 predecessor.set(u,INVALID); 170 142 pred_node.set(u,INVALID); 171 // If a node is unreacheable, then why should be the dist=0?172 // distance.set(u,0);173 // reach.set(u,false);174 143 } 175 144 … … 177 146 178 147 Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map); 179 180 148 heap.push(s,0); 181 149 182 while ( !heap.empty() ) { 150 while ( !heap.empty() ) { 151 152 Node v=heap.top(); 153 ValueType oldvalue=heap[v]; 154 heap.pop(); 155 distance.set(v, oldvalue); 183 156 184 Node v=heap.top(); 185 ValueType oldvalue=heap[v]; 186 heap.pop(); 187 distance.set(v, oldvalue); 188 189 { //FIXME this bracket is for e to be local 190 OutEdgeIt e; 191 for(G.first(e, v); 192 G.valid(e); G.next(e)) { 157 { //FIXME this bracket is for e to be local 158 OutEdgeIt e; 159 for(G.first(e, v); G.valid(e); G.next(e)) { 193 160 Node w=G.head(e); 194 161 … … 210 177 } 211 178 } 212 } //FIXME t is bracket213 179 } //FIXME this bracket 180 } 214 181 } 215 182 -
src/include/fib_heap.h
r255 r373 1 1 // -*- C++ -*- 2 /* 3 *template <typename Item, 4 * typename Prio, 5 * typename ItemIntMap, 6 * typename Compare = std::less<Prio> > 7 * 8 *constructors: 9 * 10 *FibHeap(ItemIntMap), FibHeap(ItemIntMap, Compare) 11 * 12 *Member functions: 13 * 14 *int size() : returns the number of elements in the heap 15 * 16 *bool empty() : true iff size()=0 17 * 18 *void set(Item, Prio) : calls push(Item, Prio) if Item is not 19 * in the heap, and calls decrease/increase(Item, Prio) otherwise 20 * 21 *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item 22 * mustn't be in the heap. 23 * 24 *Item top() : returns the Item with least Prio. 25 * Must be called only if heap is nonempty. 26 * 27 *Prio prio() : returns the least Prio 28 * Must be called only if heap is nonempty. 29 * 30 *Prio get(Item) : returns Prio of Item 31 * Must be called only if Item is in heap. 32 * 33 *void pop() : deletes the Item with least Prio 34 * 35 *void erase(Item) : deletes Item from the heap if it was already there 36 * 37 *void decrease(Item, P) : decreases prio of Item to P. 38 * Item must be in the heap with prio at least P. 39 * 40 *void increase(Item, P) : sets prio of Item to P. 41 * 42 *state_enum state(Item) : returns PRE_HEAP if Item has not been in the 43 * heap until now, IN_HEAP if it is in the heap at the moment, and 44 * POST_HEAP otherwise. In the latter case it is possible that Item 45 * will get back to the heap again. 46 * 47 *In Fibonacci heaps, increase and erase are not efficient, in case of 48 *many calls to these operations, it is better to use bin_heap. 49 */ 50 51 #ifndef FIB_HEAP_H 52 #define FIB_HEAP_H 2 3 #ifndef HUGO_FIB_HEAP_H 4 #define HUGO_FIB_HEAP_H 53 5 54 6 ///\file … … 61 13 namespace hugo { 62 14 63 /// A Fibonacci Heap implementation. 64 template <typename Item, typename Prio, typename ItemIntMap, 15 /// An implementation of the Fibonacci Heap. 16 17 /** 18 This class implements the \e Fibonacci \e heap data structure. A \e 19 heap is a data structure for storing items with specified priorities, 20 such that finding the item with minimum priority is efficient. In a 21 heap one can change the priority of an item, and to add or erase an 22 item. 23 24 The methods \ref increase and \ref erase are not efficient, in 25 case of many calls to these operations, it is better to use 26 a binary heap. 27 28 /param Item The type of the items to be stored. 29 /param Prio The type of the priority of the items. 30 /param ItemIntMap A read and writable Item int map, for the usage of 31 the heap. 32 /param Compare A class for the comparison of the priorities. The 33 default is \c std::less<Prio>. 34 35 */ 36 37 #ifdef DOXYGEN 38 template <typename Item, 39 typename Prio, 40 typename ItemIntMap, 41 typename Compare> 42 #else 43 template <typename Item, 44 typename Prio, 45 typename ItemIntMap, 65 46 typename Compare = std::less<Prio> > 47 #endif 66 48 class FibHeap { 67 49 public: 68 50 typedef Prio PrioType; 69 51 52 private: 70 53 class store; 71 54 … … 75 58 Compare comp; 76 59 int num_items; 77 60 78 61 ///\todo It is use nowhere 79 62 ///\todo It doesn't conform to the naming conventions. … … 87 70 public : 88 71 89 FibHeap(ItemIntMap &_iimap) : minimum( ), iimap(_iimap), num_items() {}90 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum( ),72 FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {} 73 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), 91 74 iimap(_iimap), comp(_comp), num_items() {} 92 75 93 94 int size() const { 95 return num_items; 96 } 97 98 76 ///The number of items stored in the heap. 77 78 /** 79 Returns the number of items stored in the heap. 80 */ 81 int size() const { return num_items; } 82 83 ///Checks if the heap stores no items. 84 85 /** 86 Returns true iff the heap stores no items. 87 */ 99 88 bool empty() const { return num_items==0; } 100 89 90 ///Item \c item gets to the heap with priority \c value independently if \c item was already there. 91 92 /** 93 This method calls \ref push(item, value) if \c item is not 94 stored in the heap, and it calls \ref decrease(it, \c value) or 95 \ref increase(it, \c value) otherwise. 96 */ 97 void set (Item const item, PrioType const value); //vigyazat: az implementacioban it van 98 99 ///Adds \c item to the heap with priority \c value. 100 101 /** 102 Adds \c item to the heap with priority \c value. 103 \pre \c item must not be stored in the heap. 104 */ 105 void push (Item const it, PrioType const value); /*vigyazat: az implementacioban it van*/ 106 107 108 ///Returns the item having the minimum priority w.r.t. Compare. 109 110 /** 111 This method returns the item having the minimum priority w.r.t. Compare. 112 \pre The heap must be nonempty. 113 */ 114 Item top() const { return container[minimum].name; } 115 116 117 ///Returns the minimum priority w.r.t. Compare. 118 119 /** 120 It returns the minimum priority w.r.t. Compare. 121 \pre The heap must be nonempty. 122 */ 123 PrioType prio() const { return container[minimum].prio; } 124 125 126 ///Returns the priority of \c item. 127 128 /** 129 It returns the priority of \c item. 130 \pre \c item must be in the heap. 131 */ 132 PrioType& operator[](const Item& it) { return container[iimap[it]].prio; } 133 134 ///Returns the priority of \c item. 135 136 /** 137 It returns the priority of \c item. 138 \pre \c item must be in the heap. 139 */ 140 const PrioType& operator[](const Item& it) const { 141 return container[iimap[it]].prio; 142 } 143 144 145 ///Deletes the item with minimum priority w.r.t. Compare. 146 147 /** 148 This method deletes the item with minimum priority w.r.t. 149 Compare from the heap. 150 \pre The heap must be non-empty. 151 */ 152 void pop(); 153 154 ///Deletes \c item from the heap. 155 156 /** 157 This method deletes \c item from the heap, if \c item was already 158 stored in the heap. It is quite inefficient in Fibonacci heaps. 159 */ 160 void erase (const Item& item); /*vigyazat: az implementacioban it van*/ 161 162 ///Decreases the priority of \c item to \c value. 163 164 /** 165 This method decreases the priority of \c item to \c value. 166 \pre \c item must be stored in the heap with priority at least \c 167 value w.r.t. Compare. 168 */ 169 void decrease (Item item, PrioType const value); /*vigyazat: az implementacioban it van*/ 170 171 172 ///Increases the priority of \c item to \c value. 173 174 /** 175 This method sets the priority of \c item to \c value. Though 176 there is no precondition on the priority of \c item, this 177 method should be used only if one wants to \e increase 178 (w.r.t. Compare) the priority of \c item, because this 179 method is inefficient. 180 */ 181 void increase (Item it, PrioType const value) { 182 erase(it); 183 push(it, value); 184 } 185 186 187 ///Tells if \c item is in, was in, or has not been in the heap. 188 189 /** 190 This method returns PRE_HEAP if \c item has never been in the 191 heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 192 otherwise. In the latter case it is possible that \c item will 193 get back to the heap again. 194 */ 195 state_enum state(const Item &it); /*vigyazat: az implementacioban it van*/ 196 197 198 199 // ********************************************************************** 200 // IMPLEMENTATIONS 201 // ********************************************************************** 202 101 203 102 204 void set (Item const it, PrioType const value) { … … 139 241 } 140 242 141 142 Item top() const {143 return container[minimum].name;144 }145 146 147 PrioType prio() const {148 return container[minimum].prio;149 }150 151 152 153 154 PrioType& operator[](const Item& it) {155 return container[iimap[it]].prio;156 }157 158 const PrioType& operator[](const Item& it) const {159 return container[iimap[it]].prio;160 }161 162 // const PrioType get(const Item& it) const {163 // return container[iimap[it]].prio;164 // }165 243 166 244 void pop() { … … 224 302 225 303 226 void increase (Item it, PrioType const value) {227 erase(it);228 push(it, value);229 }230 231 232 304 state_enum state(const Item &it) const { 233 305 int i=iimap[it];
Note: See TracChangeset
for help on using the changeset viewer.