Changes in lemon/bellman_ford.h [870:4db8d5ccd26b:1337:4add05447ca0] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bellman_ford.h
r870 r1337 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-2013 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 30 30 #include <lemon/maps.h> 31 31 #include <lemon/path.h> 32 #include <lemon/bits/stl_iterators.h> 32 33 33 34 #include <limits> … … 36 37 37 38 /// \brief Default OperationTraits for the BellmanFord algorithm class. 38 /// 39 /// 39 40 /// This operation traits class defines all computational operations 40 41 /// and constants that are used in the Bellman-Ford algorithm. … … 43 44 /// value is used as extremal infinity value. 44 45 template < 45 typename V, 46 typename V, 46 47 bool has_inf = std::numeric_limits<V>::has_infinity> 47 48 struct BellmanFordDefaultOperationTraits { … … 84 85 } 85 86 }; 86 87 87 88 /// \brief Default traits class of BellmanFord class. 88 89 /// … … 92 93 template<typename GR, typename LEN> 93 94 struct BellmanFordDefaultTraits { 94 /// The type of the digraph the algorithm runs on. 95 /// The type of the digraph the algorithm runs on. 95 96 typedef GR Digraph; 96 97 … … 110 111 /// \see BellmanFordDefaultOperationTraits 111 112 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; 112 113 /// \brief The type of the map that stores the last arcs of the 113 114 /// \brief The type of the map that stores the last arcs of the 114 115 /// shortest paths. 115 /// 116 /// 116 117 /// The type of the map that stores the last 117 118 /// arcs of the shortest paths. … … 120 121 121 122 /// \brief Instantiates a \c PredMap. 122 /// 123 /// This function instantiates a \ref PredMap. 123 /// 124 /// This function instantiates a \ref PredMap. 124 125 /// \param g is the digraph to which we would like to define the 125 126 /// \ref PredMap. … … 136 137 /// \brief Instantiates a \c DistMap. 137 138 /// 138 /// This function instantiates a \ref DistMap. 139 /// \param g is the digraph to which we would like to define the 139 /// This function instantiates a \ref DistMap. 140 /// \param g is the digraph to which we would like to define the 140 141 /// \ref DistMap. 141 142 static DistMap *createDistMap(const GR& g) { … … 144 145 145 146 }; 146 147 147 148 /// \brief %BellmanFord algorithm class. 148 149 /// 149 150 /// \ingroup shortest_path 150 /// This class provides an efficient implementation of the Bellman-Ford 151 /// This class provides an efficient implementation of the Bellman-Ford 151 152 /// algorithm. The maximum time complexity of the algorithm is 152 /// <tt>O(n e)</tt>.153 /// <tt>O(nm)</tt>. 153 154 /// 154 155 /// The Bellman-Ford algorithm solves the single-source shortest path … … 159 160 /// 160 161 /// The arc lengths are passed to the algorithm using a 161 /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 162 /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 162 163 /// kind of length. The type of the length values is determined by the 163 164 /// \ref concepts::ReadMap::Value "Value" type of the length map. … … 172 173 /// the lengths of the arcs. The default map type is 173 174 /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 175 /// \tparam TR The traits class that defines various types used by the 176 /// algorithm. By default, it is \ref BellmanFordDefaultTraits 177 /// "BellmanFordDefaultTraits<GR, LEN>". 178 /// In most cases, this parameter should not be set directly, 179 /// consider to use the named template parameters instead. 174 180 #ifdef DOXYGEN 175 181 template <typename GR, typename LEN, typename TR> … … 184 190 ///The type of the underlying digraph. 185 191 typedef typename TR::Digraph Digraph; 186 192 187 193 /// \brief The type of the arc lengths. 188 194 typedef typename TR::LengthMap::Value Value; … … 196 202 /// The type of the paths. 197 203 typedef PredMapPath<Digraph, PredMap> Path; 198 ///\brief The \ref BellmanFordDefaultOperationTraits204 ///\brief The \ref lemon::BellmanFordDefaultOperationTraits 199 205 /// "operation traits class" of the algorithm. 200 206 typedef typename TR::OperationTraits OperationTraits; 201 207 202 ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm. 208 ///\brief The \ref lemon::BellmanFordDefaultTraits "traits class" 209 ///of the algorithm. 203 210 typedef TR Traits; 204 211 … … 231 238 void create_maps() { 232 239 if(!_pred) { 233 234 240 _local_pred = true; 241 _pred = Traits::createPredMap(*_gr); 235 242 } 236 243 if(!_dist) { 237 238 244 _local_dist = true; 245 _dist = Traits::createDistMap(*_gr); 239 246 } 240 247 if(!_mask) { … … 242 249 } 243 250 } 244 251 245 252 public : 246 253 247 254 typedef BellmanFord Create; 248 255 … … 267 274 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. 268 275 template <class T> 269 struct SetPredMap 276 struct SetPredMap 270 277 : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > { 271 278 typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create; 272 279 }; 273 280 274 281 template <class T> 275 282 struct SetDistMapTraits : public Traits { … … 288 295 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. 289 296 template <class T> 290 struct SetDistMap 297 struct SetDistMap 291 298 : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > { 292 299 typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create; … … 297 304 typedef T OperationTraits; 298 305 }; 299 300 /// \brief \ref named-templ-param "Named parameter" for setting 306 307 /// \brief \ref named-templ-param "Named parameter" for setting 301 308 /// \c OperationTraits type. 302 309 /// … … 310 317 Create; 311 318 }; 312 319 313 320 ///@} 314 321 315 322 protected: 316 323 317 324 BellmanFord() {} 318 325 319 public: 320 326 public: 327 321 328 /// \brief Constructor. 322 329 /// … … 328 335 _pred(0), _local_pred(false), 329 336 _dist(0), _local_dist(false), _mask(0) {} 330 337 331 338 ///Destructor. 332 339 ~BellmanFord() { … … 355 362 BellmanFord &predMap(PredMap &map) { 356 363 if(_local_pred) { 357 358 364 delete _pred; 365 _local_pred=false; 359 366 } 360 367 _pred = ↦ … … 373 380 BellmanFord &distMap(DistMap &map) { 374 381 if(_local_dist) { 375 376 382 delete _dist; 383 _local_dist=false; 377 384 } 378 385 _dist = ↦ … … 392 399 393 400 /// \brief Initializes the internal data structures. 394 /// 401 /// 395 402 /// Initializes the internal data structures. The optional parameter 396 403 /// is the initial distance of each node. … … 398 405 create_maps(); 399 406 for (NodeIt it(*_gr); it != INVALID; ++it) { 400 401 407 _pred->set(it, INVALID); 408 _dist->set(it, value); 402 409 } 403 410 _process.clear(); 404 411 if (OperationTraits::less(value, OperationTraits::infinity())) { 405 406 407 408 412 for (NodeIt it(*_gr); it != INVALID; ++it) { 413 _process.push_back(it); 414 _mask->set(it, true); 415 } 409 416 } else { 410 411 412 413 } 414 } 415 417 for (NodeIt it(*_gr); it != INVALID; ++it) { 418 _mask->set(it, false); 419 } 420 } 421 } 422 416 423 /// \brief Adds a new source node. 417 424 /// … … 421 428 _dist->set(source, dst); 422 429 if (!(*_mask)[source]) { 423 424 430 _process.push_back(source); 431 _mask->set(source, true); 425 432 } 426 433 } … … 447 454 bool processNextRound() { 448 455 for (int i = 0; i < int(_process.size()); ++i) { 449 456 _mask->set(_process[i], false); 450 457 } 451 458 std::vector<Node> nextProcess; 452 459 std::vector<Value> values(_process.size()); 453 460 for (int i = 0; i < int(_process.size()); ++i) { 454 461 values[i] = (*_dist)[_process[i]]; 455 462 } 456 463 for (int i = 0; i < int(_process.size()); ++i) { 457 458 459 460 461 462 463 464 465 466 467 } 468 464 for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) { 465 Node target = _gr->target(it); 466 Value relaxed = OperationTraits::plus(values[i], (*_length)[it]); 467 if (OperationTraits::less(relaxed, (*_dist)[target])) { 468 _pred->set(target, it); 469 _dist->set(target, relaxed); 470 if (!(*_mask)[target]) { 471 _mask->set(target, true); 472 nextProcess.push_back(target); 473 } 474 } 475 } 469 476 } 470 477 _process.swap(nextProcess); … … 488 495 bool processNextWeakRound() { 489 496 for (int i = 0; i < int(_process.size()); ++i) { 490 497 _mask->set(_process[i], false); 491 498 } 492 499 std::vector<Node> nextProcess; 493 500 for (int i = 0; i < int(_process.size()); ++i) { 494 495 496 Value relaxed = 497 498 499 500 501 502 503 504 505 } 506 501 for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) { 502 Node target = _gr->target(it); 503 Value relaxed = 504 OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]); 505 if (OperationTraits::less(relaxed, (*_dist)[target])) { 506 _pred->set(target, it); 507 _dist->set(target, relaxed); 508 if (!(*_mask)[target]) { 509 _mask->set(target, true); 510 nextProcess.push_back(target); 511 } 512 } 513 } 507 514 } 508 515 _process.swap(nextProcess); … … 526 533 int num = countNodes(*_gr) - 1; 527 534 for (int i = 0; i < num; ++i) { 528 535 if (processNextWeakRound()) break; 529 536 } 530 537 } … … 538 545 /// if the digraph contains cycles with negative total length. 539 546 /// 540 /// The algorithm computes 547 /// The algorithm computes 541 548 /// - the shortest path tree (forest), 542 549 /// - the distance of each node from the root(s). 543 /// 550 /// 544 551 /// \return \c false if there is a negative cycle in the digraph. 545 552 /// 546 553 /// \pre init() must be called and at least one root node should be 547 /// added with addSource() before using this function. 554 /// added with addSource() before using this function. 548 555 bool checkedStart() { 549 556 int num = countNodes(*_gr); 550 557 for (int i = 0; i < num; ++i) { 551 558 if (processNextWeakRound()) return true; 552 559 } 553 560 return _process.empty(); … … 573 580 /// 574 581 /// \pre init() must be called and at least one root node should be 575 /// added with addSource() before using this function. 582 /// added with addSource() before using this function. 576 583 void limitedStart(int num) { 577 584 for (int i = 0; i < num; ++i) { 578 579 } 580 } 581 585 if (processNextRound()) break; 586 } 587 } 588 582 589 /// \brief Runs the algorithm from the given root node. 583 /// 590 /// 584 591 /// This method runs the Bellman-Ford algorithm from the given root 585 592 /// node \c s in order to compute the shortest path to each node. … … 600 607 start(); 601 608 } 602 609 603 610 /// \brief Runs the algorithm from the given root node with arc 604 611 /// number limit. 605 /// 612 /// 606 613 /// This method runs the Bellman-Ford algorithm from the given root 607 614 /// node \c s in order to compute the shortest path distance for each … … 629 636 limitedStart(num); 630 637 } 631 638 632 639 ///@} 633 640 … … 644 651 /// 645 652 /// Constructor for getting the active nodes of the given BellmanFord 646 /// instance. 653 /// instance. 647 654 ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm) 648 655 { … … 658 665 /// 659 666 /// Conversion to \c Node. 660 operator Node() const { 667 operator Node() const { 661 668 return _index >= 0 ? _algorithm->_process[_index] : INVALID; 662 669 } … … 667 674 ActiveIt& operator++() { 668 675 --_index; 669 return *this; 670 } 671 672 bool operator==(const ActiveIt& it) const { 673 return static_cast<Node>(*this) == static_cast<Node>(it); 674 } 675 bool operator!=(const ActiveIt& it) const { 676 return static_cast<Node>(*this) != static_cast<Node>(it); 677 } 678 bool operator<(const ActiveIt& it) const { 679 return static_cast<Node>(*this) < static_cast<Node>(it); 680 } 681 676 return *this; 677 } 678 679 bool operator==(const ActiveIt& it) const { 680 return static_cast<Node>(*this) == static_cast<Node>(it); 681 } 682 bool operator!=(const ActiveIt& it) const { 683 return static_cast<Node>(*this) != static_cast<Node>(it); 684 } 685 bool operator<(const ActiveIt& it) const { 686 return static_cast<Node>(*this) < static_cast<Node>(it); 687 } 688 682 689 private: 683 690 const BellmanFord* _algorithm; 684 691 int _index; 685 692 }; 686 693 694 /// \brief Gets the collection of the active nodes. 695 /// 696 /// This function can be used for iterating on the active nodes of the 697 /// Bellman-Ford algorithm after the last phase. 698 /// These nodes should be checked in the next phase to 699 /// find augmenting arcs outgoing from them. 700 /// It returns a wrapped ActiveIt, which looks 701 /// like an STL container (by having begin() and end()) 702 /// which you can use in range-based for loops, STL algorithms, etc. 703 LemonRangeWrapper1<ActiveIt, BellmanFord> 704 activeNodes() const { 705 return LemonRangeWrapper1<ActiveIt, BellmanFord>(*this); 706 } 707 708 687 709 /// \name Query Functions 688 710 /// The result of the Bellman-Ford algorithm can be obtained using these 689 711 /// functions.\n 690 712 /// Either \ref run() or \ref init() should be called before using them. 691 713 692 714 ///@{ 693 715 694 716 /// \brief The shortest path to the given node. 695 /// 717 /// 696 718 /// Gives back the shortest path to the given node from the root(s). 697 719 /// … … 704 726 return Path(*_gr, *_pred, t); 705 727 } 706 728 707 729 /// \brief The distance of the given node from the root(s). 708 730 /// … … 744 766 /// \pre Either \ref run() or \ref init() must be called before 745 767 /// using this function. 746 Node predNode(Node v) const { 747 return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); 748 } 749 768 Node predNode(Node v) const { 769 return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); 770 } 771 750 772 /// \brief Returns a const reference to the node map that stores the 751 773 /// distances of the nodes. … … 757 779 /// using this function. 758 780 const DistMap &distMap() const { return *_dist;} 759 781 760 782 /// \brief Returns a const reference to the node map that stores the 761 783 /// predecessor arcs. … … 767 789 /// using this function. 768 790 const PredMap &predMap() const { return *_pred; } 769 791 770 792 /// \brief Checks if a node is reached from the root(s). 771 793 /// … … 779 801 780 802 /// \brief Gives back a negative cycle. 781 /// 803 /// 782 804 /// This function gives back a directed cycle with negative total 783 805 /// length if the algorithm has already found one. … … 806 828 return cycle; 807 829 } 808 830 809 831 ///@} 810 832 }; 811 833 812 834 /// \brief Default traits class of bellmanFord() function. 813 835 /// … … 817 839 template <typename GR, typename LEN> 818 840 struct BellmanFordWizardDefaultTraits { 819 /// The type of the digraph the algorithm runs on. 841 /// The type of the digraph the algorithm runs on. 820 842 typedef GR Digraph; 821 843 … … 838 860 /// \brief The type of the map that stores the last 839 861 /// arcs of the shortest paths. 840 /// 862 /// 841 863 /// The type of the map that stores the last arcs of the shortest paths. 842 864 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. … … 844 866 845 867 /// \brief Instantiates a \c PredMap. 846 /// 868 /// 847 869 /// This function instantiates a \ref PredMap. 848 870 /// \param g is the digraph to which we would like to define the … … 860 882 /// \brief Instantiates a \c DistMap. 861 883 /// 862 /// This function instantiates a \ref DistMap. 884 /// This function instantiates a \ref DistMap. 863 885 /// \param g is the digraph to which we would like to define the 864 886 /// \ref DistMap. … … 873 895 typedef lemon::Path<Digraph> Path; 874 896 }; 875 897 876 898 /// \brief Default traits class used by BellmanFordWizard. 877 899 /// … … 880 902 /// \tparam LEN The type of the length map. 881 903 template <typename GR, typename LEN> 882 class BellmanFordWizardBase 904 class BellmanFordWizardBase 883 905 : public BellmanFordWizardDefaultTraits<GR, LEN> { 884 906 … … 903 925 public: 904 926 /// Constructor. 905 927 906 928 /// This constructor does not require parameters, it initiates 907 929 /// all of the attributes to default values \c 0. … … 910 932 911 933 /// Constructor. 912 934 913 935 /// This constructor requires two parameters, 914 936 /// others are initiated to \c 0. 915 937 /// \param gr The digraph the algorithm runs on. 916 938 /// \param len The length map. 917 BellmanFordWizardBase(const GR& gr, 918 919 _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))), 920 _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))), 939 BellmanFordWizardBase(const GR& gr, 940 const LEN& len) : 941 _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))), 942 _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))), 921 943 _pred(0), _dist(0), _path(0), _di(0) {} 922 944 923 945 }; 924 946 925 947 /// \brief Auxiliary class for the function-type interface of the 926 948 /// \ref BellmanFord "Bellman-Ford" algorithm. … … 934 956 /// This class should only be used through the \ref bellmanFord() 935 957 /// function, which makes it easier to use the algorithm. 958 /// 959 /// \tparam TR The traits class that defines various types used by the 960 /// algorithm. 936 961 template<class TR> 937 962 class BellmanFordWizard : public TR { … … 944 969 typedef typename Digraph::Arc Arc; 945 970 typedef typename Digraph::OutArcIt ArcIt; 946 971 947 972 typedef typename TR::LengthMap LengthMap; 948 973 typedef typename LengthMap::Value Value; … … 961 986 /// \param gr The digraph the algorithm runs on. 962 987 /// \param len The length map. 963 BellmanFordWizard(const Digraph& gr, const LengthMap& len) 988 BellmanFordWizard(const Digraph& gr, const LengthMap& len) 964 989 : TR(gr, len) {} 965 990 … … 970 995 971 996 /// \brief Runs the Bellman-Ford algorithm from the given source node. 972 /// 997 /// 973 998 /// This method runs the Bellman-Ford algorithm from the given source 974 999 /// node in order to compute the shortest path to each node. 975 1000 void run(Node s) { 976 BellmanFord<Digraph,LengthMap,TR> 977 bf(*reinterpret_cast<const Digraph*>(Base::_graph), 1001 BellmanFord<Digraph,LengthMap,TR> 1002 bf(*reinterpret_cast<const Digraph*>(Base::_graph), 978 1003 *reinterpret_cast<const LengthMap*>(Base::_length)); 979 1004 if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); … … 1010 1035 SetPredMapBase(const TR &b) : TR(b) {} 1011 1036 }; 1012 1037 1013 1038 /// \brief \ref named-templ-param "Named parameter" for setting 1014 1039 /// the predecessor map. … … 1021 1046 return BellmanFordWizard<SetPredMapBase<T> >(*this); 1022 1047 } 1023 1048 1024 1049 template<class T> 1025 1050 struct SetDistMapBase : public Base { … … 1028 1053 SetDistMapBase(const TR &b) : TR(b) {} 1029 1054 }; 1030 1055 1031 1056 /// \brief \ref named-templ-param "Named parameter" for setting 1032 1057 /// the distance map. … … 1069 1094 return *this; 1070 1095 } 1071 1096 1072 1097 }; 1073 1098 1074 1099 /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford" 1075 1100 /// algorithm. … … 1079 1104 /// algorithm. 1080 1105 /// 1081 /// This function also has several \ref named-templ-func-param 1082 /// "named parameters", they are declared as the members of class 1106 /// This function also has several \ref named-templ-func-param 1107 /// "named parameters", they are declared as the members of class 1083 1108 /// \ref BellmanFordWizard. 1084 1109 /// The following examples show how to use these parameters. … … 1097 1122 BellmanFordWizard<BellmanFordWizardBase<GR,LEN> > 1098 1123 bellmanFord(const GR& digraph, 1099 1124 const LEN& length) 1100 1125 { 1101 1126 return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);
Note: See TracChangeset
for help on using the changeset viewer.