Changeset 956:141f9c0db4a3 in lemon for lemon/bellman_ford.h
- Timestamp:
- 03/06/10 15:35:12 (14 years ago)
- Branch:
- default
- Children:
- 957:f802439d2b58, 959:38213abd2911, 1041:f112c18bc304
- Phase:
- public
- File:
-
- 1 edited
-
lemon/bellman_ford.h (modified) (56 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/bellman_ford.h
r917 r956 1 /* -*- C++-*-1 /* -*- mode: C++; indent-tabs-mode: 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) 2003-20 085 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 37 37 38 38 /// \brief Default operation traits for the BellmanFord algorithm class. 39 /// 39 /// 40 40 /// This operation traits class defines all computational operations 41 41 /// and constants that are used in the Bellman-Ford algorithm. … … 46 46 /// \see BellmanFordToleranceOperationTraits 47 47 template < 48 typename V, 48 typename V, 49 49 bool has_inf = std::numeric_limits<V>::has_infinity> 50 50 struct BellmanFordDefaultOperationTraits { … … 87 87 } 88 88 }; 89 89 90 90 /// \brief Operation traits for the BellmanFord algorithm class 91 91 /// using tolerance. … … 140 140 template<typename GR, typename LEN> 141 141 struct BellmanFordDefaultTraits { 142 /// The type of the digraph the algorithm runs on. 142 /// The type of the digraph the algorithm runs on. 143 143 typedef GR Digraph; 144 144 … … 159 159 /// BellmanFordToleranceOperationTraits 160 160 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; 161 162 /// \brief The type of the map that stores the last arcs of the 161 162 /// \brief The type of the map that stores the last arcs of the 163 163 /// shortest paths. 164 /// 164 /// 165 165 /// The type of the map that stores the last 166 166 /// arcs of the shortest paths. … … 169 169 170 170 /// \brief Instantiates a \c PredMap. 171 /// 172 /// This function instantiates a \ref PredMap. 171 /// 172 /// This function instantiates a \ref PredMap. 173 173 /// \param g is the digraph to which we would like to define the 174 174 /// \ref PredMap. … … 185 185 /// \brief Instantiates a \c DistMap. 186 186 /// 187 /// This function instantiates a \ref DistMap. 188 /// \param g is the digraph to which we would like to define the 187 /// This function instantiates a \ref DistMap. 188 /// \param g is the digraph to which we would like to define the 189 189 /// \ref DistMap. 190 190 static DistMap *createDistMap(const GR& g) { … … 193 193 194 194 }; 195 195 196 196 /// \brief %BellmanFord algorithm class. 197 197 /// 198 198 /// \ingroup shortest_path 199 /// This class provides an efficient implementation of the Bellman-Ford 199 /// This class provides an efficient implementation of the Bellman-Ford 200 200 /// algorithm. The maximum time complexity of the algorithm is 201 201 /// <tt>O(ne)</tt>. … … 208 208 /// 209 209 /// The arc lengths are passed to the algorithm using a 210 /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 210 /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 211 211 /// kind of length. The type of the length values is determined by the 212 212 /// \ref concepts::ReadMap::Value "Value" type of the length map. … … 238 238 ///The type of the underlying digraph. 239 239 typedef typename TR::Digraph Digraph; 240 240 241 241 /// \brief The type of the arc lengths. 242 242 typedef typename TR::LengthMap::Value Value; … … 285 285 void create_maps() { 286 286 if(!_pred) { 287 288 287 _local_pred = true; 288 _pred = Traits::createPredMap(*_gr); 289 289 } 290 290 if(!_dist) { 291 292 291 _local_dist = true; 292 _dist = Traits::createDistMap(*_gr); 293 293 } 294 294 if(!_mask) { … … 296 296 } 297 297 } 298 298 299 299 public : 300 300 301 301 typedef BellmanFord Create; 302 302 … … 321 321 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. 322 322 template <class T> 323 struct SetPredMap 323 struct SetPredMap 324 324 : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > { 325 325 typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create; 326 326 }; 327 327 328 328 template <class T> 329 329 struct SetDistMapTraits : public Traits { … … 342 342 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. 343 343 template <class T> 344 struct SetDistMap 344 struct SetDistMap 345 345 : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > { 346 346 typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create; … … 351 351 typedef T OperationTraits; 352 352 }; 353 354 /// \brief \ref named-templ-param "Named parameter" for setting 353 354 /// \brief \ref named-templ-param "Named parameter" for setting 355 355 /// \c OperationTraits type. 356 356 /// … … 364 364 Create; 365 365 }; 366 366 367 367 ///@} 368 368 369 369 protected: 370 370 371 371 BellmanFord() {} 372 372 373 public: 374 373 public: 374 375 375 /// \brief Constructor. 376 376 /// … … 382 382 _pred(0), _local_pred(false), 383 383 _dist(0), _local_dist(false), _mask(0) {} 384 384 385 385 ///Destructor. 386 386 ~BellmanFord() { … … 409 409 BellmanFord &predMap(PredMap &map) { 410 410 if(_local_pred) { 411 412 411 delete _pred; 412 _local_pred=false; 413 413 } 414 414 _pred = ↦ … … 427 427 BellmanFord &distMap(DistMap &map) { 428 428 if(_local_dist) { 429 430 429 delete _dist; 430 _local_dist=false; 431 431 } 432 432 _dist = ↦ … … 446 446 447 447 /// \brief Initializes the internal data structures. 448 /// 448 /// 449 449 /// Initializes the internal data structures. The optional parameter 450 450 /// is the initial distance of each node. … … 452 452 create_maps(); 453 453 for (NodeIt it(*_gr); it != INVALID; ++it) { 454 455 454 _pred->set(it, INVALID); 455 _dist->set(it, value); 456 456 } 457 457 _process.clear(); 458 458 if (OperationTraits::less(value, OperationTraits::infinity())) { 459 460 461 462 459 for (NodeIt it(*_gr); it != INVALID; ++it) { 460 _process.push_back(it); 461 _mask->set(it, true); 462 } 463 463 } else { 464 465 466 467 } 468 } 469 464 for (NodeIt it(*_gr); it != INVALID; ++it) { 465 _mask->set(it, false); 466 } 467 } 468 } 469 470 470 /// \brief Adds a new source node. 471 471 /// … … 475 475 _dist->set(source, dst); 476 476 if (!(*_mask)[source]) { 477 478 477 _process.push_back(source); 478 _mask->set(source, true); 479 479 } 480 480 } … … 501 501 bool processNextRound() { 502 502 for (int i = 0; i < int(_process.size()); ++i) { 503 503 _mask->set(_process[i], false); 504 504 } 505 505 std::vector<Node> nextProcess; 506 506 std::vector<Value> values(_process.size()); 507 507 for (int i = 0; i < int(_process.size()); ++i) { 508 508 values[i] = (*_dist)[_process[i]]; 509 509 } 510 510 for (int i = 0; i < int(_process.size()); ++i) { 511 512 513 514 515 516 517 518 519 520 521 } 522 511 for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) { 512 Node target = _gr->target(it); 513 Value relaxed = OperationTraits::plus(values[i], (*_length)[it]); 514 if (OperationTraits::less(relaxed, (*_dist)[target])) { 515 _pred->set(target, it); 516 _dist->set(target, relaxed); 517 if (!(*_mask)[target]) { 518 _mask->set(target, true); 519 nextProcess.push_back(target); 520 } 521 } 522 } 523 523 } 524 524 _process.swap(nextProcess); … … 542 542 bool processNextWeakRound() { 543 543 for (int i = 0; i < int(_process.size()); ++i) { 544 544 _mask->set(_process[i], false); 545 545 } 546 546 std::vector<Node> nextProcess; 547 547 for (int i = 0; i < int(_process.size()); ++i) { 548 549 550 Value relaxed = 551 552 553 554 555 556 557 558 559 } 560 548 for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) { 549 Node target = _gr->target(it); 550 Value relaxed = 551 OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]); 552 if (OperationTraits::less(relaxed, (*_dist)[target])) { 553 _pred->set(target, it); 554 _dist->set(target, relaxed); 555 if (!(*_mask)[target]) { 556 _mask->set(target, true); 557 nextProcess.push_back(target); 558 } 559 } 560 } 561 561 } 562 562 _process.swap(nextProcess); … … 580 580 int num = countNodes(*_gr) - 1; 581 581 for (int i = 0; i < num; ++i) { 582 582 if (processNextWeakRound()) break; 583 583 } 584 584 } … … 592 592 /// if the digraph contains cycles with negative total length. 593 593 /// 594 /// The algorithm computes 594 /// The algorithm computes 595 595 /// - the shortest path tree (forest), 596 596 /// - the distance of each node from the root(s). 597 /// 597 /// 598 598 /// \return \c false if there is a negative cycle in the digraph. 599 599 /// 600 600 /// \pre init() must be called and at least one root node should be 601 /// added with addSource() before using this function. 601 /// added with addSource() before using this function. 602 602 bool checkedStart() { 603 603 int num = countNodes(*_gr); 604 604 for (int i = 0; i < num; ++i) { 605 605 if (processNextWeakRound()) return true; 606 606 } 607 607 return _process.empty(); … … 627 627 /// 628 628 /// \pre init() must be called and at least one root node should be 629 /// added with addSource() before using this function. 629 /// added with addSource() before using this function. 630 630 void limitedStart(int num) { 631 631 for (int i = 0; i < num; ++i) { 632 633 } 634 } 635 632 if (processNextRound()) break; 633 } 634 } 635 636 636 /// \brief Runs the algorithm from the given root node. 637 /// 637 /// 638 638 /// This method runs the Bellman-Ford algorithm from the given root 639 639 /// node \c s in order to compute the shortest path to each node. … … 654 654 start(); 655 655 } 656 656 657 657 /// \brief Runs the algorithm from the given root node with arc 658 658 /// number limit. 659 /// 659 /// 660 660 /// This method runs the Bellman-Ford algorithm from the given root 661 661 /// node \c s in order to compute the shortest path distance for each … … 683 683 limitedStart(num); 684 684 } 685 685 686 686 ///@} 687 687 … … 698 698 /// 699 699 /// Constructor for getting the active nodes of the given BellmanFord 700 /// instance. 700 /// instance. 701 701 ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm) 702 702 { … … 712 712 /// 713 713 /// Conversion to \c Node. 714 operator Node() const { 714 operator Node() const { 715 715 return _index >= 0 ? _algorithm->_process[_index] : INVALID; 716 716 } … … 721 721 ActiveIt& operator++() { 722 722 --_index; 723 return *this; 724 } 725 726 bool operator==(const ActiveIt& it) const { 727 return static_cast<Node>(*this) == static_cast<Node>(it); 728 } 729 bool operator!=(const ActiveIt& it) const { 730 return static_cast<Node>(*this) != static_cast<Node>(it); 731 } 732 bool operator<(const ActiveIt& it) const { 733 return static_cast<Node>(*this) < static_cast<Node>(it); 734 } 735 723 return *this; 724 } 725 726 bool operator==(const ActiveIt& it) const { 727 return static_cast<Node>(*this) == static_cast<Node>(it); 728 } 729 bool operator!=(const ActiveIt& it) const { 730 return static_cast<Node>(*this) != static_cast<Node>(it); 731 } 732 bool operator<(const ActiveIt& it) const { 733 return static_cast<Node>(*this) < static_cast<Node>(it); 734 } 735 736 736 private: 737 737 const BellmanFord* _algorithm; 738 738 int _index; 739 739 }; 740 740 741 741 /// \name Query Functions 742 742 /// The result of the Bellman-Ford algorithm can be obtained using these 743 743 /// functions.\n 744 744 /// Either \ref run() or \ref init() should be called before using them. 745 745 746 746 ///@{ 747 747 748 748 /// \brief The shortest path to the given node. 749 /// 749 /// 750 750 /// Gives back the shortest path to the given node from the root(s). 751 751 /// … … 758 758 return Path(*_gr, *_pred, t); 759 759 } 760 760 761 761 /// \brief The distance of the given node from the root(s). 762 762 /// … … 798 798 /// \pre Either \ref run() or \ref init() must be called before 799 799 /// using this function. 800 Node predNode(Node v) const { 801 return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); 802 } 803 800 Node predNode(Node v) const { 801 return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); 802 } 803 804 804 /// \brief Returns a const reference to the node map that stores the 805 805 /// distances of the nodes. … … 811 811 /// using this function. 812 812 const DistMap &distMap() const { return *_dist;} 813 813 814 814 /// \brief Returns a const reference to the node map that stores the 815 815 /// predecessor arcs. … … 821 821 /// using this function. 822 822 const PredMap &predMap() const { return *_pred; } 823 823 824 824 /// \brief Checks if a node is reached from the root(s). 825 825 /// … … 833 833 834 834 /// \brief Gives back a negative cycle. 835 /// 835 /// 836 836 /// This function gives back a directed cycle with negative total 837 837 /// length if the algorithm has already found one. … … 860 860 return cycle; 861 861 } 862 862 863 863 ///@} 864 864 }; 865 865 866 866 /// \brief Default traits class of bellmanFord() function. 867 867 /// … … 871 871 template <typename GR, typename LEN> 872 872 struct BellmanFordWizardDefaultTraits { 873 /// The type of the digraph the algorithm runs on. 873 /// The type of the digraph the algorithm runs on. 874 874 typedef GR Digraph; 875 875 … … 893 893 /// \brief The type of the map that stores the last 894 894 /// arcs of the shortest paths. 895 /// 895 /// 896 896 /// The type of the map that stores the last arcs of the shortest paths. 897 897 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. … … 899 899 900 900 /// \brief Instantiates a \c PredMap. 901 /// 901 /// 902 902 /// This function instantiates a \ref PredMap. 903 903 /// \param g is the digraph to which we would like to define the … … 915 915 /// \brief Instantiates a \c DistMap. 916 916 /// 917 /// This function instantiates a \ref DistMap. 917 /// This function instantiates a \ref DistMap. 918 918 /// \param g is the digraph to which we would like to define the 919 919 /// \ref DistMap. … … 928 928 typedef lemon::Path<Digraph> Path; 929 929 }; 930 930 931 931 /// \brief Default traits class used by BellmanFordWizard. 932 932 /// … … 935 935 /// \tparam LEN The type of the length map. 936 936 template <typename GR, typename LEN> 937 class BellmanFordWizardBase 937 class BellmanFordWizardBase 938 938 : public BellmanFordWizardDefaultTraits<GR, LEN> { 939 939 … … 958 958 public: 959 959 /// Constructor. 960 960 961 961 /// This constructor does not require parameters, it initiates 962 962 /// all of the attributes to default values \c 0. … … 965 965 966 966 /// Constructor. 967 967 968 968 /// This constructor requires two parameters, 969 969 /// others are initiated to \c 0. 970 970 /// \param gr The digraph the algorithm runs on. 971 971 /// \param len The length map. 972 BellmanFordWizardBase(const GR& gr, 973 974 _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))), 975 _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))), 972 BellmanFordWizardBase(const GR& gr, 973 const LEN& len) : 974 _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))), 975 _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))), 976 976 _pred(0), _dist(0), _path(0), _di(0) {} 977 977 978 978 }; 979 979 980 980 /// \brief Auxiliary class for the function-type interface of the 981 981 /// \ref BellmanFord "Bellman-Ford" algorithm. … … 1002 1002 typedef typename Digraph::Arc Arc; 1003 1003 typedef typename Digraph::OutArcIt ArcIt; 1004 1004 1005 1005 typedef typename TR::LengthMap LengthMap; 1006 1006 typedef typename LengthMap::Value Value; … … 1019 1019 /// \param gr The digraph the algorithm runs on. 1020 1020 /// \param len The length map. 1021 BellmanFordWizard(const Digraph& gr, const LengthMap& len) 1021 BellmanFordWizard(const Digraph& gr, const LengthMap& len) 1022 1022 : TR(gr, len) {} 1023 1023 … … 1028 1028 1029 1029 /// \brief Runs the Bellman-Ford algorithm from the given source node. 1030 /// 1030 /// 1031 1031 /// This method runs the Bellman-Ford algorithm from the given source 1032 1032 /// node in order to compute the shortest path to each node. 1033 1033 void run(Node s) { 1034 BellmanFord<Digraph,LengthMap,TR> 1035 bf(*reinterpret_cast<const Digraph*>(Base::_graph), 1034 BellmanFord<Digraph,LengthMap,TR> 1035 bf(*reinterpret_cast<const Digraph*>(Base::_graph), 1036 1036 *reinterpret_cast<const LengthMap*>(Base::_length)); 1037 1037 if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); … … 1068 1068 SetPredMapBase(const TR &b) : TR(b) {} 1069 1069 }; 1070 1070 1071 1071 /// \brief \ref named-templ-param "Named parameter" for setting 1072 1072 /// the predecessor map. … … 1079 1079 return BellmanFordWizard<SetPredMapBase<T> >(*this); 1080 1080 } 1081 1081 1082 1082 template<class T> 1083 1083 struct SetDistMapBase : public Base { … … 1086 1086 SetDistMapBase(const TR &b) : TR(b) {} 1087 1087 }; 1088 1088 1089 1089 /// \brief \ref named-templ-param "Named parameter" for setting 1090 1090 /// the distance map. … … 1127 1127 return *this; 1128 1128 } 1129 1129 1130 1130 }; 1131 1131 1132 1132 /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford" 1133 1133 /// algorithm. … … 1137 1137 /// algorithm. 1138 1138 /// 1139 /// This function also has several \ref named-templ-func-param 1140 /// "named parameters", they are declared as the members of class 1139 /// This function also has several \ref named-templ-func-param 1140 /// "named parameters", they are declared as the members of class 1141 1141 /// \ref BellmanFordWizard. 1142 1142 /// The following examples show how to use these parameters. … … 1155 1155 BellmanFordWizard<BellmanFordWizardBase<GR,LEN> > 1156 1156 bellmanFord(const GR& digraph, 1157 1157 const LEN& length) 1158 1158 { 1159 1159 return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);
Note: See TracChangeset
for help on using the changeset viewer.
