lemon-1.1: comparison lemon/dijkstra.h

equal deleted inserted replaced

-:5f5e9a5f2538
+:c63c1a4939a1
 ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
 typedef LM LengthMap;
 ///The type of the length of the arcs.
 typedef typename LM::Value Value;
-/// Operation traits for Dijkstra algorithm.
+/// Operation traits for %Dijkstra algorithm.
 /// This class defines the operations that are used in the algorithm.
 /// \see DijkstraDefaultOperationTraits
 typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
 /// The cross reference type used by the heap.
 /// The cross reference type used by the heap.
 /// Usually it is \c Digraph::NodeMap<int>.
 typedef typename Digraph::template NodeMap<int> HeapCrossRef;
-///Instantiates a \ref HeapCrossRef.
+///Instantiates a \c HeapCrossRef.
 ///This function instantiates a \ref HeapCrossRef.
 /// \param g is the digraph, to which we would like to define the
 /// \ref HeapCrossRef.
 static HeapCrossRef *createHeapCrossRef(const Digraph &g)
 {
 return new HeapCrossRef(g);
 }
-///The heap type used by the Dijkstra algorithm.
+///The heap type used by the %Dijkstra algorithm.
 ///The heap type used by the Dijkstra algorithm.
 ///
 ///\sa BinHeap
 ///\sa Dijkstra
 typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
-///Instantiates a \ref Heap.
+///Instantiates a \c Heap.
 ///This function instantiates a \ref Heap.
 static Heap *createHeap(HeapCrossRef& r)
 {
 return new Heap(r);
 ///
 ///The type of the map that stores the predecessor
 ///arcs of the shortest paths.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
-///Instantiates a PredMap.
+///Instantiates a \c PredMap.
-///This function instantiates a PredMap.
+///This function instantiates a \ref PredMap.
 ///\param g is the digraph, to which we would like to define the
-///PredMap.
+///\ref PredMap.
 static PredMap *createPredMap(const Digraph &g)
 {
 return new PredMap(g);
 }
 ///The type of the map that indicates which nodes are processed.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 ///By default it is a NullMap.
 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
-///Instantiates a ProcessedMap.
+///Instantiates a \c ProcessedMap.
-///This function instantiates a ProcessedMap.
+///This function instantiates a \ref ProcessedMap.
 ///\param g is the digraph, to which
-///we would like to define the ProcessedMap
+///we would like to define the \ref ProcessedMap.
 #ifdef DOXYGEN
 static ProcessedMap *createProcessedMap(const Digraph &g)
 #else
 static ProcessedMap *createProcessedMap(const Digraph &)
 #endif
 ///The type of the map that stores the distances of the nodes.
 ///The type of the map that stores the distances of the nodes.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
-///Instantiates a DistMap.
+///Instantiates a \c DistMap.
-///This function instantiates a DistMap.
+///This function instantiates a \ref DistMap.
 ///\param g is the digraph, to which we would like to define
-///the DistMap
+///the \ref DistMap.
 static DistMap *createDistMap(const Digraph &g)
 {
 return new DistMap(g);
 }
 };
 typedef PredMapPath<Digraph, PredMap> Path;
 ///The cross reference type used for the current heap.
 typedef typename TR::HeapCrossRef HeapCrossRef;
 ///The heap type used by the algorithm.
 typedef typename TR::Heap Heap;
-///The operation traits class.
+///\brief The \ref DijkstraDefaultOperationTraits "operation traits class"
+///of the algorithm.
 typedef typename TR::OperationTraits OperationTraits;
 ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
 typedef TR Traits;
 typedef typename Digraph::OutArcIt OutArcIt;
 //Pointer to the underlying digraph.
 const Digraph *G;
 //Pointer to the length map.
-const LengthMap *length;
+const LengthMap *_length;
 //Pointer to the map of predecessors arcs.
 PredMap *_pred;
 //Indicates if _pred is locally allocated (true) or not.
 bool local_pred;
 //Pointer to the map of distances.
 LEMON_ASSERT(false, "PredMap is not initialized");
 return 0; // ignore warnings
 }
 };
 ///\brief \ref named-templ-param "Named parameter" for setting
-///PredMap type.
+///\c PredMap type.
 ///
 ///\ref named-templ-param "Named parameter" for setting
-///PredMap type.
+///\c PredMap type.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 template <class T>
 struct SetPredMap
 : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
 typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
 LEMON_ASSERT(false, "DistMap is not initialized");
 return 0; // ignore warnings
 }
 };
 ///\brief \ref named-templ-param "Named parameter" for setting
-///DistMap type.
+///\c DistMap type.
 ///
 ///\ref named-templ-param "Named parameter" for setting
-///DistMap type.
+///\c DistMap type.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 template <class T>
 struct SetDistMap
 : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
 typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
 LEMON_ASSERT(false, "ProcessedMap is not initialized");
 return 0; // ignore warnings
 }
 };
 ///\brief \ref named-templ-param "Named parameter" for setting
-///ProcessedMap type.
+///\c ProcessedMap type.
 ///
 ///\ref named-templ-param "Named parameter" for setting
-///ProcessedMap type.
+///\c ProcessedMap type.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 template <class T>
 struct SetProcessedMap
 : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
 typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
 {
 return new ProcessedMap(g);
 }
 };
 ///\brief \ref named-templ-param "Named parameter" for setting
-///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 ///
 ///\ref named-templ-param "Named parameter" for setting
-///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 ///If you don't set it explicitly, it will be automatically allocated.
 struct SetStandardProcessedMap
 : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
 typedef Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits >
 Create;
 /// \brief \ref named-templ-param "Named parameter" for setting
 ///\c OperationTraits type
 ///
 ///\ref named-templ-param "Named parameter" for setting
-///\ref OperationTraits type.
+///\c OperationTraits type.
 template <class T>
 struct SetOperationTraits
 : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
 typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> >
 Create;
 public:
 ///Constructor.
 ///Constructor.
-///\param _g The digraph the algorithm runs on.
+///\param g The digraph the algorithm runs on.
-///\param _length The length map used by the algorithm.
+///\param length The length map used by the algorithm.
-Dijkstra(const Digraph& _g, const LengthMap& _length) :
+Dijkstra(const Digraph& g, const LengthMap& length) :
-G(&_g), length(&_length),
+G(&g), _length(&length),
 _pred(NULL), local_pred(false),
 _dist(NULL), local_dist(false),
 _processed(NULL), local_processed(false),
 _heap_cross_ref(NULL), local_heap_cross_ref(false),
 _heap(NULL), local_heap(false)
 ///Sets the length map.
 ///\return <tt> (*this) </tt>
 Dijkstra &lengthMap(const LengthMap &m)
 {
-length = &m;
+_length = &m;
 return *this;
 }
 ///Sets the map that stores the predecessor arcs.
 for(OutArcIt e(*G,v); e!=INVALID; ++e) {
 Node w=G->target(e);
 switch(_heap->state(w)) {
 case Heap::PRE_HEAP:
-_heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
+_heap->push(w,OperationTraits::plus(oldvalue, (*_length)[e]));
 _pred->set(w,e);
 break;
 case Heap::IN_HEAP:
 {
-Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
+Value newvalue = OperationTraits::plus(oldvalue, (*_length)[e]);
 if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
 _heap->decrease(w, newvalue);
 _pred->set(w,e);
 }
 }

changeset 530	fc6c7aab4b8d
parent 440	88ed40ad0d4f
child 550	c5fd2d996909