Changeset 1119:d3504fc075dc in lemon0.x
 Timestamp:
 02/03/05 17:08:56 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1518
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/alpar/dijkstra.h
r1117 r1119 25 25 #include <lemon/bin_heap.h> 26 26 #include <lemon/invalid.h> 27 #include <lemon/error.h> 28 #include <lemon/maps.h> 27 29 28 30 namespace lemon { 31 32 33 class UninitializedData : public LogicError {}; 34 29 35 30 36 /// \addtogroup flowalgs … … 68 74 69 75 ///\todo Please document... 70 /// 76 ///\todo The graph alone may be insufficient for the initialization 71 77 static PredMap *createPredMap(const GR &G) 72 78 { … … 86 92 { 87 93 return new PredNodeMap(G); 94 } 95 96 ///The type of the map that stores whether a nodes is reached. 97 98 ///It must meet the \ref concept::WriteMap "WriteMap" concept. 99 ///By default it is a NullMap. 100 ///\todo If it is set to a real map, Dijkstra::reached() should read this. 101 ///\todo named parameter to set this type, function to read and write. 102 typedef NullMap<typename Graph::Node,bool> ReachedMap; 103 ///Instantiates a ReachedMap. 104 105 ///\todo Please document... 106 /// 107 static ReachedMap *createReachedMap(const GR &G) 108 { 109 return new ReachedMap(); 88 110 } 89 111 ///The type of the map that stores the dists of the nodes. … … 146 168 class Dijkstra { 147 169 public: 170 ///Exception thrown by dijkstra. 171 class UninitializedData : public lemon::UninitializedData {}; 172 148 173 typedef TR Traits; 149 174 ///The type of the underlying graph. … … 168 193 ///nodes of the shortest paths. 169 194 typedef typename TR::PredNodeMap PredNodeMap; 195 ///The type of the map indicating if a node is reached. 196 typedef typename TR::ReachedMap ReachedMap; 170 197 ///The type of the map that stores the dists of the nodes. 171 198 typedef typename TR::DistMap DistMap; … … 178 205 const LengthMap *length; 179 206 ///Pointer to the map of predecessors edges. 180 PredMap * predecessor;181 ///Indicates if \ref predecessoris locally allocated (\c true) or not.182 bool local_pred ecessor;207 PredMap *_pred; 208 ///Indicates if \ref _pred is locally allocated (\c true) or not. 209 bool local_pred; 183 210 ///Pointer to the map of predecessors nodes. 184 211 PredNodeMap *pred_node; … … 189 216 ///Indicates if \ref distance is locally allocated (\c true) or not. 190 217 bool local_distance; 218 ///Pointer to the map of reached status of the nodes. 219 ReachedMap *_reached; 220 ///Indicates if \ref _reached is locally allocated (\c true) or not. 221 bool local_reached; 191 222 192 223 ///The source node of the last execution. … … 199 230 void init_maps() 200 231 { 201 if(! predecessor) {202 local_pred ecessor= true;203 predecessor= Traits::createPredMap(*G);232 if(!_pred) { 233 local_pred = true; 234 _pred = Traits::createPredMap(*G); 204 235 } 205 236 if(!pred_node) { … … 210 241 local_distance = true; 211 242 distance = Traits::createDistMap(*G); 243 } 244 if(!_reached) { 245 local_reached = true; 246 _reached = Traits::createReachedMap(*G); 212 247 } 213 248 } … … 222 257 static PredMap *createPredMap(const Graph &G) 223 258 { 224 std::cerr << __FILE__ ":" << __LINE__ << 225 ": error: Special maps should be manually created" << std::endl; 226 exit(1); 259 throw UninitializedData(); 227 260 } 228 261 }; … … 243 276 static PredNodeMap *createPredNodeMap(const Graph &G) 244 277 { 245 std::cerr << __FILE__ ":" << __LINE__ << 246 ": error: Special maps should be manually created" << std::endl; 247 exit(1); 278 throw UninitializedData(); 248 279 } 249 280 }; … … 264 295 static DistMap *createDistMap(const Graph &G) 265 296 { 266 std::cerr << __FILE__ ":" << __LINE__ << 267 ": error: Special maps should be manually created" << std::endl; 268 exit(1); 297 throw UninitializedData(); 269 298 } 270 299 }; … … 284 313 Dijkstra(const Graph& _G, const LengthMap& _length) : 285 314 G(&_G), length(&_length), 286 predecessor(NULL), local_predecessor(false),315 _pred(NULL), local_pred(false), 287 316 pred_node(NULL), local_pred_node(false), 288 distance(NULL), local_distance(false) 317 distance(NULL), local_distance(false), 318 _reached(NULL), local_reached(false) 289 319 { } 290 320 … … 292 322 ~Dijkstra() 293 323 { 294 if(local_pred ecessor) delete predecessor;324 if(local_pred) delete _pred; 295 325 if(local_pred_node) delete pred_node; 296 326 if(local_distance) delete distance; 327 if(local_reached) delete _reached; 297 328 } 298 329 … … 316 347 Dijkstra &predMap(PredMap &m) 317 348 { 318 if(local_pred ecessor) {319 delete predecessor;320 local_pred ecessor=false;321 } 322 predecessor= &m;349 if(local_pred) { 350 delete _pred; 351 local_pred=false; 352 } 353 _pred = &m; 323 354 return *this; 324 355 } … … 374 405 375 406 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { 376 predecessor>set(u,INVALID);407 _pred>set(u,INVALID); 377 408 pred_node>set(u,INVALID); 409 ///\todo *_reached is not set to false. 378 410 } 379 411 … … 387 419 388 420 Node v=heap.top(); 421 _reached>set(v,true); 389 422 Value oldvalue=heap[v]; 390 423 heap.pop(); … … 397 430 case Heap::PRE_HEAP: 398 431 heap.push(w,oldvalue+(*length)[e]); 399 predecessor>set(w,e);432 _pred>set(w,e); 400 433 pred_node>set(w,v); 401 434 break; … … 403 436 if ( oldvalue+(*length)[e] < heap[w] ) { 404 437 heap.decrease(w, oldvalue+(*length)[e]); 405 predecessor>set(w,e);438 _pred>set(w,e); 406 439 pred_node>set(w,v); 407 440 } … … 432 465 ///this function. 433 466 ///\todo predEdge could be a better name. 434 Edge pred(Node v) const { return (* predecessor)[v]; }467 Edge pred(Node v) const { return (*_pred)[v]; } 435 468 436 469 ///Returns the 'previous node' of the shortest path tree. … … 455 488 ///shortest path tree. 456 489 ///\pre \ref run() must be called before using this function. 457 const PredMap &predMap() const { return * predecessor;}490 const PredMap &predMap() const { return *_pred;} 458 491 459 492 ///Returns a reference to the map of nodes of shortest paths. … … 470 503 ///\pre \ref run() must be called before using this function. 471 504 /// 472 bool reached(Node v) { return v==source  (* predecessor)[v]!=INVALID; }505 bool reached(Node v) { return v==source  (*_pred)[v]!=INVALID; } 473 506 474 507 }; … … 514 547 typedef TR Base; 515 548 516 // /The type of the underlying graph.549 //The type of the underlying graph. 517 550 typedef typename TR::Graph Graph; 518 // /\e551 //\e 519 552 typedef typename Graph::Node Node; 520 // /\e553 //\e 521 554 typedef typename Graph::NodeIt NodeIt; 522 // /\e555 //\e 523 556 typedef typename Graph::Edge Edge; 524 // /\e557 //\e 525 558 typedef typename Graph::OutEdgeIt OutEdgeIt; 526 559 527 // /The type of the map that stores the edge lengths.560 //The type of the map that stores the edge lengths. 528 561 typedef typename TR::LengthMap LengthMap; 529 // /The type of the length of the edges.562 //The type of the length of the edges. 530 563 typedef typename LengthMap::Value Value; 531 // /\brief The type of the map that stores the last532 // /edges of the shortest paths.564 //\brief The type of the map that stores the last 565 //edges of the shortest paths. 533 566 typedef typename TR::PredMap PredMap; 534 // /\brief The type of the map that stores the last but one535 // /nodes of the shortest paths.567 //\brief The type of the map that stores the last but one 568 //nodes of the shortest paths. 536 569 typedef typename TR::PredNodeMap PredNodeMap; 537 // /The type of the map that stores the dists of the nodes.570 //The type of the map that stores the dists of the nodes. 538 571 typedef typename TR::DistMap DistMap; 539 572 540 // /The heap type used by the dijkstra algorithm.573 //The heap type used by the dijkstra algorithm. 541 574 typedef typename TR::Heap Heap; 542 575 public: … … 553 586 void run() 554 587 { 588 if(_source==0) throw UninitializedData(); 555 589 Dijkstra<Graph,LengthMap,TR> Dij(*(Graph*)_g,*(LengthMap*)_length); 556 590 if(_pred) Dij.predMap(*(PredMap*)_pred);
Note: See TracChangeset
for help on using the changeset viewer.