Changeset 688:bdc429a557f2 in lemon0.x
 Timestamp:
 06/30/04 16:50:31 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@938
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/hugo/dijkstra.h
r584 r688 73 73 74 74 private: 75 const Graph& G; 76 const LM& length; 77 PredMap predecessor; 78 PredNodeMap pred_node; 79 DistMap distance; 75 const Graph *G; 76 const LM *length; 77 // bool local_length; 78 PredMap *predecessor; 79 bool local_predecessor; 80 PredNodeMap *pred_node; 81 bool local_pred_node; 82 DistMap *distance; 83 bool local_distance; 84 85 ///Initialize maps 86 87 ///\todo Error if \c G or are \c NULL. What about \c length 88 ///\todo Better memory allocation (instead of new). 89 void init_maps() 90 { 91 // if(!length) { 92 // local_length = true; 93 // length = new LM(G); 94 // } 95 if(!predecessor) { 96 local_predecessor = true; 97 predecessor = new PredMap(*G); 98 } 99 if(!pred_node) { 100 local_pred_node = true; 101 pred_node = new PredNodeMap(*G); 102 } 103 if(!distance) { 104 local_distance = true; 105 distance = new DistMap(*G); 106 } 107 } 80 108 81 109 public : 82 110 83 111 Dijkstra(const Graph& _G, const LM& _length) : 84 G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { } 112 G(&_G), length(&_length), 113 predecessor(NULL), pred_node(NULL), distance(NULL), 114 local_predecessor(false), local_pred_node(false), local_distance(false) 115 { } 116 117 ~Dijkstra() 118 { 119 // if(local_length) delete length; 120 if(local_predecessor) delete predecessor; 121 if(local_pred_node) delete pred_node; 122 if(local_distance) delete distance; 123 } 124 125 ///Sets the graph the algorithm will run on. 126 127 ///Sets the graph the algorithm will run on. 128 ///\return <tt> (*this) </tt> 129 Dijkstra &setGraph(const Graph &_G) 130 { 131 G = &_G; 132 return *this; 133 } 134 ///Sets the length map. 135 136 ///Sets the length map. 137 ///\return <tt> (*this) </tt> 138 Dijkstra &setLengthMap(const LM &m) 139 { 140 // if(local_length) { 141 // delete length; 142 // local_length=false; 143 // } 144 length = &m; 145 return *this; 146 } 147 148 ///Sets the map storing the predecessor edges. 149 150 ///Sets the map storing the predecessor edges. 151 ///If you don't use this function before calling \ref run(), 152 ///it will allocate one. The destuctor deallocates this 153 ///automatically allocated map, of course. 154 ///\return <tt> (*this) </tt> 155 Dijkstra &setPredMap(PredMap &m) 156 { 157 if(local_predecessor) { 158 delete predecessor; 159 local_predecessor=false; 160 } 161 predecessor = &m; 162 return *this; 163 } 164 165 ///Sets the map storing the predecessor nodes. 166 167 ///Sets the map storing the predecessor nodes. 168 ///If you don't use this function before calling \ref run(), 169 ///it will allocate one. The destuctor deallocates this 170 ///automatically allocated map, of course. 171 ///\return <tt> (*this) </tt> 172 Dijkstra &setPredNodeMap(PredNodeMap &m) 173 { 174 if(local_pred_node) { 175 delete pred_node; 176 local_pred_node=false; 177 } 178 pred_node = &m; 179 return *this; 180 } 181 182 ///Sets the map storing the distances calculated by the algorithm. 183 184 ///Sets the map storing the distances calculated by the algorithm. 185 ///If you don't use this function before calling \ref run(), 186 ///it will allocate one. The destuctor deallocates this 187 ///automatically allocated map, of course. 188 ///\return <tt> (*this) </tt> 189 Dijkstra &setDistMap(DistMap &m) 190 { 191 if(local_distance) { 192 delete distance; 193 local_distance=false; 194 } 195 distance = &m; 196 return *this; 197 } 85 198 86 199 void run(Node s); … … 92 205 ///\warning If node \c v in unreachable from the root the return value 93 206 ///of this funcion is undefined. 94 ValueType dist(Node v) const { return distance[v]; }207 ValueType dist(Node v) const { return (*distance)[v]; } 95 208 96 209 ///Returns the 'previous edge' of the shortest path tree. … … 98 211 ///For a node \c v it returns the 'previous edge' of the shortest path tree, 99 212 ///i.e. it returns the last edge from a shortest path from the root to \c 100 ///v. It is INVALID if \c v is unreachable from the root or if \c v=s. The 213 ///v. It is \ref INVALID 214 ///if \c v is unreachable from the root or if \c v=s. The 101 215 ///shortest path tree used here is equal to the shortest path tree used in 102 216 ///\ref predNode(Node v). \pre \ref run() must be called before using 103 217 ///this function. 104 Edge pred(Node v) const { return predecessor[v]; }218 Edge pred(Node v) const { return (*predecessor)[v]; } 105 219 106 220 ///Returns the 'previous node' of the shortest path tree. … … 112 226 ///tree used in \ref pred(Node v). \pre \ref run() must be called before 113 227 ///using this function. 114 Node predNode(Node v) const { return pred_node[v]; }228 Node predNode(Node v) const { return (*pred_node)[v]; } 115 229 116 230 ///Returns a reference to the NodeMap of distances. … … 118 232 ///Returns a reference to the NodeMap of distances. \pre \ref run() must 119 233 ///be called before using this function. 120 const DistMap &distMap() const { return distance;}234 const DistMap &distMap() const { return *distance;} 121 235 122 236 ///Returns a reference to the shortest path tree map. … … 125 239 ///shortest path tree. 126 240 ///\pre \ref run() must be called before using this function. 127 const PredMap &predMap() const { return predecessor;}241 const PredMap &predMap() const { return *predecessor;} 128 242 129 243 ///Returns a reference to the map of nodes of shortest paths. … … 132 246 ///shortest path tree. 133 247 ///\pre \ref run() must be called before using this function. 134 const PredNodeMap &predNodeMap() const { return pred_node;}248 const PredNodeMap &predNodeMap() const { return *pred_node;} 135 249 136 250 ///Checks if a node is reachable from the root. … … 141 255 ///\pre \ref run() must be called before using this function. 142 256 /// 143 bool reached(Node v) { return G .valid(predecessor[v]); }257 bool reached(Node v) { return G>valid((*predecessor)[v]); } 144 258 145 259 }; … … 161 275 template<class,class,class,class> class Heap > 162 276 void Dijkstra<GR,LM,Heap>::run(Node s) { 163 164 NodeIt u; 165 for ( G.first(u) ; G.valid(u) ; G.next(u) ) { 166 predecessor.set(u,INVALID); 167 pred_node.set(u,INVALID); 168 } 169 170 typename GR::template NodeMap<int> heap_map(G,1); 277 278 init_maps(); 279 280 for ( NodeIt u(*G) ; G>valid(u) ; G>next(u) ) { 281 predecessor>set(u,INVALID); 282 pred_node>set(u,INVALID); 283 } 284 285 typename GR::template NodeMap<int> heap_map(*G,1); 171 286 172 287 typedef Heap<Node, ValueType, typename GR::template NodeMap<int>, … … 183 298 ValueType oldvalue=heap[v]; 184 299 heap.pop(); 185 distance .set(v, oldvalue);300 distance>set(v, oldvalue); 186 301 187 { //FIXME this bracket is for e to be local 188 OutEdgeIt e; 189 for(G.first(e, v); 190 G.valid(e); G.next(e)) { 191 Node w=G.bNode(e); 302 303 for(OutEdgeIt e(*G,v); G>valid(e); G>next(e)) { 304 Node w=G>bNode(e); 192 305 193 306 switch(heap.state(w)) { 194 307 case HeapType::PRE_HEAP: 195 heap.push(w,oldvalue+ length[e]);196 predecessor .set(w,e);197 pred_node .set(w,v);308 heap.push(w,oldvalue+(*length)[e]); 309 predecessor>set(w,e); 310 pred_node>set(w,v); 198 311 break; 199 312 case HeapType::IN_HEAP: 200 if ( oldvalue+ length[e] < heap[w] ) {201 heap.decrease(w, oldvalue+ length[e]);202 predecessor .set(w,e);203 pred_node .set(w,v);313 if ( oldvalue+(*length)[e] < heap[w] ) { 314 heap.decrease(w, oldvalue+(*length)[e]); 315 predecessor>set(w,e); 316 pred_node>set(w,v); 204 317 } 205 318 break; … … 208 321 } 209 322 } 210 } //FIXME tis bracket211 323 } 212 324 }
Note: See TracChangeset
for help on using the changeset viewer.