Changeset 694:2d87cefb35b2 in lemon-0.x
- Timestamp:
- 07/06/04 12:07:48 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@944
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/hugo/dijkstra.h
r693 r694 85 85 ///Initialize maps 86 86 87 ///\todo Error if \c G or are \c NULL. What about \c length 87 ///\todo Error if \c G or are \c NULL. What about \c length? 88 88 ///\todo Better memory allocation (instead of new). 89 89 void init_maps() … … 197 197 } 198 198 199 void run(Node s); 200 201 ///The distance of a node from the root. 202 203 ///Returns the distance of a node from the root. 204 ///\pre \ref run() must be called before using this function. 205 ///\warning If node \c v in unreachable from the root the return value 206 ///of this funcion is undefined. 207 ValueType dist(Node v) const { return (*distance)[v]; } 208 209 ///Returns the 'previous edge' of the shortest path tree. 210 211 ///For a node \c v it returns the 'previous edge' of the shortest path tree, 212 ///i.e. it returns the last edge from a shortest path from the root to \c 213 ///v. It is \ref INVALID 214 ///if \c v is unreachable from the root or if \c v=s. The 215 ///shortest path tree used here is equal to the shortest path tree used in 216 ///\ref predNode(Node v). \pre \ref run() must be called before using 217 ///this function. 218 Edge pred(Node v) const { return (*predecessor)[v]; } 219 220 ///Returns the 'previous node' of the shortest path tree. 221 222 ///For a node \c v it returns the 'previous node' of the shortest path tree, 223 ///i.e. it returns the last but one node from a shortest path from the 224 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if 225 ///\c v=s. The shortest path tree used here is equal to the shortest path 226 ///tree used in \ref pred(Node v). \pre \ref run() must be called before 227 ///using this function. 228 Node predNode(Node v) const { return (*pred_node)[v]; } 229 230 ///Returns a reference to the NodeMap of distances. 231 232 ///Returns a reference to the NodeMap of distances. \pre \ref run() must 233 ///be called before using this function. 234 const DistMap &distMap() const { return *distance;} 235 236 ///Returns a reference to the shortest path tree map. 237 238 ///Returns a reference to the NodeMap of the edges of the 239 ///shortest path tree. 240 ///\pre \ref run() must be called before using this function. 241 const PredMap &predMap() const { return *predecessor;} 242 243 ///Returns a reference to the map of nodes of shortest paths. 244 245 ///Returns a reference to the NodeMap of the last but one nodes of the 246 ///shortest path tree. 247 ///\pre \ref run() must be called before using this function. 248 const PredNodeMap &predNodeMap() const { return *pred_node;} 249 250 ///Checks if a node is reachable from the root. 251 252 ///Returns \c true if \c v is reachable from the root. 253 ///\warning the root node is reported to be unreached! 254 ///\todo Is this what we want? 255 ///\pre \ref run() must be called before using this function. 256 /// 257 bool reached(Node v) { return G->valid((*predecessor)[v]); } 258 259 }; 260 261 262 // ********************************************************************** 263 // IMPLEMENTATIONS 264 // ********************************************************************** 265 266 ///Runs %Dijkstra algorithm from node the root. 199 ///Runs %Dijkstra algorithm from node \c s. 267 200 268 201 ///This method runs the %Dijkstra algorithm from a root node \c s … … 272 205 ///- The shortest path tree. 273 206 ///- The distance of each node from the root. 274 template <typename GR, typename LM, 275 template<class,class,class,class> class Heap > 276 void Dijkstra<GR,LM,Heap>::run(Node s) { 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); 286 287 typedef Heap<Node, ValueType, typename GR::template NodeMap<int>, 207 208 void run(Node s) { 209 210 init_maps(); 211 212 for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) { 213 predecessor->set(u,INVALID); 214 pred_node->set(u,INVALID); 215 } 216 217 typename GR::template NodeMap<int> heap_map(*G,-1); 218 219 typedef Heap<Node, ValueType, typename GR::template NodeMap<int>, 288 220 std::less<ValueType> > 289 221 HeapType; 290 291 HeapType heap(heap_map);292 293 heap.push(s,0);294 222 223 HeapType heap(heap_map); 224 225 heap.push(s,0); 226 295 227 while ( !heap.empty() ) { 296 228 … … 300 232 distance->set(v, oldvalue); 301 233 302 234 303 235 for(OutEdgeIt e(*G,v); G->valid(e); G->next(e)) { 304 236 Node w=G->bNode(e); … … 322 254 } 323 255 } 324 } 256 } 257 258 ///The distance of a node from the root. 259 260 ///Returns the distance of a node from the root. 261 ///\pre \ref run() must be called before using this function. 262 ///\warning If node \c v in unreachable from the root the return value 263 ///of this funcion is undefined. 264 ValueType dist(Node v) const { return (*distance)[v]; } 265 266 ///Returns the 'previous edge' of the shortest path tree. 267 268 ///For a node \c v it returns the 'previous edge' of the shortest path tree, 269 ///i.e. it returns the last edge from a shortest path from the root to \c 270 ///v. It is \ref INVALID 271 ///if \c v is unreachable from the root or if \c v=s. The 272 ///shortest path tree used here is equal to the shortest path tree used in 273 ///\ref predNode(Node v). \pre \ref run() must be called before using 274 ///this function. 275 Edge pred(Node v) const { return (*predecessor)[v]; } 276 277 ///Returns the 'previous node' of the shortest path tree. 278 279 ///For a node \c v it returns the 'previous node' of the shortest path tree, 280 ///i.e. it returns the last but one node from a shortest path from the 281 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if 282 ///\c v=s. The shortest path tree used here is equal to the shortest path 283 ///tree used in \ref pred(Node v). \pre \ref run() must be called before 284 ///using this function. 285 Node predNode(Node v) const { return (*pred_node)[v]; } 286 287 ///Returns a reference to the NodeMap of distances. 288 289 ///Returns a reference to the NodeMap of distances. \pre \ref run() must 290 ///be called before using this function. 291 const DistMap &distMap() const { return *distance;} 292 293 ///Returns a reference to the shortest path tree map. 294 295 ///Returns a reference to the NodeMap of the edges of the 296 ///shortest path tree. 297 ///\pre \ref run() must be called before using this function. 298 const PredMap &predMap() const { return *predecessor;} 299 300 ///Returns a reference to the map of nodes of shortest paths. 301 302 ///Returns a reference to the NodeMap of the last but one nodes of the 303 ///shortest path tree. 304 ///\pre \ref run() must be called before using this function. 305 const PredNodeMap &predNodeMap() const { return *pred_node;} 306 307 ///Checks if a node is reachable from the root. 308 309 ///Returns \c true if \c v is reachable from the root. 310 ///\warning the root node is reported to be unreached! 311 ///\todo Is this what we want? 312 ///\pre \ref run() must be called before using this function. 313 /// 314 bool reached(Node v) { return G->valid((*predecessor)[v]); } 315 316 }; 317 318 319 // ********************************************************************** 320 // IMPLEMENTATIONS 321 // ********************************************************************** 325 322 326 323 /// @}
Note: See TracChangeset
for help on using the changeset viewer.