Changeset 876:3b53491bf643 in lemon for lemon
 Timestamp:
 11/12/09 23:34:35 (13 years ago)
 Branch:
 default
 Phase:
 public
 Rebase:
 31306464373530663736663634663865303635326136663934636335303533383063623764626530
 Location:
 lemon
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/capacity_scaling.h
r873 r876 174 174 175 175 Value _delta; 176 int _ phase_num;176 int _factor; 177 177 IntVector _pred; 178 178 … … 514 514 /// have to be set again. See \ref reset() for examples. 515 515 /// However the underlying digraph must not be modified after this 516 /// class have been constructed, since it copies the digraph. 517 /// 518 /// \param scaling Enable or disable capacity scaling. 519 /// If the maximum upper bound and/or the amount of total supply 520 /// is rather small, the algorithm could be slightly faster without 521 /// scaling. 516 /// class have been constructed, since it copies and extends the graph. 517 /// 518 /// \param factor The capacity scaling factor. It must be larger than 519 /// one to use scaling. If it is less or equal to one, then scaling 520 /// will be disabled. 522 521 /// 523 522 /// \return \c INFEASIBLE if no feasible flow exists, … … 532 531 /// 533 532 /// \see ProblemType 534 ProblemType run(bool scaling = true) { 535 ProblemType pt = init(scaling); 533 ProblemType run(int factor = 4) { 534 _factor = factor; 535 ProblemType pt = init(); 536 536 if (pt != OPTIMAL) return pt; 537 537 return start(); … … 547 547 /// used, all the parameters given before are kept for the next 548 548 /// \ref run() call. 549 /// However the underlying digraph must not be modified after this549 /// However, the underlying digraph must not be modified after this 550 550 /// class have been constructed, since it copies and extends the graph. 551 551 /// … … 678 678 679 679 // Initialize the algorithm 680 ProblemType init( bool scaling) {680 ProblemType init() { 681 681 if (_node_num == 0) return INFEASIBLE; 682 682 … … 759 759 760 760 // Initialize delta value 761 if ( scaling) {761 if (_factor > 1) { 762 762 // With scaling 763 763 Value max_sup = 0, max_dem = 0; … … 771 771 } 772 772 max_sup = std::min(std::min(max_sup, max_dem), max_cap); 773 _phase_num = 0; 774 for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2) 775 ++_phase_num; 773 for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2) ; 776 774 } else { 777 775 // Without scaling … … 812 810 // Perform capacity scaling phases 813 811 int s, t; 814 int phase_cnt = 0;815 int factor = 4;816 812 ResidualDijkstra _dijkstra(*this); 817 813 while (true) { … … 888 884 889 885 if (_delta == 1) break; 890 if (++phase_cnt == _phase_num / 4) factor = 2; 891 _delta = _delta <= factor ? 1 : _delta / factor; 886 _delta = _delta <= _factor ? 1 : _delta / _factor; 892 887 } 893 888 
lemon/cost_scaling.h
r875 r876 111 111 /// \warning This algorithm does not support negative costs for such 112 112 /// arcs that have infinite upper bound. 113 /// 114 /// \note %CostScaling provides three different internal methods, 115 /// from which the most efficient one is used by default. 116 /// For more information, see \ref Method. 113 117 #ifdef DOXYGEN 114 118 template <typename GR, typename V, typename C, typename TR> … … 160 164 }; 161 165 166 /// \brief Constants for selecting the internal method. 167 /// 168 /// Enum type containing constants for selecting the internal method 169 /// for the \ref run() function. 170 /// 171 /// \ref CostScaling provides three internal methods that differ mainly 172 /// in their base operations, which are used in conjunction with the 173 /// relabel operation. 174 /// By default, the so called \ref PARTIAL_AUGMENT 175 /// "Partial AugmentRelabel" method is used, which proved to be 176 /// the most efficient and the most robust on various test inputs. 177 /// However, the other methods can be selected using the \ref run() 178 /// function with the proper parameter. 179 enum Method { 180 /// Local push operations are used, i.e. flow is moved only on one 181 /// admissible arc at once. 182 PUSH, 183 /// Augment operations are used, i.e. flow is moved on admissible 184 /// paths from a node with excess to a node with deficit. 185 AUGMENT, 186 /// Partial augment operations are used, i.e. flow is moved on 187 /// admissible paths started from a node with excess, but the 188 /// lengths of these paths are limited. This method can be viewed 189 /// as a combined version of the previous two operations. 190 PARTIAL_AUGMENT 191 }; 192 162 193 private: 163 194 … … 506 537 /// \ref reset() is called, thus only the modified parameters 507 538 /// have to be set again. See \ref reset() for examples. 508 /// However the underlying digraph must not be modified after this 509 /// class have been constructed, since it copies the digraph. 510 /// 511 /// \param partial_augment By default the algorithm performs 512 /// partial augment and relabel operations in the cost scaling 513 /// phases. Set this parameter to \c false for using local push and 514 /// relabel operations instead. 539 /// However, the underlying digraph must not be modified after this 540 /// class have been constructed, since it copies and extends the graph. 541 /// 542 /// \param method The internal method that will be used in the 543 /// algorithm. For more information, see \ref Method. 544 /// \param factor The cost scaling factor. It must be larger than one. 515 545 /// 516 546 /// \return \c INFEASIBLE if no feasible flow exists, … … 524 554 /// these cases. 525 555 /// 526 /// \see ProblemType 527 ProblemType run(bool partial_augment = true) { 556 /// \see ProblemType, Method 557 ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) { 558 _alpha = factor; 528 559 ProblemType pt = init(); 529 560 if (pt != OPTIMAL) return pt; 530 start( partial_augment);561 start(method); 531 562 return OPTIMAL; 532 563 } … … 681 712 ProblemType init() { 682 713 if (_res_node_num == 0) return INFEASIBLE; 683 684 // Scaling factor685 _alpha = 8;686 714 687 715 // Check the sum of supply values … … 818 846 819 847 // Execute the algorithm and transform the results 820 void start(bool partial_augment) { 848 void start(Method method) { 849 // Maximum path length for partial augment 850 const int MAX_PATH_LENGTH = 4; 851 821 852 // Execute the algorithm 822 if (partial_augment) { 823 startPartialAugment(); 824 } else { 825 startPushRelabel(); 853 switch (method) { 854 case PUSH: 855 startPush(); 856 break; 857 case AUGMENT: 858 startAugment(); 859 break; 860 case PARTIAL_AUGMENT: 861 startAugment(MAX_PATH_LENGTH); 862 break; 826 863 } 827 864 … … 852 889 } 853 890 854 /// Execute the algorithm performing partial augmentation and 855 /// relabel operations 856 void startPartialAugment() { 891 /// Execute the algorithm performing augment and relabel operations 892 void startAugment(int max_length = std::numeric_limits<int>::max()) { 857 893 // Paramters for heuristics 858 894 const int BF_HEURISTIC_EPSILON_BOUND = 1000; 859 895 const int BF_HEURISTIC_BOUND_FACTOR = 3; 860 // Maximum augment path length861 const int MAX_PATH_LENGTH = 4;862 896 863 897 // Perform cost scaling phases … … 926 960 int tip = start; 927 961 while (_excess[tip] >= 0 && 928 int(path_nodes.size()) <= MAX_PATH_LENGTH) {962 int(path_nodes.size()) <= max_length) { 929 963 int u; 930 964 LargeCost min_red_cost, rc; … … 985 1019 986 1020 /// Execute the algorithm performing push and relabel operations 987 void startPush Relabel() {1021 void startPush() { 988 1022 // Paramters for heuristics 989 1023 const int BF_HEURISTIC_EPSILON_BOUND = 1000;
Note: See TracChangeset
for help on using the changeset viewer.