59 ///Instantiates a HeapCrossRef. |
59 ///Instantiates a HeapCrossRef. |
60 |
60 |
61 ///This function instantiates a \ref HeapCrossRef. |
61 ///This function instantiates a \ref HeapCrossRef. |
62 /// \param G is the graph, to which we would like to define the |
62 /// \param G is the graph, to which we would like to define the |
63 /// HeapCrossRef. |
63 /// HeapCrossRef. |
64 /// \todo The graph alone may be insufficient for the initialization |
|
65 static HeapCrossRef *createHeapCrossRef(const GR &G) |
64 static HeapCrossRef *createHeapCrossRef(const GR &G) |
66 { |
65 { |
67 return new HeapCrossRef(G); |
66 return new HeapCrossRef(G); |
68 } |
67 } |
69 |
68 |
72 ///The heap type used by Dijkstra algorithm. |
71 ///The heap type used by Dijkstra algorithm. |
73 /// |
72 /// |
74 ///\sa BinHeap |
73 ///\sa BinHeap |
75 ///\sa Dijkstra |
74 ///\sa Dijkstra |
76 typedef BinHeap<typename Graph::Node, typename LM::Value, |
75 typedef BinHeap<typename Graph::Node, typename LM::Value, |
77 typename GR::template NodeMap<int>, |
76 HeapCrossRef, std::less<Value> > Heap; |
78 std::less<Value> > Heap; |
|
79 |
77 |
80 static Heap *createHeap(HeapCrossRef& R) |
78 static Heap *createHeap(HeapCrossRef& R) |
81 { |
79 { |
82 return new Heap(R); |
80 return new Heap(R); |
83 } |
81 } |
358 |
356 |
359 template <class H, class CR> |
357 template <class H, class CR> |
360 struct DefHeapTraits : public Traits { |
358 struct DefHeapTraits : public Traits { |
361 typedef CR HeapCrossRef; |
359 typedef CR HeapCrossRef; |
362 typedef H Heap; |
360 typedef H Heap; |
363 static HeapCrossRef *createHeapCrossRef(const Graph &G) { |
361 static HeapCrossRef *createHeapCrossRef(const Graph &) { |
364 return new HeapCrossRef(G); |
362 throw UninitializedParameter(); |
365 } |
363 } |
366 static Heap *createHeap(HeapCrossRef &R) |
364 static Heap *createHeap(HeapCrossRef &) |
367 { |
365 { |
368 return new Heap(R); |
366 throw UninitializedParameter(); |
369 } |
367 } |
370 }; |
368 }; |
371 ///\ref named-templ-param "Named parameter" for setting heap and cross |
369 ///\ref named-templ-param "Named parameter" for setting heap and cross |
372 ///reference type |
370 ///reference type |
373 |
371 |
376 /// |
374 /// |
377 template <class H, class CR = typename Graph::template NodeMap<int> > |
375 template <class H, class CR = typename Graph::template NodeMap<int> > |
378 struct DefHeap |
376 struct DefHeap |
379 : public Dijkstra< Graph, LengthMap, DefHeapTraits<H, CR> > { |
377 : public Dijkstra< Graph, LengthMap, DefHeapTraits<H, CR> > { |
380 typedef Dijkstra< Graph, LengthMap, DefHeapTraits<H, CR> > Create; |
378 typedef Dijkstra< Graph, LengthMap, DefHeapTraits<H, CR> > Create; |
|
379 }; |
|
380 |
|
381 template <class H, class CR> |
|
382 struct DefStandardHeapTraits : public Traits { |
|
383 typedef CR HeapCrossRef; |
|
384 typedef H Heap; |
|
385 static HeapCrossRef *createHeapCrossRef(const Graph &G) { |
|
386 return new HeapCrossRef(G); |
|
387 } |
|
388 static Heap *createHeap(HeapCrossRef &R) |
|
389 { |
|
390 return new Heap(R); |
|
391 } |
|
392 }; |
|
393 ///\ref named-templ-param "Named parameter" for setting heap and cross |
|
394 ///reference type with automatic allocation |
|
395 |
|
396 ///\ref named-templ-param "Named parameter" for setting heap and cross |
|
397 ///reference type. It can allocate the heap and the cross reference |
|
398 ///object if the cross reference's constructor waits for the graph as |
|
399 ///parameter and the heap's constructor waits for the cross reference. |
|
400 template <class H, class CR = typename Graph::template NodeMap<int> > |
|
401 struct DefStandardHeap |
|
402 : public Dijkstra< Graph, LengthMap, DefStandardHeapTraits<H, CR> > { |
|
403 typedef Dijkstra< Graph, LengthMap, DefStandardHeapTraits<H, CR> > |
|
404 Create; |
381 }; |
405 }; |
382 |
406 |
383 ///@} |
407 ///@} |
384 |
408 |
385 |
409 |
451 if(local_dist) { |
475 if(local_dist) { |
452 delete _dist; |
476 delete _dist; |
453 local_dist=false; |
477 local_dist=false; |
454 } |
478 } |
455 _dist = &m; |
479 _dist = &m; |
|
480 return *this; |
|
481 } |
|
482 |
|
483 ///Sets the heap and the cross reference used by algorithm. |
|
484 |
|
485 ///Sets the heap and the cross reference used by algorithm. |
|
486 ///If you don't use this function before calling \ref run(), |
|
487 ///it will allocate one. The destuctor deallocates this |
|
488 ///automatically allocated map, of course. |
|
489 ///\return <tt> (*this) </tt> |
|
490 Dijkstra &heap(Heap& heap, HeapCrossRef &crossRef) |
|
491 { |
|
492 if(local_heap_cross_ref) { |
|
493 delete _heap_cross_ref; |
|
494 local_heap_cross_ref=false; |
|
495 } |
|
496 _heap_cross_ref = &crossRef; |
|
497 if(local_heap) { |
|
498 delete _heap; |
|
499 local_heap=false; |
|
500 } |
|
501 _heap = &heap; |
456 return *this; |
502 return *this; |
457 } |
503 } |
458 |
504 |
459 private: |
505 private: |
460 void finalizeNodeData(Node v,Value dst) |
506 void finalizeNodeData(Node v,Value dst) |