Changes in lemon/network_simplex.h [956:141f9c0db4a3:1026:9312d6c89d02] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/network_simplex.h
r956 r1026 48 48 /// flow problem. 49 49 /// 50 /// In general, %NetworkSimplex is the fastest implementation available51 /// i n LEMON for this problem.52 /// Moreover, it supports both directions of the supply/demand inequality53 /// constraints. For more information, see \ref SupplyType.50 /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest 51 /// implementations available in LEMON for this problem. 52 /// Furthermore, this class supports both directions of the supply/demand 53 /// inequality constraints. For more information, see \ref SupplyType. 54 54 /// 55 55 /// Most of the parameters of the problem (except for the digraph) … … 64 64 /// algorithm. By default, it is the same as \c V. 65 65 /// 66 /// \warning Both number types must be signed and all input data must 66 /// \warning Both \c V and \c C must be signed number types. 67 /// \warning All input data (capacities, supply values, and costs) must 67 68 /// be integer. 68 69 /// … … 126 127 /// of the algorithm. 127 128 /// By default, \ref BLOCK_SEARCH "Block Search" is used, which 128 /// provedto be the most efficient and the most robust on various129 /// turend out to be the most efficient and the most robust on various 129 130 /// test inputs. 130 131 /// However, another pivot rule can be selected using the \ref run() … … 167 168 typedef std::vector<Value> ValueVector; 168 169 typedef std::vector<Cost> CostVector; 169 typedef std::vector<char> BoolVector; 170 // Note: vector<char> is used instead of vector<bool> for efficiency reasons 170 typedef std::vector<signed char> CharVector; 171 // Note: vector<signed char> is used instead of vector<ArcState> and 172 // vector<ArcDirection> for efficiency reasons 171 173 172 174 // State constants for arcs … … 177 179 }; 178 180 179 typedef std::vector<signed char> StateVector; 180 // Note: vector<signed char> is used instead of vector<ArcState> for 181 // efficiency reasons 181 // Direction constants for tree arcs 182 enum ArcDirection { 183 DIR_DOWN = -1, 184 DIR_UP = 1 185 }; 182 186 183 187 private: … … 218 222 IntVector _succ_num; 219 223 IntVector _last_succ; 224 CharVector _pred_dir; 225 CharVector _state; 220 226 IntVector _dirty_revs; 221 BoolVector _forward;222 StateVector _state;223 227 int _root; 224 228 225 229 // Temporary data used in the current pivot iteration 226 230 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 231 Value delta; 230 232 … … 251 253 const IntVector &_target; 252 254 const CostVector &_cost; 253 const StateVector &_state;255 const CharVector &_state; 254 256 const CostVector &_pi; 255 257 int &_in_arc; … … 303 305 const IntVector &_target; 304 306 const CostVector &_cost; 305 const StateVector &_state;307 const CharVector &_state; 306 308 const CostVector &_pi; 307 309 int &_in_arc; … … 342 344 const IntVector &_target; 343 345 const CostVector &_cost; 344 const StateVector &_state;346 const CharVector &_state; 345 347 const CostVector &_pi; 346 348 int &_in_arc; … … 415 417 const IntVector &_target; 416 418 const CostVector &_cost; 417 const StateVector &_state;419 const CharVector &_state; 418 420 const CostVector &_pi; 419 421 int &_in_arc; … … 518 520 const IntVector &_target; 519 521 const CostVector &_cost; 520 const StateVector &_state;522 const CharVector &_state; 521 523 const CostVector &_pi; 522 524 int &_in_arc; … … 571 573 // Check the current candidate list 572 574 int e; 575 Cost c; 573 576 for (int i = 0; i != _curr_length; ++i) { 574 577 e = _candidates[i]; 575 _cand_cost[e] = _state[e] * 576 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 577 if (_cand_cost[e] >= 0) { 578 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 579 if (c < 0) { 580 _cand_cost[e] = c; 581 } else { 578 582 _candidates[i--] = _candidates[--_curr_length]; 579 583 } … … 585 589 586 590 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) {591 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 592 if (c < 0) { 593 _cand_cost[e] = c; 590 594 _candidates[_curr_length++] = e; 591 595 } … … 634 638 /// 635 639 /// \param graph The digraph the algorithm runs on. 636 /// \param arc_mixing Indicate if the arcs have tobe stored in a640 /// \param arc_mixing Indicate if the arcs will be stored in a 637 641 /// 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) : 642 /// In general, it leads to similar performance as using the original 643 /// arc order, but it makes the algorithm more robust and in special 644 /// cases, even significantly faster. Therefore, it is enabled by default. 645 NetworkSimplex(const GR& graph, bool arc_mixing = true) : 641 646 _graph(graph), _node_id(graph), _arc_id(graph), 642 647 _arc_mixing(arc_mixing), … … 731 736 /// 732 737 /// \return <tt>(*this)</tt> 738 /// 739 /// \sa supplyType() 733 740 template<typename SupplyMap> 734 741 NetworkSimplex& supplyMap(const SupplyMap& map) { … … 747 754 /// 748 755 /// Using this function has the same effect as using \ref supplyMap() 749 /// with sucha map in which \c k is assigned to \c s, \c -k is756 /// with a map in which \c k is assigned to \c s, \c -k is 750 757 /// assigned to \c t and all other nodes have zero supply value. 751 758 /// … … 914 921 _parent.resize(all_node_num); 915 922 _pred.resize(all_node_num); 916 _ forward.resize(all_node_num);923 _pred_dir.resize(all_node_num); 917 924 _thread.resize(all_node_num); 918 925 _rev_thread.resize(all_node_num); … … 928 935 if (_arc_mixing) { 929 936 // Store the arcs in a mixed order 930 int k = std::max(int(std::sqrt(double(_arc_num))), 10);937 const int skip = std::max(_arc_num / _node_num, 3); 931 938 int i = 0, j = 0; 932 939 for (ArcIt a(_graph); a != INVALID; ++a) { … … 934 941 _source[i] = _node_id[_graph.source(a)]; 935 942 _target[i] = _node_id[_graph.target(a)]; 936 if ((i += k) >= _arc_num) i = ++j;943 if ((i += skip) >= _arc_num) i = ++j; 937 944 } 938 945 } else { … … 1078 1085 ART_COST = std::numeric_limits<Cost>::max() / 2 + 1; 1079 1086 } else { 1080 ART_COST = std::numeric_limits<Cost>::min();1087 ART_COST = 0; 1081 1088 for (int i = 0; i != _arc_num; ++i) { 1082 1089 if (_cost[i] > ART_COST) ART_COST = _cost[i]; … … 1117 1124 _state[e] = STATE_TREE; 1118 1125 if (_supply[u] >= 0) { 1119 _ forward[u] = true;1126 _pred_dir[u] = DIR_UP; 1120 1127 _pi[u] = 0; 1121 1128 _source[e] = u; … … 1124 1131 _cost[e] = 0; 1125 1132 } else { 1126 _ forward[u] = false;1133 _pred_dir[u] = DIR_DOWN; 1127 1134 _pi[u] = ART_COST; 1128 1135 _source[e] = _root; … … 1144 1151 _last_succ[u] = u; 1145 1152 if (_supply[u] >= 0) { 1146 _ forward[u] = true;1153 _pred_dir[u] = DIR_UP; 1147 1154 _pi[u] = 0; 1148 1155 _pred[u] = e; … … 1154 1161 _state[e] = STATE_TREE; 1155 1162 } else { 1156 _ forward[u] = false;1163 _pred_dir[u] = DIR_DOWN; 1157 1164 _pi[u] = ART_COST; 1158 1165 _pred[u] = f; … … 1185 1192 _last_succ[u] = u; 1186 1193 if (_supply[u] <= 0) { 1187 _ forward[u] = false;1194 _pred_dir[u] = DIR_DOWN; 1188 1195 _pi[u] = 0; 1189 1196 _pred[u] = e; … … 1195 1202 _state[e] = STATE_TREE; 1196 1203 } else { 1197 _ forward[u] = true;1204 _pred_dir[u] = DIR_UP; 1198 1205 _pi[u] = -ART_COST; 1199 1206 _pred[u] = f; … … 1238 1245 // Initialize first and second nodes according to the direction 1239 1246 // of the cycle 1247 int first, second; 1240 1248 if (_state[in_arc] == STATE_LOWER) { 1241 1249 first = _source[in_arc]; … … 1247 1255 delta = _cap[in_arc]; 1248 1256 int result = 0; 1249 Value d;1257 Value c, d; 1250 1258 int e; 1251 1259 1252 // Search the cycle along the path form the first node to the root1260 // Search the cycle form the first node to the join node 1253 1261 for (int u = first; u != join; u = _parent[u]) { 1254 1262 e = _pred[u]; 1255 d = _forward[u] ? 1256 _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]); 1263 d = _flow[e]; 1264 if (_pred_dir[u] == DIR_DOWN) { 1265 c = _cap[e]; 1266 d = c >= MAX ? INF : c - d; 1267 } 1257 1268 if (d < delta) { 1258 1269 delta = d; … … 1261 1272 } 1262 1273 } 1263 // Search the cycle along the path form the second node to the root 1274 1275 // Search the cycle form the second node to the join node 1264 1276 for (int u = second; u != join; u = _parent[u]) { 1265 1277 e = _pred[u]; 1266 d = _forward[u] ? 1267 (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e]; 1278 d = _flow[e]; 1279 if (_pred_dir[u] == DIR_UP) { 1280 c = _cap[e]; 1281 d = c >= MAX ? INF : c - d; 1282 } 1268 1283 if (d <= delta) { 1269 1284 delta = d; … … 1290 1305 _flow[in_arc] += val; 1291 1306 for (int u = _source[in_arc]; u != join; u = _parent[u]) { 1292 _flow[_pred[u]] += _forward[u] ? -val :val;1307 _flow[_pred[u]] -= _pred_dir[u] * val; 1293 1308 } 1294 1309 for (int u = _target[in_arc]; u != join; u = _parent[u]) { 1295 _flow[_pred[u]] += _ forward[u] ? val : -val;1310 _flow[_pred[u]] += _pred_dir[u] * val; 1296 1311 } 1297 1312 } … … 1308 1323 // Update the tree structure 1309 1324 void updateTreeStructure() { 1310 int u, w;1311 1325 int old_rev_thread = _rev_thread[u_out]; 1312 1326 int old_succ_num = _succ_num[u_out]; … … 1314 1328 v_out = _parent[u_out]; 1315 1329 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]]; 1330 // Check if u_in and u_out coincide 1331 if (u_in == u_out) { 1332 // Update _parent, _pred, _pred_dir 1333 _parent[u_in] = v_in; 1334 _pred[u_in] = in_arc; 1335 _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN; 1336 1337 // Update _thread and _rev_thread 1338 if (_thread[v_in] != u_out) { 1339 int after = _thread[old_last_succ]; 1340 _thread[old_rev_thread] = after; 1341 _rev_thread[after] = old_rev_thread; 1342 after = _thread[v_in]; 1343 _thread[v_in] = u_out; 1344 _rev_thread[u_out] = v_in; 1345 _thread[old_last_succ] = after; 1346 _rev_thread[after] = old_last_succ; 1347 } 1323 1348 } 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; 1349 // Handle the case when old_rev_thread equals to v_in 1350 // (it also means that join and v_out coincide) 1351 int thread_continue = old_rev_thread == v_in ? 1352 _thread[old_last_succ] : _thread[v_in]; 1353 1354 // Update _thread and _parent along the stem nodes (i.e. the nodes 1355 // between u_in and u_out, whose parent have to be changed) 1356 int stem = u_in; // the current stem node 1357 int par_stem = v_in; // the new parent of stem 1358 int next_stem; // the next stem node 1359 int last = _last_succ[u_in]; // the last successor of stem 1360 int before, after = _thread[last]; 1361 _thread[v_in] = u_in; 1362 _dirty_revs.clear(); 1363 _dirty_revs.push_back(v_in); 1364 while (stem != u_out) { 1365 // Insert the next stem node into the thread list 1366 next_stem = _parent[stem]; 1367 _thread[last] = next_stem; 1368 _dirty_revs.push_back(last); 1369 1370 // Remove the subtree of stem from the thread list 1371 before = _rev_thread[stem]; 1372 _thread[before] = after; 1373 _rev_thread[after] = before; 1374 1375 // Change the parent node and shift stem nodes 1376 _parent[stem] = par_stem; 1377 par_stem = stem; 1378 stem = next_stem; 1379 1380 // Update last and after 1381 last = _last_succ[stem] == _last_succ[par_stem] ? 1382 _rev_thread[par_stem] : _last_succ[stem]; 1383 after = _thread[last]; 1384 } 1385 _parent[u_out] = par_stem; 1386 _thread[last] = thread_continue; 1387 _rev_thread[thread_continue] = last; 1388 _last_succ[u_out] = last; 1389 1390 // Remove the subtree of u_out from the thread list except for 1391 // the case when old_rev_thread equals to v_in 1392 if (old_rev_thread != v_in) { 1393 _thread[old_rev_thread] = after; 1394 _rev_thread[after] = old_rev_thread; 1395 } 1396 1397 // Update _rev_thread using the new _thread values 1398 for (int i = 0; i != int(_dirty_revs.size()); ++i) { 1399 int u = _dirty_revs[i]; 1400 _rev_thread[_thread[u]] = u; 1401 } 1402 1403 // Update _pred, _pred_dir, _last_succ and _succ_num for the 1404 // stem nodes from u_out to u_in 1405 int tmp_sc = 0, tmp_ls = _last_succ[u_out]; 1406 for (int u = u_out, p = _parent[u]; u != u_in; u = p, p = _parent[u]) { 1407 _pred[u] = _pred[p]; 1408 _pred_dir[u] = -_pred_dir[p]; 1409 tmp_sc += _succ_num[u] - _succ_num[p]; 1410 _succ_num[u] = tmp_sc; 1411 _last_succ[p] = tmp_ls; 1412 } 1413 _pred[u_in] = in_arc; 1414 _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN; 1415 _succ_num[u_in] = old_succ_num; 1398 1416 } 1399 1417 1400 1418 // 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 } 1419 int up_limit_out = _last_succ[join] == v_in ? join : -1; 1420 int last_succ_out = _last_succ[u_out]; 1421 for (int u = v_in; u != -1 && _last_succ[u] == v_in; u = _parent[u]) { 1422 _last_succ[u] = last_succ_out; 1423 } 1424 1405 1425 // Update _last_succ from v_out towards the root 1406 1426 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;1427 for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ; 1408 1428 u = _parent[u]) { 1409 1429 _last_succ[u] = old_rev_thread; 1410 1430 } 1411 } else { 1412 for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ; 1431 } 1432 else if (last_succ_out != old_last_succ) { 1433 for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ; 1413 1434 u = _parent[u]) { 1414 _last_succ[u] = _last_succ[u_out];1435 _last_succ[u] = last_succ_out; 1415 1436 } 1416 1437 } 1417 1438 1418 1439 // Update _succ_num from v_in to join 1419 for ( u = v_in; u != join; u = _parent[u]) {1440 for (int u = v_in; u != join; u = _parent[u]) { 1420 1441 _succ_num[u] += old_succ_num; 1421 1442 } 1422 1443 // Update _succ_num from v_out to join 1423 for ( u = v_out; u != join; u = _parent[u]) {1444 for (int u = v_out; u != join; u = _parent[u]) { 1424 1445 _succ_num[u] -= old_succ_num; 1425 1446 } 1426 1447 } 1427 1448 1428 // Update potentials 1449 // Update potentials in the subtree that has been moved 1429 1450 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 1451 Cost sigma = _pi[v_in] - _pi[u_in] - 1452 _pred_dir[u_in] * _cost[in_arc]; 1434 1453 int end = _thread[_last_succ[u_in]]; 1435 1454 for (int u = u_in; u != end; u = _thread[u]) { … … 1590 1609 if (_sum_supply == 0) { 1591 1610 if (_stype == GEQ) { 1592 Cost max_pot = std::numeric_limits<Cost>::min();1611 Cost max_pot = -std::numeric_limits<Cost>::max(); 1593 1612 for (int i = 0; i != _node_num; ++i) { 1594 1613 if (_pi[i] > max_pot) max_pot = _pi[i];
Note: See TracChangeset
for help on using the changeset viewer.