1.1 --- a/lemon/bfs.h Fri Sep 30 13:15:28 2005 +0000
1.2 +++ b/lemon/bfs.h Mon Oct 03 10:11:29 2005 +0000
1.3 @@ -549,7 +549,7 @@
1.4 ///
1.5 ///\return The next node to be processed or INVALID if the queue is
1.6 /// empty.
1.7 - Node NextNode()
1.8 + Node nextNode()
1.9 {
1.10 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
1.11 }
2.1 --- a/lemon/dfs.h Fri Sep 30 13:15:28 2005 +0000
2.2 +++ b/lemon/dfs.h Mon Oct 03 10:11:29 2005 +0000
2.3 @@ -336,8 +336,9 @@
2.4 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
2.5 ///
2.6 template <class T>
2.7 - class DefProcessedMap : public Dfs< Graph,
2.8 - DefProcessedMapTraits<T> > { };
2.9 + struct DefProcessedMap : public Dfs< Graph, DefProcessedMapTraits<T> > {
2.10 + typedef Dfs< Graph, DefProcessedMapTraits<T> > Dfs;
2.11 + };
2.12
2.13 struct DefGraphProcessedMapTraits : public Traits {
2.14 typedef typename Graph::template NodeMap<bool> ProcessedMap;
2.15 @@ -563,11 +564,11 @@
2.16 ///
2.17 ///\return The next edge to be processed or INVALID if the stack is
2.18 /// empty.
2.19 - OutEdgeIt NextEdge()
2.20 + OutEdgeIt nextEdge()
2.21 {
2.22 return _stack_head>=0?_stack[_stack_head]:INVALID;
2.23 }
2.24 -
2.25 +
2.26 ///\brief Returns \c false if there are nodes
2.27 ///to be processed in the queue
2.28 ///
3.1 --- a/lemon/dijkstra.h Fri Sep 30 13:15:28 2005 +0000
3.2 +++ b/lemon/dijkstra.h Mon Oct 03 10:11:29 2005 +0000
3.3 @@ -78,23 +78,6 @@
3.4 {
3.5 return new PredMap(G);
3.6 }
3.7 -// ///\brief The type of the map that stores the last but one
3.8 -// ///nodes of the shortest paths.
3.9 -// ///
3.10 -// ///The type of the map that stores the last but one
3.11 -// ///nodes of the shortest paths.
3.12 -// ///It must meet the \ref concept::WriteMap "WriteMap" concept.
3.13 -// ///
3.14 -// typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
3.15 -// ///Instantiates a PredNodeMap.
3.16 -
3.17 -// ///This function instantiates a \ref PredNodeMap.
3.18 -// ///\param G is the graph, to which
3.19 -// ///we would like to define the \ref PredNodeMap
3.20 -// static PredNodeMap *createPredNodeMap(const GR &G)
3.21 -// {
3.22 -// return new PredNodeMap();
3.23 -// }
3.24
3.25 ///The type of the map that stores whether a nodes is processed.
3.26
3.27 @@ -209,9 +192,6 @@
3.28 ///\brief The type of the map that stores the last
3.29 ///edges of the shortest paths.
3.30 typedef typename TR::PredMap PredMap;
3.31 -// ///\brief The type of the map that stores the last but one
3.32 -// ///nodes of the shortest paths.
3.33 -// typedef typename TR::PredNodeMap PredNodeMap;
3.34 ///The type of the map indicating if a node is processed.
3.35 typedef typename TR::ProcessedMap ProcessedMap;
3.36 ///The type of the map that stores the dists of the nodes.
3.37 @@ -227,10 +207,6 @@
3.38 PredMap *_pred;
3.39 ///Indicates if \ref _pred is locally allocated (\c true) or not.
3.40 bool local_pred;
3.41 -// ///Pointer to the map of predecessors nodes.
3.42 -// PredNodeMap *_predNode;
3.43 -// ///Indicates if \ref _predNode is locally allocated (\c true) or not.
3.44 -// bool local_predNode;
3.45 ///Pointer to the map of distances.
3.46 DistMap *_dist;
3.47 ///Indicates if \ref _dist is locally allocated (\c true) or not.
3.48 @@ -240,9 +216,6 @@
3.49 ///Indicates if \ref _processed is locally allocated (\c true) or not.
3.50 bool local_processed;
3.51
3.52 -// ///The source node of the last execution.
3.53 -// Node source;
3.54 -
3.55 ///Creates the maps if necessary.
3.56
3.57 ///\todo Error if \c G or are \c NULL. What about \c length?
3.58 @@ -253,10 +226,6 @@
3.59 local_pred = true;
3.60 _pred = Traits::createPredMap(*G);
3.61 }
3.62 -// if(!_predNode) {
3.63 -// local_predNode = true;
3.64 -// _predNode = Traits::createPredNodeMap(*G);
3.65 -// }
3.66 if(!_dist) {
3.67 local_dist = true;
3.68 _dist = Traits::createDistMap(*G);
3.69 @@ -290,23 +259,6 @@
3.70 LengthMap,
3.71 DefPredMapTraits<T> > { };
3.72
3.73 -// template <class T>
3.74 -// struct DefPredNodeMapTraits : public Traits {
3.75 -// typedef T PredNodeMap;
3.76 -// static PredNodeMap *createPredNodeMap(const Graph &G)
3.77 -// {
3.78 -// throw UninitializedParameter();
3.79 -// }
3.80 -// };
3.81 -// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
3.82 -
3.83 -// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
3.84 -// ///
3.85 -// template <class T>
3.86 -// class DefPredNodeMap : public Dijkstra< Graph,
3.87 -// LengthMap,
3.88 -// DefPredNodeMapTraits<T> > { };
3.89 -
3.90 template <class T>
3.91 struct DefDistMapTraits : public Traits {
3.92 typedef T DistMap;
3.93 @@ -375,7 +327,6 @@
3.94 Dijkstra(const Graph& _G, const LengthMap& _length) :
3.95 G(&_G), length(&_length),
3.96 _pred(NULL), local_pred(false),
3.97 -// _predNode(NULL), local_predNode(false),
3.98 _dist(NULL), local_dist(false),
3.99 _processed(NULL), local_processed(false),
3.100 _heap_map(*G,-1),_heap(_heap_map)
3.101 @@ -385,7 +336,6 @@
3.102 ~Dijkstra()
3.103 {
3.104 if(local_pred) delete _pred;
3.105 -// if(local_predNode) delete _predNode;
3.106 if(local_dist) delete _dist;
3.107 if(local_processed) delete _processed;
3.108 }
3.109 @@ -417,23 +367,6 @@
3.110 return *this;
3.111 }
3.112
3.113 -// ///Sets the map storing the predecessor nodes.
3.114 -
3.115 -// ///Sets the map storing the predecessor nodes.
3.116 -// ///If you don't use this function before calling \ref run(),
3.117 -// ///it will allocate one. The destuctor deallocates this
3.118 -// ///automatically allocated map, of course.
3.119 -// ///\return <tt> (*this) </tt>
3.120 -// Dijkstra &predNodeMap(PredNodeMap &m)
3.121 -// {
3.122 -// if(local_predNode) {
3.123 -// delete _predNode;
3.124 -// local_predNode=false;
3.125 -// }
3.126 -// _predNode = &m;
3.127 -// return *this;
3.128 -// }
3.129 -
3.130 ///Sets the map storing the distances calculated by the algorithm.
3.131
3.132 ///Sets the map storing the distances calculated by the algorithm.
3.133 @@ -456,8 +389,6 @@
3.134 {
3.135 _processed->set(v,true);
3.136 _dist->set(v, dst);
3.137 -// if((*_pred)[v]!=INVALID)
3.138 -// _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do?
3.139 }
3.140
3.141 public:
3.142 @@ -485,7 +416,6 @@
3.143 while(!_heap.empty()) _heap.pop();
3.144 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
3.145 _pred->set(u,INVALID);
3.146 -// _predNode->set(u,INVALID);
3.147 _processed->set(u,false);
3.148 _heap_map.set(u,Heap::PRE_HEAP);
3.149 }
3.150 @@ -502,7 +432,6 @@
3.151 ///or the shortest path found till then is longer then \c dst.
3.152 void addSource(Node s,Value dst=0)
3.153 {
3.154 -// source = s;
3.155 if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
3.156 else if(_heap[s]<dst) {
3.157 _heap.push(s,dst);
3.158 @@ -530,13 +459,11 @@
3.159 case Heap::PRE_HEAP:
3.160 _heap.push(w,oldvalue+(*length)[e]);
3.161 _pred->set(w,e);
3.162 -// _predNode->set(w,v);
3.163 break;
3.164 case Heap::IN_HEAP:
3.165 if ( oldvalue+(*length)[e] < _heap[w] ) {
3.166 _heap.decrease(w, oldvalue+(*length)[e]);
3.167 _pred->set(w,e);
3.168 -// _predNode->set(w,v);
3.169 }
3.170 break;
3.171 case Heap::POST_HEAP:
3.172 @@ -552,7 +479,7 @@
3.173 ///
3.174 ///\return The next node to be processed or INVALID if the priority heap
3.175 /// is empty.
3.176 - Node NextNode()
3.177 + Node nextNode()
3.178 {
3.179 return _heap.empty()?_heap.top():INVALID;
3.180 }
3.181 @@ -742,13 +669,6 @@
3.182 ///\pre \ref run() must be called before using this function.
3.183 const PredMap &predMap() const { return *_pred;}
3.184
3.185 -// ///Returns a reference to the map of nodes of shortest paths.
3.186 -
3.187 -// ///Returns a reference to the NodeMap of the last but one nodes of the
3.188 -// ///shortest path tree.
3.189 -// ///\pre \ref run() must be called before using this function.
3.190 -// const PredNodeMap &predNodeMap() const { return *_predNode;}
3.191 -
3.192 ///Checks if a node is reachable from the root.
3.193
3.194 ///Returns \c true if \c v is reachable from the root.
3.195 @@ -1101,4 +1021,3 @@
3.196 } //END OF NAMESPACE LEMON
3.197
3.198 #endif
3.199 -