1.1 --- a/lemon/dijkstra.h Thu Jan 01 00:00:00 2009 +0100
1.2 +++ b/lemon/dijkstra.h Mon Feb 23 12:10:26 2009 +0100
1.3 @@ -73,7 +73,7 @@
1.4 ///The type of the length of the arcs.
1.5 typedef typename LM::Value Value;
1.6
1.7 - /// Operation traits for Dijkstra algorithm.
1.8 + /// Operation traits for %Dijkstra algorithm.
1.9
1.10 /// This class defines the operations that are used in the algorithm.
1.11 /// \see DijkstraDefaultOperationTraits
1.12 @@ -84,7 +84,7 @@
1.13 /// The cross reference type used by the heap.
1.14 /// Usually it is \c Digraph::NodeMap<int>.
1.15 typedef typename Digraph::template NodeMap<int> HeapCrossRef;
1.16 - ///Instantiates a \ref HeapCrossRef.
1.17 + ///Instantiates a \c HeapCrossRef.
1.18
1.19 ///This function instantiates a \ref HeapCrossRef.
1.20 /// \param g is the digraph, to which we would like to define the
1.21 @@ -94,14 +94,14 @@
1.22 return new HeapCrossRef(g);
1.23 }
1.24
1.25 - ///The heap type used by the Dijkstra algorithm.
1.26 + ///The heap type used by the %Dijkstra algorithm.
1.27
1.28 ///The heap type used by the Dijkstra algorithm.
1.29 ///
1.30 ///\sa BinHeap
1.31 ///\sa Dijkstra
1.32 typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
1.33 - ///Instantiates a \ref Heap.
1.34 + ///Instantiates a \c Heap.
1.35
1.36 ///This function instantiates a \ref Heap.
1.37 static Heap *createHeap(HeapCrossRef& r)
1.38 @@ -116,11 +116,11 @@
1.39 ///arcs of the shortest paths.
1.40 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.41 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.42 - ///Instantiates a PredMap.
1.43 + ///Instantiates a \c PredMap.
1.44
1.45 - ///This function instantiates a PredMap.
1.46 + ///This function instantiates a \ref PredMap.
1.47 ///\param g is the digraph, to which we would like to define the
1.48 - ///PredMap.
1.49 + ///\ref PredMap.
1.50 static PredMap *createPredMap(const Digraph &g)
1.51 {
1.52 return new PredMap(g);
1.53 @@ -132,11 +132,11 @@
1.54 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.55 ///By default it is a NullMap.
1.56 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.57 - ///Instantiates a ProcessedMap.
1.58 + ///Instantiates a \c ProcessedMap.
1.59
1.60 - ///This function instantiates a ProcessedMap.
1.61 + ///This function instantiates a \ref ProcessedMap.
1.62 ///\param g is the digraph, to which
1.63 - ///we would like to define the ProcessedMap
1.64 + ///we would like to define the \ref ProcessedMap.
1.65 #ifdef DOXYGEN
1.66 static ProcessedMap *createProcessedMap(const Digraph &g)
1.67 #else
1.68 @@ -151,11 +151,11 @@
1.69 ///The type of the map that stores the distances of the nodes.
1.70 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.71 typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
1.72 - ///Instantiates a DistMap.
1.73 + ///Instantiates a \c DistMap.
1.74
1.75 - ///This function instantiates a DistMap.
1.76 + ///This function instantiates a \ref DistMap.
1.77 ///\param g is the digraph, to which we would like to define
1.78 - ///the DistMap
1.79 + ///the \ref DistMap.
1.80 static DistMap *createDistMap(const Digraph &g)
1.81 {
1.82 return new DistMap(g);
1.83 @@ -216,7 +216,8 @@
1.84 typedef typename TR::HeapCrossRef HeapCrossRef;
1.85 ///The heap type used by the algorithm.
1.86 typedef typename TR::Heap Heap;
1.87 - ///The operation traits class.
1.88 + ///\brief The \ref DijkstraDefaultOperationTraits "operation traits class"
1.89 + ///of the algorithm.
1.90 typedef typename TR::OperationTraits OperationTraits;
1.91
1.92 ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
1.93 @@ -232,7 +233,7 @@
1.94 //Pointer to the underlying digraph.
1.95 const Digraph *G;
1.96 //Pointer to the length map.
1.97 - const LengthMap *length;
1.98 + const LengthMap *_length;
1.99 //Pointer to the map of predecessors arcs.
1.100 PredMap *_pred;
1.101 //Indicates if _pred is locally allocated (true) or not.
1.102 @@ -297,10 +298,10 @@
1.103 }
1.104 };
1.105 ///\brief \ref named-templ-param "Named parameter" for setting
1.106 - ///PredMap type.
1.107 + ///\c PredMap type.
1.108 ///
1.109 ///\ref named-templ-param "Named parameter" for setting
1.110 - ///PredMap type.
1.111 + ///\c PredMap type.
1.112 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.113 template <class T>
1.114 struct SetPredMap
1.115 @@ -318,10 +319,10 @@
1.116 }
1.117 };
1.118 ///\brief \ref named-templ-param "Named parameter" for setting
1.119 - ///DistMap type.
1.120 + ///\c DistMap type.
1.121 ///
1.122 ///\ref named-templ-param "Named parameter" for setting
1.123 - ///DistMap type.
1.124 + ///\c DistMap type.
1.125 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.126 template <class T>
1.127 struct SetDistMap
1.128 @@ -339,10 +340,10 @@
1.129 }
1.130 };
1.131 ///\brief \ref named-templ-param "Named parameter" for setting
1.132 - ///ProcessedMap type.
1.133 + ///\c ProcessedMap type.
1.134 ///
1.135 ///\ref named-templ-param "Named parameter" for setting
1.136 - ///ProcessedMap type.
1.137 + ///\c ProcessedMap type.
1.138 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.139 template <class T>
1.140 struct SetProcessedMap
1.141 @@ -358,10 +359,10 @@
1.142 }
1.143 };
1.144 ///\brief \ref named-templ-param "Named parameter" for setting
1.145 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.146 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.147 ///
1.148 ///\ref named-templ-param "Named parameter" for setting
1.149 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.150 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.151 ///If you don't set it explicitly, it will be automatically allocated.
1.152 struct SetStandardProcessedMap
1.153 : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
1.154 @@ -439,7 +440,7 @@
1.155 ///\c OperationTraits type
1.156 ///
1.157 ///\ref named-templ-param "Named parameter" for setting
1.158 - ///\ref OperationTraits type.
1.159 + ///\c OperationTraits type.
1.160 template <class T>
1.161 struct SetOperationTraits
1.162 : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
1.163 @@ -458,10 +459,10 @@
1.164 ///Constructor.
1.165
1.166 ///Constructor.
1.167 - ///\param _g The digraph the algorithm runs on.
1.168 - ///\param _length The length map used by the algorithm.
1.169 - Dijkstra(const Digraph& _g, const LengthMap& _length) :
1.170 - G(&_g), length(&_length),
1.171 + ///\param g The digraph the algorithm runs on.
1.172 + ///\param length The length map used by the algorithm.
1.173 + Dijkstra(const Digraph& g, const LengthMap& length) :
1.174 + G(&g), _length(&length),
1.175 _pred(NULL), local_pred(false),
1.176 _dist(NULL), local_dist(false),
1.177 _processed(NULL), local_processed(false),
1.178 @@ -485,7 +486,7 @@
1.179 ///\return <tt> (*this) </tt>
1.180 Dijkstra &lengthMap(const LengthMap &m)
1.181 {
1.182 - length = &m;
1.183 + _length = &m;
1.184 return *this;
1.185 }
1.186
1.187 @@ -638,12 +639,12 @@
1.188 Node w=G->target(e);
1.189 switch(_heap->state(w)) {
1.190 case Heap::PRE_HEAP:
1.191 - _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
1.192 + _heap->push(w,OperationTraits::plus(oldvalue, (*_length)[e]));
1.193 _pred->set(w,e);
1.194 break;
1.195 case Heap::IN_HEAP:
1.196 {
1.197 - Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
1.198 + Value newvalue = OperationTraits::plus(oldvalue, (*_length)[e]);
1.199 if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
1.200 _heap->decrease(w, newvalue);
1.201 _pred->set(w,e);