Changeset 2537:4a2091b1796a in lemon0.x
 Timestamp:
 12/10/07 17:33:37 (13 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@3414
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/dijkstra.h
r2476 r2537 24 24 ///\brief Dijkstra algorithm. 25 25 /// 26 ///\todo dijkstraZero() solution should be revised.27 26 28 27 #include <lemon/list_graph.h> … … 36 35 namespace lemon { 37 36 38 template<class T> T dijkstraZero() {return 0;} 37 /// \brief Default OperationTraits for the Dijkstra algorithm class. 38 /// 39 /// It defines all computational operations and constants which are 40 /// used in the Dijkstra algorithm. 41 template <typename Value> 42 struct DijkstraDefaultOperationTraits { 43 /// \brief Gives back the zero value of the type. 44 static Value zero() { 45 return static_cast<Value>(0); 46 } 47 /// \brief Gives back the sum of the given two elements. 48 static Value plus(const Value& left, const Value& right) { 49 return left + right; 50 } 51 /// \brief Gives back true only if the first value less than the second. 52 static bool less(const Value& left, const Value& right) { 53 return left < right; 54 } 55 }; 56 57 /// \brief Widest path OperationTraits for the Dijkstra algorithm class. 58 /// 59 /// It defines all computational operations and constants which are 60 /// used in the Dijkstra algorithm for widest path computation. 61 template <typename Value> 62 struct DijkstraWidestPathOperationTraits { 63 /// \brief Gives back the maximum value of the type. 64 static Value zero() { 65 return std::numeric_limits<Value>::max(); 66 } 67 /// \brief Gives back the maximum of the given two elements. 68 static Value plus(const Value& left, const Value& right) { 69 return std::min(left, right); 70 } 71 /// \brief Gives back true only if the first value less than the second. 72 static bool less(const Value& left, const Value& right) { 73 return left < right; 74 } 75 }; 39 76 40 77 ///Default traits class of Dijkstra class. … … 55 92 //The type of the length of the edges. 56 93 typedef typename LM::Value Value; 94 /// Operation traits for Dijkstra algorithm. 95 96 /// It defines the used operation by the algorithm. 97 /// \see DijkstraDefaultOperationTraits 98 typedef DijkstraDefaultOperationTraits<Value> OperationTraits; 57 99 /// The cross reference type used by heap. 100 58 101 59 102 /// The cross reference type used by heap. … … 62 105 ///Instantiates a HeapCrossRef. 63 106 64 ///This function instantiates a \ refHeapCrossRef.107 ///This function instantiates a \c HeapCrossRef. 65 108 /// \param G is the graph, to which we would like to define the 66 109 /// HeapCrossRef. … … 93 136 ///Instantiates a PredMap. 94 137 95 ///This function instantiates a \ refPredMap.138 ///This function instantiates a \c PredMap. 96 139 ///\param G is the graph, to which we would like to define the PredMap. 97 140 ///\todo The graph alone may be insufficient for the initialization … … 112 155 ///Instantiates a ProcessedMap. 113 156 114 ///This function instantiates a \ refProcessedMap.157 ///This function instantiates a \c ProcessedMap. 115 158 ///\param g is the graph, to which 116 ///we would like to define the \ refProcessedMap159 ///we would like to define the \c ProcessedMap 117 160 #ifdef DOXYGEN 118 161 static ProcessedMap *createProcessedMap(const GR &g) … … 171 214 172 215 #ifdef DOXYGEN 173 template <typename GR, 174 typename LM, 175 typename TR> 216 template <typename GR, typename LM, typename TR> 176 217 #else 177 218 template <typename GR=ListGraph, … … 221 262 ///The heap type used by the dijkstra algorithm. 222 263 typedef typename TR::Heap Heap; 264 ///The operation traits. 265 typedef typename TR::OperationTraits OperationTraits; 223 266 private: 224 267 /// Pointer to the underlying graph. … … 404 447 Create; 405 448 }; 449 450 template <class T> 451 struct DefOperationTraitsTraits : public Traits { 452 typedef T OperationTraits; 453 }; 454 455 /// \brief \ref namedtemplparam "Named parameter" for setting 456 /// OperationTraits type 457 /// 458 /// \ref namedtemplparam "Named parameter" for setting OperationTraits 459 /// type 460 template <class T> 461 struct DefOperationTraits 462 : public Dijkstra<Graph, LengthMap, DefOperationTraitsTraits<T> > { 463 typedef Dijkstra<Graph, LengthMap, DefOperationTraitsTraits<T> > 464 Create; 465 }; 406 466 407 467 ///@} … … 550 610 ///it is pushed to the heap only if either it was not in the heap 551 611 ///or the shortest path found till then is shorter than \c dst. 552 void addSource(Node s,Value dst= dijkstraZero<Value>())612 void addSource(Node s,Value dst=OperationTraits::zero()) 553 613 { 554 614 if(_heap>state(s) != Heap::IN_HEAP) { 555 615 _heap>push(s,dst); 556 } else if( (*_heap)[s]<dst) {616 } else if(OperationTraits::less((*_heap)[s], dst)) { 557 617 _heap>set(s,dst); 558 618 _pred>set(s,INVALID); … … 578 638 switch(_heap>state(w)) { 579 639 case Heap::PRE_HEAP: 580 _heap>push(w, oldvalue+(*length)[e]);640 _heap>push(w,OperationTraits::plus(oldvalue, (*length)[e])); 581 641 _pred>set(w,e); 582 642 break; 583 643 case Heap::IN_HEAP: 584 if ( oldvalue+(*length)[e] < (*_heap)[w] ) { 585 _heap>decrease(w, oldvalue+(*length)[e]); 586 _pred>set(w,e); 644 { 645 Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]); 646 if ( OperationTraits::less(newvalue, (*_heap)[w]) ) { 647 _heap>decrease(w, newvalue); 648 _pred>set(w,e); 649 } 587 650 } 588 651 break; … … 715 778 addSource(s); 716 779 start(t); 717 return (*_pred)[t]==INVALID? dijkstraZero<Value>():(*_dist)[t];780 return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t]; 718 781 } 719 782 … … 827 890 //The type of the length of the edges. 828 891 typedef typename LM::Value Value; 892 /// Operation traits for Dijkstra algorithm. 893 894 /// It defines the used operation by the algorithm. 895 /// \see DijkstraDefaultOperationTraits 896 typedef DijkstraDefaultOperationTraits<Value> OperationTraits; 829 897 ///The heap type used by Dijkstra algorithm. 830 898
Note: See TracChangeset
for help on using the changeset viewer.