101 /// The cross reference type used by heap. |
101 /// The cross reference type used by heap. |
102 /// Usually it is \c Digraph::NodeMap<int>. |
102 /// Usually it is \c Digraph::NodeMap<int>. |
103 typedef typename Digraph::template NodeMap<int> HeapCrossRef; |
103 typedef typename Digraph::template NodeMap<int> HeapCrossRef; |
104 ///Instantiates a HeapCrossRef. |
104 ///Instantiates a HeapCrossRef. |
105 |
105 |
106 ///This function instantiates a \c HeapCrossRef. |
106 ///This function instantiates a \c HeapCrossRef. |
107 /// \param G is the digraph, to which we would like to define the |
107 /// \param G is the digraph, to which we would like to define the |
108 /// HeapCrossRef. |
108 /// HeapCrossRef. |
109 static HeapCrossRef *createHeapCrossRef(const GR &G) |
109 static HeapCrossRef *createHeapCrossRef(const GR &G) |
110 { |
110 { |
111 return new HeapCrossRef(G); |
111 return new HeapCrossRef(G); |
112 } |
112 } |
113 |
113 |
114 ///The heap type used by Dijkstra algorithm. |
114 ///The heap type used by Dijkstra algorithm. |
115 |
115 |
116 ///The heap type used by Dijkstra algorithm. |
116 ///The heap type used by Dijkstra algorithm. |
117 /// |
117 /// |
118 ///\sa BinHeap |
118 ///\sa BinHeap |
119 ///\sa Dijkstra |
119 ///\sa Dijkstra |
120 typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap; |
120 typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap; |
121 |
121 |
122 static Heap *createHeap(HeapCrossRef& R) |
122 static Heap *createHeap(HeapCrossRef& R) |
123 { |
123 { |
124 return new Heap(R); |
124 return new Heap(R); |
125 } |
125 } |
126 |
126 |
127 ///\brief The type of the map that stores the last |
127 ///\brief The type of the map that stores the last |
128 ///arcs of the shortest paths. |
128 ///arcs of the shortest paths. |
129 /// |
129 /// |
130 ///The type of the map that stores the last |
130 ///The type of the map that stores the last |
131 ///arcs of the shortest paths. |
131 ///arcs of the shortest paths. |
132 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
132 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
133 /// |
133 /// |
134 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap; |
134 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap; |
135 ///Instantiates a PredMap. |
135 ///Instantiates a PredMap. |
136 |
136 |
137 ///This function instantiates a \c PredMap. |
137 ///This function instantiates a \c PredMap. |
138 ///\param G is the digraph, to which we would like to define the PredMap. |
138 ///\param G is the digraph, to which we would like to define the PredMap. |
139 ///\todo The digraph alone may be insufficient for the initialization |
139 ///\todo The digraph alone may be insufficient for the initialization |
140 static PredMap *createPredMap(const GR &G) |
140 static PredMap *createPredMap(const GR &G) |
141 { |
141 { |
142 return new PredMap(G); |
142 return new PredMap(G); |
143 } |
143 } |
144 |
144 |
145 ///The type of the map that stores whether a nodes is processed. |
145 ///The type of the map that stores whether a nodes is processed. |
146 |
146 |
147 ///The type of the map that stores whether a nodes is processed. |
147 ///The type of the map that stores whether a nodes is processed. |
148 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
148 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
149 ///By default it is a NullMap. |
149 ///By default it is a NullMap. |
150 ///\todo If it is set to a real map, |
150 ///\todo If it is set to a real map, |
151 ///Dijkstra::processed() should read this. |
151 ///Dijkstra::processed() should read this. |
152 ///\todo named parameter to set this type, function to read and write. |
152 ///\todo named parameter to set this type, function to read and write. |
153 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
153 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
154 ///Instantiates a ProcessedMap. |
154 ///Instantiates a ProcessedMap. |
155 |
155 |
156 ///This function instantiates a \c ProcessedMap. |
156 ///This function instantiates a \c ProcessedMap. |
157 ///\param g is the digraph, to which |
157 ///\param g is the digraph, to which |
158 ///we would like to define the \c ProcessedMap |
158 ///we would like to define the \c ProcessedMap |
159 #ifdef DOXYGEN |
159 #ifdef DOXYGEN |
160 static ProcessedMap *createProcessedMap(const GR &g) |
160 static ProcessedMap *createProcessedMap(const GR &g) |
161 #else |
161 #else |
286 Heap *_heap; |
286 Heap *_heap; |
287 ///Indicates if \ref _heap is locally allocated (\c true) or not. |
287 ///Indicates if \ref _heap is locally allocated (\c true) or not. |
288 bool local_heap; |
288 bool local_heap; |
289 |
289 |
290 ///Creates the maps if necessary. |
290 ///Creates the maps if necessary. |
291 |
291 |
292 ///\todo Better memory allocation (instead of new). |
292 ///\todo Better memory allocation (instead of new). |
293 void create_maps() |
293 void create_maps() |
294 { |
294 { |
295 if(!_pred) { |
295 if(!_pred) { |
296 local_pred = true; |
296 local_pred = true; |
297 _pred = Traits::createPredMap(*G); |
297 _pred = Traits::createPredMap(*G); |
298 } |
298 } |
299 if(!_dist) { |
299 if(!_dist) { |
300 local_dist = true; |
300 local_dist = true; |
301 _dist = Traits::createDistMap(*G); |
301 _dist = Traits::createDistMap(*G); |
302 } |
302 } |
303 if(!_processed) { |
303 if(!_processed) { |
304 local_processed = true; |
304 local_processed = true; |
305 _processed = Traits::createProcessedMap(*G); |
305 _processed = Traits::createProcessedMap(*G); |
306 } |
306 } |
307 if (!_heap_cross_ref) { |
307 if (!_heap_cross_ref) { |
308 local_heap_cross_ref = true; |
308 local_heap_cross_ref = true; |
309 _heap_cross_ref = Traits::createHeapCrossRef(*G); |
309 _heap_cross_ref = Traits::createHeapCrossRef(*G); |
310 } |
310 } |
311 if (!_heap) { |
311 if (!_heap) { |
312 local_heap = true; |
312 local_heap = true; |
313 _heap = Traits::createHeap(*_heap_cross_ref); |
313 _heap = Traits::createHeap(*_heap_cross_ref); |
314 } |
314 } |
315 } |
315 } |
316 |
316 |
317 public : |
317 public : |
318 |
318 |
319 typedef Dijkstra Create; |
319 typedef Dijkstra Create; |
320 |
320 |
321 ///\name Named template parameters |
321 ///\name Named template parameters |
322 |
322 |
323 ///@{ |
323 ///@{ |
324 |
324 |
325 template <class T> |
325 template <class T> |
326 struct DefPredMapTraits : public Traits { |
326 struct DefPredMapTraits : public Traits { |
327 typedef T PredMap; |
327 typedef T PredMap; |
328 static PredMap *createPredMap(const Digraph &) |
328 static PredMap *createPredMap(const Digraph &) |
329 { |
329 { |
330 throw UninitializedParameter(); |
330 throw UninitializedParameter(); |
331 } |
331 } |
332 }; |
332 }; |
333 ///\ref named-templ-param "Named parameter" for setting PredMap type |
333 ///\ref named-templ-param "Named parameter" for setting PredMap type |
334 |
334 |
335 ///\ref named-templ-param "Named parameter" for setting PredMap type |
335 ///\ref named-templ-param "Named parameter" for setting PredMap type |
336 /// |
336 /// |
337 template <class T> |
337 template <class T> |
338 struct DefPredMap |
338 struct DefPredMap |
339 : public Dijkstra< Digraph, LengthMap, DefPredMapTraits<T> > { |
339 : public Dijkstra< Digraph, LengthMap, DefPredMapTraits<T> > { |
340 typedef Dijkstra< Digraph, LengthMap, DefPredMapTraits<T> > Create; |
340 typedef Dijkstra< Digraph, LengthMap, DefPredMapTraits<T> > Create; |
341 }; |
341 }; |
342 |
342 |
343 template <class T> |
343 template <class T> |
344 struct DefDistMapTraits : public Traits { |
344 struct DefDistMapTraits : public Traits { |
345 typedef T DistMap; |
345 typedef T DistMap; |
346 static DistMap *createDistMap(const Digraph &) |
346 static DistMap *createDistMap(const Digraph &) |
347 { |
347 { |
348 throw UninitializedParameter(); |
348 throw UninitializedParameter(); |
349 } |
349 } |
350 }; |
350 }; |
351 ///\ref named-templ-param "Named parameter" for setting DistMap type |
351 ///\ref named-templ-param "Named parameter" for setting DistMap type |
352 |
352 |
353 ///\ref named-templ-param "Named parameter" for setting DistMap type |
353 ///\ref named-templ-param "Named parameter" for setting DistMap type |
354 /// |
354 /// |
355 template <class T> |
355 template <class T> |
356 struct DefDistMap |
356 struct DefDistMap |
357 : public Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > { |
357 : public Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > { |
358 typedef Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > Create; |
358 typedef Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > Create; |
359 }; |
359 }; |
360 |
360 |
361 template <class T> |
361 template <class T> |
362 struct DefProcessedMapTraits : public Traits { |
362 struct DefProcessedMapTraits : public Traits { |
363 typedef T ProcessedMap; |
363 typedef T ProcessedMap; |
364 static ProcessedMap *createProcessedMap(const Digraph &G) |
364 static ProcessedMap *createProcessedMap(const Digraph &G) |
365 { |
365 { |
366 throw UninitializedParameter(); |
366 throw UninitializedParameter(); |
367 } |
367 } |
368 }; |
368 }; |
369 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type |
369 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type |
370 |
370 |
371 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type |
371 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type |
372 /// |
372 /// |
373 template <class T> |
373 template <class T> |
374 struct DefProcessedMap |
374 struct DefProcessedMap |
375 : public Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > { |
375 : public Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > { |
376 typedef Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > Create; |
376 typedef Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > Create; |
377 }; |
377 }; |
378 |
378 |
379 struct DefDigraphProcessedMapTraits : public Traits { |
379 struct DefDigraphProcessedMapTraits : public Traits { |
380 typedef typename Digraph::template NodeMap<bool> ProcessedMap; |
380 typedef typename Digraph::template NodeMap<bool> ProcessedMap; |
381 static ProcessedMap *createProcessedMap(const Digraph &G) |
381 static ProcessedMap *createProcessedMap(const Digraph &G) |
382 { |
382 { |
383 return new ProcessedMap(G); |
383 return new ProcessedMap(G); |
384 } |
384 } |
385 }; |
385 }; |
386 ///\brief \ref named-templ-param "Named parameter" |
386 ///\brief \ref named-templ-param "Named parameter" |
387 ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>. |
387 ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>. |
388 /// |
388 /// |
389 ///\ref named-templ-param "Named parameter" |
389 ///\ref named-templ-param "Named parameter" |
390 ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>. |
390 ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>. |
391 ///If you don't set it explicitely, it will be automatically allocated. |
391 ///If you don't set it explicitely, it will be automatically allocated. |
392 template <class T> |
392 template <class T> |
393 struct DefProcessedMapToBeDefaultMap |
393 struct DefProcessedMapToBeDefaultMap |
394 : public Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> { |
394 : public Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> { |
395 typedef Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> Create; |
395 typedef Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> Create; |
396 }; |
396 }; |
397 |
397 |
398 template <class H, class CR> |
398 template <class H, class CR> |
399 struct DefHeapTraits : public Traits { |
399 struct DefHeapTraits : public Traits { |
400 typedef CR HeapCrossRef; |
400 typedef CR HeapCrossRef; |
401 typedef H Heap; |
401 typedef H Heap; |
402 static HeapCrossRef *createHeapCrossRef(const Digraph &) { |
402 static HeapCrossRef *createHeapCrossRef(const Digraph &) { |
403 throw UninitializedParameter(); |
403 throw UninitializedParameter(); |
404 } |
404 } |
405 static Heap *createHeap(HeapCrossRef &) |
405 static Heap *createHeap(HeapCrossRef &) |
406 { |
406 { |
407 throw UninitializedParameter(); |
407 throw UninitializedParameter(); |
408 } |
408 } |
409 }; |
409 }; |
410 ///\brief \ref named-templ-param "Named parameter" for setting |
410 ///\brief \ref named-templ-param "Named parameter" for setting |
411 ///heap and cross reference type |
411 ///heap and cross reference type |
412 /// |
412 /// |
413 ///\ref named-templ-param "Named parameter" for setting heap and cross |
413 ///\ref named-templ-param "Named parameter" for setting heap and cross |
414 ///reference type |
414 ///reference type |
415 /// |
415 /// |
416 template <class H, class CR = typename Digraph::template NodeMap<int> > |
416 template <class H, class CR = typename Digraph::template NodeMap<int> > |
417 struct DefHeap |
417 struct DefHeap |
418 : public Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > { |
418 : public Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > { |
419 typedef Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > Create; |
419 typedef Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > Create; |
420 }; |
420 }; |
421 |
421 |
422 template <class H, class CR> |
422 template <class H, class CR> |
423 struct DefStandardHeapTraits : public Traits { |
423 struct DefStandardHeapTraits : public Traits { |
424 typedef CR HeapCrossRef; |
424 typedef CR HeapCrossRef; |
425 typedef H Heap; |
425 typedef H Heap; |
426 static HeapCrossRef *createHeapCrossRef(const Digraph &G) { |
426 static HeapCrossRef *createHeapCrossRef(const Digraph &G) { |
427 return new HeapCrossRef(G); |
427 return new HeapCrossRef(G); |
428 } |
428 } |
429 static Heap *createHeap(HeapCrossRef &R) |
429 static Heap *createHeap(HeapCrossRef &R) |
430 { |
430 { |
431 return new Heap(R); |
431 return new Heap(R); |
432 } |
432 } |
433 }; |
433 }; |
434 ///\brief \ref named-templ-param "Named parameter" for setting |
434 ///\brief \ref named-templ-param "Named parameter" for setting |
435 ///heap and cross reference type with automatic allocation |
435 ///heap and cross reference type with automatic allocation |
436 /// |
436 /// |
437 ///\ref named-templ-param "Named parameter" for setting heap and cross |
437 ///\ref named-templ-param "Named parameter" for setting heap and cross |
438 ///reference type. It can allocate the heap and the cross reference |
438 ///reference type. It can allocate the heap and the cross reference |
439 ///object if the cross reference's constructor waits for the digraph as |
439 ///object if the cross reference's constructor waits for the digraph as |
440 ///parameter and the heap's constructor waits for the cross reference. |
440 ///parameter and the heap's constructor waits for the cross reference. |
441 template <class H, class CR = typename Digraph::template NodeMap<int> > |
441 template <class H, class CR = typename Digraph::template NodeMap<int> > |
442 struct DefStandardHeap |
442 struct DefStandardHeap |
443 : public Dijkstra< Digraph, LengthMap, DefStandardHeapTraits<H, CR> > { |
443 : public Dijkstra< Digraph, LengthMap, DefStandardHeapTraits<H, CR> > { |
444 typedef Dijkstra< Digraph, LengthMap, DefStandardHeapTraits<H, CR> > |
444 typedef Dijkstra< Digraph, LengthMap, DefStandardHeapTraits<H, CR> > |
445 Create; |
445 Create; |
446 }; |
446 }; |
447 |
447 |
448 template <class T> |
448 template <class T> |
449 struct DefOperationTraitsTraits : public Traits { |
449 struct DefOperationTraitsTraits : public Traits { |
450 typedef T OperationTraits; |
450 typedef T OperationTraits; |
451 }; |
451 }; |
452 |
452 |
453 /// \brief \ref named-templ-param "Named parameter" for setting |
453 /// \brief \ref named-templ-param "Named parameter" for setting |
454 /// OperationTraits type |
454 /// OperationTraits type |
455 /// |
455 /// |
456 /// \ref named-templ-param "Named parameter" for setting OperationTraits |
456 /// \ref named-templ-param "Named parameter" for setting OperationTraits |
457 /// type |
457 /// type |
458 template <class T> |
458 template <class T> |
459 struct DefOperationTraits |
459 struct DefOperationTraits |
460 : public Dijkstra<Digraph, LengthMap, DefOperationTraitsTraits<T> > { |
460 : public Dijkstra<Digraph, LengthMap, DefOperationTraitsTraits<T> > { |
461 typedef Dijkstra<Digraph, LengthMap, DefOperationTraitsTraits<T> > |
461 typedef Dijkstra<Digraph, LengthMap, DefOperationTraitsTraits<T> > |
462 Create; |
462 Create; |
463 }; |
463 }; |
464 |
464 |
465 ///@} |
465 ///@} |
466 |
466 |
467 |
467 |
468 protected: |
468 protected: |
469 |
469 |
470 Dijkstra() {} |
470 Dijkstra() {} |
471 |
471 |
472 public: |
472 public: |
473 |
473 |
474 ///Constructor. |
474 ///Constructor. |
475 |
475 |
476 ///\param _G the digraph the algorithm will run on. |
476 ///\param _G the digraph the algorithm will run on. |
477 ///\param _length the length map used by the algorithm. |
477 ///\param _length the length map used by the algorithm. |
478 Dijkstra(const Digraph& _G, const LengthMap& _length) : |
478 Dijkstra(const Digraph& _G, const LengthMap& _length) : |
479 G(&_G), length(&_length), |
479 G(&_G), length(&_length), |
480 _pred(NULL), local_pred(false), |
480 _pred(NULL), local_pred(false), |
481 _dist(NULL), local_dist(false), |
481 _dist(NULL), local_dist(false), |
482 _processed(NULL), local_processed(false), |
482 _processed(NULL), local_processed(false), |
483 _heap_cross_ref(NULL), local_heap_cross_ref(false), |
483 _heap_cross_ref(NULL), local_heap_cross_ref(false), |
484 _heap(NULL), local_heap(false) |
484 _heap(NULL), local_heap(false) |
485 { } |
485 { } |
486 |
486 |
487 ///Destructor. |
487 ///Destructor. |
488 ~Dijkstra() |
488 ~Dijkstra() |
489 { |
489 { |
490 if(local_pred) delete _pred; |
490 if(local_pred) delete _pred; |
491 if(local_dist) delete _dist; |
491 if(local_dist) delete _dist; |
492 if(local_processed) delete _processed; |
492 if(local_processed) delete _processed; |
493 if(local_heap_cross_ref) delete _heap_cross_ref; |
493 if(local_heap_cross_ref) delete _heap_cross_ref; |
608 ///it is pushed to the heap only if either it was not in the heap |
608 ///it is pushed to the heap only if either it was not in the heap |
609 ///or the shortest path found till then is shorter than \c dst. |
609 ///or the shortest path found till then is shorter than \c dst. |
610 void addSource(Node s,Value dst=OperationTraits::zero()) |
610 void addSource(Node s,Value dst=OperationTraits::zero()) |
611 { |
611 { |
612 if(_heap->state(s) != Heap::IN_HEAP) { |
612 if(_heap->state(s) != Heap::IN_HEAP) { |
613 _heap->push(s,dst); |
613 _heap->push(s,dst); |
614 } else if(OperationTraits::less((*_heap)[s], dst)) { |
614 } else if(OperationTraits::less((*_heap)[s], dst)) { |
615 _heap->set(s,dst); |
615 _heap->set(s,dst); |
616 _pred->set(s,INVALID); |
616 _pred->set(s,INVALID); |
617 } |
617 } |
618 } |
618 } |
619 |
619 |
620 ///Processes the next node in the priority heap |
620 ///Processes the next node in the priority heap |
621 |
621 |
622 ///Processes the next node in the priority heap. |
622 ///Processes the next node in the priority heap. |
623 /// |
623 /// |
624 ///\return The processed node. |
624 ///\return The processed node. |
625 /// |
625 /// |
626 ///\warning The priority heap must not be empty! |
626 ///\warning The priority heap must not be empty! |
627 Node processNextNode() |
627 Node processNextNode() |
628 { |
628 { |
629 Node v=_heap->top(); |
629 Node v=_heap->top(); |
630 Value oldvalue=_heap->prio(); |
630 Value oldvalue=_heap->prio(); |
631 _heap->pop(); |
631 _heap->pop(); |
632 finalizeNodeData(v,oldvalue); |
632 finalizeNodeData(v,oldvalue); |
633 |
633 |
634 for(OutArcIt e(*G,v); e!=INVALID; ++e) { |
634 for(OutArcIt e(*G,v); e!=INVALID; ++e) { |
635 Node w=G->target(e); |
635 Node w=G->target(e); |
636 switch(_heap->state(w)) { |
636 switch(_heap->state(w)) { |
637 case Heap::PRE_HEAP: |
637 case Heap::PRE_HEAP: |
638 _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e])); |
638 _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e])); |
639 _pred->set(w,e); |
639 _pred->set(w,e); |
640 break; |
640 break; |
641 case Heap::IN_HEAP: |
641 case Heap::IN_HEAP: |
642 { |
642 { |
643 Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]); |
643 Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]); |
644 if ( OperationTraits::less(newvalue, (*_heap)[w]) ) { |
644 if ( OperationTraits::less(newvalue, (*_heap)[w]) ) { |
645 _heap->decrease(w, newvalue); |
645 _heap->decrease(w, newvalue); |
646 _pred->set(w,e); |
646 _pred->set(w,e); |
647 } |
647 } |
648 } |
648 } |
649 break; |
649 break; |
650 case Heap::POST_HEAP: |
650 case Heap::POST_HEAP: |
651 break; |
651 break; |
652 } |
652 } |
653 } |
653 } |
654 return v; |
654 return v; |
655 } |
655 } |
656 |
656 |
657 ///Next node to be processed. |
657 ///Next node to be processed. |
658 |
658 |
659 ///Next node to be processed. |
659 ///Next node to be processed. |
660 /// |
660 /// |
661 ///\return The next node to be processed or INVALID if the priority heap |
661 ///\return The next node to be processed or INVALID if the priority heap |
662 /// is empty. |
662 /// is empty. |
663 Node nextNode() |
663 Node nextNode() |
664 { |
664 { |
665 return !_heap->empty()?_heap->top():INVALID; |
665 return !_heap->empty()?_heap->top():INVALID; |
666 } |
666 } |
667 |
667 |
668 ///\brief Returns \c false if there are nodes |
668 ///\brief Returns \c false if there are nodes |
669 ///to be processed in the priority heap |
669 ///to be processed in the priority heap |
670 /// |
670 /// |
671 ///Returns \c false if there are nodes |
671 ///Returns \c false if there are nodes |
672 ///to be processed in the priority heap |
672 ///to be processed in the priority heap |
899 /// The cross reference type used by heap. |
899 /// The cross reference type used by heap. |
900 /// Usually it is \c Digraph::NodeMap<int>. |
900 /// Usually it is \c Digraph::NodeMap<int>. |
901 typedef typename Digraph::template NodeMap<int> HeapCrossRef; |
901 typedef typename Digraph::template NodeMap<int> HeapCrossRef; |
902 ///Instantiates a HeapCrossRef. |
902 ///Instantiates a HeapCrossRef. |
903 |
903 |
904 ///This function instantiates a \ref HeapCrossRef. |
904 ///This function instantiates a \ref HeapCrossRef. |
905 /// \param G is the digraph, to which we would like to define the |
905 /// \param G is the digraph, to which we would like to define the |
906 /// HeapCrossRef. |
906 /// HeapCrossRef. |
907 /// \todo The digraph alone may be insufficient for the initialization |
907 /// \todo The digraph alone may be insufficient for the initialization |
908 static HeapCrossRef *createHeapCrossRef(const GR &G) |
908 static HeapCrossRef *createHeapCrossRef(const GR &G) |
909 { |
909 { |
910 return new HeapCrossRef(G); |
910 return new HeapCrossRef(G); |
911 } |
911 } |
912 |
912 |
913 ///The heap type used by Dijkstra algorithm. |
913 ///The heap type used by Dijkstra algorithm. |
914 |
914 |
915 ///The heap type used by Dijkstra algorithm. |
915 ///The heap type used by Dijkstra algorithm. |
916 /// |
916 /// |
917 ///\sa BinHeap |
917 ///\sa BinHeap |
918 ///\sa Dijkstra |
918 ///\sa Dijkstra |
919 typedef BinHeap<typename LM::Value, typename GR::template NodeMap<int>, |
919 typedef BinHeap<typename LM::Value, typename GR::template NodeMap<int>, |
920 std::less<Value> > Heap; |
920 std::less<Value> > Heap; |
921 |
921 |
922 static Heap *createHeap(HeapCrossRef& R) |
922 static Heap *createHeap(HeapCrossRef& R) |
923 { |
923 { |
924 return new Heap(R); |
924 return new Heap(R); |
925 } |
925 } |
926 |
926 |
927 ///\brief The type of the map that stores the last |
927 ///\brief The type of the map that stores the last |
928 ///arcs of the shortest paths. |
928 ///arcs of the shortest paths. |
929 /// |
929 /// |
930 ///The type of the map that stores the last |
930 ///The type of the map that stores the last |
931 ///arcs of the shortest paths. |
931 ///arcs of the shortest paths. |
932 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
932 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
933 /// |
933 /// |
934 typedef NullMap <typename GR::Node,typename GR::Arc> PredMap; |
934 typedef NullMap <typename GR::Node,typename GR::Arc> PredMap; |
935 ///Instantiates a PredMap. |
935 ///Instantiates a PredMap. |
936 |
936 |
937 ///This function instantiates a \ref PredMap. |
937 ///This function instantiates a \ref PredMap. |
938 ///\param g is the digraph, to which we would like to define the PredMap. |
938 ///\param g is the digraph, to which we would like to define the PredMap. |
939 ///\todo The digraph alone may be insufficient for the initialization |
939 ///\todo The digraph alone may be insufficient for the initialization |
940 #ifdef DOXYGEN |
940 #ifdef DOXYGEN |
941 static PredMap *createPredMap(const GR &g) |
941 static PredMap *createPredMap(const GR &g) |
942 #else |
942 #else |
943 static PredMap *createPredMap(const GR &) |
943 static PredMap *createPredMap(const GR &) |
944 #endif |
944 #endif |
945 { |
945 { |
946 return new PredMap(); |
946 return new PredMap(); |
947 } |
947 } |
948 ///The type of the map that stores whether a nodes is processed. |
948 ///The type of the map that stores whether a nodes is processed. |
949 |
949 |
950 ///The type of the map that stores whether a nodes is processed. |
950 ///The type of the map that stores whether a nodes is processed. |
951 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
951 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
952 ///By default it is a NullMap. |
952 ///By default it is a NullMap. |
953 ///\todo If it is set to a real map, |
953 ///\todo If it is set to a real map, |
954 ///Dijkstra::processed() should read this. |
954 ///Dijkstra::processed() should read this. |
955 ///\todo named parameter to set this type, function to read and write. |
955 ///\todo named parameter to set this type, function to read and write. |
956 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
956 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
957 ///Instantiates a ProcessedMap. |
957 ///Instantiates a ProcessedMap. |
958 |
958 |
959 ///This function instantiates a \ref ProcessedMap. |
959 ///This function instantiates a \ref ProcessedMap. |
960 ///\param g is the digraph, to which |
960 ///\param g is the digraph, to which |
961 ///we would like to define the \ref ProcessedMap |
961 ///we would like to define the \ref ProcessedMap |
962 #ifdef DOXYGEN |
962 #ifdef DOXYGEN |
963 static ProcessedMap *createProcessedMap(const GR &g) |
963 static ProcessedMap *createProcessedMap(const GR &g) |
964 #else |
964 #else |
1016 ///Pointer to the source node. |
1016 ///Pointer to the source node. |
1017 Node _source; |
1017 Node _source; |
1018 |
1018 |
1019 public: |
1019 public: |
1020 /// Constructor. |
1020 /// Constructor. |
1021 |
1021 |
1022 /// This constructor does not require parameters, therefore it initiates |
1022 /// This constructor does not require parameters, therefore it initiates |
1023 /// all of the attributes to default values (0, INVALID). |
1023 /// all of the attributes to default values (0, INVALID). |
1024 DijkstraWizardBase() : _g(0), _length(0), _pred(0), |
1024 DijkstraWizardBase() : _g(0), _length(0), _pred(0), |
1025 _dist(0), _source(INVALID) {} |
1025 _dist(0), _source(INVALID) {} |
1026 |
1026 |
1027 /// Constructor. |
1027 /// Constructor. |
1028 |
1028 |
1029 /// This constructor requires some parameters, |
1029 /// This constructor requires some parameters, |
1030 /// listed in the parameters list. |
1030 /// listed in the parameters list. |
1031 /// Others are initiated to 0. |
1031 /// Others are initiated to 0. |
1032 /// \param g is the initial value of \ref _g |
1032 /// \param g is the initial value of \ref _g |
1033 /// \param l is the initial value of \ref _length |
1033 /// \param l is the initial value of \ref _length |
1034 /// \param s is the initial value of \ref _source |
1034 /// \param s is the initial value of \ref _source |
1035 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) : |
1035 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) : |
1036 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), |
1036 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), |
1037 _length(reinterpret_cast<void*>(const_cast<LM*>(&l))), |
1037 _length(reinterpret_cast<void*>(const_cast<LM*>(&l))), |
1038 _pred(0), _dist(0), _source(s) {} |
1038 _pred(0), _dist(0), _source(s) {} |
1039 |
1039 |
1040 }; |
1040 }; |
1041 |
1041 |
1042 /// A class to make the usage of Dijkstra algorithm easier |
1042 /// A class to make the usage of Dijkstra algorithm easier |
1043 |
1043 |
1044 /// This class is created to make it easier to use Dijkstra algorithm. |
1044 /// This class is created to make it easier to use Dijkstra algorithm. |
1045 /// It uses the functions and features of the plain \ref Dijkstra, |
1045 /// It uses the functions and features of the plain \ref Dijkstra, |
1046 /// but it is much simpler to use it. |
1046 /// but it is much simpler to use it. |
1130 struct DefPredMapBase : public Base { |
1130 struct DefPredMapBase : public Base { |
1131 typedef T PredMap; |
1131 typedef T PredMap; |
1132 static PredMap *createPredMap(const Digraph &) { return 0; }; |
1132 static PredMap *createPredMap(const Digraph &) { return 0; }; |
1133 DefPredMapBase(const TR &b) : TR(b) {} |
1133 DefPredMapBase(const TR &b) : TR(b) {} |
1134 }; |
1134 }; |
1135 |
1135 |
1136 ///\brief \ref named-templ-param "Named parameter" |
1136 ///\brief \ref named-templ-param "Named parameter" |
1137 ///function for setting PredMap type |
1137 ///function for setting PredMap type |
1138 /// |
1138 /// |
1139 /// \ref named-templ-param "Named parameter" |
1139 /// \ref named-templ-param "Named parameter" |
1140 ///function for setting PredMap type |
1140 ///function for setting PredMap type |
1141 /// |
1141 /// |
1142 template<class T> |
1142 template<class T> |
1143 DijkstraWizard<DefPredMapBase<T> > predMap(const T &t) |
1143 DijkstraWizard<DefPredMapBase<T> > predMap(const T &t) |
1144 { |
1144 { |
1145 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1145 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1146 return DijkstraWizard<DefPredMapBase<T> >(*this); |
1146 return DijkstraWizard<DefPredMapBase<T> >(*this); |
1147 } |
1147 } |
1148 |
1148 |
1149 template<class T> |
1149 template<class T> |
1150 struct DefDistMapBase : public Base { |
1150 struct DefDistMapBase : public Base { |
1151 typedef T DistMap; |
1151 typedef T DistMap; |
1152 static DistMap *createDistMap(const Digraph &) { return 0; }; |
1152 static DistMap *createDistMap(const Digraph &) { return 0; }; |
1153 DefDistMapBase(const TR &b) : TR(b) {} |
1153 DefDistMapBase(const TR &b) : TR(b) {} |
1154 }; |
1154 }; |
1155 |
1155 |
1156 ///\brief \ref named-templ-param "Named parameter" |
1156 ///\brief \ref named-templ-param "Named parameter" |
1157 ///function for setting DistMap type |
1157 ///function for setting DistMap type |
1158 /// |
1158 /// |
1159 /// \ref named-templ-param "Named parameter" |
1159 /// \ref named-templ-param "Named parameter" |
1160 ///function for setting DistMap type |
1160 ///function for setting DistMap type |
1161 /// |
1161 /// |
1162 template<class T> |
1162 template<class T> |
1163 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t) |
1163 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t) |
1164 { |
1164 { |
1165 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1165 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1166 return DijkstraWizard<DefDistMapBase<T> >(*this); |
1166 return DijkstraWizard<DefDistMapBase<T> >(*this); |
1167 } |
1167 } |
1168 |
1168 |
1169 /// Sets the source node, from which the Dijkstra algorithm runs. |
1169 /// Sets the source node, from which the Dijkstra algorithm runs. |
1170 |
1170 |
1171 /// Sets the source node, from which the Dijkstra algorithm runs. |
1171 /// Sets the source node, from which the Dijkstra algorithm runs. |
1172 /// \param s is the source node. |
1172 /// \param s is the source node. |
1173 DijkstraWizard<TR> &source(Node s) |
1173 DijkstraWizard<TR> &source(Node s) |
1174 { |
1174 { |
1175 Base::_source=s; |
1175 Base::_source=s; |
1176 return *this; |
1176 return *this; |
1177 } |
1177 } |
1178 |
1178 |
1179 }; |
1179 }; |
1180 |
1180 |
1181 ///Function type interface for Dijkstra algorithm. |
1181 ///Function type interface for Dijkstra algorithm. |
1182 |
1182 |
1183 /// \ingroup shortest_path |
1183 /// \ingroup shortest_path |
1184 ///Function type interface for Dijkstra algorithm. |
1184 ///Function type interface for Dijkstra algorithm. |
1185 /// |
1185 /// |