1.1 --- a/lemon/dijkstra.h Fri Sep 30 13:15:28 2005 +0000
1.2 +++ b/lemon/dijkstra.h Mon Oct 03 10:11:29 2005 +0000
1.3 @@ -78,23 +78,6 @@
1.4 {
1.5 return new PredMap(G);
1.6 }
1.7 -// ///\brief The type of the map that stores the last but one
1.8 -// ///nodes of the shortest paths.
1.9 -// ///
1.10 -// ///The type of the map that stores the last but one
1.11 -// ///nodes of the shortest paths.
1.12 -// ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.13 -// ///
1.14 -// typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
1.15 -// ///Instantiates a PredNodeMap.
1.16 -
1.17 -// ///This function instantiates a \ref PredNodeMap.
1.18 -// ///\param G is the graph, to which
1.19 -// ///we would like to define the \ref PredNodeMap
1.20 -// static PredNodeMap *createPredNodeMap(const GR &G)
1.21 -// {
1.22 -// return new PredNodeMap();
1.23 -// }
1.24
1.25 ///The type of the map that stores whether a nodes is processed.
1.26
1.27 @@ -209,9 +192,6 @@
1.28 ///\brief The type of the map that stores the last
1.29 ///edges of the shortest paths.
1.30 typedef typename TR::PredMap PredMap;
1.31 -// ///\brief The type of the map that stores the last but one
1.32 -// ///nodes of the shortest paths.
1.33 -// typedef typename TR::PredNodeMap PredNodeMap;
1.34 ///The type of the map indicating if a node is processed.
1.35 typedef typename TR::ProcessedMap ProcessedMap;
1.36 ///The type of the map that stores the dists of the nodes.
1.37 @@ -227,10 +207,6 @@
1.38 PredMap *_pred;
1.39 ///Indicates if \ref _pred is locally allocated (\c true) or not.
1.40 bool local_pred;
1.41 -// ///Pointer to the map of predecessors nodes.
1.42 -// PredNodeMap *_predNode;
1.43 -// ///Indicates if \ref _predNode is locally allocated (\c true) or not.
1.44 -// bool local_predNode;
1.45 ///Pointer to the map of distances.
1.46 DistMap *_dist;
1.47 ///Indicates if \ref _dist is locally allocated (\c true) or not.
1.48 @@ -240,9 +216,6 @@
1.49 ///Indicates if \ref _processed is locally allocated (\c true) or not.
1.50 bool local_processed;
1.51
1.52 -// ///The source node of the last execution.
1.53 -// Node source;
1.54 -
1.55 ///Creates the maps if necessary.
1.56
1.57 ///\todo Error if \c G or are \c NULL. What about \c length?
1.58 @@ -253,10 +226,6 @@
1.59 local_pred = true;
1.60 _pred = Traits::createPredMap(*G);
1.61 }
1.62 -// if(!_predNode) {
1.63 -// local_predNode = true;
1.64 -// _predNode = Traits::createPredNodeMap(*G);
1.65 -// }
1.66 if(!_dist) {
1.67 local_dist = true;
1.68 _dist = Traits::createDistMap(*G);
1.69 @@ -290,23 +259,6 @@
1.70 LengthMap,
1.71 DefPredMapTraits<T> > { };
1.72
1.73 -// template <class T>
1.74 -// struct DefPredNodeMapTraits : public Traits {
1.75 -// typedef T PredNodeMap;
1.76 -// static PredNodeMap *createPredNodeMap(const Graph &G)
1.77 -// {
1.78 -// throw UninitializedParameter();
1.79 -// }
1.80 -// };
1.81 -// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
1.82 -
1.83 -// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
1.84 -// ///
1.85 -// template <class T>
1.86 -// class DefPredNodeMap : public Dijkstra< Graph,
1.87 -// LengthMap,
1.88 -// DefPredNodeMapTraits<T> > { };
1.89 -
1.90 template <class T>
1.91 struct DefDistMapTraits : public Traits {
1.92 typedef T DistMap;
1.93 @@ -375,7 +327,6 @@
1.94 Dijkstra(const Graph& _G, const LengthMap& _length) :
1.95 G(&_G), length(&_length),
1.96 _pred(NULL), local_pred(false),
1.97 -// _predNode(NULL), local_predNode(false),
1.98 _dist(NULL), local_dist(false),
1.99 _processed(NULL), local_processed(false),
1.100 _heap_map(*G,-1),_heap(_heap_map)
1.101 @@ -385,7 +336,6 @@
1.102 ~Dijkstra()
1.103 {
1.104 if(local_pred) delete _pred;
1.105 -// if(local_predNode) delete _predNode;
1.106 if(local_dist) delete _dist;
1.107 if(local_processed) delete _processed;
1.108 }
1.109 @@ -417,23 +367,6 @@
1.110 return *this;
1.111 }
1.112
1.113 -// ///Sets the map storing the predecessor nodes.
1.114 -
1.115 -// ///Sets the map storing the predecessor nodes.
1.116 -// ///If you don't use this function before calling \ref run(),
1.117 -// ///it will allocate one. The destuctor deallocates this
1.118 -// ///automatically allocated map, of course.
1.119 -// ///\return <tt> (*this) </tt>
1.120 -// Dijkstra &predNodeMap(PredNodeMap &m)
1.121 -// {
1.122 -// if(local_predNode) {
1.123 -// delete _predNode;
1.124 -// local_predNode=false;
1.125 -// }
1.126 -// _predNode = &m;
1.127 -// return *this;
1.128 -// }
1.129 -
1.130 ///Sets the map storing the distances calculated by the algorithm.
1.131
1.132 ///Sets the map storing the distances calculated by the algorithm.
1.133 @@ -456,8 +389,6 @@
1.134 {
1.135 _processed->set(v,true);
1.136 _dist->set(v, dst);
1.137 -// if((*_pred)[v]!=INVALID)
1.138 -// _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do?
1.139 }
1.140
1.141 public:
1.142 @@ -485,7 +416,6 @@
1.143 while(!_heap.empty()) _heap.pop();
1.144 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
1.145 _pred->set(u,INVALID);
1.146 -// _predNode->set(u,INVALID);
1.147 _processed->set(u,false);
1.148 _heap_map.set(u,Heap::PRE_HEAP);
1.149 }
1.150 @@ -502,7 +432,6 @@
1.151 ///or the shortest path found till then is longer then \c dst.
1.152 void addSource(Node s,Value dst=0)
1.153 {
1.154 -// source = s;
1.155 if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
1.156 else if(_heap[s]<dst) {
1.157 _heap.push(s,dst);
1.158 @@ -530,13 +459,11 @@
1.159 case Heap::PRE_HEAP:
1.160 _heap.push(w,oldvalue+(*length)[e]);
1.161 _pred->set(w,e);
1.162 -// _predNode->set(w,v);
1.163 break;
1.164 case Heap::IN_HEAP:
1.165 if ( oldvalue+(*length)[e] < _heap[w] ) {
1.166 _heap.decrease(w, oldvalue+(*length)[e]);
1.167 _pred->set(w,e);
1.168 -// _predNode->set(w,v);
1.169 }
1.170 break;
1.171 case Heap::POST_HEAP:
1.172 @@ -552,7 +479,7 @@
1.173 ///
1.174 ///\return The next node to be processed or INVALID if the priority heap
1.175 /// is empty.
1.176 - Node NextNode()
1.177 + Node nextNode()
1.178 {
1.179 return _heap.empty()?_heap.top():INVALID;
1.180 }
1.181 @@ -742,13 +669,6 @@
1.182 ///\pre \ref run() must be called before using this function.
1.183 const PredMap &predMap() const { return *_pred;}
1.184
1.185 -// ///Returns a reference to the map of nodes of shortest paths.
1.186 -
1.187 -// ///Returns a reference to the NodeMap of the last but one nodes of the
1.188 -// ///shortest path tree.
1.189 -// ///\pre \ref run() must be called before using this function.
1.190 -// const PredNodeMap &predNodeMap() const { return *_predNode;}
1.191 -
1.192 ///Checks if a node is reachable from the root.
1.193
1.194 ///Returns \c true if \c v is reachable from the root.
1.195 @@ -1101,4 +1021,3 @@
1.196 } //END OF NAMESPACE LEMON
1.197
1.198 #endif
1.199 -