Changeset 810:3b53491bf643 in lemonmain for lemon/cost_scaling.h
 Timestamp:
 11/12/09 23:34:35 (11 years ago)
 Branch:
 default
 Phase:
 public
 Rebase:
 31306464373530663736663634663865303635326136663934636335303533383063623764626530
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/cost_scaling.h
r809 r810 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.