Changeset 1721:c0f5e8401373 in lemon-0.x
- Timestamp:
- 10/14/05 12:52:15 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2248
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/dijkstra.h
r1710 r1721 51 51 //The type of the length of the edges. 52 52 typedef typename LM::Value Value; 53 /// The cross reference type used by heap. 54 55 /// The cross reference type used by heap. 56 /// Usually it is \c Graph::NodeMap<int>. 57 typedef typename Graph::template NodeMap<int> HeapCrossRef; 58 ///Instantiates a HeapCrossRef. 59 60 ///This function instantiates a \ref HeapCrossRef. 61 /// \param G is the graph, to which we would like to define the 62 /// HeapCrossRef. 63 /// \todo The graph alone may be insufficient for the initialization 64 static HeapCrossRef *createHeapCrossRef(const GR &G) 65 { 66 return new HeapCrossRef(G); 67 } 68 53 69 ///The heap type used by Dijkstra algorithm. 54 70 … … 60 76 typename GR::template NodeMap<int>, 61 77 std::less<Value> > Heap; 78 79 static Heap *createHeap(HeapCrossRef& R) 80 { 81 return new Heap(R); 82 } 62 83 63 84 ///\brief The type of the map that stores the last … … 196 217 ///The type of the map that stores the dists of the nodes. 197 218 typedef typename TR::DistMap DistMap; 219 ///The cross reference type used for the current heap. 220 typedef typename TR::HeapCrossRef HeapCrossRef; 198 221 ///The heap type used by the dijkstra algorithm. 199 222 typedef typename TR::Heap Heap; … … 215 238 ///Indicates if \ref _processed is locally allocated (\c true) or not. 216 239 bool local_processed; 240 ///Pointer to the heap cross references. 241 HeapCrossRef *_heap_cross_ref; 242 ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not. 243 bool local_heap_cross_ref; 244 ///Pointer to the heap. 245 Heap *_heap; 246 ///Indicates if \ref _heap is locally allocated (\c true) or not. 247 bool local_heap; 217 248 218 249 ///Creates the maps if necessary. … … 233 264 local_processed = true; 234 265 _processed = Traits::createProcessedMap(*G); 266 } 267 if (!_heap_cross_ref) { 268 local_heap_cross_ref = true; 269 _heap_cross_ref = Traits::createHeapCrossRef(*G); 270 } 271 if (!_heap) { 272 local_heap = true; 273 _heap = Traits::createHeap(*_heap_cross_ref); 235 274 } 236 275 } … … 316 355 typedef Dijkstra< Graph, LengthMap, DefGraphProcessedMapTraits> Create; 317 356 }; 357 358 template <class H, class CR> 359 struct DefHeapTraits : public Traits { 360 typedef CR HeapCrossRef; 361 typedef H Heap; 362 static HeapCrossRef *createHeapCrossRef(const Graph &G) { 363 return new HeapCrossRef(G); 364 } 365 static Heap *createHeap(HeapCrossRef &R) 366 { 367 return new Heap(R); 368 } 369 }; 370 ///\ref named-templ-param "Named parameter" for setting heap and cross 371 ///reference type 372 373 ///\ref named-templ-param "Named parameter" for setting heap and cross 374 ///reference type 375 /// 376 template <class H, class CR = typename Graph::template NodeMap<int> > 377 struct DefHeap 378 : public Dijkstra< Graph, LengthMap, DefHeapTraits<H, CR> > { 379 typedef Dijkstra< Graph, LengthMap, DefHeapTraits<H, CR> > Create; 380 }; 318 381 319 382 ///@} 320 383 321 384 322 private:323 typename Graph::template NodeMap<int> _heap_map;324 Heap _heap;325 385 protected: 326 386 … … 338 398 _dist(NULL), local_dist(false), 339 399 _processed(NULL), local_processed(false), 340 _heap_map(*G,-1),_heap(_heap_map) 400 _heap_cross_ref(NULL), local_heap_cross_ref(false), 401 _heap(NULL), local_heap(false) 341 402 { } 342 403 … … 347 408 if(local_dist) delete _dist; 348 409 if(local_processed) delete _processed; 410 if(local_heap_cross_ref) delete _heap_cross_ref; 411 if(local_heap) delete _heap; 349 412 } 350 413 … … 417 480 ///Initializes the internal data structures. 418 481 /// 419 ///\todo _heap_map's type could also be in the traits class.420 ///\todo The heaps should be able to make themselves empty directly.421 482 void init() 422 483 { 423 484 create_maps(); 424 while(!_heap.empty()) _heap.pop();485 _heap->clear(); 425 486 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { 426 487 _pred->set(u,INVALID); 427 488 _processed->set(u,false); 428 _heap_ map.set(u,Heap::PRE_HEAP);489 _heap_cross_ref->set(u,Heap::PRE_HEAP); 429 490 } 430 491 } … … 441 502 void addSource(Node s,Value dst=0) 442 503 { 443 if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst); 444 else if(_heap[s]<dst) { 445 _heap.push(s,dst); 504 if(_heap->state(s) != Heap::IN_HEAP) { 505 _heap->push(s,dst); 506 } else if((*_heap)[s]<dst) { 507 _heap->push(s,dst); 446 508 _pred->set(s,INVALID); 447 509 } … … 457 519 Node processNextNode() 458 520 { 459 Node v=_heap .top();460 Value oldvalue=_heap [v];461 _heap .pop();521 Node v=_heap->top(); 522 Value oldvalue=_heap->prio(); 523 _heap->pop(); 462 524 finalizeNodeData(v,oldvalue); 463 525 464 526 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { 465 527 Node w=G->target(e); 466 switch(_heap .state(w)) {528 switch(_heap->state(w)) { 467 529 case Heap::PRE_HEAP: 468 _heap .push(w,oldvalue+(*length)[e]);530 _heap->push(w,oldvalue+(*length)[e]); 469 531 _pred->set(w,e); 470 532 break; 471 533 case Heap::IN_HEAP: 472 if ( oldvalue+(*length)[e] < _heap[w] ) {473 _heap .decrease(w, oldvalue+(*length)[e]);534 if ( oldvalue+(*length)[e] < (*_heap)[w] ) { 535 _heap->decrease(w, oldvalue+(*length)[e]); 474 536 _pred->set(w,e); 475 537 } … … 490 552 Node nextNode() 491 553 { 492 return _heap .empty()?_heap.top():INVALID;554 return _heap->empty()?_heap->top():INVALID; 493 555 } 494 556 … … 498 560 ///Returns \c false if there are nodes 499 561 ///to be processed in the priority heap 500 bool emptyQueue() { return _heap .empty(); }562 bool emptyQueue() { return _heap->empty(); } 501 563 ///Returns the number of the nodes to be processed in the priority heap 502 564 503 565 ///Returns the number of the nodes to be processed in the priority heap 504 566 /// 505 int queueSize() { return _heap .size(); }567 int queueSize() { return _heap->size(); } 506 568 507 569 ///Executes the algorithm. … … 521 583 void start() 522 584 { 523 while ( !_heap .empty() ) processNextNode();585 while ( !_heap->empty() ) processNextNode(); 524 586 } 525 587 … … 540 602 void start(Node dest) 541 603 { 542 while ( !_heap .empty() && _heap.top()!=dest ) processNextNode();543 if ( !_heap .empty() ) finalizeNodeData(_heap.top(),_heap.prio());604 while ( !_heap->empty() && _heap->top()!=dest ) processNextNode(); 605 if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio()); 544 606 } 545 607 … … 556 618 void start(const NodeBoolMap &nm) 557 619 { 558 while ( !_heap .empty() && !nm[_heap.top()] ) processNextNode();559 if ( !_heap .empty() ) finalizeNodeData(_heap.top(),_heap.prio());620 while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode(); 621 if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio()); 560 622 } 561 623 … … 684 746 ///\pre \ref run() must be called before using this function. 685 747 /// 686 bool reached(Node v) { return _heap_map[v]!=Heap::PRE_HEAP; }748 bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; } 687 749 688 750 ///@} … … 712 774 ///The heap type used by Dijkstra algorithm. 713 775 776 /// The cross reference type used by heap. 777 778 /// The cross reference type used by heap. 779 /// Usually it is \c Graph::NodeMap<int>. 780 typedef typename Graph::template NodeMap<int> HeapCrossRef; 781 ///Instantiates a HeapCrossRef. 782 783 ///This function instantiates a \ref HeapCrossRef. 784 /// \param G is the graph, to which we would like to define the 785 /// HeapCrossRef. 786 /// \todo The graph alone may be insufficient for the initialization 787 static HeapCrossRef *createHeapCrossRef(const GR &G) 788 { 789 return new HeapCrossRef(G); 790 } 791 792 ///The heap type used by Dijkstra algorithm. 793 714 794 ///The heap type used by Dijkstra algorithm. 715 795 /// 716 796 ///\sa BinHeap 717 797 ///\sa Dijkstra 718 typedef BinHeap<typename Graph::Node, 719 typename LM::Value, 798 typedef BinHeap<typename Graph::Node, typename LM::Value, 720 799 typename GR::template NodeMap<int>, 721 800 std::less<Value> > Heap; 801 802 static Heap *createHeap(HeapCrossRef& R) 803 { 804 return new Heap(R); 805 } 722 806 723 807 ///\brief The type of the map that stores the last … … 808 892 ///Pointer to the map of predecessors edges. 809 893 void *_pred; 810 // ///Pointer to the map of predecessors nodes.811 // void *_predNode;812 894 ///Pointer to the map of distances. 813 895 void *_dist; … … 821 903 /// all of the attributes to default values (0, INVALID). 822 904 DijkstraWizardBase() : _g(0), _length(0), _pred(0), 823 // _predNode(0),824 905 _dist(0), _source(INVALID) {} 825 906 … … 834 915 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) : 835 916 _g((void *)&g), _length((void *)&l), _pred(0), 836 // _predNode(0),837 917 _dist(0), _source(s) {} 838 918 … … 856 936 /// 857 937 /// It does not have own \ref run method. When its \ref run method is called 858 /// it initiates a plain \ref Dijkstra class, and calls the \ref Dijkstra::run859 /// method of it.938 /// it initiates a plain \ref Dijkstra class, and calls the \ref 939 /// Dijkstra::run method of it. 860 940 template<class TR> 861 941 class DijkstraWizard : public TR … … 881 961 ///edges of the shortest paths. 882 962 typedef typename TR::PredMap PredMap; 883 // ///\brief The type of the map that stores the last but one884 // ///nodes of the shortest paths.885 // typedef typename TR::PredNodeMap PredNodeMap;886 963 ///The type of the map that stores the dists of the nodes. 887 964 typedef typename TR::DistMap DistMap; 888 889 965 ///The heap type used by the dijkstra algorithm. 890 966 typedef typename TR::Heap Heap; … … 915 991 dij(*(Graph*)Base::_g,*(LengthMap*)Base::_length); 916 992 if(Base::_pred) dij.predMap(*(PredMap*)Base::_pred); 917 // if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode);918 993 if(Base::_dist) dij.distMap(*(DistMap*)Base::_dist); 919 994 dij.run(Base::_source); … … 950 1025 } 951 1026 952 953 // template<class T>954 // struct DefPredNodeMapBase : public Base {955 // typedef T PredNodeMap;956 // static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };957 // DefPredNodeMapBase(const TR &b) : TR(b) {}958 // };959 960 // ///\brief \ref named-templ-param "Named parameter"961 // ///function for setting PredNodeMap type962 // ///963 // /// \ref named-templ-param "Named parameter"964 // ///function for setting PredNodeMap type965 // ///966 // template<class T>967 // DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)968 // {969 // Base::_predNode=(void *)&t;970 // return DijkstraWizard<DefPredNodeMapBase<T> >(*this);971 // }972 973 1027 template<class T> 974 1028 struct DefDistMapBase : public Base {
Note: See TracChangeset
for help on using the changeset viewer.