r935:6ea176638264
Tue, 15 Mar 2011 19:16:20
[Not Reviewed]
0 comments (0 inline)
0
1
0
46
25
| ... | ... |
@@ -1105,12 +1105,11 @@ |
| 1105 | 1105 |
const int EARLY_TERM_EPSILON_LIMIT = 1000; |
| 1106 |
const double GLOBAL_UPDATE_FACTOR = 3.0; |
|
| 1107 |
|
|
| 1108 |
const |
|
| 1106 |
const double GLOBAL_UPDATE_FACTOR = 1.0; |
|
| 1107 |
const int global_update_skip = static_cast<int>(GLOBAL_UPDATE_FACTOR * |
|
| 1109 | 1108 |
(_res_node_num + _sup_node_num * _sup_node_num)); |
| 1110 |
int next_update_limit = global_update_freq; |
|
| 1111 |
|
|
| 1112 |
int |
|
| 1109 |
int next_global_update_limit = global_update_skip; |
|
| 1113 | 1110 |
|
| 1114 | 1111 |
// Perform cost scaling phases |
| 1115 |
|
|
| 1112 |
IntVector path; |
|
| 1113 |
BoolVector path_arc(_res_arc_num, false); |
|
| 1114 |
int relabel_cnt = 0; |
|
| 1116 | 1115 |
for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ? |
| ... | ... |
@@ -1137,16 +1136,26 @@ |
| 1137 | 1136 |
// Find an augmenting path from the start node |
| 1138 |
path.clear(); |
|
| 1139 | 1137 |
int tip = start; |
| 1140 |
while ( |
|
| 1138 |
while (int(path.size()) < max_length && _excess[tip] >= 0) {
|
|
| 1141 | 1139 |
int u; |
| 1142 |
LargeCost |
|
| 1140 |
LargeCost rc, min_red_cost = std::numeric_limits<LargeCost>::max(); |
|
| 1141 |
LargeCost pi_tip = _pi[tip]; |
|
| 1143 | 1142 |
int last_out = _first_out[tip+1]; |
| 1144 | 1143 |
for (int a = _next_out[tip]; a != last_out; ++a) {
|
| 1144 |
if (_res_cap[a] > 0) {
|
|
| 1145 | 1145 |
u = _target[a]; |
| 1146 |
|
|
| 1146 |
rc = _cost[a] + pi_tip - _pi[u]; |
|
| 1147 |
if (rc < 0) {
|
|
| 1147 | 1148 |
path.push_back(a); |
| 1148 | 1149 |
_next_out[tip] = a; |
| 1150 |
if (path_arc[a]) {
|
|
| 1151 |
goto augment; // a cycle is found, stop path search |
|
| 1152 |
} |
|
| 1149 | 1153 |
tip = u; |
| 1154 |
path_arc[a] = true; |
|
| 1150 | 1155 |
goto next_step; |
| 1151 | 1156 |
} |
| 1157 |
else if (rc < min_red_cost) {
|
|
| 1158 |
min_red_cost = rc; |
|
| 1159 |
} |
|
| 1160 |
} |
|
| 1152 | 1161 |
} |
| ... | ... |
@@ -1154,10 +1163,12 @@ |
| 1154 | 1163 |
// Relabel tip node |
| 1155 |
min_red_cost = std::numeric_limits<LargeCost>::max(); |
|
| 1156 | 1164 |
if (tip != start) {
|
| 1157 | 1165 |
int ra = _reverse[path.back()]; |
| 1158 |
min_red_cost = |
|
| 1166 |
min_red_cost = |
|
| 1167 |
std::min(min_red_cost, _cost[ra] + pi_tip - _pi[_target[ra]]); |
|
| 1159 | 1168 |
} |
| 1169 |
last_out = _next_out[tip]; |
|
| 1160 | 1170 |
for (int a = _first_out[tip]; a != last_out; ++a) {
|
| 1171 |
if (_res_cap[a] > 0) {
|
|
| 1161 | 1172 |
rc = _cost[a] + pi_tip - _pi[_target[a]]; |
| 1162 |
if ( |
|
| 1173 |
if (rc < min_red_cost) {
|
|
| 1163 | 1174 |
min_red_cost = rc; |
| ... | ... |
@@ -1165,2 +1176,3 @@ |
| 1165 | 1176 |
} |
| 1177 |
} |
|
| 1166 | 1178 |
_pi[tip] -= min_red_cost + _epsilon; |
| ... | ... |
@@ -1171,3 +1183,5 @@ |
| 1171 | 1183 |
if (tip != start) {
|
| 1172 |
|
|
| 1184 |
int pa = path.back(); |
|
| 1185 |
path_arc[pa] = false; |
|
| 1186 |
tip = _source[pa]; |
|
| 1173 | 1187 |
path.pop_back(); |
| ... | ... |
@@ -1179,2 +1193,3 @@ |
| 1179 | 1193 |
// Augment along the found path (as much flow as possible) |
| 1194 |
augment: |
|
| 1180 | 1195 |
Value delta; |
| ... | ... |
@@ -1185,2 +1200,3 @@ |
| 1185 | 1200 |
v = _target[pa]; |
| 1201 |
path_arc[pa] = false; |
|
| 1186 | 1202 |
delta = std::min(_res_cap[pa], _excess[u]); |
| ... | ... |
@@ -1190,13 +1206,17 @@ |
| 1190 | 1206 |
_excess[v] += delta; |
| 1191 |
if (_excess[v] > 0 && _excess[v] <= delta) |
|
| 1207 |
if (_excess[v] > 0 && _excess[v] <= delta) {
|
|
| 1192 | 1208 |
_active_nodes.push_back(v); |
| 1193 | 1209 |
} |
| 1210 |
} |
|
| 1211 |
path.clear(); |
|
| 1194 | 1212 |
|
| 1195 | 1213 |
// Global update heuristic |
| 1196 |
if (relabel_cnt >= |
|
| 1214 |
if (relabel_cnt >= next_global_update_limit) {
|
|
| 1197 | 1215 |
globalUpdate(); |
| 1198 |
|
|
| 1216 |
next_global_update_limit += global_update_skip; |
|
| 1199 | 1217 |
} |
| 1200 | 1218 |
} |
| 1219 |
|
|
| 1201 | 1220 |
} |
| 1221 |
|
|
| 1202 | 1222 |
} |
| ... | ... |
@@ -1209,7 +1229,5 @@ |
| 1209 | 1229 |
|
| 1210 |
const int |
|
| 1230 |
const int global_update_skip = static_cast<int>(GLOBAL_UPDATE_FACTOR * |
|
| 1211 | 1231 |
(_res_node_num + _sup_node_num * _sup_node_num)); |
| 1212 |
int next_update_limit = global_update_freq; |
|
| 1213 |
|
|
| 1214 |
int |
|
| 1232 |
int next_global_update_limit = global_update_skip; |
|
| 1215 | 1233 |
|
| ... | ... |
@@ -1218,2 +1236,3 @@ |
| 1218 | 1236 |
LargeCostVector hyper_cost(_res_node_num); |
| 1237 |
int relabel_cnt = 0; |
|
| 1219 | 1238 |
for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ? |
| ... | ... |
@@ -1295,4 +1314,5 @@ |
| 1295 | 1314 |
for (int a = _first_out[n]; a != last_out; ++a) {
|
| 1315 |
if (_res_cap[a] > 0) {
|
|
| 1296 | 1316 |
rc = _cost[a] + pi_n - _pi[_target[a]]; |
| 1297 |
if ( |
|
| 1317 |
if (rc < min_red_cost) {
|
|
| 1298 | 1318 |
min_red_cost = rc; |
| ... | ... |
@@ -1300,2 +1320,3 @@ |
| 1300 | 1320 |
} |
| 1321 |
} |
|
| 1301 | 1322 |
_pi[n] -= min_red_cost + _epsilon; |
| ... | ... |
@@ -1315,3 +1336,3 @@ |
| 1315 | 1336 |
// Global update heuristic |
| 1316 |
if (relabel_cnt >= |
|
| 1337 |
if (relabel_cnt >= next_global_update_limit) {
|
|
| 1317 | 1338 |
globalUpdate(); |
| ... | ... |
@@ -1319,3 +1340,3 @@ |
| 1319 | 1340 |
hyper[u] = false; |
| 1320 |
|
|
| 1341 |
next_global_update_limit += global_update_skip; |
|
| 1321 | 1342 |
} |
0 comments (0 inline)