Changeset 877:141f9c0db4a3 in lemon-main for lemon/cost_scaling.h
- Timestamp:
- 03/06/10 15:35:12 (14 years ago)
- Branch:
- default
- Children:
- 879:38213abd2911, 931:f112c18bc304
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/cost_scaling.h
r863 r877 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-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 93 93 /// push/augment and relabel operations for finding a \ref min_cost_flow 94 94 /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation, 95 /// \ref goldberg97efficient, \ref bunnagel98efficient. 95 /// \ref goldberg97efficient, \ref bunnagel98efficient. 96 96 /// It is a highly efficient primal-dual solution method, which 97 97 /// can be viewed as the generalization of the \ref Preflow … … 190 190 /// paths from a node with excess to a node with deficit. 191 191 AUGMENT, 192 /// Partial augment operations are used, i.e. flow is moved on 192 /// Partial augment operations are used, i.e. flow is moved on 193 193 /// admissible paths started from a node with excess, but the 194 194 /// lengths of these paths are limited. This method can be viewed … … 209 209 210 210 private: 211 211 212 212 template <typename KT, typename VT> 213 213 class StaticVectorMap { … … 215 215 typedef KT Key; 216 216 typedef VT Value; 217 217 218 218 StaticVectorMap(std::vector<Value>& v) : _v(v) {} 219 219 220 220 const Value& operator[](const Key& key) const { 221 221 return _v[StaticDigraph::id(key)]; … … 225 225 return _v[StaticDigraph::id(key)]; 226 226 } 227 227 228 228 void set(const Key& key, const Value& val) { 229 229 _v[StaticDigraph::id(key)] = val; … … 284 284 IntVector _rank; 285 285 int _max_rank; 286 286 287 287 // Data for a StaticDigraph structure 288 288 typedef std::pair<int, int> IntPair; … … 292 292 LargeCostArcMap _cost_map; 293 293 LargeCostNodeMap _pi_map; 294 294 295 295 public: 296 296 297 297 /// \brief Constant for infinite upper bounds (capacities). 298 298 /// … … 349 349 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, 350 350 "The cost type of CostScaling must be signed"); 351 351 352 352 // Reset data structures 353 353 reset(); … … 465 465 return *this; 466 466 } 467 467 468 468 /// @} 469 469 … … 567 567 _scost[j] = 0; 568 568 _scost[_reverse[j]] = 0; 569 } 569 } 570 570 _have_lower = false; 571 571 return *this; … … 602 602 _scost.resize(_res_arc_num); 603 603 _supply.resize(_res_node_num); 604 604 605 605 _res_cap.resize(_res_arc_num); 606 606 _cost.resize(_res_arc_num); … … 650 650 _reverse[bi] = fi; 651 651 } 652 652 653 653 // Reset parameters 654 654 resetParams(); … … 759 759 } 760 760 if (_sum_supply > 0) return INFEASIBLE; 761 761 762 762 763 763 // Initialize vectors … … 766 766 _excess[i] = _supply[i]; 767 767 } 768 768 769 769 // Remove infinite upper bounds and check negative arcs 770 770 const Value MAX = std::numeric_limits<Value>::max(); … … 886 886 } 887 887 } 888 888 889 889 return OPTIMAL; 890 890 } … … 895 895 const int MAX_PATH_LENGTH = 4; 896 896 897 // Initialize data structures for buckets 897 // Initialize data structures for buckets 898 898 _max_rank = _alpha * _res_node_num; 899 899 _buckets.resize(_max_rank); … … 901 901 _bucket_prev.resize(_res_node_num + 1); 902 902 _rank.resize(_res_node_num + 1); 903 903 904 904 // Execute the algorithm 905 905 switch (method) { … … 940 940 } 941 941 } 942 942 943 943 // Initialize a cost scaling phase 944 944 void initPhase() { … … 958 958 } 959 959 } 960 960 961 961 // Find active nodes (i.e. nodes with positive excess) 962 962 for (int u = 0; u != _res_node_num; ++u) { … … 969 969 } 970 970 } 971 971 972 972 // Early termination heuristic 973 973 bool earlyTermination() { … … 999 999 void globalUpdate() { 1000 1000 int bucket_end = _root + 1; 1001 1001 1002 1002 // Initialize buckets 1003 1003 for (int r = 0; r != _max_rank; ++r) { … … 1025 1025 int u = _buckets[r]; 1026 1026 _buckets[r] = _bucket_next[u]; 1027 1027 1028 1028 // Search the incomming arcs of u 1029 1029 LargeCost pi_u = _pi[u]; … … 1040 1040 if (nrc < LargeCost(_max_rank)) 1041 1041 new_rank_v = r + 1 + int(nrc); 1042 1042 1043 1043 // Change the rank of v 1044 1044 if (new_rank_v < old_rank_v) { 1045 1045 _rank[v] = new_rank_v; 1046 1046 _next_out[v] = _first_out[v]; 1047 1047 1048 1048 // Remove v from its old bucket 1049 1049 if (old_rank_v < _max_rank) { … … 1055 1055 } 1056 1056 } 1057 1057 1058 1058 // Insert v to its new bucket 1059 1059 _bucket_next[v] = _buckets[new_rank_v]; … … 1073 1073 if (total_excess <= 0) break; 1074 1074 } 1075 1075 1076 1076 // Relabel nodes 1077 1077 for (int u = 0; u != _res_node_num; ++u) { … … 1093 1093 (_res_node_num + _sup_node_num * _sup_node_num)); 1094 1094 int next_update_limit = global_update_freq; 1095 1095 1096 1096 int relabel_cnt = 0; 1097 1097 1098 1098 // Perform cost scaling phases 1099 1099 std::vector<int> path; … … 1105 1105 if (earlyTermination()) break; 1106 1106 } 1107 1107 1108 1108 // Initialize current phase 1109 1109 initPhase(); 1110 1110 1111 1111 // Perform partial augment and relabel operations 1112 1112 while (true) { … … 1197 1197 1198 1198 int relabel_cnt = 0; 1199 1199 1200 1200 // Perform cost scaling phases 1201 1201 BoolVector hyper(_res_node_num, false); … … 1208 1208 if (earlyTermination()) break; 1209 1209 } 1210 1210 1211 1211 // Initialize current phase 1212 1212 initPhase(); … … 1223 1223 last_out = _first_out[n+1]; 1224 1224 pi_n = _pi[n]; 1225 1225 1226 1226 // Perform push operations if there are admissible arcs 1227 1227 if (_excess[n] > 0) { … … 1237 1237 LargeCost pi_t = _pi[t]; 1238 1238 for (int ta = _next_out[t]; ta != last_out_t; ++ta) { 1239 if (_res_cap[ta] > 0 && 1239 if (_res_cap[ta] > 0 && 1240 1240 _cost[ta] + pi_t - _pi[_target[ta]] < 0) 1241 1241 ahead += _res_cap[ta]; … … 1288 1288 ++relabel_cnt; 1289 1289 } 1290 1290 1291 1291 // Remove nodes that are not active nor hyper 1292 1292 remove_nodes: … … 1296 1296 _active_nodes.pop_front(); 1297 1297 } 1298 1298 1299 1299 // Global update heuristic 1300 1300 if (relabel_cnt >= next_update_limit) {
Note: See TracChangeset
for help on using the changeset viewer.