Changeset 1130:47ef467ccf70 in lemon0.x for src/work/alpar/dijkstra.h
 Timestamp:
 02/06/05 21:00:56 (16 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1529
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/alpar/dijkstra.h
r1128 r1130 86 86 ///It must meet the \ref concept::WriteMap "WriteMap" concept. 87 87 /// 88 typedef typename Graph::template NodeMap<typename GR::Node> PredNodeMap;88 typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap; 89 89 ///Instantiates a PredNodeMap. 90 90 … … 93 93 static PredNodeMap *createPredNodeMap(const GR &G) 94 94 { 95 return new PredNodeMap( G);95 return new PredNodeMap(); 96 96 } 97 97 … … 223 223 bool local_pred; 224 224 ///Pointer to the map of predecessors nodes. 225 PredNodeMap * pred_node;226 ///Indicates if \ref pred_node is locally allocated (\c true) or not.227 bool local_pred _node;225 PredNodeMap *_predNode; 226 ///Indicates if \ref _predNode is locally allocated (\c true) or not. 227 bool local_predNode; 228 228 ///Pointer to the map of distances. 229 DistMap * distance;230 ///Indicates if \ref distanceis locally allocated (\c true) or not.231 bool local_dist ance;229 DistMap *_dist; 230 ///Indicates if \ref _dist is locally allocated (\c true) or not. 231 bool local_dist; 232 232 ///Pointer to the map of reached status of the nodes. 233 233 ReachedMap *_reached; … … 248 248 _pred = Traits::createPredMap(*G); 249 249 } 250 if(! pred_node) {251 local_pred _node = true;252 pred_node = Traits::createPredNodeMap(*G);253 } 254 if(! distance) {255 local_dist ance= true;256 distance= Traits::createDistMap(*G);250 if(!_predNode) { 251 local_predNode = true; 252 _predNode = Traits::createPredNodeMap(*G); 253 } 254 if(!_dist) { 255 local_dist = true; 256 _dist = Traits::createDistMap(*G); 257 257 } 258 258 if(!_reached) { … … 370 370 G(&_G), length(&_length), 371 371 _pred(NULL), local_pred(false), 372 pred_node(NULL), local_pred_node(false),373 distance(NULL), local_distance(false),372 _predNode(NULL), local_predNode(false), 373 _dist(NULL), local_dist(false), 374 374 _reached(NULL), local_reached(false), 375 375 _heap_map(*G,1),_heap(_heap_map) … … 380 380 { 381 381 if(local_pred) delete _pred; 382 if(local_pred _node) delete pred_node;383 if(local_dist ance) delete distance;382 if(local_predNode) delete _predNode; 383 if(local_dist) delete _dist; 384 384 if(local_reached) delete _reached; 385 385 } … … 421 421 Dijkstra &predNodeMap(PredNodeMap &m) 422 422 { 423 if(local_pred _node) {424 delete pred_node;425 local_pred _node=false;426 } 427 pred_node = &m;423 if(local_predNode) { 424 delete _predNode; 425 local_predNode=false; 426 } 427 _predNode = &m; 428 428 return *this; 429 429 } … … 438 438 Dijkstra &distMap(DistMap &m) 439 439 { 440 if(local_dist ance) {441 delete distance;442 local_dist ance=false;443 } 444 distance= &m;440 if(local_dist) { 441 delete _dist; 442 local_dist=false; 443 } 444 _dist = &m; 445 445 return *this; 446 446 } 447 447 448 private: 449 void finalizeNodeData(Node v,Value dst) 450 { 451 _reached>set(v,true); 452 _dist>set(v, dst); 453 _predNode>set(v,G>source((*_pred)[v])); 454 } 455 456 public: 448 457 ///\name Excetution control 449 458 ///The simplest way to execute the algorithm is to use … … 468 477 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { 469 478 _pred>set(u,INVALID); 470 pred_node>set(u,INVALID);479 _predNode>set(u,INVALID); 471 480 ///\todo *_reached is not set to false. 472 481 _heap_map.set(u,Heap::PRE_HEAP); … … 491 500 { 492 501 Node v=_heap.top(); 493 _reached>set(v,true);494 502 Value oldvalue=_heap[v]; 495 503 _heap.pop(); 496 distance>set(v,oldvalue);504 finalizeNodeData(v,oldvalue); 497 505 498 506 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { … … 502 510 _heap.push(w,oldvalue+(*length)[e]); 503 511 _pred>set(w,e); 504 pred_node>set(w,v);512 // _predNode>set(w,v); 505 513 break; 506 514 case Heap::IN_HEAP: … … 508 516 _heap.decrease(w, oldvalue+(*length)[e]); 509 517 _pred>set(w,e); 510 pred_node>set(w,v);518 // _predNode>set(w,v); 511 519 } 512 520 break; … … 517 525 } 518 526 519 /// Starts the execution ofthe algorithm.520 521 /// Starts the execution ofthe algorithm.522 /// 523 ///\pre init() must be called beforeand at least one node should be added524 ///with addSource() .527 ///Executes the algorithm. 528 529 ///Executes the algorithm. 530 /// 531 ///\pre init() must be called and at least one node should be added 532 ///with addSource() before using this function. 525 533 /// 526 534 ///This method runs the %Dijkstra algorithm from the root node(s) … … 536 544 } 537 545 538 /// Starts the execution ofthe algorithm until \c dest is reached.539 540 /// Starts the execution ofthe algorithm until \c dest is reached.541 /// 542 ///\pre init() must be called beforeand at least one node should be added543 ///with addSource() .546 ///Executes the algorithm until \c dest is reached. 547 548 ///Executes the algorithm until \c dest is reached. 549 /// 550 ///\pre init() must be called and at least one node should be added 551 ///with addSource() before using this function. 544 552 /// 545 553 ///This method runs the %Dijkstra algorithm from the root node(s) … … 552 560 void start(Node dest) 553 561 { 554 while ( !_heap.empty() && _heap.top()!=dest) processNode(); 562 while ( !_heap.empty() && _heap.top()!=dest ) processNode(); 563 if ( _heap.top()==dest ) finalizeNodeData(_heap.top()); 564 } 565 566 ///Executes the algorithm until a condition is met. 567 568 ///Executes the algorithm until a condition is met. 569 /// 570 ///\pre init() must be called and at least one node should be added 571 ///with addSource() before using this function. 572 /// 573 ///\param nm must be a bool (or convertible) node map. The algorithm 574 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>. 575 template<class NM> 576 void start(const NM &nm) 577 { 578 while ( !_heap.empty() && !mn[_heap.top()] ) processNode(); 579 if ( !_heap.empty() ) finalizeNodeData(_heap.top()); 555 580 } 556 581 … … 576 601 } 577 602 603 ///Finds the shortest path between \c s and \c t. 604 605 ///Finds the shortest path between \c s and \c t. 606 /// 607 ///\return The length of the shortest st path if there exists one, 608 ///0 otherwise. 609 ///\note Apart from the return value, d.run(s) is 610 ///just a shortcut of the following code. 611 ///\code 612 /// d.init(); 613 /// d.addSource(s); 614 /// d.start(t); 615 ///\endcode 616 Value run(Node s,Node t) { 617 init(); 618 addSource(s); 619 start(t); 620 return (*_pred)[t]==INVALID?0:(*_dist)[t]; 621 } 622 578 623 ///@} 579 624 … … 592 637 ///\warning If node \c v in unreachable from the root the return value 593 638 ///of this funcion is undefined. 594 Value dist(Node v) const { return (* distance)[v]; }639 Value dist(Node v) const { return (*_dist)[v]; } 595 640 596 641 ///Returns the 'previous edge' of the shortest path tree. … … 614 659 ///tree used in \ref pred(Node v). \pre \ref run() must be called before 615 660 ///using this function. 616 Node predNode(Node v) const { return (*pred_node)[v]; } 661 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 662 G>source((*_pred)[v]); } 617 663 618 664 ///Returns a reference to the NodeMap of distances. … … 620 666 ///Returns a reference to the NodeMap of distances. \pre \ref run() must 621 667 ///be called before using this function. 622 const DistMap &distMap() const { return * distance;}668 const DistMap &distMap() const { return *_dist;} 623 669 624 670 ///Returns a reference to the shortest path tree map. … … 634 680 ///shortest path tree. 635 681 ///\pre \ref run() must be called before using this function. 636 const PredNodeMap &predNodeMap() const { return * pred_node;}682 const PredNodeMap &predNodeMap() const { return *_predNode;} 637 683 638 684 ///Checks if a node is reachable from the root.
Note: See TracChangeset
for help on using the changeset viewer.