Changes in / [997:a725503acfe9:998:3ffd46dc8e01] in lemon
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/network_simplex.h
r978 r991 167 167 typedef std::vector<Value> ValueVector; 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 172 173 // State constants for arcs … … 177 178 }; 178 179 179 typedef std::vector<signed char> StateVector; 180 // Note: vector<signed char> is used instead of vector<ArcState> for 181 // efficiency reasons 180 // Direction constants for tree arcs 181 enum ArcDirection { 182 DIR_DOWN = 1, 183 DIR_UP = 1 184 }; 182 185 183 186 private: … … 218 221 IntVector _succ_num; 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; 224 227 225 228 // Temporary data used in the current pivot iteration 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; 230 231 … … 251 252 const IntVector &_target; 252 253 const CostVector &_cost; 253 const StateVector &_state;254 const CharVector &_state; 254 255 const CostVector &_pi; 255 256 int &_in_arc; … … 303 304 const IntVector &_target; 304 305 const CostVector &_cost; 305 const StateVector &_state;306 const CharVector &_state; 306 307 const CostVector &_pi; 307 308 int &_in_arc; … … 342 343 const IntVector &_target; 343 344 const CostVector &_cost; 344 const StateVector &_state;345 const CharVector &_state; 345 346 const CostVector &_pi; 346 347 int &_in_arc; … … 415 416 const IntVector &_target; 416 417 const CostVector &_cost; 417 const StateVector &_state;418 const CharVector &_state; 418 419 const CostVector &_pi; 419 420 int &_in_arc; … … 518 519 const IntVector &_target; 519 520 const CostVector &_cost; 520 const StateVector &_state;521 const CharVector &_state; 521 522 const CostVector &_pi; 522 523 int &_in_arc; … … 571 572 // Check the current candidate list 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 if (_cand_cost[e] >= 0) { 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]; 579 582 } … … 585 588 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 if (_cand_cost[e] < 0) {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; 591 594 } … … 634 637 /// 635 638 /// \param graph The digraph the algorithm runs on. 636 /// \param arc_mixing Indicate if the arcs have tobe stored in a639 /// \param arc_mixing Indicate if the arcs will be stored in a 637 640 /// mixed order in the internal data structure. 638 /// In special cases, it could lead to better overall performance, 639 /// but it is usually slower. Therefore it is disabled by default. 640 NetworkSimplex(const GR& graph, bool arc_mixing = false) : 641 /// In general, it leads to similar performance as using the original 642 /// arc order, but it makes the algorithm more robust and in special 643 /// cases, even significantly faster. Therefore, it is enabled by default. 644 NetworkSimplex(const GR& graph, bool arc_mixing = true) : 641 645 _graph(graph), _node_id(graph), _arc_id(graph), 642 646 _arc_mixing(arc_mixing), … … 914 918 _parent.resize(all_node_num); 915 919 _pred.resize(all_node_num); 916 _ forward.resize(all_node_num);920 _pred_dir.resize(all_node_num); 917 921 _thread.resize(all_node_num); 918 922 _rev_thread.resize(all_node_num); … … 928 932 if (_arc_mixing) { 929 933 // Store the arcs in a mixed order 930 int k = std::max(int(std::sqrt(double(_arc_num))), 10);934 const int skip = std::max(_arc_num / _node_num, 3); 931 935 int i = 0, j = 0; 932 936 for (ArcIt a(_graph); a != INVALID; ++a) { … … 934 938 _source[i] = _node_id[_graph.source(a)]; 935 939 _target[i] = _node_id[_graph.target(a)]; 936 if ((i += k) >= _arc_num) i = ++j;940 if ((i += skip) >= _arc_num) i = ++j; 937 941 } 938 942 } else { … … 1117 1121 _state[e] = STATE_TREE; 1118 1122 if (_supply[u] >= 0) { 1119 _ forward[u] = true;1123 _pred_dir[u] = DIR_UP; 1120 1124 _pi[u] = 0; 1121 1125 _source[e] = u; … … 1124 1128 _cost[e] = 0; 1125 1129 } else { 1126 _ forward[u] = false;1130 _pred_dir[u] = DIR_DOWN; 1127 1131 _pi[u] = ART_COST; 1128 1132 _source[e] = _root; … … 1144 1148 _last_succ[u] = u; 1145 1149 if (_supply[u] >= 0) { 1146 _ forward[u] = true;1150 _pred_dir[u] = DIR_UP; 1147 1151 _pi[u] = 0; 1148 1152 _pred[u] = e; … … 1154 1158 _state[e] = STATE_TREE; 1155 1159 } else { 1156 _ forward[u] = false;1160 _pred_dir[u] = DIR_DOWN; 1157 1161 _pi[u] = ART_COST; 1158 1162 _pred[u] = f; … … 1185 1189 _last_succ[u] = u; 1186 1190 if (_supply[u] <= 0) { 1187 _ forward[u] = false;1191 _pred_dir[u] = DIR_DOWN; 1188 1192 _pi[u] = 0; 1189 1193 _pred[u] = e; … … 1195 1199 _state[e] = STATE_TREE; 1196 1200 } else { 1197 _ forward[u] = true;1201 _pred_dir[u] = DIR_UP; 1198 1202 _pi[u] = ART_COST; 1199 1203 _pred[u] = f; … … 1238 1242 // Initialize first and second nodes according to the direction 1239 1243 // of the cycle 1244 int first, second; 1240 1245 if (_state[in_arc] == STATE_LOWER) { 1241 1246 first = _source[in_arc]; … … 1247 1252 delta = _cap[in_arc]; 1248 1253 int result = 0; 1249 Value d;1254 Value c, d; 1250 1255 int e; 1251 1256 1252 // Search the cycle along the path form the first node to the root1257 // Search the cycle form the first node to the join node 1253 1258 for (int u = first; u != join; u = _parent[u]) { 1254 1259 e = _pred[u]; 1255 d = _forward[u] ? 1256 _flow[e] : (_cap[e] >= MAX ? INF : _cap[e]  _flow[e]); 1260 d = _flow[e]; 1261 if (_pred_dir[u] == DIR_DOWN) { 1262 c = _cap[e]; 1263 d = c >= MAX ? INF : c  d; 1264 } 1257 1265 if (d < delta) { 1258 1266 delta = d; … … 1261 1269 } 1262 1270 } 1263 // Search the cycle along the path form the second node to the root 1271 1272 // Search the cycle form the second node to the join node 1264 1273 for (int u = second; u != join; u = _parent[u]) { 1265 1274 e = _pred[u]; 1266 d = _forward[u] ? 1267 (_cap[e] >= MAX ? INF : _cap[e]  _flow[e]) : _flow[e]; 1275 d = _flow[e]; 1276 if (_pred_dir[u] == DIR_UP) { 1277 c = _cap[e]; 1278 d = c >= MAX ? INF : c  d; 1279 } 1268 1280 if (d <= delta) { 1269 1281 delta = d; … … 1290 1302 _flow[in_arc] += val; 1291 1303 for (int u = _source[in_arc]; u != join; u = _parent[u]) { 1292 _flow[_pred[u]] += _forward[u] ? val :val;1304 _flow[_pred[u]] = _pred_dir[u] * val; 1293 1305 } 1294 1306 for (int u = _target[in_arc]; u != join; u = _parent[u]) { 1295 _flow[_pred[u]] += _ forward[u] ? val : val;1307 _flow[_pred[u]] += _pred_dir[u] * val; 1296 1308 } 1297 1309 } … … 1308 1320 // Update the tree structure 1309 1321 void updateTreeStructure() { 1310 int u, w;1311 1322 int old_rev_thread = _rev_thread[u_out]; 1312 1323 int old_succ_num = _succ_num[u_out]; … … 1314 1325 v_out = _parent[u_out]; 1315 1326 1316 u = _last_succ[u_in]; // the last successor of u_in 1317 right = _thread[u]; // the node after it 1318 1319 // Handle the case when old_rev_thread equals to v_in 1320 // (it also means that join and v_out coincide) 1321 if (old_rev_thread == v_in) { 1322 last = _thread[_last_succ[u_out]]; 1327 // Check if u_in and u_out coincide 1328 if (u_in == u_out) { 1329 // Update _parent, _pred, _pred_dir 1330 _parent[u_in] = v_in; 1331 _pred[u_in] = in_arc; 1332 _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN; 1333 1334 // Update _thread and _rev_thread 1335 if (_thread[v_in] != u_out) { 1336 int after = _thread[old_last_succ]; 1337 _thread[old_rev_thread] = after; 1338 _rev_thread[after] = old_rev_thread; 1339 after = _thread[v_in]; 1340 _thread[v_in] = u_out; 1341 _rev_thread[u_out] = v_in; 1342 _thread[old_last_succ] = after; 1343 _rev_thread[after] = old_last_succ; 1344 } 1323 1345 } else { 1324 last = _thread[v_in]; 1325 } 1326 1327 // Update _thread and _parent along the stem nodes (i.e. the nodes 1328 // between u_in and u_out, whose parent have to be changed) 1329 _thread[v_in] = stem = u_in; 1330 _dirty_revs.clear(); 1331 _dirty_revs.push_back(v_in); 1332 par_stem = v_in; 1333 while (stem != u_out) { 1334 // Insert the next stem node into the thread list 1335 new_stem = _parent[stem]; 1336 _thread[u] = new_stem; 1337 _dirty_revs.push_back(u); 1338 1339 // Remove the subtree of stem from the thread list 1340 w = _rev_thread[stem]; 1341 _thread[w] = right; 1342 _rev_thread[right] = w; 1343 1344 // Change the parent node and shift stem nodes 1345 _parent[stem] = par_stem; 1346 par_stem = stem; 1347 stem = new_stem; 1348 1349 // Update u and right 1350 u = _last_succ[stem] == _last_succ[par_stem] ? 1351 _rev_thread[par_stem] : _last_succ[stem]; 1352 right = _thread[u]; 1353 } 1354 _parent[u_out] = par_stem; 1355 _thread[u] = last; 1356 _rev_thread[last] = u; 1357 _last_succ[u_out] = u; 1358 1359 // Remove the subtree of u_out from the thread list except for 1360 // the case when old_rev_thread equals to v_in 1361 // (it also means that join and v_out coincide) 1362 if (old_rev_thread != v_in) { 1363 _thread[old_rev_thread] = right; 1364 _rev_thread[right] = old_rev_thread; 1365 } 1366 1367 // Update _rev_thread using the new _thread values 1368 for (int i = 0; i != int(_dirty_revs.size()); ++i) { 1369 u = _dirty_revs[i]; 1370 _rev_thread[_thread[u]] = u; 1371 } 1372 1373 // Update _pred, _forward, _last_succ and _succ_num for the 1374 // stem nodes from u_out to u_in 1375 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]; 1382 _succ_num[u] = tmp_sc; 1383 _last_succ[w] = tmp_ls; 1384 u = w; 1385 } 1386 _pred[u_in] = in_arc; 1387 _forward[u_in] = (u_in == _source[in_arc]); 1388 _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; 1346 // Handle the case when old_rev_thread equals to v_in 1347 // (it also means that join and v_out coincide) 1348 int thread_continue = old_rev_thread == v_in ? 1349 _thread[old_last_succ] : _thread[v_in]; 1350 1351 // Update _thread and _parent along the stem nodes (i.e. the nodes 1352 // between u_in and u_out, whose parent have to be changed) 1353 int stem = u_in; // the current stem node 1354 int par_stem = v_in; // the new parent of stem 1355 int next_stem; // the next stem node 1356 int last = _last_succ[u_in]; // the last successor of stem 1357 int before, after = _thread[last]; 1358 _thread[v_in] = u_in; 1359 _dirty_revs.clear(); 1360 _dirty_revs.push_back(v_in); 1361 while (stem != u_out) { 1362 // Insert the next stem node into the thread list 1363 next_stem = _parent[stem]; 1364 _thread[last] = next_stem; 1365 _dirty_revs.push_back(last); 1366 1367 // Remove the subtree of stem from the thread list 1368 before = _rev_thread[stem]; 1369 _thread[before] = after; 1370 _rev_thread[after] = before; 1371 1372 // Change the parent node and shift stem nodes 1373 _parent[stem] = par_stem; 1374 par_stem = stem; 1375 stem = next_stem; 1376 1377 // Update last and after 1378 last = _last_succ[stem] == _last_succ[par_stem] ? 1379 _rev_thread[par_stem] : _last_succ[stem]; 1380 after = _thread[last]; 1381 } 1382 _parent[u_out] = par_stem; 1383 _thread[last] = thread_continue; 1384 _rev_thread[thread_continue] = last; 1385 _last_succ[u_out] = last; 1386 1387 // Remove the subtree of u_out from the thread list except for 1388 // the case when old_rev_thread equals to v_in 1389 if (old_rev_thread != v_in) { 1390 _thread[old_rev_thread] = after; 1391 _rev_thread[after] = old_rev_thread; 1392 } 1393 1394 // Update _rev_thread using the new _thread values 1395 for (int i = 0; i != int(_dirty_revs.size()); ++i) { 1396 int u = _dirty_revs[i]; 1397 _rev_thread[_thread[u]] = u; 1398 } 1399 1400 // Update _pred, _pred_dir, _last_succ and _succ_num for the 1401 // stem nodes from u_out to u_in 1402 int tmp_sc = 0, tmp_ls = _last_succ[u_out]; 1403 for (int u = u_out, p = _parent[u]; u != u_in; u = p, p = _parent[u]) { 1404 _pred[u] = _pred[p]; 1405 _pred_dir[u] = _pred_dir[p]; 1406 tmp_sc += _succ_num[u]  _succ_num[p]; 1407 _succ_num[u] = tmp_sc; 1408 _last_succ[p] = tmp_ls; 1409 } 1410 _pred[u_in] = in_arc; 1411 _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN; 1412 _succ_num[u_in] = old_succ_num; 1398 1413 } 1399 1414 1400 1415 // 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 _last_succ[u] = _last_succ[u_out]; 1404 } 1416 int up_limit_out = _last_succ[join] == v_in ? join : 1; 1417 int last_succ_out = _last_succ[u_out]; 1418 for (int u = v_in; u != 1 && _last_succ[u] == v_in; u = _parent[u]) { 1419 _last_succ[u] = last_succ_out; 1420 } 1421 1405 1422 // Update _last_succ from v_out towards the root 1406 1423 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;1424 for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ; 1408 1425 u = _parent[u]) { 1409 1426 _last_succ[u] = old_rev_thread; 1410 1427 } 1411 } else { 1412 for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ; 1428 } 1429 else if (last_succ_out != old_last_succ) { 1430 for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ; 1413 1431 u = _parent[u]) { 1414 _last_succ[u] = _last_succ[u_out];1432 _last_succ[u] = last_succ_out; 1415 1433 } 1416 1434 } 1417 1435 1418 1436 // Update _succ_num from v_in to join 1419 for ( u = v_in; u != join; u = _parent[u]) {1437 for (int u = v_in; u != join; u = _parent[u]) { 1420 1438 _succ_num[u] += old_succ_num; 1421 1439 } 1422 1440 // Update _succ_num from v_out to join 1423 for ( u = v_out; u != join; u = _parent[u]) {1441 for (int u = v_out; u != join; u = _parent[u]) { 1424 1442 _succ_num[u] = old_succ_num; 1425 1443 } 1426 1444 } 1427 1445 1428 // Update potentials 1446 // Update potentials in the subtree that has been moved 1429 1447 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 1448 Cost sigma = _pi[v_in]  _pi[u_in]  1449 _pred_dir[u_in] * _cost[in_arc]; 1434 1450 int end = _thread[_last_succ[u_in]]; 1435 1451 for (int u = u_in; u != end; u = _thread[u]) {
Note: See TracChangeset
for help on using the changeset viewer.