1.1 --- a/lemon/dijkstra.h Fri Dec 07 12:00:32 2007 +0000
1.2 +++ b/lemon/dijkstra.h Mon Dec 10 16:33:37 2007 +0000
1.3 @@ -23,7 +23,6 @@
1.4 ///\file
1.5 ///\brief Dijkstra algorithm.
1.6 ///
1.7 -///\todo dijkstraZero() solution should be revised.
1.8
1.9 #include <lemon/list_graph.h>
1.10 #include <lemon/bin_heap.h>
1.11 @@ -35,7 +34,45 @@
1.12
1.13 namespace lemon {
1.14
1.15 - template<class T> T dijkstraZero() {return 0;}
1.16 + /// \brief Default OperationTraits for the Dijkstra algorithm class.
1.17 + ///
1.18 + /// It defines all computational operations and constants which are
1.19 + /// used in the Dijkstra algorithm.
1.20 + template <typename Value>
1.21 + struct DijkstraDefaultOperationTraits {
1.22 + /// \brief Gives back the zero value of the type.
1.23 + static Value zero() {
1.24 + return static_cast<Value>(0);
1.25 + }
1.26 + /// \brief Gives back the sum of the given two elements.
1.27 + static Value plus(const Value& left, const Value& right) {
1.28 + return left + right;
1.29 + }
1.30 + /// \brief Gives back true only if the first value less than the second.
1.31 + static bool less(const Value& left, const Value& right) {
1.32 + return left < right;
1.33 + }
1.34 + };
1.35 +
1.36 + /// \brief Widest path OperationTraits for the Dijkstra algorithm class.
1.37 + ///
1.38 + /// It defines all computational operations and constants which are
1.39 + /// used in the Dijkstra algorithm for widest path computation.
1.40 + template <typename Value>
1.41 + struct DijkstraWidestPathOperationTraits {
1.42 + /// \brief Gives back the maximum value of the type.
1.43 + static Value zero() {
1.44 + return std::numeric_limits<Value>::max();
1.45 + }
1.46 + /// \brief Gives back the maximum of the given two elements.
1.47 + static Value plus(const Value& left, const Value& right) {
1.48 + return std::min(left, right);
1.49 + }
1.50 + /// \brief Gives back true only if the first value less than the second.
1.51 + static bool less(const Value& left, const Value& right) {
1.52 + return left < right;
1.53 + }
1.54 + };
1.55
1.56 ///Default traits class of Dijkstra class.
1.57
1.58 @@ -54,14 +91,20 @@
1.59 typedef LM LengthMap;
1.60 //The type of the length of the edges.
1.61 typedef typename LM::Value Value;
1.62 + /// Operation traits for Dijkstra algorithm.
1.63 +
1.64 + /// It defines the used operation by the algorithm.
1.65 + /// \see DijkstraDefaultOperationTraits
1.66 + typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
1.67 /// The cross reference type used by heap.
1.68
1.69 +
1.70 /// The cross reference type used by heap.
1.71 /// Usually it is \c Graph::NodeMap<int>.
1.72 typedef typename Graph::template NodeMap<int> HeapCrossRef;
1.73 ///Instantiates a HeapCrossRef.
1.74
1.75 - ///This function instantiates a \ref HeapCrossRef.
1.76 + ///This function instantiates a \c HeapCrossRef.
1.77 /// \param G is the graph, to which we would like to define the
1.78 /// HeapCrossRef.
1.79 static HeapCrossRef *createHeapCrossRef(const GR &G)
1.80 @@ -92,7 +135,7 @@
1.81 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
1.82 ///Instantiates a PredMap.
1.83
1.84 - ///This function instantiates a \ref PredMap.
1.85 + ///This function instantiates a \c PredMap.
1.86 ///\param G is the graph, to which we would like to define the PredMap.
1.87 ///\todo The graph alone may be insufficient for the initialization
1.88 static PredMap *createPredMap(const GR &G)
1.89 @@ -111,9 +154,9 @@
1.90 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
1.91 ///Instantiates a ProcessedMap.
1.92
1.93 - ///This function instantiates a \ref ProcessedMap.
1.94 + ///This function instantiates a \c ProcessedMap.
1.95 ///\param g is the graph, to which
1.96 - ///we would like to define the \ref ProcessedMap
1.97 + ///we would like to define the \c ProcessedMap
1.98 #ifdef DOXYGEN
1.99 static ProcessedMap *createProcessedMap(const GR &g)
1.100 #else
1.101 @@ -170,9 +213,7 @@
1.102 ///\author Jacint Szabo and Alpar Juttner
1.103
1.104 #ifdef DOXYGEN
1.105 - template <typename GR,
1.106 - typename LM,
1.107 - typename TR>
1.108 + template <typename GR, typename LM, typename TR>
1.109 #else
1.110 template <typename GR=ListGraph,
1.111 typename LM=typename GR::template EdgeMap<int>,
1.112 @@ -220,6 +261,8 @@
1.113 typedef typename TR::HeapCrossRef HeapCrossRef;
1.114 ///The heap type used by the dijkstra algorithm.
1.115 typedef typename TR::Heap Heap;
1.116 + ///The operation traits.
1.117 + typedef typename TR::OperationTraits OperationTraits;
1.118 private:
1.119 /// Pointer to the underlying graph.
1.120 const Graph *G;
1.121 @@ -403,6 +446,23 @@
1.122 typedef Dijkstra< Graph, LengthMap, DefStandardHeapTraits<H, CR> >
1.123 Create;
1.124 };
1.125 +
1.126 + template <class T>
1.127 + struct DefOperationTraitsTraits : public Traits {
1.128 + typedef T OperationTraits;
1.129 + };
1.130 +
1.131 + /// \brief \ref named-templ-param "Named parameter" for setting
1.132 + /// OperationTraits type
1.133 + ///
1.134 + /// \ref named-templ-param "Named parameter" for setting OperationTraits
1.135 + /// type
1.136 + template <class T>
1.137 + struct DefOperationTraits
1.138 + : public Dijkstra<Graph, LengthMap, DefOperationTraitsTraits<T> > {
1.139 + typedef Dijkstra<Graph, LengthMap, DefOperationTraitsTraits<T> >
1.140 + Create;
1.141 + };
1.142
1.143 ///@}
1.144
1.145 @@ -549,11 +609,11 @@
1.146 ///It checks if the node has already been added to the heap and
1.147 ///it is pushed to the heap only if either it was not in the heap
1.148 ///or the shortest path found till then is shorter than \c dst.
1.149 - void addSource(Node s,Value dst=dijkstraZero<Value>())
1.150 + void addSource(Node s,Value dst=OperationTraits::zero())
1.151 {
1.152 if(_heap->state(s) != Heap::IN_HEAP) {
1.153 _heap->push(s,dst);
1.154 - } else if((*_heap)[s]<dst) {
1.155 + } else if(OperationTraits::less((*_heap)[s], dst)) {
1.156 _heap->set(s,dst);
1.157 _pred->set(s,INVALID);
1.158 }
1.159 @@ -577,13 +637,16 @@
1.160 Node w=G->target(e);
1.161 switch(_heap->state(w)) {
1.162 case Heap::PRE_HEAP:
1.163 - _heap->push(w,oldvalue+(*length)[e]);
1.164 + _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
1.165 _pred->set(w,e);
1.166 break;
1.167 case Heap::IN_HEAP:
1.168 - if ( oldvalue+(*length)[e] < (*_heap)[w] ) {
1.169 - _heap->decrease(w, oldvalue+(*length)[e]);
1.170 - _pred->set(w,e);
1.171 + {
1.172 + Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
1.173 + if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
1.174 + _heap->decrease(w, newvalue);
1.175 + _pred->set(w,e);
1.176 + }
1.177 }
1.178 break;
1.179 case Heap::POST_HEAP:
1.180 @@ -714,7 +777,7 @@
1.181 init();
1.182 addSource(s);
1.183 start(t);
1.184 - return (*_pred)[t]==INVALID?dijkstraZero<Value>():(*_dist)[t];
1.185 + return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];
1.186 }
1.187
1.188 ///@}
1.189 @@ -826,6 +889,11 @@
1.190 typedef LM LengthMap;
1.191 //The type of the length of the edges.
1.192 typedef typename LM::Value Value;
1.193 + /// Operation traits for Dijkstra algorithm.
1.194 +
1.195 + /// It defines the used operation by the algorithm.
1.196 + /// \see DijkstraDefaultOperationTraits
1.197 + typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
1.198 ///The heap type used by Dijkstra algorithm.
1.199
1.200 /// The cross reference type used by heap.