Changes in lemon/bellman_ford.h [870:4db8d5ccd26b:1270:dceba191c00d] in lemon
- File:
-
- 1 edited
-
lemon/bellman_ford.h (modified) (59 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/bellman_ford.h
r870 r1270 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). … … 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 Bellman-Ford 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 Bellman-Ford 150 /// This class provides an efficient implementation of the Bellman-Ford 151 151 /// algorithm. The maximum time complexity of the algorithm is 152 /// <tt>O(n e)</tt>.152 /// <tt>O(nm)</tt>. 153 153 /// 154 154 /// The Bellman-Ford algorithm solves the single-source shortest path … … 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. … … 172 172 /// the lengths of the arcs. The default map type is 173 173 /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 174 /// \tparam TR The traits class that defines various types used by the 175 /// algorithm. By default, it is \ref BellmanFordDefaultTraits 176 /// "BellmanFordDefaultTraits<GR, LEN>". 177 /// In most cases, this parameter should not be set directly, 178 /// consider to use the named template parameters instead. 174 179 #ifdef DOXYGEN 175 180 template <typename GR, typename LEN, typename TR> … … 184 189 ///The type of the underlying digraph. 185 190 typedef typename TR::Digraph Digraph; 186 191 187 192 /// \brief The type of the arc lengths. 188 193 typedef typename TR::LengthMap::Value Value; … … 196 201 /// The type of the paths. 197 202 typedef PredMapPath<Digraph, PredMap> Path; 198 ///\brief The \ref BellmanFordDefaultOperationTraits203 ///\brief The \ref lemon::BellmanFordDefaultOperationTraits 199 204 /// "operation traits class" of the algorithm. 200 205 typedef typename TR::OperationTraits OperationTraits; 201 206 202 ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm. 207 ///\brief The \ref lemon::BellmanFordDefaultTraits "traits class" 208 ///of the algorithm. 203 209 typedef TR Traits; 204 210 … … 231 237 void create_maps() { 232 238 if(!_pred) { 233 234 239 _local_pred = true; 240 _pred = Traits::createPredMap(*_gr); 235 241 } 236 242 if(!_dist) { 237 238 243 _local_dist = true; 244 _dist = Traits::createDistMap(*_gr); 239 245 } 240 246 if(!_mask) { … … 242 248 } 243 249 } 244 250 245 251 public : 246 252 247 253 typedef BellmanFord Create; 248 254 … … 267 273 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. 268 274 template <class T> 269 struct SetPredMap 275 struct SetPredMap 270 276 : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > { 271 277 typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create; 272 278 }; 273 279 274 280 template <class T> 275 281 struct SetDistMapTraits : public Traits { … … 288 294 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. 289 295 template <class T> 290 struct SetDistMap 296 struct SetDistMap 291 297 : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > { 292 298 typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create; … … 297 303 typedef T OperationTraits; 298 304 }; 299 300 /// \brief \ref named-templ-param "Named parameter" for setting 305 306 /// \brief \ref named-templ-param "Named parameter" for setting 301 307 /// \c OperationTraits type. 302 308 /// … … 310 316 Create; 311 317 }; 312 318 313 319 ///@} 314 320 315 321 protected: 316 322 317 323 BellmanFord() {} 318 324 319 public: 320 325 public: 326 321 327 /// \brief Constructor. 322 328 /// … … 328 334 _pred(0), _local_pred(false), 329 335 _dist(0), _local_dist(false), _mask(0) {} 330 336 331 337 ///Destructor. 332 338 ~BellmanFord() { … … 355 361 BellmanFord &predMap(PredMap &map) { 356 362 if(_local_pred) { 357 358 363 delete _pred; 364 _local_pred=false; 359 365 } 360 366 _pred = ↦ … … 373 379 BellmanFord &distMap(DistMap &map) { 374 380 if(_local_dist) { 375 376 381 delete _dist; 382 _local_dist=false; 377 383 } 378 384 _dist = ↦ … … 392 398 393 399 /// \brief Initializes the internal data structures. 394 /// 400 /// 395 401 /// Initializes the internal data structures. The optional parameter 396 402 /// is the initial distance of each node. … … 398 404 create_maps(); 399 405 for (NodeIt it(*_gr); it != INVALID; ++it) { 400 401 406 _pred->set(it, INVALID); 407 _dist->set(it, value); 402 408 } 403 409 _process.clear(); 404 410 if (OperationTraits::less(value, OperationTraits::infinity())) { 405 406 407 408 411 for (NodeIt it(*_gr); it != INVALID; ++it) { 412 _process.push_back(it); 413 _mask->set(it, true); 414 } 409 415 } else { 410 411 412 413 } 414 } 415 416 for (NodeIt it(*_gr); it != INVALID; ++it) { 417 _mask->set(it, false); 418 } 419 } 420 } 421 416 422 /// \brief Adds a new source node. 417 423 /// … … 421 427 _dist->set(source, dst); 422 428 if (!(*_mask)[source]) { 423 424 429 _process.push_back(source); 430 _mask->set(source, true); 425 431 } 426 432 } … … 447 453 bool processNextRound() { 448 454 for (int i = 0; i < int(_process.size()); ++i) { 449 455 _mask->set(_process[i], false); 450 456 } 451 457 std::vector<Node> nextProcess; 452 458 std::vector<Value> values(_process.size()); 453 459 for (int i = 0; i < int(_process.size()); ++i) { 454 460 values[i] = (*_dist)[_process[i]]; 455 461 } 456 462 for (int i = 0; i < int(_process.size()); ++i) { 457 458 459 460 461 462 463 464 465 466 467 } 468 463 for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) { 464 Node target = _gr->target(it); 465 Value relaxed = OperationTraits::plus(values[i], (*_length)[it]); 466 if (OperationTraits::less(relaxed, (*_dist)[target])) { 467 _pred->set(target, it); 468 _dist->set(target, relaxed); 469 if (!(*_mask)[target]) { 470 _mask->set(target, true); 471 nextProcess.push_back(target); 472 } 473 } 474 } 469 475 } 470 476 _process.swap(nextProcess); … … 488 494 bool processNextWeakRound() { 489 495 for (int i = 0; i < int(_process.size()); ++i) { 490 496 _mask->set(_process[i], false); 491 497 } 492 498 std::vector<Node> nextProcess; 493 499 for (int i = 0; i < int(_process.size()); ++i) { 494 495 496 Value relaxed = 497 498 499 500 501 502 503 504 505 } 506 500 for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) { 501 Node target = _gr->target(it); 502 Value relaxed = 503 OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]); 504 if (OperationTraits::less(relaxed, (*_dist)[target])) { 505 _pred->set(target, it); 506 _dist->set(target, relaxed); 507 if (!(*_mask)[target]) { 508 _mask->set(target, true); 509 nextProcess.push_back(target); 510 } 511 } 512 } 507 513 } 508 514 _process.swap(nextProcess); … … 526 532 int num = countNodes(*_gr) - 1; 527 533 for (int i = 0; i < num; ++i) { 528 534 if (processNextWeakRound()) break; 529 535 } 530 536 } … … 538 544 /// if the digraph contains cycles with negative total length. 539 545 /// 540 /// The algorithm computes 546 /// The algorithm computes 541 547 /// - the shortest path tree (forest), 542 548 /// - the distance of each node from the root(s). 543 /// 549 /// 544 550 /// \return \c false if there is a negative cycle in the digraph. 545 551 /// 546 552 /// \pre init() must be called and at least one root node should be 547 /// added with addSource() before using this function. 553 /// added with addSource() before using this function. 548 554 bool checkedStart() { 549 555 int num = countNodes(*_gr); 550 556 for (int i = 0; i < num; ++i) { 551 557 if (processNextWeakRound()) return true; 552 558 } 553 559 return _process.empty(); … … 573 579 /// 574 580 /// \pre init() must be called and at least one root node should be 575 /// added with addSource() before using this function. 581 /// added with addSource() before using this function. 576 582 void limitedStart(int num) { 577 583 for (int i = 0; i < num; ++i) { 578 579 } 580 } 581 584 if (processNextRound()) break; 585 } 586 } 587 582 588 /// \brief Runs the algorithm from the given root node. 583 /// 589 /// 584 590 /// This method runs the Bellman-Ford algorithm from the given root 585 591 /// node \c s in order to compute the shortest path to each node. … … 600 606 start(); 601 607 } 602 608 603 609 /// \brief Runs the algorithm from the given root node with arc 604 610 /// number limit. 605 /// 611 /// 606 612 /// This method runs the Bellman-Ford algorithm from the given root 607 613 /// node \c s in order to compute the shortest path distance for each … … 629 635 limitedStart(num); 630 636 } 631 637 632 638 ///@} 633 639 … … 644 650 /// 645 651 /// Constructor for getting the active nodes of the given BellmanFord 646 /// instance. 652 /// instance. 647 653 ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm) 648 654 { … … 658 664 /// 659 665 /// Conversion to \c Node. 660 operator Node() const { 666 operator Node() const { 661 667 return _index >= 0 ? _algorithm->_process[_index] : INVALID; 662 668 } … … 667 673 ActiveIt& operator++() { 668 674 --_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 675 return *this; 676 } 677 678 bool operator==(const ActiveIt& it) const { 679 return static_cast<Node>(*this) == static_cast<Node>(it); 680 } 681 bool operator!=(const ActiveIt& it) const { 682 return static_cast<Node>(*this) != static_cast<Node>(it); 683 } 684 bool operator<(const ActiveIt& it) const { 685 return static_cast<Node>(*this) < static_cast<Node>(it); 686 } 687 682 688 private: 683 689 const BellmanFord* _algorithm; 684 690 int _index; 685 691 }; 686 692 687 693 /// \name Query Functions 688 694 /// The result of the Bellman-Ford algorithm can be obtained using these 689 695 /// functions.\n 690 696 /// Either \ref run() or \ref init() should be called before using them. 691 697 692 698 ///@{ 693 699 694 700 /// \brief The shortest path to the given node. 695 /// 701 /// 696 702 /// Gives back the shortest path to the given node from the root(s). 697 703 /// … … 704 710 return Path(*_gr, *_pred, t); 705 711 } 706 712 707 713 /// \brief The distance of the given node from the root(s). 708 714 /// … … 744 750 /// \pre Either \ref run() or \ref init() must be called before 745 751 /// using this function. 746 Node predNode(Node v) const { 747 return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); 748 } 749 752 Node predNode(Node v) const { 753 return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]); 754 } 755 750 756 /// \brief Returns a const reference to the node map that stores the 751 757 /// distances of the nodes. … … 757 763 /// using this function. 758 764 const DistMap &distMap() const { return *_dist;} 759 765 760 766 /// \brief Returns a const reference to the node map that stores the 761 767 /// predecessor arcs. … … 767 773 /// using this function. 768 774 const PredMap &predMap() const { return *_pred; } 769 775 770 776 /// \brief Checks if a node is reached from the root(s). 771 777 /// … … 779 785 780 786 /// \brief Gives back a negative cycle. 781 /// 787 /// 782 788 /// This function gives back a directed cycle with negative total 783 789 /// length if the algorithm has already found one. … … 806 812 return cycle; 807 813 } 808 814 809 815 ///@} 810 816 }; 811 817 812 818 /// \brief Default traits class of bellmanFord() function. 813 819 /// … … 817 823 template <typename GR, typename LEN> 818 824 struct BellmanFordWizardDefaultTraits { 819 /// The type of the digraph the algorithm runs on. 825 /// The type of the digraph the algorithm runs on. 820 826 typedef GR Digraph; 821 827 … … 838 844 /// \brief The type of the map that stores the last 839 845 /// arcs of the shortest paths. 840 /// 846 /// 841 847 /// The type of the map that stores the last arcs of the shortest paths. 842 848 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept. … … 844 850 845 851 /// \brief Instantiates a \c PredMap. 846 /// 852 /// 847 853 /// This function instantiates a \ref PredMap. 848 854 /// \param g is the digraph to which we would like to define the … … 860 866 /// \brief Instantiates a \c DistMap. 861 867 /// 862 /// This function instantiates a \ref DistMap. 868 /// This function instantiates a \ref DistMap. 863 869 /// \param g is the digraph to which we would like to define the 864 870 /// \ref DistMap. … … 873 879 typedef lemon::Path<Digraph> Path; 874 880 }; 875 881 876 882 /// \brief Default traits class used by BellmanFordWizard. 877 883 /// … … 880 886 /// \tparam LEN The type of the length map. 881 887 template <typename GR, typename LEN> 882 class BellmanFordWizardBase 888 class BellmanFordWizardBase 883 889 : public BellmanFordWizardDefaultTraits<GR, LEN> { 884 890 … … 903 909 public: 904 910 /// Constructor. 905 911 906 912 /// This constructor does not require parameters, it initiates 907 913 /// all of the attributes to default values \c 0. … … 910 916 911 917 /// Constructor. 912 918 913 919 /// This constructor requires two parameters, 914 920 /// others are initiated to \c 0. 915 921 /// \param gr The digraph the algorithm runs on. 916 922 /// \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))), 923 BellmanFordWizardBase(const GR& gr, 924 const LEN& len) : 925 _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))), 926 _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))), 921 927 _pred(0), _dist(0), _path(0), _di(0) {} 922 928 923 929 }; 924 930 925 931 /// \brief Auxiliary class for the function-type interface of the 926 932 /// \ref BellmanFord "Bellman-Ford" algorithm. … … 934 940 /// This class should only be used through the \ref bellmanFord() 935 941 /// function, which makes it easier to use the algorithm. 942 /// 943 /// \tparam TR The traits class that defines various types used by the 944 /// algorithm. 936 945 template<class TR> 937 946 class BellmanFordWizard : public TR { … … 944 953 typedef typename Digraph::Arc Arc; 945 954 typedef typename Digraph::OutArcIt ArcIt; 946 955 947 956 typedef typename TR::LengthMap LengthMap; 948 957 typedef typename LengthMap::Value Value; … … 961 970 /// \param gr The digraph the algorithm runs on. 962 971 /// \param len The length map. 963 BellmanFordWizard(const Digraph& gr, const LengthMap& len) 972 BellmanFordWizard(const Digraph& gr, const LengthMap& len) 964 973 : TR(gr, len) {} 965 974 … … 970 979 971 980 /// \brief Runs the Bellman-Ford algorithm from the given source node. 972 /// 981 /// 973 982 /// This method runs the Bellman-Ford algorithm from the given source 974 983 /// node in order to compute the shortest path to each node. 975 984 void run(Node s) { 976 BellmanFord<Digraph,LengthMap,TR> 977 bf(*reinterpret_cast<const Digraph*>(Base::_graph), 985 BellmanFord<Digraph,LengthMap,TR> 986 bf(*reinterpret_cast<const Digraph*>(Base::_graph), 978 987 *reinterpret_cast<const LengthMap*>(Base::_length)); 979 988 if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); … … 1010 1019 SetPredMapBase(const TR &b) : TR(b) {} 1011 1020 }; 1012 1021 1013 1022 /// \brief \ref named-templ-param "Named parameter" for setting 1014 1023 /// the predecessor map. … … 1021 1030 return BellmanFordWizard<SetPredMapBase<T> >(*this); 1022 1031 } 1023 1032 1024 1033 template<class T> 1025 1034 struct SetDistMapBase : public Base { … … 1028 1037 SetDistMapBase(const TR &b) : TR(b) {} 1029 1038 }; 1030 1039 1031 1040 /// \brief \ref named-templ-param "Named parameter" for setting 1032 1041 /// the distance map. … … 1069 1078 return *this; 1070 1079 } 1071 1080 1072 1081 }; 1073 1082 1074 1083 /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford" 1075 1084 /// algorithm. … … 1079 1088 /// algorithm. 1080 1089 /// 1081 /// This function also has several \ref named-templ-func-param 1082 /// "named parameters", they are declared as the members of class 1090 /// This function also has several \ref named-templ-func-param 1091 /// "named parameters", they are declared as the members of class 1083 1092 /// \ref BellmanFordWizard. 1084 1093 /// The following examples show how to use these parameters. … … 1097 1106 BellmanFordWizard<BellmanFordWizardBase<GR,LEN> > 1098 1107 bellmanFord(const GR& digraph, 1099 1108 const LEN& length) 1100 1109 { 1101 1110 return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);
Note: See TracChangeset
for help on using the changeset viewer.
