diff -r 269f0cbfbcc8 -r 6d81e6f7a88d lemon/dijkstra.h --- a/lemon/dijkstra.h Fri Sep 30 13:15:28 2005 +0000 +++ b/lemon/dijkstra.h Mon Oct 03 10:11:29 2005 +0000 @@ -78,23 +78,6 @@ { return new PredMap(G); } -// ///\brief The type of the map that stores the last but one -// ///nodes of the shortest paths. -// /// -// ///The type of the map that stores the last but one -// ///nodes of the shortest paths. -// ///It must meet the \ref concept::WriteMap "WriteMap" concept. -// /// -// typedef NullMap PredNodeMap; -// ///Instantiates a PredNodeMap. - -// ///This function instantiates a \ref PredNodeMap. -// ///\param G is the graph, to which -// ///we would like to define the \ref PredNodeMap -// static PredNodeMap *createPredNodeMap(const GR &G) -// { -// return new PredNodeMap(); -// } ///The type of the map that stores whether a nodes is processed. @@ -209,9 +192,6 @@ ///\brief The type of the map that stores the last ///edges of the shortest paths. typedef typename TR::PredMap PredMap; -// ///\brief The type of the map that stores the last but one -// ///nodes of the shortest paths. -// typedef typename TR::PredNodeMap PredNodeMap; ///The type of the map indicating if a node is processed. typedef typename TR::ProcessedMap ProcessedMap; ///The type of the map that stores the dists of the nodes. @@ -227,10 +207,6 @@ PredMap *_pred; ///Indicates if \ref _pred is locally allocated (\c true) or not. bool local_pred; -// ///Pointer to the map of predecessors nodes. -// PredNodeMap *_predNode; -// ///Indicates if \ref _predNode is locally allocated (\c true) or not. -// bool local_predNode; ///Pointer to the map of distances. DistMap *_dist; ///Indicates if \ref _dist is locally allocated (\c true) or not. @@ -240,9 +216,6 @@ ///Indicates if \ref _processed is locally allocated (\c true) or not. bool local_processed; -// ///The source node of the last execution. -// Node source; - ///Creates the maps if necessary. ///\todo Error if \c G or are \c NULL. What about \c length? @@ -253,10 +226,6 @@ local_pred = true; _pred = Traits::createPredMap(*G); } -// if(!_predNode) { -// local_predNode = true; -// _predNode = Traits::createPredNodeMap(*G); -// } if(!_dist) { local_dist = true; _dist = Traits::createDistMap(*G); @@ -290,23 +259,6 @@ LengthMap, DefPredMapTraits > { }; -// template -// struct DefPredNodeMapTraits : public Traits { -// typedef T PredNodeMap; -// static PredNodeMap *createPredNodeMap(const Graph &G) -// { -// throw UninitializedParameter(); -// } -// }; -// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type - -// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type -// /// -// template -// class DefPredNodeMap : public Dijkstra< Graph, -// LengthMap, -// DefPredNodeMapTraits > { }; - template struct DefDistMapTraits : public Traits { typedef T DistMap; @@ -375,7 +327,6 @@ Dijkstra(const Graph& _G, const LengthMap& _length) : G(&_G), length(&_length), _pred(NULL), local_pred(false), -// _predNode(NULL), local_predNode(false), _dist(NULL), local_dist(false), _processed(NULL), local_processed(false), _heap_map(*G,-1),_heap(_heap_map) @@ -385,7 +336,6 @@ ~Dijkstra() { if(local_pred) delete _pred; -// if(local_predNode) delete _predNode; if(local_dist) delete _dist; if(local_processed) delete _processed; } @@ -417,23 +367,6 @@ return *this; } -// ///Sets the map storing the predecessor nodes. - -// ///Sets the map storing the predecessor nodes. -// ///If you don't use this function before calling \ref run(), -// ///it will allocate one. The destuctor deallocates this -// ///automatically allocated map, of course. -// ///\return (*this) -// Dijkstra &predNodeMap(PredNodeMap &m) -// { -// if(local_predNode) { -// delete _predNode; -// local_predNode=false; -// } -// _predNode = &m; -// return *this; -// } - ///Sets the map storing the distances calculated by the algorithm. ///Sets the map storing the distances calculated by the algorithm. @@ -456,8 +389,6 @@ { _processed->set(v,true); _dist->set(v, dst); -// if((*_pred)[v]!=INVALID) -// _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do? } public: @@ -485,7 +416,6 @@ while(!_heap.empty()) _heap.pop(); for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { _pred->set(u,INVALID); -// _predNode->set(u,INVALID); _processed->set(u,false); _heap_map.set(u,Heap::PRE_HEAP); } @@ -502,7 +432,6 @@ ///or the shortest path found till then is longer then \c dst. void addSource(Node s,Value dst=0) { -// source = s; if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst); else if(_heap[s]set(w,e); -// _predNode->set(w,v); break; case Heap::IN_HEAP: if ( oldvalue+(*length)[e] < _heap[w] ) { _heap.decrease(w, oldvalue+(*length)[e]); _pred->set(w,e); -// _predNode->set(w,v); } break; case Heap::POST_HEAP: @@ -552,7 +479,7 @@ /// ///\return The next node to be processed or INVALID if the priority heap /// is empty. - Node NextNode() + Node nextNode() { return _heap.empty()?_heap.top():INVALID; } @@ -742,13 +669,6 @@ ///\pre \ref run() must be called before using this function. const PredMap &predMap() const { return *_pred;} -// ///Returns a reference to the map of nodes of shortest paths. - -// ///Returns a reference to the NodeMap of the last but one nodes of the -// ///shortest path tree. -// ///\pre \ref run() must be called before using this function. -// const PredNodeMap &predNodeMap() const { return *_predNode;} - ///Checks if a node is reachable from the root. ///Returns \c true if \c v is reachable from the root. @@ -1101,4 +1021,3 @@ } //END OF NAMESPACE LEMON #endif -