1.1 --- a/lemon/dijkstra.h Fri Oct 14 10:49:51 2005 +0000
1.2 +++ b/lemon/dijkstra.h Fri Oct 14 10:52:15 2005 +0000
1.3 @@ -50,6 +50,22 @@
1.4 typedef LM LengthMap;
1.5 //The type of the length of the edges.
1.6 typedef typename LM::Value Value;
1.7 + /// The cross reference type used by heap.
1.8 +
1.9 + /// The cross reference type used by heap.
1.10 + /// Usually it is \c Graph::NodeMap<int>.
1.11 + typedef typename Graph::template NodeMap<int> HeapCrossRef;
1.12 + ///Instantiates a HeapCrossRef.
1.13 +
1.14 + ///This function instantiates a \ref HeapCrossRef.
1.15 + /// \param G is the graph, to which we would like to define the
1.16 + /// HeapCrossRef.
1.17 + /// \todo The graph alone may be insufficient for the initialization
1.18 + static HeapCrossRef *createHeapCrossRef(const GR &G)
1.19 + {
1.20 + return new HeapCrossRef(G);
1.21 + }
1.22 +
1.23 ///The heap type used by Dijkstra algorithm.
1.24
1.25 ///The heap type used by Dijkstra algorithm.
1.26 @@ -60,6 +76,11 @@
1.27 typename GR::template NodeMap<int>,
1.28 std::less<Value> > Heap;
1.29
1.30 + static Heap *createHeap(HeapCrossRef& R)
1.31 + {
1.32 + return new Heap(R);
1.33 + }
1.34 +
1.35 ///\brief The type of the map that stores the last
1.36 ///edges of the shortest paths.
1.37 ///
1.38 @@ -195,6 +216,8 @@
1.39 typedef typename TR::ProcessedMap ProcessedMap;
1.40 ///The type of the map that stores the dists of the nodes.
1.41 typedef typename TR::DistMap DistMap;
1.42 + ///The cross reference type used for the current heap.
1.43 + typedef typename TR::HeapCrossRef HeapCrossRef;
1.44 ///The heap type used by the dijkstra algorithm.
1.45 typedef typename TR::Heap Heap;
1.46 private:
1.47 @@ -214,6 +237,14 @@
1.48 ProcessedMap *_processed;
1.49 ///Indicates if \ref _processed is locally allocated (\c true) or not.
1.50 bool local_processed;
1.51 + ///Pointer to the heap cross references.
1.52 + HeapCrossRef *_heap_cross_ref;
1.53 + ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
1.54 + bool local_heap_cross_ref;
1.55 + ///Pointer to the heap.
1.56 + Heap *_heap;
1.57 + ///Indicates if \ref _heap is locally allocated (\c true) or not.
1.58 + bool local_heap;
1.59
1.60 ///Creates the maps if necessary.
1.61
1.62 @@ -233,6 +264,14 @@
1.63 local_processed = true;
1.64 _processed = Traits::createProcessedMap(*G);
1.65 }
1.66 + if (!_heap_cross_ref) {
1.67 + local_heap_cross_ref = true;
1.68 + _heap_cross_ref = Traits::createHeapCrossRef(*G);
1.69 + }
1.70 + if (!_heap) {
1.71 + local_heap = true;
1.72 + _heap = Traits::createHeap(*_heap_cross_ref);
1.73 + }
1.74 }
1.75
1.76 public :
1.77 @@ -315,13 +354,34 @@
1.78 : public Dijkstra< Graph, LengthMap, DefGraphProcessedMapTraits> {
1.79 typedef Dijkstra< Graph, LengthMap, DefGraphProcessedMapTraits> Create;
1.80 };
1.81 +
1.82 + template <class H, class CR>
1.83 + struct DefHeapTraits : public Traits {
1.84 + typedef CR HeapCrossRef;
1.85 + typedef H Heap;
1.86 + static HeapCrossRef *createHeapCrossRef(const Graph &G) {
1.87 + return new HeapCrossRef(G);
1.88 + }
1.89 + static Heap *createHeap(HeapCrossRef &R)
1.90 + {
1.91 + return new Heap(R);
1.92 + }
1.93 + };
1.94 + ///\ref named-templ-param "Named parameter" for setting heap and cross
1.95 + ///reference type
1.96 +
1.97 + ///\ref named-templ-param "Named parameter" for setting heap and cross
1.98 + ///reference type
1.99 + ///
1.100 + template <class H, class CR = typename Graph::template NodeMap<int> >
1.101 + struct DefHeap
1.102 + : public Dijkstra< Graph, LengthMap, DefHeapTraits<H, CR> > {
1.103 + typedef Dijkstra< Graph, LengthMap, DefHeapTraits<H, CR> > Create;
1.104 + };
1.105
1.106 ///@}
1.107
1.108
1.109 - private:
1.110 - typename Graph::template NodeMap<int> _heap_map;
1.111 - Heap _heap;
1.112 protected:
1.113
1.114 Dijkstra() {}
1.115 @@ -337,7 +397,8 @@
1.116 _pred(NULL), local_pred(false),
1.117 _dist(NULL), local_dist(false),
1.118 _processed(NULL), local_processed(false),
1.119 - _heap_map(*G,-1),_heap(_heap_map)
1.120 + _heap_cross_ref(NULL), local_heap_cross_ref(false),
1.121 + _heap(NULL), local_heap(false)
1.122 { }
1.123
1.124 ///Destructor.
1.125 @@ -346,6 +407,8 @@
1.126 if(local_pred) delete _pred;
1.127 if(local_dist) delete _dist;
1.128 if(local_processed) delete _processed;
1.129 + if(local_heap_cross_ref) delete _heap_cross_ref;
1.130 + if(local_heap) delete _heap;
1.131 }
1.132
1.133 ///Sets the length map.
1.134 @@ -416,16 +479,14 @@
1.135
1.136 ///Initializes the internal data structures.
1.137 ///
1.138 - ///\todo _heap_map's type could also be in the traits class.
1.139 - ///\todo The heaps should be able to make themselves empty directly.
1.140 void init()
1.141 {
1.142 create_maps();
1.143 - while(!_heap.empty()) _heap.pop();
1.144 + _heap->clear();
1.145 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
1.146 _pred->set(u,INVALID);
1.147 _processed->set(u,false);
1.148 - _heap_map.set(u,Heap::PRE_HEAP);
1.149 + _heap_cross_ref->set(u,Heap::PRE_HEAP);
1.150 }
1.151 }
1.152
1.153 @@ -440,9 +501,10 @@
1.154 ///or the shortest path found till then is longer then \c dst.
1.155 void addSource(Node s,Value dst=0)
1.156 {
1.157 - if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
1.158 - else if(_heap[s]<dst) {
1.159 - _heap.push(s,dst);
1.160 + if(_heap->state(s) != Heap::IN_HEAP) {
1.161 + _heap->push(s,dst);
1.162 + } else if((*_heap)[s]<dst) {
1.163 + _heap->push(s,dst);
1.164 _pred->set(s,INVALID);
1.165 }
1.166 }
1.167 @@ -456,21 +518,21 @@
1.168 ///\warning The priority heap must not be empty!
1.169 Node processNextNode()
1.170 {
1.171 - Node v=_heap.top();
1.172 - Value oldvalue=_heap[v];
1.173 - _heap.pop();
1.174 + Node v=_heap->top();
1.175 + Value oldvalue=_heap->prio();
1.176 + _heap->pop();
1.177 finalizeNodeData(v,oldvalue);
1.178
1.179 for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
1.180 Node w=G->target(e);
1.181 - switch(_heap.state(w)) {
1.182 + switch(_heap->state(w)) {
1.183 case Heap::PRE_HEAP:
1.184 - _heap.push(w,oldvalue+(*length)[e]);
1.185 + _heap->push(w,oldvalue+(*length)[e]);
1.186 _pred->set(w,e);
1.187 break;
1.188 case Heap::IN_HEAP:
1.189 - if ( oldvalue+(*length)[e] < _heap[w] ) {
1.190 - _heap.decrease(w, oldvalue+(*length)[e]);
1.191 + if ( oldvalue+(*length)[e] < (*_heap)[w] ) {
1.192 + _heap->decrease(w, oldvalue+(*length)[e]);
1.193 _pred->set(w,e);
1.194 }
1.195 break;
1.196 @@ -489,7 +551,7 @@
1.197 /// is empty.
1.198 Node nextNode()
1.199 {
1.200 - return _heap.empty()?_heap.top():INVALID;
1.201 + return _heap->empty()?_heap->top():INVALID;
1.202 }
1.203
1.204 ///\brief Returns \c false if there are nodes
1.205 @@ -497,12 +559,12 @@
1.206 ///
1.207 ///Returns \c false if there are nodes
1.208 ///to be processed in the priority heap
1.209 - bool emptyQueue() { return _heap.empty(); }
1.210 + bool emptyQueue() { return _heap->empty(); }
1.211 ///Returns the number of the nodes to be processed in the priority heap
1.212
1.213 ///Returns the number of the nodes to be processed in the priority heap
1.214 ///
1.215 - int queueSize() { return _heap.size(); }
1.216 + int queueSize() { return _heap->size(); }
1.217
1.218 ///Executes the algorithm.
1.219
1.220 @@ -520,7 +582,7 @@
1.221 ///
1.222 void start()
1.223 {
1.224 - while ( !_heap.empty() ) processNextNode();
1.225 + while ( !_heap->empty() ) processNextNode();
1.226 }
1.227
1.228 ///Executes the algorithm until \c dest is reached.
1.229 @@ -539,8 +601,8 @@
1.230 ///
1.231 void start(Node dest)
1.232 {
1.233 - while ( !_heap.empty() && _heap.top()!=dest ) processNextNode();
1.234 - if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio());
1.235 + while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
1.236 + if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
1.237 }
1.238
1.239 ///Executes the algorithm until a condition is met.
1.240 @@ -555,8 +617,8 @@
1.241 template<class NodeBoolMap>
1.242 void start(const NodeBoolMap &nm)
1.243 {
1.244 - while ( !_heap.empty() && !nm[_heap.top()] ) processNextNode();
1.245 - if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio());
1.246 + while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
1.247 + if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
1.248 }
1.249
1.250 ///Runs %Dijkstra algorithm from node \c s.
1.251 @@ -683,7 +745,7 @@
1.252 ///\warning The source nodes are inditated as unreached.
1.253 ///\pre \ref run() must be called before using this function.
1.254 ///
1.255 - bool reached(Node v) { return _heap_map[v]!=Heap::PRE_HEAP; }
1.256 + bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
1.257
1.258 ///@}
1.259 };
1.260 @@ -711,15 +773,37 @@
1.261 typedef typename LM::Value Value;
1.262 ///The heap type used by Dijkstra algorithm.
1.263
1.264 + /// The cross reference type used by heap.
1.265 +
1.266 + /// The cross reference type used by heap.
1.267 + /// Usually it is \c Graph::NodeMap<int>.
1.268 + typedef typename Graph::template NodeMap<int> HeapCrossRef;
1.269 + ///Instantiates a HeapCrossRef.
1.270 +
1.271 + ///This function instantiates a \ref HeapCrossRef.
1.272 + /// \param G is the graph, to which we would like to define the
1.273 + /// HeapCrossRef.
1.274 + /// \todo The graph alone may be insufficient for the initialization
1.275 + static HeapCrossRef *createHeapCrossRef(const GR &G)
1.276 + {
1.277 + return new HeapCrossRef(G);
1.278 + }
1.279 +
1.280 + ///The heap type used by Dijkstra algorithm.
1.281 +
1.282 ///The heap type used by Dijkstra algorithm.
1.283 ///
1.284 ///\sa BinHeap
1.285 ///\sa Dijkstra
1.286 - typedef BinHeap<typename Graph::Node,
1.287 - typename LM::Value,
1.288 + typedef BinHeap<typename Graph::Node, typename LM::Value,
1.289 typename GR::template NodeMap<int>,
1.290 std::less<Value> > Heap;
1.291
1.292 + static Heap *createHeap(HeapCrossRef& R)
1.293 + {
1.294 + return new Heap(R);
1.295 + }
1.296 +
1.297 ///\brief The type of the map that stores the last
1.298 ///edges of the shortest paths.
1.299 ///
1.300 @@ -807,8 +891,6 @@
1.301 void *_length;
1.302 ///Pointer to the map of predecessors edges.
1.303 void *_pred;
1.304 -// ///Pointer to the map of predecessors nodes.
1.305 -// void *_predNode;
1.306 ///Pointer to the map of distances.
1.307 void *_dist;
1.308 ///Pointer to the source node.
1.309 @@ -820,7 +902,6 @@
1.310 /// This constructor does not require parameters, therefore it initiates
1.311 /// all of the attributes to default values (0, INVALID).
1.312 DijkstraWizardBase() : _g(0), _length(0), _pred(0),
1.313 -// _predNode(0),
1.314 _dist(0), _source(INVALID) {}
1.315
1.316 /// Constructor.
1.317 @@ -833,7 +914,6 @@
1.318 /// \param s is the initial value of \ref _source
1.319 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
1.320 _g((void *)&g), _length((void *)&l), _pred(0),
1.321 -// _predNode(0),
1.322 _dist(0), _source(s) {}
1.323
1.324 };
1.325 @@ -855,8 +935,8 @@
1.326 /// return the needed class.
1.327 ///
1.328 /// It does not have own \ref run method. When its \ref run method is called
1.329 - /// it initiates a plain \ref Dijkstra class, and calls the \ref Dijkstra::run
1.330 - /// method of it.
1.331 + /// it initiates a plain \ref Dijkstra class, and calls the \ref
1.332 + /// Dijkstra::run method of it.
1.333 template<class TR>
1.334 class DijkstraWizard : public TR
1.335 {
1.336 @@ -880,12 +960,8 @@
1.337 ///\brief The type of the map that stores the last
1.338 ///edges of the shortest paths.
1.339 typedef typename TR::PredMap PredMap;
1.340 -// ///\brief The type of the map that stores the last but one
1.341 -// ///nodes of the shortest paths.
1.342 -// typedef typename TR::PredNodeMap PredNodeMap;
1.343 ///The type of the map that stores the dists of the nodes.
1.344 typedef typename TR::DistMap DistMap;
1.345 -
1.346 ///The heap type used by the dijkstra algorithm.
1.347 typedef typename TR::Heap Heap;
1.348 public:
1.349 @@ -914,7 +990,6 @@
1.350 Dijkstra<Graph,LengthMap,TR>
1.351 dij(*(Graph*)Base::_g,*(LengthMap*)Base::_length);
1.352 if(Base::_pred) dij.predMap(*(PredMap*)Base::_pred);
1.353 -// if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode);
1.354 if(Base::_dist) dij.distMap(*(DistMap*)Base::_dist);
1.355 dij.run(Base::_source);
1.356 }
1.357 @@ -949,27 +1024,6 @@
1.358 return DijkstraWizard<DefPredMapBase<T> >(*this);
1.359 }
1.360
1.361 -
1.362 -// template<class T>
1.363 -// struct DefPredNodeMapBase : public Base {
1.364 -// typedef T PredNodeMap;
1.365 -// static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1.366 -// DefPredNodeMapBase(const TR &b) : TR(b) {}
1.367 -// };
1.368 -
1.369 -// ///\brief \ref named-templ-param "Named parameter"
1.370 -// ///function for setting PredNodeMap type
1.371 -// ///
1.372 -// /// \ref named-templ-param "Named parameter"
1.373 -// ///function for setting PredNodeMap type
1.374 -// ///
1.375 -// template<class T>
1.376 -// DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1.377 -// {
1.378 -// Base::_predNode=(void *)&t;
1.379 -// return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
1.380 -// }
1.381 -
1.382 template<class T>
1.383 struct DefDistMapBase : public Base {
1.384 typedef T DistMap;