Changes in lemon/cost_scaling.h [831:cc9e0c15d747:840:2914b6f0fde0] in lemon-main
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/cost_scaling.h
r831 r840 202 202 203 203 typedef std::vector<int> IntVector; 204 typedef std::vector<char> BoolVector;205 204 typedef std::vector<Value> ValueVector; 206 205 typedef std::vector<Cost> CostVector; 207 206 typedef std::vector<LargeCost> LargeCostVector; 207 typedef std::vector<char> BoolVector; 208 // Note: vector<char> is used instead of vector<bool> for efficiency reasons 208 209 209 210 private: … … 249 250 bool _have_lower; 250 251 Value _sum_supply; 252 int _sup_node_num; 251 253 252 254 // Data structures for storing the digraph … … 277 279 int _alpha; 278 280 281 IntVector _buckets; 282 IntVector _bucket_next; 283 IntVector _bucket_prev; 284 IntVector _rank; 285 int _max_rank; 286 279 287 // Data for a StaticDigraph structure 280 288 typedef std::pair<int, int> IntPair; … … 829 837 } 830 838 839 _sup_node_num = 0; 840 for (NodeIt n(_graph); n != INVALID; ++n) { 841 if (sup[n] > 0) ++_sup_node_num; 842 } 843 831 844 // Find a feasible flow using Circulation 832 845 Circulation<Digraph, ConstMap<Arc, Value>, ValueArcMap, ValueNodeMap> … … 863 876 for (int a = _first_out[_root]; a != _res_arc_num; ++a) { 864 877 int ra = _reverse[a]; 865 _res_cap[a] = 1;878 _res_cap[a] = 0; 866 879 _res_cap[ra] = 0; 867 880 _cost[a] = 0; … … 877 890 // Maximum path length for partial augment 878 891 const int MAX_PATH_LENGTH = 4; 879 892 893 // Initialize data structures for buckets 894 _max_rank = _alpha * _res_node_num; 895 _buckets.resize(_max_rank); 896 _bucket_next.resize(_res_node_num + 1); 897 _bucket_prev.resize(_res_node_num + 1); 898 _rank.resize(_res_node_num + 1); 899 880 900 // Execute the algorithm 881 901 switch (method) { … … 916 936 } 917 937 } 938 939 // Initialize a cost scaling phase 940 void initPhase() { 941 // Saturate arcs not satisfying the optimality condition 942 for (int u = 0; u != _res_node_num; ++u) { 943 int last_out = _first_out[u+1]; 944 LargeCost pi_u = _pi[u]; 945 for (int a = _first_out[u]; a != last_out; ++a) { 946 int v = _target[a]; 947 if (_res_cap[a] > 0 && _cost[a] + pi_u - _pi[v] < 0) { 948 Value delta = _res_cap[a]; 949 _excess[u] -= delta; 950 _excess[v] += delta; 951 _res_cap[a] = 0; 952 _res_cap[_reverse[a]] += delta; 953 } 954 } 955 } 956 957 // Find active nodes (i.e. nodes with positive excess) 958 for (int u = 0; u != _res_node_num; ++u) { 959 if (_excess[u] > 0) _active_nodes.push_back(u); 960 } 961 962 // Initialize the next arcs 963 for (int u = 0; u != _res_node_num; ++u) { 964 _next_out[u] = _first_out[u]; 965 } 966 } 967 968 // Early termination heuristic 969 bool earlyTermination() { 970 const double EARLY_TERM_FACTOR = 3.0; 971 972 // Build a static residual graph 973 _arc_vec.clear(); 974 _cost_vec.clear(); 975 for (int j = 0; j != _res_arc_num; ++j) { 976 if (_res_cap[j] > 0) { 977 _arc_vec.push_back(IntPair(_source[j], _target[j])); 978 _cost_vec.push_back(_cost[j] + 1); 979 } 980 } 981 _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end()); 982 983 // Run Bellman-Ford algorithm to check if the current flow is optimal 984 BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map); 985 bf.init(0); 986 bool done = false; 987 int K = int(EARLY_TERM_FACTOR * std::sqrt(double(_res_node_num))); 988 for (int i = 0; i < K && !done; ++i) { 989 done = bf.processNextWeakRound(); 990 } 991 return done; 992 } 993 994 // Global potential update heuristic 995 void globalUpdate() { 996 int bucket_end = _root + 1; 997 998 // Initialize buckets 999 for (int r = 0; r != _max_rank; ++r) { 1000 _buckets[r] = bucket_end; 1001 } 1002 Value total_excess = 0; 1003 for (int i = 0; i != _res_node_num; ++i) { 1004 if (_excess[i] < 0) { 1005 _rank[i] = 0; 1006 _bucket_next[i] = _buckets[0]; 1007 _bucket_prev[_buckets[0]] = i; 1008 _buckets[0] = i; 1009 } else { 1010 total_excess += _excess[i]; 1011 _rank[i] = _max_rank; 1012 } 1013 } 1014 if (total_excess == 0) return; 1015 1016 // Search the buckets 1017 int r = 0; 1018 for ( ; r != _max_rank; ++r) { 1019 while (_buckets[r] != bucket_end) { 1020 // Remove the first node from the current bucket 1021 int u = _buckets[r]; 1022 _buckets[r] = _bucket_next[u]; 1023 1024 // Search the incomming arcs of u 1025 LargeCost pi_u = _pi[u]; 1026 int last_out = _first_out[u+1]; 1027 for (int a = _first_out[u]; a != last_out; ++a) { 1028 int ra = _reverse[a]; 1029 if (_res_cap[ra] > 0) { 1030 int v = _source[ra]; 1031 int old_rank_v = _rank[v]; 1032 if (r < old_rank_v) { 1033 // Compute the new rank of v 1034 LargeCost nrc = (_cost[ra] + _pi[v] - pi_u) / _epsilon; 1035 int new_rank_v = old_rank_v; 1036 if (nrc < LargeCost(_max_rank)) 1037 new_rank_v = r + 1 + int(nrc); 1038 1039 // Change the rank of v 1040 if (new_rank_v < old_rank_v) { 1041 _rank[v] = new_rank_v; 1042 _next_out[v] = _first_out[v]; 1043 1044 // Remove v from its old bucket 1045 if (old_rank_v < _max_rank) { 1046 if (_buckets[old_rank_v] == v) { 1047 _buckets[old_rank_v] = _bucket_next[v]; 1048 } else { 1049 _bucket_next[_bucket_prev[v]] = _bucket_next[v]; 1050 _bucket_prev[_bucket_next[v]] = _bucket_prev[v]; 1051 } 1052 } 1053 1054 // Insert v to its new bucket 1055 _bucket_next[v] = _buckets[new_rank_v]; 1056 _bucket_prev[_buckets[new_rank_v]] = v; 1057 _buckets[new_rank_v] = v; 1058 } 1059 } 1060 } 1061 } 1062 1063 // Finish search if there are no more active nodes 1064 if (_excess[u] > 0) { 1065 total_excess -= _excess[u]; 1066 if (total_excess <= 0) break; 1067 } 1068 } 1069 if (total_excess <= 0) break; 1070 } 1071 1072 // Relabel nodes 1073 for (int u = 0; u != _res_node_num; ++u) { 1074 int k = std::min(_rank[u], r); 1075 if (k > 0) { 1076 _pi[u] -= _epsilon * k; 1077 _next_out[u] = _first_out[u]; 1078 } 1079 } 1080 } 918 1081 919 1082 /// Execute the algorithm performing augment and relabel operations 920 1083 void startAugment(int max_length = std::numeric_limits<int>::max()) { 921 1084 // Paramters for heuristics 922 const int BF_HEURISTIC_EPSILON_BOUND = 1000; 923 const int BF_HEURISTIC_BOUND_FACTOR = 3; 924 1085 const int EARLY_TERM_EPSILON_LIMIT = 1000; 1086 const double GLOBAL_UPDATE_FACTOR = 3.0; 1087 1088 const int global_update_freq = int(GLOBAL_UPDATE_FACTOR * 1089 (_res_node_num + _sup_node_num * _sup_node_num)); 1090 int next_update_limit = global_update_freq; 1091 1092 int relabel_cnt = 0; 1093 925 1094 // Perform cost scaling phases 926 IntVector pred_arc(_res_node_num); 927 std::vector<int> path_nodes; 1095 std::vector<int> path; 928 1096 for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ? 929 1097 1 : _epsilon / _alpha ) 930 1098 { 931 // "Early Termination" heuristic: use Bellman-Ford algorithm 932 // to check if the current flow is optimal 933 if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) { 934 _arc_vec.clear(); 935 _cost_vec.clear(); 936 for (int j = 0; j != _res_arc_num; ++j) { 937 if (_res_cap[j] > 0) { 938 _arc_vec.push_back(IntPair(_source[j], _target[j])); 939 _cost_vec.push_back(_cost[j] + 1); 940 } 941 } 942 _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end()); 943 944 BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map); 945 bf.init(0); 946 bool done = false; 947 int K = int(BF_HEURISTIC_BOUND_FACTOR * sqrt(_res_node_num)); 948 for (int i = 0; i < K && !done; ++i) 949 done = bf.processNextWeakRound(); 950 if (done) break; 951 } 952 953 // Saturate arcs not satisfying the optimality condition 954 for (int a = 0; a != _res_arc_num; ++a) { 955 if (_res_cap[a] > 0 && 956 _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) { 957 Value delta = _res_cap[a]; 958 _excess[_source[a]] -= delta; 959 _excess[_target[a]] += delta; 960 _res_cap[a] = 0; 961 _res_cap[_reverse[a]] += delta; 962 } 1099 // Early termination heuristic 1100 if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) { 1101 if (earlyTermination()) break; 963 1102 } 964 1103 965 // Find active nodes (i.e. nodes with positive excess) 966 for (int u = 0; u != _res_node_num; ++u) { 967 if (_excess[u] > 0) _active_nodes.push_back(u); 968 } 969 970 // Initialize the next arcs 971 for (int u = 0; u != _res_node_num; ++u) { 972 _next_out[u] = _first_out[u]; 973 } 974 1104 // Initialize current phase 1105 initPhase(); 1106 975 1107 // Perform partial augment and relabel operations 976 1108 while (true) { … … 982 1114 if (_active_nodes.size() == 0) break; 983 1115 int start = _active_nodes.front(); 984 path_nodes.clear();985 path_nodes.push_back(start);986 1116 987 1117 // Find an augmenting path from the start node 1118 path.clear(); 988 1119 int tip = start; 989 while (_excess[tip] >= 0 && 990 int(path_nodes.size()) <= max_length) { 1120 while (_excess[tip] >= 0 && int(path.size()) < max_length) { 991 1121 int u; 992 LargeCost min_red_cost, rc; 993 int last_out = _sum_supply < 0 ? 994 _first_out[tip+1] : _first_out[tip+1] - 1; 1122 LargeCost min_red_cost, rc, pi_tip = _pi[tip]; 1123 int last_out = _first_out[tip+1]; 995 1124 for (int a = _next_out[tip]; a != last_out; ++a) { 996 if (_res_cap[a] > 0 && 997 _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) { 998 u = _target[a]; 999 pred_arc[u] = a; 1125 u = _target[a]; 1126 if (_res_cap[a] > 0 && _cost[a] + pi_tip - _pi[u] < 0) { 1127 path.push_back(a); 1000 1128 _next_out[tip] = a; 1001 1129 tip = u; 1002 path_nodes.push_back(tip);1003 1130 goto next_step; 1004 1131 } … … 1006 1133 1007 1134 // Relabel tip node 1008 min_red_cost = std::numeric_limits<LargeCost>::max() / 2; 1135 min_red_cost = std::numeric_limits<LargeCost>::max(); 1136 if (tip != start) { 1137 int ra = _reverse[path.back()]; 1138 min_red_cost = _cost[ra] + pi_tip - _pi[_target[ra]]; 1139 } 1009 1140 for (int a = _first_out[tip]; a != last_out; ++a) { 1010 rc = _cost[a] + _pi[_source[a]]- _pi[_target[a]];1141 rc = _cost[a] + pi_tip - _pi[_target[a]]; 1011 1142 if (_res_cap[a] > 0 && rc < min_red_cost) { 1012 1143 min_red_cost = rc; … … 1014 1145 } 1015 1146 _pi[tip] -= min_red_cost + _epsilon; 1016 1017 // Reset the next arc of tip1018 1147 _next_out[tip] = _first_out[tip]; 1148 ++relabel_cnt; 1019 1149 1020 1150 // Step back 1021 1151 if (tip != start) { 1022 path_nodes.pop_back();1023 tip = path_nodes.back();1152 tip = _source[path.back()]; 1153 path.pop_back(); 1024 1154 } 1025 1155 … … 1029 1159 // Augment along the found path (as much flow as possible) 1030 1160 Value delta; 1031 int u, v = path_nodes.front(), pa; 1032 for (int i = 1; i < int(path_nodes.size()); ++i) { 1161 int pa, u, v = start; 1162 for (int i = 0; i != int(path.size()); ++i) { 1163 pa = path[i]; 1033 1164 u = v; 1034 v = path_nodes[i]; 1035 pa = pred_arc[v]; 1165 v = _target[pa]; 1036 1166 delta = std::min(_res_cap[pa], _excess[u]); 1037 1167 _res_cap[pa] -= delta; … … 1042 1172 _active_nodes.push_back(v); 1043 1173 } 1174 1175 // Global update heuristic 1176 if (relabel_cnt >= next_update_limit) { 1177 globalUpdate(); 1178 next_update_limit += global_update_freq; 1179 } 1044 1180 } 1045 1181 } … … 1049 1185 void startPush() { 1050 1186 // Paramters for heuristics 1051 const int BF_HEURISTIC_EPSILON_BOUND = 1000; 1052 const int BF_HEURISTIC_BOUND_FACTOR = 3; 1053 1187 const int EARLY_TERM_EPSILON_LIMIT = 1000; 1188 const double GLOBAL_UPDATE_FACTOR = 2.0; 1189 1190 const int global_update_freq = int(GLOBAL_UPDATE_FACTOR * 1191 (_res_node_num + _sup_node_num * _sup_node_num)); 1192 int next_update_limit = global_update_freq; 1193 1194 int relabel_cnt = 0; 1195 1054 1196 // Perform cost scaling phases 1055 1197 BoolVector hyper(_res_node_num, false); 1198 LargeCostVector hyper_cost(_res_node_num); 1056 1199 for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ? 1057 1200 1 : _epsilon / _alpha ) 1058 1201 { 1059 // "Early Termination" heuristic: use Bellman-Ford algorithm 1060 // to check if the current flow is optimal 1061 if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) { 1062 _arc_vec.clear(); 1063 _cost_vec.clear(); 1064 for (int j = 0; j != _res_arc_num; ++j) { 1065 if (_res_cap[j] > 0) { 1066 _arc_vec.push_back(IntPair(_source[j], _target[j])); 1067 _cost_vec.push_back(_cost[j] + 1); 1068 } 1069 } 1070 _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end()); 1071 1072 BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map); 1073 bf.init(0); 1074 bool done = false; 1075 int K = int(BF_HEURISTIC_BOUND_FACTOR * sqrt(_res_node_num)); 1076 for (int i = 0; i < K && !done; ++i) 1077 done = bf.processNextWeakRound(); 1078 if (done) break; 1079 } 1080 1081 // Saturate arcs not satisfying the optimality condition 1082 for (int a = 0; a != _res_arc_num; ++a) { 1083 if (_res_cap[a] > 0 && 1084 _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) { 1085 Value delta = _res_cap[a]; 1086 _excess[_source[a]] -= delta; 1087 _excess[_target[a]] += delta; 1088 _res_cap[a] = 0; 1089 _res_cap[_reverse[a]] += delta; 1090 } 1091 } 1092 1093 // Find active nodes (i.e. nodes with positive excess) 1094 for (int u = 0; u != _res_node_num; ++u) { 1095 if (_excess[u] > 0) _active_nodes.push_back(u); 1096 } 1097 1098 // Initialize the next arcs 1099 for (int u = 0; u != _res_node_num; ++u) { 1100 _next_out[u] = _first_out[u]; 1101 } 1202 // Early termination heuristic 1203 if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) { 1204 if (earlyTermination()) break; 1205 } 1206 1207 // Initialize current phase 1208 initPhase(); 1102 1209 1103 1210 // Perform push and relabel operations 1104 1211 while (_active_nodes.size() > 0) { 1105 LargeCost min_red_cost, rc ;1212 LargeCost min_red_cost, rc, pi_n; 1106 1213 Value delta; 1107 1214 int n, t, a, last_out = _res_arc_num; 1108 1215 1216 next_node: 1109 1217 // Select an active node (FIFO selection) 1110 next_node:1111 1218 n = _active_nodes.front(); 1112 last_out = _ sum_supply < 0 ?1113 _first_out[n+1] : _first_out[n+1] - 1;1114 1219 last_out = _first_out[n+1]; 1220 pi_n = _pi[n]; 1221 1115 1222 // Perform push operations if there are admissible arcs 1116 1223 if (_excess[n] > 0) { 1117 1224 for (a = _next_out[n]; a != last_out; ++a) { 1118 1225 if (_res_cap[a] > 0 && 1119 _cost[a] + _pi[_source[a]]- _pi[_target[a]] < 0) {1226 _cost[a] + pi_n - _pi[_target[a]] < 0) { 1120 1227 delta = std::min(_res_cap[a], _excess[n]); 1121 1228 t = _target[a]; … … 1123 1230 // Push-look-ahead heuristic 1124 1231 Value ahead = -_excess[t]; 1125 int last_out_t = _ sum_supply < 0 ?1126 _first_out[t+1] : _first_out[t+1] - 1;1232 int last_out_t = _first_out[t+1]; 1233 LargeCost pi_t = _pi[t]; 1127 1234 for (int ta = _next_out[t]; ta != last_out_t; ++ta) { 1128 1235 if (_res_cap[ta] > 0 && 1129 _cost[ta] + _pi[_source[ta]]- _pi[_target[ta]] < 0)1236 _cost[ta] + pi_t - _pi[_target[ta]] < 0) 1130 1237 ahead += _res_cap[ta]; 1131 1238 if (ahead >= delta) break; … … 1134 1241 1135 1242 // Push flow along the arc 1136 if (ahead < delta ) {1243 if (ahead < delta && !hyper[t]) { 1137 1244 _res_cap[a] -= ahead; 1138 1245 _res_cap[_reverse[a]] += ahead; … … 1141 1248 _active_nodes.push_front(t); 1142 1249 hyper[t] = true; 1250 hyper_cost[t] = _cost[a] + pi_n - pi_t; 1143 1251 _next_out[n] = a; 1144 1252 goto next_node; … … 1163 1271 // Relabel the node if it is still active (or hyper) 1164 1272 if (_excess[n] > 0 || hyper[n]) { 1165 min_red_cost = std::numeric_limits<LargeCost>::max() / 2; 1273 min_red_cost = hyper[n] ? -hyper_cost[n] : 1274 std::numeric_limits<LargeCost>::max(); 1166 1275 for (int a = _first_out[n]; a != last_out; ++a) { 1167 rc = _cost[a] + _pi[_source[a]]- _pi[_target[a]];1276 rc = _cost[a] + pi_n - _pi[_target[a]]; 1168 1277 if (_res_cap[a] > 0 && rc < min_red_cost) { 1169 1278 min_red_cost = rc; … … 1171 1280 } 1172 1281 _pi[n] -= min_red_cost + _epsilon; 1282 _next_out[n] = _first_out[n]; 1173 1283 hyper[n] = false; 1174 1175 // Reset the next arc 1176 _next_out[n] = _first_out[n]; 1284 ++relabel_cnt; 1177 1285 } 1178 1286 … … 1184 1292 _active_nodes.pop_front(); 1185 1293 } 1294 1295 // Global update heuristic 1296 if (relabel_cnt >= next_update_limit) { 1297 globalUpdate(); 1298 for (int u = 0; u != _res_node_num; ++u) 1299 hyper[u] = false; 1300 next_update_limit += global_update_freq; 1301 } 1186 1302 } 1187 1303 }
Note: See TracChangeset
for help on using the changeset viewer.