Changeset 209:765619b7cbb2 in lemon1.2 for lemon/dijkstra.h
 Timestamp:
 07/13/08 20:51:02 (16 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/dijkstra.h
r184 r209 1 /* * C++*1 /* * mode: C++; indenttabsmode: nil; * 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 20032008 … … 35 35 36 36 /// \brief Default OperationTraits for the Dijkstra algorithm class. 37 /// 37 /// 38 38 /// It defines all computational operations and constants which are 39 39 /// used in the Dijkstra algorithm. … … 55 55 56 56 /// \brief Widest path OperationTraits for the Dijkstra algorithm class. 57 /// 57 /// 58 58 /// It defines all computational operations and constants which are 59 59 /// used in the Dijkstra algorithm for widest path computation. … … 73 73 } 74 74 }; 75 75 76 76 ///Default traits class of Dijkstra class. 77 77 … … 82 82 struct DijkstraDefaultTraits 83 83 { 84 ///The digraph type the algorithm runs on. 84 ///The digraph type the algorithm runs on. 85 85 typedef GR Digraph; 86 86 ///The type of the map that stores the arc lengths. … … 104 104 ///Instantiates a HeapCrossRef. 105 105 106 ///This function instantiates a \c HeapCrossRef. 107 /// \param G is the digraph, to which we would like to define the 106 ///This function instantiates a \c HeapCrossRef. 107 /// \param G is the digraph, to which we would like to define the 108 108 /// HeapCrossRef. 109 static HeapCrossRef *createHeapCrossRef(const GR &G) 109 static HeapCrossRef *createHeapCrossRef(const GR &G) 110 110 { 111 111 return new HeapCrossRef(G); 112 112 } 113 113 114 114 ///The heap type used by Dijkstra algorithm. 115 115 … … 120 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 124 return new Heap(R); … … 127 127 ///\brief The type of the map that stores the last 128 128 ///arcs of the shortest paths. 129 /// 129 /// 130 130 ///The type of the map that stores the last 131 131 ///arcs of the shortest paths. … … 134 134 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap; 135 135 ///Instantiates a PredMap. 136 137 ///This function instantiates a \c PredMap. 136 137 ///This function instantiates a \c PredMap. 138 138 ///\param G is the digraph, to which we would like to define the PredMap. 139 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 142 return new PredMap(G); … … 144 144 145 145 ///The type of the map that stores whether a nodes is processed. 146 146 147 147 ///The type of the map that stores whether a nodes is processed. 148 148 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. … … 153 153 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 154 154 ///Instantiates a ProcessedMap. 155 156 ///This function instantiates a \c ProcessedMap. 155 156 ///This function instantiates a \c ProcessedMap. 157 157 ///\param g is the digraph, to which 158 158 ///we would like to define the \c ProcessedMap … … 166 166 } 167 167 ///The type of the map that stores the dists of the nodes. 168 168 169 169 ///The type of the map that stores the dists of the nodes. 170 170 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. … … 172 172 typedef typename Digraph::template NodeMap<typename LM::Value> DistMap; 173 173 ///Instantiates a DistMap. 174 175 ///This function instantiates a \ref DistMap. 174 175 ///This function instantiates a \ref DistMap. 176 176 ///\param G is the digraph, to which we would like to define the \ref DistMap 177 177 static DistMap *createDistMap(const GR &G) … … 180 180 } 181 181 }; 182 182 183 183 ///%Dijkstra algorithm class. 184 184 185 185 /// \ingroup shortest_path 186 186 ///This class provides an efficient implementation of %Dijkstra algorithm. … … 203 203 ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>". The value 204 204 ///of LM is not used directly by Dijkstra, it is only passed to \ref 205 ///DijkstraDefaultTraits. 205 ///DijkstraDefaultTraits. 206 206 ///\tparam TR Traits class to set 207 207 ///various data types used by the algorithm. The default traits … … 215 215 #else 216 216 template <typename GR=ListDigraph, 217 218 217 typename LM=typename GR::template ArcMap<int>, 218 typename TR=DijkstraDefaultTraits<GR,LM> > 219 219 #endif 220 220 class Dijkstra { … … 229 229 public: 230 230 virtual const char* what() const throw() { 231 231 return "lemon::Dijkstra::UninitializedParameter"; 232 232 } 233 233 }; … … 244 244 ///\e 245 245 typedef typename Digraph::OutArcIt OutArcIt; 246 246 247 247 ///The type of the length of the arcs. 248 248 typedef typename TR::LengthMap::Value Value; … … 289 289 290 290 ///Creates the maps if necessary. 291 291 292 292 ///\todo Better memory allocation (instead of new). 293 void create_maps() 293 void create_maps() 294 294 { 295 295 if(!_pred) { 296 297 296 local_pred = true; 297 _pred = Traits::createPredMap(*G); 298 298 } 299 299 if(!_dist) { 300 301 300 local_dist = true; 301 _dist = Traits::createDistMap(*G); 302 302 } 303 303 if(!_processed) { 304 305 304 local_processed = true; 305 _processed = Traits::createProcessedMap(*G); 306 306 } 307 307 if (!_heap_cross_ref) { 308 309 308 local_heap_cross_ref = true; 309 _heap_cross_ref = Traits::createHeapCrossRef(*G); 310 310 } 311 311 if (!_heap) { 312 313 314 } 315 } 316 312 local_heap = true; 313 _heap = Traits::createHeap(*_heap_cross_ref); 314 } 315 } 316 317 317 public : 318 318 319 319 typedef Dijkstra Create; 320 320 321 321 ///\name Named template parameters 322 322 … … 328 328 static PredMap *createPredMap(const Digraph &) 329 329 { 330 330 throw UninitializedParameter(); 331 331 } 332 332 }; … … 336 336 /// 337 337 template <class T> 338 struct DefPredMap 339 : public Dijkstra< Digraph, 340 typedef Dijkstra< Digraph, 341 }; 342 338 struct DefPredMap 339 : public Dijkstra< Digraph, LengthMap, DefPredMapTraits<T> > { 340 typedef Dijkstra< Digraph, LengthMap, DefPredMapTraits<T> > Create; 341 }; 342 343 343 template <class T> 344 344 struct DefDistMapTraits : public Traits { … … 346 346 static DistMap *createDistMap(const Digraph &) 347 347 { 348 348 throw UninitializedParameter(); 349 349 } 350 350 }; … … 354 354 /// 355 355 template <class T> 356 struct DefDistMap 357 : public Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > { 356 struct DefDistMap 357 : public Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > { 358 358 typedef Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > Create; 359 359 }; 360 360 361 361 template <class T> 362 362 struct DefProcessedMapTraits : public Traits { 363 363 typedef T ProcessedMap; 364 static ProcessedMap *createProcessedMap(const Digraph &G) 364 static ProcessedMap *createProcessedMap(const Digraph &G) 365 365 { 366 366 throw UninitializedParameter(); 367 367 } 368 368 }; … … 372 372 /// 373 373 template <class T> 374 struct DefProcessedMap 375 : public Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > {376 typedef Dijkstra< Digraph, 377 }; 378 374 struct DefProcessedMap 375 : public Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > { 376 typedef Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > Create; 377 }; 378 379 379 struct DefDigraphProcessedMapTraits : public Traits { 380 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 383 return new ProcessedMap(G); 384 384 } 385 385 }; … … 391 391 ///If you don't set it explicitely, it will be automatically allocated. 392 392 template <class T> 393 struct DefProcessedMapToBeDefaultMap 393 struct DefProcessedMapToBeDefaultMap 394 394 : public Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> { 395 395 typedef Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> Create; … … 401 401 typedef H Heap; 402 402 static HeapCrossRef *createHeapCrossRef(const Digraph &) { 403 404 } 405 static Heap *createHeap(HeapCrossRef &) 403 throw UninitializedParameter(); 404 } 405 static Heap *createHeap(HeapCrossRef &) 406 406 { 407 407 throw UninitializedParameter(); 408 408 } 409 409 }; … … 411 411 ///heap and cross reference type 412 412 /// 413 ///\ref namedtemplparam "Named parameter" for setting heap and cross 413 ///\ref namedtemplparam "Named parameter" for setting heap and cross 414 414 ///reference type 415 415 /// 416 416 template <class H, class CR = typename Digraph::template NodeMap<int> > 417 417 struct DefHeap 418 : public Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > {419 typedef Dijkstra< Digraph, 418 : public Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > { 419 typedef Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > Create; 420 420 }; 421 421 … … 425 425 typedef H Heap; 426 426 static HeapCrossRef *createHeapCrossRef(const Digraph &G) { 427 428 } 429 static Heap *createHeap(HeapCrossRef &R) 427 return new HeapCrossRef(G); 428 } 429 static Heap *createHeap(HeapCrossRef &R) 430 430 { 431 431 return new Heap(R); 432 432 } 433 433 }; … … 435 435 ///heap and cross reference type with automatic allocation 436 436 /// 437 ///\ref namedtemplparam "Named parameter" for setting heap and cross 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 437 ///\ref namedtemplparam "Named parameter" for setting heap and cross 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 440 440 ///parameter and the heap's constructor waits for the cross reference. 441 441 template <class H, class CR = typename Digraph::template NodeMap<int> > 442 442 struct DefStandardHeap 443 : public Dijkstra< Digraph, LengthMap, DefStandardHeapTraits<H, CR> > {444 typedef Dijkstra< Digraph, LengthMap, DefStandardHeapTraits<H, CR> >443 : public Dijkstra< Digraph, LengthMap, DefStandardHeapTraits<H, CR> > { 444 typedef Dijkstra< Digraph, LengthMap, DefStandardHeapTraits<H, CR> > 445 445 Create; 446 446 }; … … 450 450 typedef T OperationTraits; 451 451 }; 452 453 /// \brief \ref namedtemplparam "Named parameter" for setting 452 453 /// \brief \ref namedtemplparam "Named parameter" for setting 454 454 /// OperationTraits type 455 455 /// … … 462 462 Create; 463 463 }; 464 464 465 465 ///@} 466 466 … … 470 470 Dijkstra() {} 471 471 472 public: 473 472 public: 473 474 474 ///Constructor. 475 475 476 476 ///\param _G the digraph the algorithm will run on. 477 477 ///\param _length the length map used by the algorithm. … … 484 484 _heap(NULL), local_heap(false) 485 485 { } 486 486 487 487 ///Destructor. 488 ~Dijkstra() 488 ~Dijkstra() 489 489 { 490 490 if(local_pred) delete _pred; … … 499 499 ///Sets the length map. 500 500 ///\return <tt> (*this) </tt> 501 Dijkstra &lengthMap(const LengthMap &m) 501 Dijkstra &lengthMap(const LengthMap &m) 502 502 { 503 503 length = &m; … … 512 512 ///automatically allocated map, of course. 513 513 ///\return <tt> (*this) </tt> 514 Dijkstra &predMap(PredMap &m) 514 Dijkstra &predMap(PredMap &m) 515 515 { 516 516 if(local_pred) { 517 518 517 delete _pred; 518 local_pred=false; 519 519 } 520 520 _pred = &m; … … 529 529 ///automatically allocated map, of course. 530 530 ///\return <tt> (*this) </tt> 531 Dijkstra &distMap(DistMap &m) 531 Dijkstra &distMap(DistMap &m) 532 532 { 533 533 if(local_dist) { 534 535 534 delete _dist; 535 local_dist=false; 536 536 } 537 537 _dist = &m; … … 549 549 { 550 550 if(local_heap_cross_ref) { 551 552 551 delete _heap_cross_ref; 552 local_heap_cross_ref=false; 553 553 } 554 554 _heap_cross_ref = &cr; 555 555 if(local_heap) { 556 557 556 delete _heap; 557 local_heap=false; 558 558 } 559 559 _heap = &hp; … … 593 593 _heap>clear(); 594 594 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { 595 596 597 598 } 599 } 600 595 _pred>set(u,INVALID); 596 _processed>set(u,false); 597 _heap_cross_ref>set(u,Heap::PRE_HEAP); 598 } 599 } 600 601 601 ///Adds a new source node. 602 602 … … 611 611 { 612 612 if(_heap>state(s) != Heap::IN_HEAP) { 613 613 _heap>push(s,dst); 614 614 } else if(OperationTraits::less((*_heap)[s], dst)) { 615 616 617 } 618 } 619 615 _heap>set(s,dst); 616 _pred>set(s,INVALID); 617 } 618 } 619 620 620 ///Processes the next node in the priority heap 621 621 … … 627 627 Node processNextNode() 628 628 { 629 Node v=_heap>top(); 629 Node v=_heap>top(); 630 630 Value oldvalue=_heap>prio(); 631 631 _heap>pop(); 632 632 finalizeNodeData(v,oldvalue); 633 633 634 634 for(OutArcIt e(*G,v); e!=INVALID; ++e) { 635 Node w=G>target(e); 636 637 638 _heap>push(w,OperationTraits::plus(oldvalue, (*length)[e])); 639 640 641 642 643 644 645 _heap>decrease(w, newvalue); 646 647 648 649 650 651 652 635 Node w=G>target(e); 636 switch(_heap>state(w)) { 637 case Heap::PRE_HEAP: 638 _heap>push(w,OperationTraits::plus(oldvalue, (*length)[e])); 639 _pred>set(w,e); 640 break; 641 case Heap::IN_HEAP: 642 { 643 Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]); 644 if ( OperationTraits::less(newvalue, (*_heap)[w]) ) { 645 _heap>decrease(w, newvalue); 646 _pred>set(w,e); 647 } 648 } 649 break; 650 case Heap::POST_HEAP: 651 break; 652 } 653 653 } 654 654 return v; … … 656 656 657 657 ///Next node to be processed. 658 658 659 659 ///Next node to be processed. 660 660 /// … … 662 662 /// is empty. 663 663 Node nextNode() 664 { 664 { 665 665 return !_heap>empty()?_heap>top():INVALID; 666 666 } 667 667 668 668 ///\brief Returns \c false if there are nodes 669 669 ///to be processed in the priority heap … … 677 677 /// 678 678 int queueSize() { return _heap>size(); } 679 679 680 680 ///Executes the algorithm. 681 681 … … 696 696 while ( !_heap>empty() ) processNextNode(); 697 697 } 698 698 699 699 ///Executes the algorithm until \c dest is reached. 700 700 … … 716 716 if ( !_heap>empty() ) finalizeNodeData(_heap>top(),_heap>prio()); 717 717 } 718 718 719 719 ///Executes the algorithm until a condition is met. 720 720 … … 737 737 return _heap>top(); 738 738 } 739 739 740 740 ///Runs %Dijkstra algorithm from node \c s. 741 741 742 742 ///This method runs the %Dijkstra algorithm from a root node \c s 743 743 ///in order to … … 758 758 start(); 759 759 } 760 760 761 761 ///Finds the shortest path between \c s and \c t. 762 762 763 763 ///Finds the shortest path between \c s and \c t. 764 764 /// … … 778 778 return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t]; 779 779 } 780 780 781 781 ///@} 782 782 … … 786 786 ///Before the use of these functions, 787 787 ///either run() or start() must be called. 788 788 789 789 ///@{ 790 790 791 791 ///Gives back the shortest path. 792 792 793 793 ///Gives back the shortest path. 794 794 ///\pre The \c t should be reachable from the source. 795 Path path(Node t) 795 Path path(Node t) 796 796 { 797 797 return Path(*G, *_pred, t); … … 833 833 ///using this function. 834 834 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: 835 836 835 G>source((*_pred)[v]); } 836 837 837 ///Returns a reference to the NodeMap of distances. 838 838 … … 840 840 ///be called before using this function. 841 841 const DistMap &distMap() const { return *_dist;} 842 842 843 843 ///Returns a reference to the shortest path tree map. 844 844 … … 847 847 ///\pre \ref run() must be called before using this function. 848 848 const PredMap &predMap() const { return *_pred;} 849 849 850 850 ///Checks if a node is reachable from the root. 851 851 … … 863 863 /// 864 864 bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; } 865 865 866 866 ///@} 867 867 }; … … 870 870 871 871 872 872 873 873 ///Default traits class of Dijkstra function. 874 874 … … 879 879 struct DijkstraWizardDefaultTraits 880 880 { 881 ///The digraph type the algorithm runs on. 881 ///The digraph type the algorithm runs on. 882 882 typedef GR Digraph; 883 883 ///The type of the map that stores the arc lengths. … … 902 902 ///Instantiates a HeapCrossRef. 903 903 904 ///This function instantiates a \ref HeapCrossRef. 905 /// \param G is the digraph, to which we would like to define the 904 ///This function instantiates a \ref HeapCrossRef. 905 /// \param G is the digraph, to which we would like to define the 906 906 /// HeapCrossRef. 907 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 910 return new HeapCrossRef(G); 911 911 } 912 912 913 913 ///The heap type used by Dijkstra algorithm. 914 914 … … 918 918 ///\sa Dijkstra 919 919 typedef BinHeap<typename LM::Value, typename GR::template NodeMap<int>, 920 921 922 static Heap *createHeap(HeapCrossRef& R) 920 std::less<Value> > Heap; 921 922 static Heap *createHeap(HeapCrossRef& R) 923 923 { 924 924 return new Heap(R); … … 927 927 ///\brief The type of the map that stores the last 928 928 ///arcs of the shortest paths. 929 /// 929 /// 930 930 ///The type of the map that stores the last 931 931 ///arcs of the shortest paths. … … 934 934 typedef NullMap <typename GR::Node,typename GR::Arc> PredMap; 935 935 ///Instantiates a PredMap. 936 937 ///This function instantiates a \ref PredMap. 936 937 ///This function instantiates a \ref PredMap. 938 938 ///\param g is the digraph, to which we would like to define the PredMap. 939 939 ///\todo The digraph alone may be insufficient for the initialization 940 940 #ifdef DOXYGEN 941 static PredMap *createPredMap(const GR &g) 941 static PredMap *createPredMap(const GR &g) 942 942 #else 943 static PredMap *createPredMap(const GR &) 943 static PredMap *createPredMap(const GR &) 944 944 #endif 945 945 { … … 947 947 } 948 948 ///The type of the map that stores whether a nodes is processed. 949 949 950 950 ///The type of the map that stores whether a nodes is processed. 951 951 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. … … 956 956 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 957 957 ///Instantiates a ProcessedMap. 958 959 ///This function instantiates a \ref ProcessedMap. 958 959 ///This function instantiates a \ref ProcessedMap. 960 960 ///\param g is the digraph, to which 961 961 ///we would like to define the \ref ProcessedMap … … 969 969 } 970 970 ///The type of the map that stores the dists of the nodes. 971 971 972 972 ///The type of the map that stores the dists of the nodes. 973 973 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. … … 975 975 typedef NullMap<typename Digraph::Node,typename LM::Value> DistMap; 976 976 ///Instantiates a DistMap. 977 978 ///This function instantiates a \ref DistMap. 977 978 ///This function instantiates a \ref DistMap. 979 979 ///\param g is the digraph, to which we would like to define the \ref DistMap 980 980 #ifdef DOXYGEN … … 987 987 } 988 988 }; 989 989 990 990 /// Default traits used by \ref DijkstraWizard 991 991 … … 1019 1019 public: 1020 1020 /// Constructor. 1021 1021 1022 1022 /// This constructor does not require parameters, therefore it initiates 1023 1023 /// all of the attributes to default values (0, INVALID). 1024 1024 DijkstraWizardBase() : _g(0), _length(0), _pred(0), 1025 1025 _dist(0), _source(INVALID) {} 1026 1026 1027 1027 /// Constructor. 1028 1028 1029 1029 /// This constructor requires some parameters, 1030 1030 /// listed in the parameters list. … … 1034 1034 /// \param s is the initial value of \ref _source 1035 1035 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) : 1036 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 1037 _length(reinterpret_cast<void*>(const_cast<LM*>(&l))), 1036 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 1037 _length(reinterpret_cast<void*>(const_cast<LM*>(&l))), 1038 1038 _pred(0), _dist(0), _source(s) {} 1039 1039 1040 1040 }; 1041 1041 1042 1042 /// A class to make the usage of Dijkstra algorithm easier 1043 1043 … … 1057 1057 /// 1058 1058 /// It does not have own \ref run method. When its \ref run method is called 1059 /// it initiates a plain \ref Dijkstra class, and calls the \ref 1059 /// it initiates a plain \ref Dijkstra class, and calls the \ref 1060 1060 /// Dijkstra::run method of it. 1061 1061 template<class TR> … … 1074 1074 //\e 1075 1075 typedef typename Digraph::OutArcIt OutArcIt; 1076 1076 1077 1077 ///The type of the map that stores the arc lengths. 1078 1078 typedef typename TR::LengthMap LengthMap; … … 1103 1103 1104 1104 ///Runs Dijkstra algorithm from a given node. 1105 1105 1106 1106 ///Runs Dijkstra algorithm from a given node. 1107 1107 ///The node can be given by the \ref source function. … … 1109 1109 { 1110 1110 if(Base::_source==INVALID) throw UninitializedParameter(); 1111 Dijkstra<Digraph,LengthMap,TR> 1112 1111 Dijkstra<Digraph,LengthMap,TR> 1112 dij(*reinterpret_cast<const Digraph*>(Base::_g), 1113 1113 *reinterpret_cast<const LengthMap*>(Base::_length)); 1114 1114 if(Base::_pred) dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); … … 1133 1133 DefPredMapBase(const TR &b) : TR(b) {} 1134 1134 }; 1135 1135 1136 1136 ///\brief \ref namedtemplparam "Named parameter" 1137 1137 ///function for setting PredMap type … … 1141 1141 /// 1142 1142 template<class T> 1143 DijkstraWizard<DefPredMapBase<T> > predMap(const T &t) 1143 DijkstraWizard<DefPredMapBase<T> > predMap(const T &t) 1144 1144 { 1145 1145 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); 1146 1146 return DijkstraWizard<DefPredMapBase<T> >(*this); 1147 1147 } 1148 1148 1149 1149 template<class T> 1150 1150 struct DefDistMapBase : public Base { … … 1153 1153 DefDistMapBase(const TR &b) : TR(b) {} 1154 1154 }; 1155 1155 1156 1156 ///\brief \ref namedtemplparam "Named parameter" 1157 1157 ///function for setting DistMap type … … 1161 1161 /// 1162 1162 template<class T> 1163 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t) 1163 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t) 1164 1164 { 1165 1165 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1166 1166 return DijkstraWizard<DefDistMapBase<T> >(*this); 1167 1167 } 1168 1168 1169 1169 /// Sets the source node, from which the Dijkstra algorithm runs. 1170 1170 1171 1171 /// Sets the source node, from which the Dijkstra algorithm runs. 1172 1172 /// \param s is the source node. 1173 DijkstraWizard<TR> &source(Node s) 1173 DijkstraWizard<TR> &source(Node s) 1174 1174 { 1175 1175 Base::_source=s; 1176 1176 return *this; 1177 1177 } 1178 1178 1179 1179 }; 1180 1180 1181 1181 ///Function type interface for Dijkstra algorithm. 1182 1182
Note: See TracChangeset
for help on using the changeset viewer.