Changeset 1128:6a347310d4c2 in lemon0.x
 Timestamp:
 02/06/05 15:44:41 (16 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1527
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/alpar/dijkstra.h
r1126 r1128 159 159 /// 160 160 ///\author Jacint Szabo and Alpar Juttner 161 ///\todo We need a typedefnames should be standardized. (:161 ///\todo A compare object would be nice. 162 162 163 163 #ifdef DOXYGEN … … 238 238 Node source; 239 239 240 /// Initializes the maps.240 ///Creates the maps if necessary. 241 241 242 242 ///\todo Error if \c G or are \c NULL. What about \c length? 243 243 ///\todo Better memory allocation (instead of new). 244 void init_maps()244 void create_maps() 245 245 { 246 246 if(!_pred) { … … 264 264 public : 265 265 266 ///\name Named template parameters 267 268 ///@{ 269 266 270 template <class T> 267 271 struct DefPredMapTraits : public Traits { 268 272 typedef T PredMap; 269 ///\todo An exception should be thrown.270 ///271 273 static PredMap *createPredMap(const Graph &G) 272 274 { … … 286 288 struct DefPredNodeMapTraits : public Traits { 287 289 typedef T PredNodeMap; 288 ///\todo An exception should be thrown.289 ///290 290 static PredNodeMap *createPredNodeMap(const Graph &G) 291 291 { … … 305 305 struct DefDistMapTraits : public Traits { 306 306 typedef T DistMap; 307 ///\todo An exception should be thrown.308 ///309 307 static DistMap *createDistMap(const Graph &G) 310 308 { … … 320 318 LengthMap, 321 319 DefDistMapTraits<T> > { }; 320 321 template <class T> 322 struct DefReachedMapTraits : public Traits { 323 typedef T ReachedMap; 324 static ReachedMap *createReachedMap(const Graph &G) 325 { 326 throw UninitializedParameter(); 327 } 328 }; 329 ///\ref namedtemplparam "Named parameter" for setting ReachedMap type 330 331 ///\ref namedtemplparam "Named parameter" for setting ReachedMap type 332 /// 333 template <class T> 334 class DefReachedMap : public Dijkstra< Graph, 335 LengthMap, 336 DefReachedMapTraits<T> > { }; 337 338 struct DefGraphReachedMapTraits : public Traits { 339 typedef typename Graph::NodeMap<bool> ReachedMap; 340 static ReachedMap *createReachedMap(const Graph &G) 341 { 342 return new ReachedMap(G); 343 } 344 }; 345 ///\brief \ref namedtemplparam "Named parameter" 346 ///for setting the ReachedMap type to be Graph::NodeMap<bool>. 347 /// 348 ///\ref namedtemplparam "Named parameter" 349 ///for setting the ReachedMap type to be Graph::NodeMap<bool>. 350 ///If you don't set it explicitely, it will be automatically allocated. 351 template <class T> 352 class DefReachedMapToBeDefaultMap : 353 public Dijkstra< Graph, 354 LengthMap, 355 DefGraphReachedMapTraits> { }; 356 357 ///@} 358 359 360 private: 361 typename Graph::template NodeMap<int> _heap_map; 362 Heap _heap; 363 public: 322 364 323 365 ///Constructor. … … 330 372 pred_node(NULL), local_pred_node(false), 331 373 distance(NULL), local_distance(false), 332 _reached(NULL), local_reached(false) 374 _reached(NULL), local_reached(false), 375 _heap_map(*G,1),_heap(_heap_map) 333 376 { } 334 377 … … 402 445 return *this; 403 446 } 404 405 ///Runs %Dijkstra algorithm from node \c s. 406 407 ///This method runs the %Dijkstra algorithm from a root node \c s 408 ///in order to 409 ///compute the 410 ///shortest path to each node. The algorithm computes 411 /// The shortest path tree. 412 /// The distance of each node from the root. 413 ///\todo heap_map's type could also be in the traits class. 414 void run(Node s) { 415 416 init_maps(); 417 418 source = s; 447 448 ///\name Excetution control 449 ///The simplest way to execute the algorithm is to use 450 ///\ref run(). 451 ///\n 452 ///It you need more control on the execution, 453 ///first you must call \ref init(), then you can add several source nodes 454 ///with \ref addSource(). Finally \ref start() will perform the actual path 455 ///computation. 456 457 ///@{ 458 459 ///Initializes the internal data structures. 460 461 ///Initializes the internal data structures. 462 /// 463 ///\todo _heap_map's type could also be in the traits class. 464 void init() 465 { 466 create_maps(); 419 467 420 468 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { … … 422 470 pred_node>set(u,INVALID); 423 471 ///\todo *_reached is not set to false. 424 } 472 _heap_map.set(u,Heap::PRE_HEAP); 473 } 474 } 475 476 ///Adds a new source node. 477 478 ///Adds a new source node the the priority heap. 479 ///It checks if the node has already been added to the heap. 480 /// 481 ///The optional second parameter is the initial distance of the node. 482 /// 483 ///\todo Do we really want to check it? 484 void addSource(Node s,Value dst=0) 485 { 486 source = s; 487 if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst); 488 } 489 490 void processNode() 491 { 492 Node v=_heap.top(); 493 _reached>set(v,true); 494 Value oldvalue=_heap[v]; 495 _heap.pop(); 496 distance>set(v, oldvalue); 425 497 426 typename Graph::template NodeMap<int> heap_map(*G,1); 427 428 Heap heap(heap_map); 429 430 heap.push(s,0); 431 432 while ( !heap.empty() ) { 433 434 Node v=heap.top(); 435 _reached>set(v,true); 436 Value oldvalue=heap[v]; 437 heap.pop(); 438 distance>set(v, oldvalue); 439 440 441 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { 442 Node w=G>target(e); 443 switch(heap.state(w)) { 444 case Heap::PRE_HEAP: 445 heap.push(w,oldvalue+(*length)[e]); 498 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { 499 Node w=G>target(e); 500 switch(_heap.state(w)) { 501 case Heap::PRE_HEAP: 502 _heap.push(w,oldvalue+(*length)[e]); 503 _pred>set(w,e); 504 pred_node>set(w,v); 505 break; 506 case Heap::IN_HEAP: 507 if ( oldvalue+(*length)[e] < _heap[w] ) { 508 _heap.decrease(w, oldvalue+(*length)[e]); 446 509 _pred>set(w,e); 447 510 pred_node>set(w,v); 448 break;449 case Heap::IN_HEAP:450 if ( oldvalue+(*length)[e] < heap[w] ) {451 heap.decrease(w, oldvalue+(*length)[e]);452 _pred>set(w,e);453 pred_node>set(w,v);454 }455 break;456 case Heap::POST_HEAP:457 break;458 511 } 512 break; 513 case Heap::POST_HEAP: 514 break; 459 515 } 460 516 } 461 517 } 462 518 519 ///Starts the execution of the algorithm. 520 521 ///Starts the execution of the algorithm. 522 /// 523 ///\pre init() must be called before and at least one node should be added 524 ///with addSource(). 525 /// 526 ///This method runs the %Dijkstra algorithm from the root node(s) 527 ///in order to 528 ///compute the 529 ///shortest path to each node. The algorithm computes 530 /// The shortest path tree. 531 /// The distance of each node from the root(s). 532 /// 533 void start() 534 { 535 while ( !_heap.empty() ) processNode(); 536 } 537 538 ///Starts the execution of the algorithm until \c dest is reached. 539 540 ///Starts the execution of the algorithm until \c dest is reached. 541 /// 542 ///\pre init() must be called before and at least one node should be added 543 ///with addSource(). 544 /// 545 ///This method runs the %Dijkstra algorithm from the root node(s) 546 ///in order to 547 ///compute the 548 ///shortest path to \c dest. The algorithm computes 549 /// The shortest path to \c dest. 550 /// The distance of \c dest from the root(s). 551 /// 552 void start(Node dest) 553 { 554 while ( !_heap.empty() && _heap.top()!=dest) processNode(); 555 } 556 557 ///Runs %Dijkstra algorithm from node \c s. 558 559 ///This method runs the %Dijkstra algorithm from a root node \c s 560 ///in order to 561 ///compute the 562 ///shortest path to each node. The algorithm computes 563 /// The shortest path tree. 564 /// The distance of each node from the root. 565 /// 566 ///\note d.run(s) is just a shortcut of the following code. 567 ///\code 568 /// d.init(); 569 /// d.addSource(s); 570 /// d.start(); 571 ///\endcode 572 void run(Node s) { 573 init(); 574 addSource(s); 575 start(); 576 } 577 578 ///@} 579 580 ///\name Query Functions 581 ///The result of the %Dijkstra algorithm can be obtained using these 582 ///functions.\n 583 ///Before the use of these functions, 584 ///either run() or start() must be called. 585 586 ///@{ 587 463 588 ///The distance of a node from the root. 464 589 … … 514 639 515 640 ///Returns \c true if \c v is reachable from the root. 516 ///\note The root node is reported to be reached! 641 ///\warning If the algorithm is started from multiple nodes, 642 ///this function may give false result for the source nodes. 517 643 ///\pre \ref run() must be called before using this function. 518 644 /// 519 645 bool reached(Node v) { return v==source  (*_pred)[v]!=INVALID; } 520 646 647 ///@} 521 648 }; 522 649
Note: See TracChangeset
for help on using the changeset viewer.