r895:dca9eed2c375
Sun, 22 Aug 2010 23:54:10
[Not Reviewed]
0 comments (0 inline)
0
1
0
111
96
| ... | ... |
@@ -168,4 +168,5 @@ |
| 168 | 168 |
typedef std::vector<Cost> CostVector; |
| 169 |
typedef std::vector<char> BoolVector; |
|
| 170 |
// Note: vector<char> is used instead of vector<bool> for efficiency reasons |
|
| 169 |
typedef std::vector<signed char> CharVector; |
|
| 170 |
// Note: vector<signed char> is used instead of vector<ArcState> and |
|
| 171 |
// vector<ArcDirection> for efficiency reasons |
|
| 171 | 172 |
|
| ... | ... |
@@ -178,5 +179,7 @@ |
| 178 | 179 |
|
| 179 |
typedef std::vector<signed char> StateVector; |
|
| 180 |
// Note: vector<signed char> is used instead of vector<ArcState> for |
|
| 181 |
// |
|
| 180 |
// Direction constants for tree arcs |
|
| 181 |
enum ArcDirection {
|
|
| 182 |
DIR_DOWN = -1, |
|
| 183 |
DIR_UP = 1 |
|
| 184 |
}; |
|
| 182 | 185 |
|
| ... | ... |
@@ -219,5 +222,5 @@ |
| 219 | 222 |
IntVector _last_succ; |
| 223 |
CharVector _pred_dir; |
|
| 224 |
CharVector _state; |
|
| 220 | 225 |
IntVector _dirty_revs; |
| 221 |
BoolVector _forward; |
|
| 222 |
StateVector _state; |
|
| 223 | 226 |
int _root; |
| ... | ... |
@@ -226,4 +229,2 @@ |
| 226 | 229 |
int in_arc, join, u_in, v_in, u_out, v_out; |
| 227 |
int first, second, right, last; |
|
| 228 |
int stem, par_stem, new_stem; |
|
| 229 | 230 |
Value delta; |
| ... | ... |
@@ -252,3 +253,3 @@ |
| 252 | 253 |
const CostVector &_cost; |
| 253 |
const |
|
| 254 |
const CharVector &_state; |
|
| 254 | 255 |
const CostVector &_pi; |
| ... | ... |
@@ -304,3 +305,3 @@ |
| 304 | 305 |
const CostVector &_cost; |
| 305 |
const |
|
| 306 |
const CharVector &_state; |
|
| 306 | 307 |
const CostVector &_pi; |
| ... | ... |
@@ -343,3 +344,3 @@ |
| 343 | 344 |
const CostVector &_cost; |
| 344 |
const |
|
| 345 |
const CharVector &_state; |
|
| 345 | 346 |
const CostVector &_pi; |
| ... | ... |
@@ -416,3 +417,3 @@ |
| 416 | 417 |
const CostVector &_cost; |
| 417 |
const |
|
| 418 |
const CharVector &_state; |
|
| 418 | 419 |
const CostVector &_pi; |
| ... | ... |
@@ -519,3 +520,3 @@ |
| 519 | 520 |
const CostVector &_cost; |
| 520 |
const |
|
| 521 |
const CharVector &_state; |
|
| 521 | 522 |
const CostVector &_pi; |
| ... | ... |
@@ -572,7 +573,9 @@ |
| 572 | 573 |
int e; |
| 574 |
Cost c; |
|
| 573 | 575 |
for (int i = 0; i != _curr_length; ++i) {
|
| 574 | 576 |
e = _candidates[i]; |
| 575 |
_cand_cost[e] = _state[e] * |
|
| 576 |
(_cost[e] + _pi[_source[e]] - _pi[_target[e]]); |
|
| 577 |
|
|
| 577 |
c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); |
|
| 578 |
if (c < 0) {
|
|
| 579 |
_cand_cost[e] = c; |
|
| 580 |
} else {
|
|
| 578 | 581 |
_candidates[i--] = _candidates[--_curr_length]; |
| ... | ... |
@@ -586,5 +589,5 @@ |
| 586 | 589 |
for (e = _next_arc; e != _search_arc_num; ++e) {
|
| 587 |
_cand_cost[e] = _state[e] * |
|
| 588 |
(_cost[e] + _pi[_source[e]] - _pi[_target[e]]); |
|
| 589 |
|
|
| 590 |
c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); |
|
| 591 |
if (c < 0) {
|
|
| 592 |
_cand_cost[e] = c; |
|
| 590 | 593 |
_candidates[_curr_length++] = e; |
| ... | ... |
@@ -915,3 +918,3 @@ |
| 915 | 918 |
_pred.resize(all_node_num); |
| 916 |
|
|
| 919 |
_pred_dir.resize(all_node_num); |
|
| 917 | 920 |
_thread.resize(all_node_num); |
| ... | ... |
@@ -1118,3 +1121,3 @@ |
| 1118 | 1121 |
if (_supply[u] >= 0) {
|
| 1119 |
|
|
| 1122 |
_pred_dir[u] = DIR_UP; |
|
| 1120 | 1123 |
_pi[u] = 0; |
| ... | ... |
@@ -1125,3 +1128,3 @@ |
| 1125 | 1128 |
} else {
|
| 1126 |
|
|
| 1129 |
_pred_dir[u] = DIR_DOWN; |
|
| 1127 | 1130 |
_pi[u] = ART_COST; |
| ... | ... |
@@ -1145,3 +1148,3 @@ |
| 1145 | 1148 |
if (_supply[u] >= 0) {
|
| 1146 |
|
|
| 1149 |
_pred_dir[u] = DIR_UP; |
|
| 1147 | 1150 |
_pi[u] = 0; |
| ... | ... |
@@ -1155,3 +1158,3 @@ |
| 1155 | 1158 |
} else {
|
| 1156 |
|
|
| 1159 |
_pred_dir[u] = DIR_DOWN; |
|
| 1157 | 1160 |
_pi[u] = ART_COST; |
| ... | ... |
@@ -1186,3 +1189,3 @@ |
| 1186 | 1189 |
if (_supply[u] <= 0) {
|
| 1187 |
|
|
| 1190 |
_pred_dir[u] = DIR_DOWN; |
|
| 1188 | 1191 |
_pi[u] = 0; |
| ... | ... |
@@ -1196,3 +1199,3 @@ |
| 1196 | 1199 |
} else {
|
| 1197 |
|
|
| 1200 |
_pred_dir[u] = DIR_UP; |
|
| 1198 | 1201 |
_pi[u] = -ART_COST; |
| ... | ... |
@@ -1239,2 +1242,3 @@ |
| 1239 | 1242 |
// of the cycle |
| 1243 |
int first, second; |
|
| 1240 | 1244 |
if (_state[in_arc] == STATE_LOWER) {
|
| ... | ... |
@@ -1248,10 +1252,13 @@ |
| 1248 | 1252 |
int result = 0; |
| 1249 |
Value d; |
|
| 1253 |
Value c, d; |
|
| 1250 | 1254 |
int e; |
| 1251 | 1255 |
|
| 1252 |
// Search the cycle |
|
| 1256 |
// Search the cycle form the first node to the join node |
|
| 1253 | 1257 |
for (int u = first; u != join; u = _parent[u]) {
|
| 1254 | 1258 |
e = _pred[u]; |
| 1255 |
d = _forward[u] ? |
|
| 1256 |
_flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]); |
|
| 1259 |
d = _flow[e]; |
|
| 1260 |
if (_pred_dir[u] == DIR_DOWN) {
|
|
| 1261 |
c = _cap[e]; |
|
| 1262 |
d = c >= MAX ? INF : c - d; |
|
| 1263 |
} |
|
| 1257 | 1264 |
if (d < delta) {
|
| ... | ... |
@@ -1262,7 +1269,11 @@ |
| 1262 | 1269 |
} |
| 1263 |
|
|
| 1270 |
|
|
| 1271 |
// Search the cycle form the second node to the join node |
|
| 1264 | 1272 |
for (int u = second; u != join; u = _parent[u]) {
|
| 1265 | 1273 |
e = _pred[u]; |
| 1266 |
d = _forward[u] ? |
|
| 1267 |
(_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e]; |
|
| 1274 |
d = _flow[e]; |
|
| 1275 |
if (_pred_dir[u] == DIR_UP) {
|
|
| 1276 |
c = _cap[e]; |
|
| 1277 |
d = c >= MAX ? INF : c - d; |
|
| 1278 |
} |
|
| 1268 | 1279 |
if (d <= delta) {
|
| ... | ... |
@@ -1291,6 +1302,6 @@ |
| 1291 | 1302 |
for (int u = _source[in_arc]; u != join; u = _parent[u]) {
|
| 1292 |
_flow[_pred[u]] |
|
| 1303 |
_flow[_pred[u]] -= _pred_dir[u] * val; |
|
| 1293 | 1304 |
} |
| 1294 | 1305 |
for (int u = _target[in_arc]; u != join; u = _parent[u]) {
|
| 1295 |
_flow[_pred[u]] += |
|
| 1306 |
_flow[_pred[u]] += _pred_dir[u] * val; |
|
| 1296 | 1307 |
} |
| ... | ... |
@@ -1309,3 +1320,2 @@ |
| 1309 | 1320 |
void updateTreeStructure() {
|
| 1310 |
int u, w; |
|
| 1311 | 1321 |
int old_rev_thread = _rev_thread[u_out]; |
| ... | ... |
@@ -1315,12 +1325,25 @@ |
| 1315 | 1325 |
|
| 1316 |
u = _last_succ[u_in]; // the last successor of u_in |
|
| 1317 |
right = _thread[u]; // the node after it |
|
| 1326 |
// Check if u_in and u_out coincide |
|
| 1327 |
if (u_in == u_out) {
|
|
| 1328 |
// Update _parent, _pred, _pred_dir |
|
| 1329 |
_parent[u_in] = v_in; |
|
| 1330 |
_pred[u_in] = in_arc; |
|
| 1331 |
_pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN; |
|
| 1318 | 1332 |
|
| 1333 |
// Update _thread and _rev_thread |
|
| 1334 |
if (_thread[v_in] != u_out) {
|
|
| 1335 |
int after = _thread[old_last_succ]; |
|
| 1336 |
_thread[old_rev_thread] = after; |
|
| 1337 |
_rev_thread[after] = old_rev_thread; |
|
| 1338 |
after = _thread[v_in]; |
|
| 1339 |
_thread[v_in] = u_out; |
|
| 1340 |
_rev_thread[u_out] = v_in; |
|
| 1341 |
_thread[old_last_succ] = after; |
|
| 1342 |
_rev_thread[after] = old_last_succ; |
|
| 1343 |
} |
|
| 1344 |
} else {
|
|
| 1319 | 1345 |
// Handle the case when old_rev_thread equals to v_in |
| 1320 | 1346 |
// (it also means that join and v_out coincide) |
| 1321 |
if (old_rev_thread == v_in) {
|
|
| 1322 |
last = _thread[_last_succ[u_out]]; |
|
| 1323 |
} else {
|
|
| 1324 |
last = _thread[v_in]; |
|
| 1325 |
|
|
| 1347 |
int thread_continue = old_rev_thread == v_in ? |
|
| 1348 |
_thread[old_last_succ] : _thread[v_in]; |
|
| 1326 | 1349 |
|
| ... | ... |
@@ -1328,16 +1351,20 @@ |
| 1328 | 1351 |
// between u_in and u_out, whose parent have to be changed) |
| 1329 |
|
|
| 1352 |
int stem = u_in; // the current stem node |
|
| 1353 |
int par_stem = v_in; // the new parent of stem |
|
| 1354 |
int next_stem; // the next stem node |
|
| 1355 |
int last = _last_succ[u_in]; // the last successor of stem |
|
| 1356 |
int before, after = _thread[last]; |
|
| 1357 |
_thread[v_in] = u_in; |
|
| 1330 | 1358 |
_dirty_revs.clear(); |
| 1331 | 1359 |
_dirty_revs.push_back(v_in); |
| 1332 |
par_stem = v_in; |
|
| 1333 | 1360 |
while (stem != u_out) {
|
| 1334 | 1361 |
// Insert the next stem node into the thread list |
| 1335 |
new_stem = _parent[stem]; |
|
| 1336 |
_thread[u] = new_stem; |
|
| 1337 |
|
|
| 1362 |
next_stem = _parent[stem]; |
|
| 1363 |
_thread[last] = next_stem; |
|
| 1364 |
_dirty_revs.push_back(last); |
|
| 1338 | 1365 |
|
| 1339 | 1366 |
// Remove the subtree of stem from the thread list |
| 1340 |
w = _rev_thread[stem]; |
|
| 1341 |
_thread[w] = right; |
|
| 1342 |
|
|
| 1367 |
before = _rev_thread[stem]; |
|
| 1368 |
_thread[before] = after; |
|
| 1369 |
_rev_thread[after] = before; |
|
| 1343 | 1370 |
|
| ... | ... |
@@ -1346,13 +1373,13 @@ |
| 1346 | 1373 |
par_stem = stem; |
| 1347 |
stem = |
|
| 1374 |
stem = next_stem; |
|
| 1348 | 1375 |
|
| 1349 |
// Update u and right |
|
| 1350 |
u = _last_succ[stem] == _last_succ[par_stem] ? |
|
| 1376 |
// Update last and after |
|
| 1377 |
last = _last_succ[stem] == _last_succ[par_stem] ? |
|
| 1351 | 1378 |
_rev_thread[par_stem] : _last_succ[stem]; |
| 1352 |
|
|
| 1379 |
after = _thread[last]; |
|
| 1353 | 1380 |
} |
| 1354 | 1381 |
_parent[u_out] = par_stem; |
| 1355 |
_thread[u] = last; |
|
| 1356 |
_rev_thread[last] = u; |
|
| 1357 |
|
|
| 1382 |
_thread[last] = thread_continue; |
|
| 1383 |
_rev_thread[thread_continue] = last; |
|
| 1384 |
_last_succ[u_out] = last; |
|
| 1358 | 1385 |
|
| ... | ... |
@@ -1360,6 +1387,5 @@ |
| 1360 | 1387 |
// the case when old_rev_thread equals to v_in |
| 1361 |
// (it also means that join and v_out coincide) |
|
| 1362 | 1388 |
if (old_rev_thread != v_in) {
|
| 1363 |
_thread[old_rev_thread] = right; |
|
| 1364 |
_rev_thread[right] = old_rev_thread; |
|
| 1389 |
_thread[old_rev_thread] = after; |
|
| 1390 |
_rev_thread[after] = old_rev_thread; |
|
| 1365 | 1391 |
} |
| ... | ... |
@@ -1368,3 +1394,3 @@ |
| 1368 | 1394 |
for (int i = 0; i != int(_dirty_revs.size()); ++i) {
|
| 1369 |
u = _dirty_revs[i]; |
|
| 1395 |
int u = _dirty_revs[i]; |
|
| 1370 | 1396 |
_rev_thread[_thread[u]] = u; |
| ... | ... |
@@ -1372,27 +1398,15 @@ |
| 1372 | 1398 |
|
| 1373 |
// Update _pred, |
|
| 1399 |
// Update _pred, _pred_dir, _last_succ and _succ_num for the |
|
| 1374 | 1400 |
// stem nodes from u_out to u_in |
| 1375 | 1401 |
int tmp_sc = 0, tmp_ls = _last_succ[u_out]; |
| 1376 |
u = u_out; |
|
| 1377 |
while (u != u_in) {
|
|
| 1378 |
w = _parent[u]; |
|
| 1379 |
_pred[u] = _pred[w]; |
|
| 1380 |
_forward[u] = !_forward[w]; |
|
| 1381 |
tmp_sc += _succ_num[u] - _succ_num[w]; |
|
| 1402 |
for (int u = u_out, p = _parent[u]; u != u_in; u = p, p = _parent[u]) {
|
|
| 1403 |
_pred[u] = _pred[p]; |
|
| 1404 |
_pred_dir[u] = -_pred_dir[p]; |
|
| 1405 |
tmp_sc += _succ_num[u] - _succ_num[p]; |
|
| 1382 | 1406 |
_succ_num[u] = tmp_sc; |
| 1383 |
_last_succ[w] = tmp_ls; |
|
| 1384 |
u = w; |
|
| 1407 |
_last_succ[p] = tmp_ls; |
|
| 1385 | 1408 |
} |
| 1386 | 1409 |
_pred[u_in] = in_arc; |
| 1387 |
|
|
| 1410 |
_pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN; |
|
| 1388 | 1411 |
_succ_num[u_in] = old_succ_num; |
| 1389 |
|
|
| 1390 |
// Set limits for updating _last_succ form v_in and v_out |
|
| 1391 |
// towards the root |
|
| 1392 |
int up_limit_in = -1; |
|
| 1393 |
int up_limit_out = -1; |
|
| 1394 |
if (_last_succ[join] == v_in) {
|
|
| 1395 |
up_limit_out = join; |
|
| 1396 |
} else {
|
|
| 1397 |
up_limit_in = join; |
|
| 1398 | 1412 |
} |
| ... | ... |
@@ -1400,9 +1414,11 @@ |
| 1400 | 1414 |
// Update _last_succ from v_in towards the root |
| 1401 |
for (u = v_in; u != up_limit_in && _last_succ[u] == v_in; |
|
| 1402 |
u = _parent[u]) {
|
|
| 1403 |
|
|
| 1415 |
int up_limit_out = _last_succ[join] == v_in ? join : -1; |
|
| 1416 |
int last_succ_out = _last_succ[u_out]; |
|
| 1417 |
for (int u = v_in; u != -1 && _last_succ[u] == v_in; u = _parent[u]) {
|
|
| 1418 |
_last_succ[u] = last_succ_out; |
|
| 1404 | 1419 |
} |
| 1420 |
|
|
| 1405 | 1421 |
// Update _last_succ from v_out towards the root |
| 1406 | 1422 |
if (join != old_rev_thread && v_in != old_rev_thread) {
|
| 1407 |
for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ; |
|
| 1423 |
for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ; |
|
| 1408 | 1424 |
u = _parent[u]) {
|
| ... | ... |
@@ -1410,6 +1426,7 @@ |
| 1410 | 1426 |
} |
| 1411 |
} else {
|
|
| 1412 |
for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ; |
|
| 1427 |
} |
|
| 1428 |
else if (last_succ_out != old_last_succ) {
|
|
| 1429 |
for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ; |
|
| 1413 | 1430 |
u = _parent[u]) {
|
| 1414 |
_last_succ[u] = |
|
| 1431 |
_last_succ[u] = last_succ_out; |
|
| 1415 | 1432 |
} |
| ... | ... |
@@ -1418,3 +1435,3 @@ |
| 1418 | 1435 |
// Update _succ_num from v_in to join |
| 1419 |
for (u = v_in; u != join; u = _parent[u]) {
|
|
| 1436 |
for (int u = v_in; u != join; u = _parent[u]) {
|
|
| 1420 | 1437 |
_succ_num[u] += old_succ_num; |
| ... | ... |
@@ -1422,3 +1439,3 @@ |
| 1422 | 1439 |
// Update _succ_num from v_out to join |
| 1423 |
for (u = v_out; u != join; u = _parent[u]) {
|
|
| 1440 |
for (int u = v_out; u != join; u = _parent[u]) {
|
|
| 1424 | 1441 |
_succ_num[u] -= old_succ_num; |
| ... | ... |
@@ -1427,8 +1444,6 @@ |
| 1427 | 1444 |
|
| 1428 |
// Update potentials |
|
| 1445 |
// Update potentials in the subtree that has been moved |
|
| 1429 | 1446 |
void updatePotential() {
|
| 1430 |
Cost sigma = _forward[u_in] ? |
|
| 1431 |
_pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] : |
|
| 1432 |
_pi[v_in] - _pi[u_in] + _cost[_pred[u_in]]; |
|
| 1433 |
// Update potentials in the subtree, which has been moved |
|
| 1447 |
Cost sigma = _pi[v_in] - _pi[u_in] - |
|
| 1448 |
_pred_dir[u_in] * _cost[in_arc]; |
|
| 1434 | 1449 |
int end = _thread[_last_succ[u_in]]; |
0 comments (0 inline)