Changeset 960:b89e46862dc2 in lemon for lemon
 Timestamp:
 03/18/10 14:17:03 (10 years ago)
 Branch:
 default
 Parents:
 959:38213abd2911 (diff), 958:d6052a9c4e8d (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.  Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/bellman_ford.h
r958 r960 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 * Copyright (C) 200320 085 * Copyright (C) 20032010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 36 36 37 37 /// \brief Default OperationTraits for the BellmanFord algorithm class. 38 /// 38 /// 39 39 /// This operation traits class defines all computational operations 40 40 /// and constants that are used in the BellmanFord algorithm. … … 43 43 /// value is used as extremal infinity value. 44 44 template < 45 typename V, 45 typename V, 46 46 bool has_inf = std::numeric_limits<V>::has_infinity> 47 47 struct BellmanFordDefaultOperationTraits { … … 84 84 } 85 85 }; 86 86 87 87 /// \brief Default traits class of BellmanFord class. 88 88 /// … … 92 92 template<typename GR, typename LEN> 93 93 struct BellmanFordDefaultTraits { 94 /// The type of the digraph the algorithm runs on. 94 /// The type of the digraph the algorithm runs on. 95 95 typedef GR Digraph; 96 96 … … 110 110 /// \see BellmanFordDefaultOperationTraits 111 111 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; 112 113 /// \brief The type of the map that stores the last arcs of the 112 113 /// \brief The type of the map that stores the last arcs of the 114 114 /// shortest paths. 115 /// 115 /// 116 116 /// The type of the map that stores the last 117 117 /// arcs of the shortest paths. … … 120 120 121 121 /// \brief Instantiates a \c PredMap. 122 /// 123 /// This function instantiates a \ref PredMap. 122 /// 123 /// This function instantiates a \ref PredMap. 124 124 /// \param g is the digraph to which we would like to define the 125 125 /// \ref PredMap. … … 136 136 /// \brief Instantiates a \c DistMap. 137 137 /// 138 /// This function instantiates a \ref DistMap. 139 /// \param g is the digraph to which we would like to define the 138 /// This function instantiates a \ref DistMap. 139 /// \param g is the digraph to which we would like to define the 140 140 /// \ref DistMap. 141 141 static DistMap *createDistMap(const GR& g) { … … 144 144 145 145 }; 146 146 147 147 /// \brief %BellmanFord algorithm class. 148 148 /// 149 149 /// \ingroup shortest_path 150 /// This class provides an efficient implementation of the BellmanFord 150 /// This class provides an efficient implementation of the BellmanFord 151 151 /// algorithm. The maximum time complexity of the algorithm is 152 152 /// <tt>O(ne)</tt>. … … 159 159 /// 160 160 /// The arc lengths are passed to the algorithm using a 161 /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 161 /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 162 162 /// kind of length. The type of the length values is determined by the 163 163 /// \ref concepts::ReadMap::Value "Value" type of the length map. … … 189 189 ///The type of the underlying digraph. 190 190 typedef typename TR::Digraph Digraph; 191 191 192 192 /// \brief The type of the arc lengths. 193 193 typedef typename TR::LengthMap::Value Value; … … 236 236 void create_maps() { 237 237 if(!_pred) { 238 239 238 _local_pred = true; 239 _pred = Traits::createPredMap(*_gr); 240 240 } 241 241 if(!_dist) { 242 243 242 _local_dist = true; 243 _dist = Traits::createDistMap(*_gr); 244 244 } 245 245 if(!_mask) { … … 247 247 } 248 248 } 249 249 250 250 public : 251 251 252 252 typedef BellmanFord Create; 253 253 … … 272 272 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. 273 273 template <class T> 274 struct SetPredMap 274 struct SetPredMap 275 275 : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > { 276 276 typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create; 277 277 }; 278 278 279 279 template <class T> 280 280 struct SetDistMapTraits : public Traits { … … 293 293 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. 294 294 template <class T> 295 struct SetDistMap 295 struct SetDistMap 296 296 : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > { 297 297 typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create; … … 302 302 typedef T OperationTraits; 303 303 }; 304 305 /// \brief \ref namedtemplparam "Named parameter" for setting 304 305 /// \brief \ref namedtemplparam "Named parameter" for setting 306 306 /// \c OperationTraits type. 307 307 /// … … 315 315 Create; 316 316 }; 317 317 318 318 ///@} 319 319 320 320 protected: 321 321 322 322 BellmanFord() {} 323 323 324 public: 325 324 public: 325 326 326 /// \brief Constructor. 327 327 /// … … 333 333 _pred(0), _local_pred(false), 334 334 _dist(0), _local_dist(false), _mask(0) {} 335 335 336 336 ///Destructor. 337 337 ~BellmanFord() { … … 360 360 BellmanFord &predMap(PredMap &map) { 361 361 if(_local_pred) { 362 363 362 delete _pred; 363 _local_pred=false; 364 364 } 365 365 _pred = ↦ … … 378 378 BellmanFord &distMap(DistMap &map) { 379 379 if(_local_dist) { 380 381 380 delete _dist; 381 _local_dist=false; 382 382 } 383 383 _dist = ↦ … … 397 397 398 398 /// \brief Initializes the internal data structures. 399 /// 399 /// 400 400 /// Initializes the internal data structures. The optional parameter 401 401 /// is the initial distance of each node. … … 403 403 create_maps(); 404 404 for (NodeIt it(*_gr); it != INVALID; ++it) { 405 406 405 _pred>set(it, INVALID); 406 _dist>set(it, value); 407 407 } 408 408 _process.clear(); 409 409 if (OperationTraits::less(value, OperationTraits::infinity())) { 410 411 412 413 410 for (NodeIt it(*_gr); it != INVALID; ++it) { 411 _process.push_back(it); 412 _mask>set(it, true); 413 } 414 414 } else { 415 416 417 418 } 419 } 420 415 for (NodeIt it(*_gr); it != INVALID; ++it) { 416 _mask>set(it, false); 417 } 418 } 419 } 420 421 421 /// \brief Adds a new source node. 422 422 /// … … 426 426 _dist>set(source, dst); 427 427 if (!(*_mask)[source]) { 428 429 428 _process.push_back(source); 429 _mask>set(source, true); 430 430 } 431 431 } … … 452 452 bool processNextRound() { 453 453 for (int i = 0; i < int(_process.size()); ++i) { 454 454 _mask>set(_process[i], false); 455 455 } 456 456 std::vector<Node> nextProcess; 457 457 std::vector<Value> values(_process.size()); 458 458 for (int i = 0; i < int(_process.size()); ++i) { 459 459 values[i] = (*_dist)[_process[i]]; 460 460 } 461 461 for (int i = 0; i < int(_process.size()); ++i) { 462 463 464 465 466 467 468 469 470 471 472 } 473 462 for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) { 463 Node target = _gr>target(it); 464 Value relaxed = OperationTraits::plus(values[i], (*_length)[it]); 465 if (OperationTraits::less(relaxed, (*_dist)[target])) { 466 _pred>set(target, it); 467 _dist>set(target, relaxed); 468 if (!(*_mask)[target]) { 469 _mask>set(target, true); 470 nextProcess.push_back(target); 471 } 472 } 473 } 474 474 } 475 475 _process.swap(nextProcess); … … 493 493 bool processNextWeakRound() { 494 494 for (int i = 0; i < int(_process.size()); ++i) { 495 495 _mask>set(_process[i], false); 496 496 } 497 497 std::vector<Node> nextProcess; 498 498 for (int i = 0; i < int(_process.size()); ++i) { 499 500 501 Value relaxed = 502 503 504 505 506 507 508 509 510 } 511 499 for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) { 500 Node target = _gr>target(it); 501 Value relaxed = 502 OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]); 503 if (OperationTraits::less(relaxed, (*_dist)[target])) { 504 _pred>set(target, it); 505 _dist>set(target, relaxed); 506 if (!(*_mask)[target]) { 507 _mask>set(target, true); 508 nextProcess.push_back(target); 509 } 510 } 511 } 512 512 } 513 513 _process.swap(nextProcess); … … 531 531 int num = countNodes(*_gr)  1; 532 532 for (int i = 0; i < num; ++i) { 533 533 if (processNextWeakRound()) break; 534 534 } 535 535 } … … 543 543 /// if the digraph contains cycles with negative total length. 544 544 /// 545 /// The algorithm computes 545 /// The algorithm computes 546 546 ///  the shortest path tree (forest), 547 547 ///  the distance of each node from the root(s). 548 /// 548 /// 549 549 /// \return \c false if there is a negative cycle in the digraph. 550 550 /// 551 551 /// \pre init() must be called and at least one root node should be 552 /// added with addSource() before using this function. 552 /// added with addSource() before using this function. 553 553 bool checkedStart() { 554 554 int num = countNodes(*_gr); 555 555 for (int i = 0; i < num; ++i) { 556 556 if (processNextWeakRound()) return true; 557 557 } 558 558 return _process.empty(); … … 578 578 /// 579 579 /// \pre init() must be called and at least one root node should be 580 /// added with addSource() before using this function. 580 /// added with addSource() before using this function. 581 581 void limitedStart(int num) { 582 582 for (int i = 0; i < num; ++i) { 583 584 } 585 } 586 583 if (processNextRound()) break; 584 } 585 } 586 587 587 /// \brief Runs the algorithm from the given root node. 588 /// 588 /// 589 589 /// This method runs the BellmanFord algorithm from the given root 590 590 /// node \c s in order to compute the shortest path to each node. … … 605 605 start(); 606 606 } 607 607 608 608 /// \brief Runs the algorithm from the given root node with arc 609 609 /// number limit. 610 /// 610 /// 611 611 /// This method runs the BellmanFord algorithm from the given root 612 612 /// node \c s in order to compute the shortest path distance for each … … 634 634 limitedStart(num); 635 635 } 636 636 637 637 ///@} 638 638 … … 649 649 /// 650 650 /// Constructor for getting the active nodes of the given BellmanFord 651 /// instance. 651 /// instance. 652 652 ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm) 653 653 { … … 663 663 /// 664 664 /// Conversion to \c Node. 665 operator Node() const { 665 operator Node() const { 666 666 return _index >= 0 ? _algorithm>_process[_index] : INVALID; 667 667 } … … 672 672 ActiveIt& operator++() { 673 673 _index; 674 return *this; 675 } 676 677 bool operator==(const ActiveIt& it) const { 678 return static_cast<Node>(*this) == static_cast<Node>(it); 679 } 680 bool operator!=(const ActiveIt& it) const { 681 return static_cast<Node>(*this) != static_cast<Node>(it); 682 } 683 bool operator<(const ActiveIt& it) const { 684 return static_cast<Node>(*this) < static_cast<Node>(it); 685 } 686 674 return *this; 675 } 676 677 bool operator==(const ActiveIt& it) const { 678 return static_cast<Node>(*this) == static_cast<Node>(it); 679 } 680 bool operator!=(const ActiveIt& it) const { 681 return static_cast<Node>(*this) != static_cast<Node>(it); 682 } 683 bool operator<(const ActiveIt& it) const { 684 return static_cast<Node>(*this) < static_cast<Node>(it); 685 } 686 687 687 private: 688 688 const BellmanFord* _algorithm; 689 689 int _index; 690 690 }; 691 691 692 692 /// \name Query Functions 693 693 /// The result of the BellmanFord algorithm can be obtained using these 694 694 /// functions.\n 695 695 /// Either \ref run() or \ref init() should be called before using them. 696 696 697 697 ///@{ 698 698 699 699 /// \brief The shortest path to the given node. 700 /// 700 /// 701 701 /// Gives back the shortest path to the given node from the root(s). 702 702 /// … … 709 709 return Path(*_gr, *_pred, t); 710 710 } 711 711 712 712 /// \brief The distance of the given node from the root(s). 713 713 /// … … 749 749 /// \pre Either \ref run() or \ref init() must be called before 750 750 /// using this function. 751 Node predNode(Node v) const { 752 return (*_pred)[v] == INVALID ? INVALID : _gr>source((*_pred)[v]); 753 } 754 751 Node predNode(Node v) const { 752 return (*_pred)[v] == INVALID ? INVALID : _gr>source((*_pred)[v]); 753 } 754 755 755 /// \brief Returns a const reference to the node map that stores the 756 756 /// distances of the nodes. … … 762 762 /// using this function. 763 763 const DistMap &distMap() const { return *_dist;} 764 764 765 765 /// \brief Returns a const reference to the node map that stores the 766 766 /// predecessor arcs. … … 772 772 /// using this function. 773 773 const PredMap &predMap() const { return *_pred; } 774 774 775 775 /// \brief Checks if a node is reached from the root(s). 776 776 /// … … 784 784 785 785 /// \brief Gives back a negative cycle. 786 /// 786 /// 787 787 /// This function gives back a directed cycle with negative total 788 788 /// length if the algorithm has already found one. … … 811 811 return cycle; 812 812 } 813 813 814 814 ///@} 815 815 }; 816 816 817 817 /// \brief Default traits class of bellmanFord() function. 818 818 /// … … 822 822 template <typename GR, typename LEN> 823 823 struct BellmanFordWizardDefaultTraits { 824 /// The type of the digraph the algorithm runs on. 824 /// The type of the digraph the algorithm runs on. 825 825 typedef GR Digraph; 826 826 … … 843 843 /// \brief The type of the map that stores the last 844 844 /// arcs of the shortest paths. 845 /// 845 /// 846 846 /// The type of the map that stores the last arcs of the shortest paths. 847 847 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. … … 849 849 850 850 /// \brief Instantiates a \c PredMap. 851 /// 851 /// 852 852 /// This function instantiates a \ref PredMap. 853 853 /// \param g is the digraph to which we would like to define the … … 865 865 /// \brief Instantiates a \c DistMap. 866 866 /// 867 /// This function instantiates a \ref DistMap. 867 /// This function instantiates a \ref DistMap. 868 868 /// \param g is the digraph to which we would like to define the 869 869 /// \ref DistMap. … … 878 878 typedef lemon::Path<Digraph> Path; 879 879 }; 880 880 881 881 /// \brief Default traits class used by BellmanFordWizard. 882 882 /// … … 885 885 /// \tparam LEN The type of the length map. 886 886 template <typename GR, typename LEN> 887 class BellmanFordWizardBase 887 class BellmanFordWizardBase 888 888 : public BellmanFordWizardDefaultTraits<GR, LEN> { 889 889 … … 908 908 public: 909 909 /// Constructor. 910 910 911 911 /// This constructor does not require parameters, it initiates 912 912 /// all of the attributes to default values \c 0. … … 915 915 916 916 /// Constructor. 917 917 918 918 /// This constructor requires two parameters, 919 919 /// others are initiated to \c 0. 920 920 /// \param gr The digraph the algorithm runs on. 921 921 /// \param len The length map. 922 BellmanFordWizardBase(const GR& gr, 923 924 _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))), 925 _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))), 922 BellmanFordWizardBase(const GR& gr, 923 const LEN& len) : 924 _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))), 925 _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))), 926 926 _pred(0), _dist(0), _path(0), _di(0) {} 927 927 928 928 }; 929 929 930 930 /// \brief Auxiliary class for the functiontype interface of the 931 931 /// \ref BellmanFord "BellmanFord" algorithm. … … 952 952 typedef typename Digraph::Arc Arc; 953 953 typedef typename Digraph::OutArcIt ArcIt; 954 954 955 955 typedef typename TR::LengthMap LengthMap; 956 956 typedef typename LengthMap::Value Value; … … 969 969 /// \param gr The digraph the algorithm runs on. 970 970 /// \param len The length map. 971 BellmanFordWizard(const Digraph& gr, const LengthMap& len) 971 BellmanFordWizard(const Digraph& gr, const LengthMap& len) 972 972 : TR(gr, len) {} 973 973 … … 978 978 979 979 /// \brief Runs the BellmanFord algorithm from the given source node. 980 /// 980 /// 981 981 /// This method runs the BellmanFord algorithm from the given source 982 982 /// node in order to compute the shortest path to each node. 983 983 void run(Node s) { 984 BellmanFord<Digraph,LengthMap,TR> 985 bf(*reinterpret_cast<const Digraph*>(Base::_graph), 984 BellmanFord<Digraph,LengthMap,TR> 985 bf(*reinterpret_cast<const Digraph*>(Base::_graph), 986 986 *reinterpret_cast<const LengthMap*>(Base::_length)); 987 987 if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); … … 1018 1018 SetPredMapBase(const TR &b) : TR(b) {} 1019 1019 }; 1020 1020 1021 1021 /// \brief \ref namedtemplparam "Named parameter" for setting 1022 1022 /// the predecessor map. … … 1029 1029 return BellmanFordWizard<SetPredMapBase<T> >(*this); 1030 1030 } 1031 1031 1032 1032 template<class T> 1033 1033 struct SetDistMapBase : public Base { … … 1036 1036 SetDistMapBase(const TR &b) : TR(b) {} 1037 1037 }; 1038 1038 1039 1039 /// \brief \ref namedtemplparam "Named parameter" for setting 1040 1040 /// the distance map. … … 1077 1077 return *this; 1078 1078 } 1079 1079 1080 1080 }; 1081 1081 1082 1082 /// \brief Function type interface for the \ref BellmanFord "BellmanFord" 1083 1083 /// algorithm. … … 1087 1087 /// algorithm. 1088 1088 /// 1089 /// This function also has several \ref namedtemplfuncparam 1090 /// "named parameters", they are declared as the members of class 1089 /// This function also has several \ref namedtemplfuncparam 1090 /// "named parameters", they are declared as the members of class 1091 1091 /// \ref BellmanFordWizard. 1092 1092 /// The following examples show how to use these parameters. … … 1105 1105 BellmanFordWizard<BellmanFordWizardBase<GR,LEN> > 1106 1106 bellmanFord(const GR& digraph, 1107 1107 const LEN& length) 1108 1108 { 1109 1109 return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length); 
lemon/bellman_ford.h
r956 r960 29 29 #include <lemon/error.h> 30 30 #include <lemon/maps.h> 31 #include <lemon/tolerance.h>32 31 #include <lemon/path.h> 33 32 … … 36 35 namespace lemon { 37 36 38 /// \brief Default operation traits for the BellmanFord algorithm class.37 /// \brief Default OperationTraits for the BellmanFord algorithm class. 39 38 /// 40 39 /// This operation traits class defines all computational operations … … 43 42 /// If the numeric type does not have infinity value, then the maximum 44 43 /// value is used as extremal infinity value. 45 ///46 /// \see BellmanFordToleranceOperationTraits47 44 template < 48 45 typename V, 49 46 bool has_inf = std::numeric_limits<V>::has_infinity> 50 47 struct BellmanFordDefaultOperationTraits { 51 /// \ brief Value type for the algorithm.48 /// \e 52 49 typedef V Value; 53 50 /// \brief Gives back the zero value of the type. … … 85 82 static bool less(const Value& left, const Value& right) { 86 83 return left < right; 87 }88 };89 90 /// \brief Operation traits for the BellmanFord algorithm class91 /// using tolerance.92 ///93 /// This operation traits class defines all computational operations94 /// and constants that are used in the BellmanFord algorithm.95 /// The only difference between this implementation and96 /// \ref BellmanFordDefaultOperationTraits is that this class uses97 /// the \ref Tolerance "tolerance technique" in its \ref less()98 /// function.99 ///100 /// \tparam V The value type.101 /// \tparam eps The epsilon value for the \ref less() function.102 /// By default, it is the epsilon value used by \ref Tolerance103 /// "Tolerance<V>".104 ///105 /// \see BellmanFordDefaultOperationTraits106 #ifdef DOXYGEN107 template <typename V, V eps>108 #else109 template <110 typename V,111 V eps = Tolerance<V>::def_epsilon>112 #endif113 struct BellmanFordToleranceOperationTraits {114 /// \brief Value type for the algorithm.115 typedef V Value;116 /// \brief Gives back the zero value of the type.117 static Value zero() {118 return static_cast<Value>(0);119 }120 /// \brief Gives back the positive infinity value of the type.121 static Value infinity() {122 return std::numeric_limits<Value>::infinity();123 }124 /// \brief Gives back the sum of the given two elements.125 static Value plus(const Value& left, const Value& right) {126 return left + right;127 }128 /// \brief Gives back \c true only if the first value is less than129 /// the second.130 static bool less(const Value& left, const Value& right) {131 return left + eps < right;132 84 } 133 85 }; … … 156 108 /// It defines the used operations and the infinity value for the 157 109 /// given \c Value type. 158 /// \see BellmanFordDefaultOperationTraits, 159 /// BellmanFordToleranceOperationTraits 110 /// \see BellmanFordDefaultOperationTraits 160 111 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; 161 112 … … 887 838 /// It defines the used operations and the infinity value for the 888 839 /// given \c Value type. 889 /// \see BellmanFordDefaultOperationTraits, 890 /// BellmanFordToleranceOperationTraits 840 /// \see BellmanFordDefaultOperationTraits 891 841 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; 892 842
Note: See TracChangeset
for help on using the changeset viewer.