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