Changes in lemon/network_simplex.h [978:cbf32bf95954:1166:d59484d5fc1f] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/network_simplex.h
r978 r1166 48 48 /// flow problem. 49 49 /// 50 /// In general, %NetworkSimplex is the fastest implementation available 51 /// in LEMON for this problem. 52 /// Moreover, it supports both directions of the supply/demand inequality 53 /// constraints. For more information, see \ref SupplyType. 50 /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest 51 /// implementations available in LEMON for solving this problem. 52 /// (For more information, see \ref min_cost_flow_algs "the module page".) 53 /// Furthermore, this class supports both directions of the supply/demand 54 /// inequality constraints. For more information, see \ref SupplyType. 54 55 /// 55 56 /// Most of the parameters of the problem (except for the digraph) … … 64 65 /// algorithm. By default, it is the same as \c V. 65 66 /// 66 /// \warning Both number types must be signed and all input data must 67 /// \warning Both \c V and \c C must be signed number types. 68 /// \warning All input data (capacities, supply values, and costs) must 67 69 /// be integer. 68 70 /// … … 122 124 /// the \ref run() function. 123 125 /// 124 /// \ref NetworkSimplex provides five different pivot rule125 /// implementations that significantly affectthe running time126 /// \ref NetworkSimplex provides five different implementations for 127 /// the pivot strategy that significantly affects the running time 126 128 /// of the algorithm. 127 /// By default, \ref BLOCK_SEARCH "Block Search" is used, which 128 /// proved to be the most efficient and the most robust on various 129 /// test inputs. 130 /// However, another pivot rule can be selected using the \ref run() 131 /// function with the proper parameter. 129 /// According to experimental tests conducted on various problem 130 /// instances, \ref BLOCK_SEARCH "Block Search" and 131 /// \ref ALTERING_LIST "Altering Candidate List" rules turned out 132 /// to be the most efficient. 133 /// Since \ref BLOCK_SEARCH "Block Search" is a simpler strategy that 134 /// seemed to be slightly more robust, it is used by default. 135 /// However, another pivot rule can easily be selected using the 136 /// \ref run() function with the proper parameter. 132 137 enum PivotRule { 133 138 … … 155 160 /// The \e Altering \e Candidate \e List pivot rule. 156 161 /// It is a modified version of the Candidate List method. 157 /// It keeps only the severalbest eligible arcs from the former162 /// It keeps only a few of the best eligible arcs from the former 158 163 /// candidate list and extends this list in every iteration. 159 164 ALTERING_LIST … … 167 172 typedef std::vector<Value> ValueVector; 168 173 typedef std::vector<Cost> CostVector; 169 typedef std::vector<char> BoolVector; 170 // Note: vector<char> is used instead of vector<bool> for efficiency reasons 174 typedef std::vector<signed char> CharVector; 175 // Note: vector<signed char> is used instead of vector<ArcState> and 176 // vector<ArcDirection> for efficiency reasons 171 177 172 178 // State constants for arcs … … 177 183 }; 178 184 179 typedef std::vector<signed char> StateVector; 180 // Note: vector<signed char> is used instead of vector<ArcState> for 181 // efficiency reasons 185 // Direction constants for tree arcs 186 enum ArcDirection { 187 DIR_DOWN = -1, 188 DIR_UP = 1 189 }; 182 190 183 191 private: … … 218 226 IntVector _succ_num; 219 227 IntVector _last_succ; 228 CharVector _pred_dir; 229 CharVector _state; 220 230 IntVector _dirty_revs; 221 BoolVector _forward;222 StateVector _state;223 231 int _root; 224 232 225 233 // Temporary data used in the current pivot iteration 226 234 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 235 Value delta; 230 236 … … 251 257 const IntVector &_target; 252 258 const CostVector &_cost; 253 const StateVector &_state;259 const CharVector &_state; 254 260 const CostVector &_pi; 255 261 int &_in_arc; … … 303 309 const IntVector &_target; 304 310 const CostVector &_cost; 305 const StateVector &_state;311 const CharVector &_state; 306 312 const CostVector &_pi; 307 313 int &_in_arc; … … 342 348 const IntVector &_target; 343 349 const CostVector &_cost; 344 const StateVector &_state;350 const CharVector &_state; 345 351 const CostVector &_pi; 346 352 int &_in_arc; … … 415 421 const IntVector &_target; 416 422 const CostVector &_cost; 417 const StateVector &_state;423 const CharVector &_state; 418 424 const CostVector &_pi; 419 425 int &_in_arc; … … 518 524 const IntVector &_target; 519 525 const CostVector &_cost; 520 const StateVector &_state;526 const CharVector &_state; 521 527 const CostVector &_pi; 522 528 int &_in_arc; … … 537 543 SortFunc(const CostVector &map) : _map(map) {} 538 544 bool operator()(int left, int right) { 539 return _map[left] >_map[right];545 return _map[left] < _map[right]; 540 546 } 541 547 }; … … 555 561 const double BLOCK_SIZE_FACTOR = 1.0; 556 562 const int MIN_BLOCK_SIZE = 10; 557 const double HEAD_LENGTH_FACTOR = 0. 1;563 const double HEAD_LENGTH_FACTOR = 0.01; 558 564 const int MIN_HEAD_LENGTH = 3; 559 565 … … 571 577 // Check the current candidate list 572 578 int e; 579 Cost c; 573 580 for (int i = 0; i != _curr_length; ++i) { 574 581 e = _candidates[i]; 575 _cand_cost[e] = _state[e] * 576 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 577 if (_cand_cost[e] >= 0) { 582 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 583 if (c < 0) { 584 _cand_cost[e] = c; 585 } else { 578 586 _candidates[i--] = _candidates[--_curr_length]; 579 587 } … … 585 593 586 594 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) {595 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 596 if (c < 0) { 597 _cand_cost[e] = c; 590 598 _candidates[_curr_length++] = e; 591 599 } … … 597 605 } 598 606 for (e = 0; e != _next_arc; ++e) { 599 _cand_cost[e] = _state[e] *600 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);601 if (_cand_cost[e] < 0) {607 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 608 if (c < 0) { 609 _cand_cost[e] = c; 602 610 _candidates[_curr_length++] = e; 603 611 } … … 612 620 search_end: 613 621 614 // Make heap of the candidate list (approximating a partial sort) 615 make_heap( _candidates.begin(), _candidates.begin() + _curr_length, 616 _sort_func ); 617 618 // Pop the first element of the heap 622 // Perform partial sort operation on the candidate list 623 int new_length = std::min(_head_length + 1, _curr_length); 624 std::partial_sort(_candidates.begin(), _candidates.begin() + new_length, 625 _candidates.begin() + _curr_length, _sort_func); 626 627 // Select the entering arc and remove it from the list 619 628 _in_arc = _candidates[0]; 620 629 _next_arc = e; 621 pop_heap( _candidates.begin(), _candidates.begin() + _curr_length, 622 _sort_func ); 623 _curr_length = std::min(_head_length, _curr_length - 1); 630 _candidates[0] = _candidates[new_length - 1]; 631 _curr_length = new_length - 1; 624 632 return true; 625 633 } … … 634 642 /// 635 643 /// \param graph The digraph the algorithm runs on. 636 /// \param arc_mixing Indicate if the arcs have tobe stored in a644 /// \param arc_mixing Indicate if the arcs will be stored in a 637 645 /// 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) : 646 /// In general, it leads to similar performance as using the original 647 /// arc order, but it makes the algorithm more robust and in special 648 /// cases, even significantly faster. Therefore, it is enabled by default. 649 NetworkSimplex(const GR& graph, bool arc_mixing = true) : 641 650 _graph(graph), _node_id(graph), _arc_id(graph), 642 651 _arc_mixing(arc_mixing), … … 731 740 /// 732 741 /// \return <tt>(*this)</tt> 742 /// 743 /// \sa supplyType() 733 744 template<typename SupplyMap> 734 745 NetworkSimplex& supplyMap(const SupplyMap& map) { … … 747 758 /// 748 759 /// 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 is760 /// with a map in which \c k is assigned to \c s, \c -k is 750 761 /// assigned to \c t and all other nodes have zero supply value. 751 762 /// … … 914 925 _parent.resize(all_node_num); 915 926 _pred.resize(all_node_num); 916 _ forward.resize(all_node_num);927 _pred_dir.resize(all_node_num); 917 928 _thread.resize(all_node_num); 918 929 _rev_thread.resize(all_node_num); … … 928 939 if (_arc_mixing) { 929 940 // Store the arcs in a mixed order 930 int k = std::max(int(std::sqrt(double(_arc_num))), 10);941 const int skip = std::max(_arc_num / _node_num, 3); 931 942 int i = 0, j = 0; 932 943 for (ArcIt a(_graph); a != INVALID; ++a) { … … 934 945 _source[i] = _node_id[_graph.source(a)]; 935 946 _target[i] = _node_id[_graph.target(a)]; 936 if ((i += k) >= _arc_num) i = ++j;947 if ((i += skip) >= _arc_num) i = ++j; 937 948 } 938 949 } else { … … 1000 1011 } 1001 1012 1002 /// \brief Return the flow map (the primal solution). 1013 /// \brief Copy the flow values (the primal solution) into the 1014 /// given map. 1003 1015 /// 1004 1016 /// This function copies the flow value on each arc into the given … … 1024 1036 } 1025 1037 1026 /// \brief Return the potential map (the dual solution). 1038 /// \brief Copy the potential values (the dual solution) into the 1039 /// given map. 1027 1040 /// 1028 1041 /// This function copies the potential (dual value) of each node … … 1117 1130 _state[e] = STATE_TREE; 1118 1131 if (_supply[u] >= 0) { 1119 _ forward[u] = true;1132 _pred_dir[u] = DIR_UP; 1120 1133 _pi[u] = 0; 1121 1134 _source[e] = u; … … 1124 1137 _cost[e] = 0; 1125 1138 } else { 1126 _ forward[u] = false;1139 _pred_dir[u] = DIR_DOWN; 1127 1140 _pi[u] = ART_COST; 1128 1141 _source[e] = _root; … … 1144 1157 _last_succ[u] = u; 1145 1158 if (_supply[u] >= 0) { 1146 _ forward[u] = true;1159 _pred_dir[u] = DIR_UP; 1147 1160 _pi[u] = 0; 1148 1161 _pred[u] = e; … … 1154 1167 _state[e] = STATE_TREE; 1155 1168 } else { 1156 _ forward[u] = false;1169 _pred_dir[u] = DIR_DOWN; 1157 1170 _pi[u] = ART_COST; 1158 1171 _pred[u] = f; … … 1185 1198 _last_succ[u] = u; 1186 1199 if (_supply[u] <= 0) { 1187 _ forward[u] = false;1200 _pred_dir[u] = DIR_DOWN; 1188 1201 _pi[u] = 0; 1189 1202 _pred[u] = e; … … 1195 1208 _state[e] = STATE_TREE; 1196 1209 } else { 1197 _ forward[u] = true;1210 _pred_dir[u] = DIR_UP; 1198 1211 _pi[u] = -ART_COST; 1199 1212 _pred[u] = f; … … 1238 1251 // Initialize first and second nodes according to the direction 1239 1252 // of the cycle 1253 int first, second; 1240 1254 if (_state[in_arc] == STATE_LOWER) { 1241 1255 first = _source[in_arc]; … … 1247 1261 delta = _cap[in_arc]; 1248 1262 int result = 0; 1249 Value d;1263 Value c, d; 1250 1264 int e; 1251 1265 1252 // Search the cycle along the path form the first node to the root1266 // Search the cycle form the first node to the join node 1253 1267 for (int u = first; u != join; u = _parent[u]) { 1254 1268 e = _pred[u]; 1255 d = _forward[u] ? 1256 _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]); 1269 d = _flow[e]; 1270 if (_pred_dir[u] == DIR_DOWN) { 1271 c = _cap[e]; 1272 d = c >= MAX ? INF : c - d; 1273 } 1257 1274 if (d < delta) { 1258 1275 delta = d; … … 1261 1278 } 1262 1279 } 1263 // Search the cycle along the path form the second node to the root 1280 1281 // Search the cycle form the second node to the join node 1264 1282 for (int u = second; u != join; u = _parent[u]) { 1265 1283 e = _pred[u]; 1266 d = _forward[u] ? 1267 (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e]; 1284 d = _flow[e]; 1285 if (_pred_dir[u] == DIR_UP) { 1286 c = _cap[e]; 1287 d = c >= MAX ? INF : c - d; 1288 } 1268 1289 if (d <= delta) { 1269 1290 delta = d; … … 1290 1311 _flow[in_arc] += val; 1291 1312 for (int u = _source[in_arc]; u != join; u = _parent[u]) { 1292 _flow[_pred[u]] += _forward[u] ? -val :val;1313 _flow[_pred[u]] -= _pred_dir[u] * val; 1293 1314 } 1294 1315 for (int u = _target[in_arc]; u != join; u = _parent[u]) { 1295 _flow[_pred[u]] += _ forward[u] ? val : -val;1316 _flow[_pred[u]] += _pred_dir[u] * val; 1296 1317 } 1297 1318 } … … 1308 1329 // Update the tree structure 1309 1330 void updateTreeStructure() { 1310 int u, w;1311 1331 int old_rev_thread = _rev_thread[u_out]; 1312 1332 int old_succ_num = _succ_num[u_out]; … … 1314 1334 v_out = _parent[u_out]; 1315 1335 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]]; 1336 // Check if u_in and u_out coincide 1337 if (u_in == u_out) { 1338 // Update _parent, _pred, _pred_dir 1339 _parent[u_in] = v_in; 1340 _pred[u_in] = in_arc; 1341 _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN; 1342 1343 // Update _thread and _rev_thread 1344 if (_thread[v_in] != u_out) { 1345 int after = _thread[old_last_succ]; 1346 _thread[old_rev_thread] = after; 1347 _rev_thread[after] = old_rev_thread; 1348 after = _thread[v_in]; 1349 _thread[v_in] = u_out; 1350 _rev_thread[u_out] = v_in; 1351 _thread[old_last_succ] = after; 1352 _rev_thread[after] = old_last_succ; 1353 } 1323 1354 } 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; 1355 // Handle the case when old_rev_thread equals to v_in 1356 // (it also means that join and v_out coincide) 1357 int thread_continue = old_rev_thread == v_in ? 1358 _thread[old_last_succ] : _thread[v_in]; 1359 1360 // Update _thread and _parent along the stem nodes (i.e. the nodes 1361 // between u_in and u_out, whose parent have to be changed) 1362 int stem = u_in; // the current stem node 1363 int par_stem = v_in; // the new parent of stem 1364 int next_stem; // the next stem node 1365 int last = _last_succ[u_in]; // the last successor of stem 1366 int before, after = _thread[last]; 1367 _thread[v_in] = u_in; 1368 _dirty_revs.clear(); 1369 _dirty_revs.push_back(v_in); 1370 while (stem != u_out) { 1371 // Insert the next stem node into the thread list 1372 next_stem = _parent[stem]; 1373 _thread[last] = next_stem; 1374 _dirty_revs.push_back(last); 1375 1376 // Remove the subtree of stem from the thread list 1377 before = _rev_thread[stem]; 1378 _thread[before] = after; 1379 _rev_thread[after] = before; 1380 1381 // Change the parent node and shift stem nodes 1382 _parent[stem] = par_stem; 1383 par_stem = stem; 1384 stem = next_stem; 1385 1386 // Update last and after 1387 last = _last_succ[stem] == _last_succ[par_stem] ? 1388 _rev_thread[par_stem] : _last_succ[stem]; 1389 after = _thread[last]; 1390 } 1391 _parent[u_out] = par_stem; 1392 _thread[last] = thread_continue; 1393 _rev_thread[thread_continue] = last; 1394 _last_succ[u_out] = last; 1395 1396 // Remove the subtree of u_out from the thread list except for 1397 // the case when old_rev_thread equals to v_in 1398 if (old_rev_thread != v_in) { 1399 _thread[old_rev_thread] = after; 1400 _rev_thread[after] = old_rev_thread; 1401 } 1402 1403 // Update _rev_thread using the new _thread values 1404 for (int i = 0; i != int(_dirty_revs.size()); ++i) { 1405 int u = _dirty_revs[i]; 1406 _rev_thread[_thread[u]] = u; 1407 } 1408 1409 // Update _pred, _pred_dir, _last_succ and _succ_num for the 1410 // stem nodes from u_out to u_in 1411 int tmp_sc = 0, tmp_ls = _last_succ[u_out]; 1412 for (int u = u_out, p = _parent[u]; u != u_in; u = p, p = _parent[u]) { 1413 _pred[u] = _pred[p]; 1414 _pred_dir[u] = -_pred_dir[p]; 1415 tmp_sc += _succ_num[u] - _succ_num[p]; 1416 _succ_num[u] = tmp_sc; 1417 _last_succ[p] = tmp_ls; 1418 } 1419 _pred[u_in] = in_arc; 1420 _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN; 1421 _succ_num[u_in] = old_succ_num; 1398 1422 } 1399 1423 1400 1424 // 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 } 1425 int up_limit_out = _last_succ[join] == v_in ? join : -1; 1426 int last_succ_out = _last_succ[u_out]; 1427 for (int u = v_in; u != -1 && _last_succ[u] == v_in; u = _parent[u]) { 1428 _last_succ[u] = last_succ_out; 1429 } 1430 1405 1431 // Update _last_succ from v_out towards the root 1406 1432 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;1433 for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ; 1408 1434 u = _parent[u]) { 1409 1435 _last_succ[u] = old_rev_thread; 1410 1436 } 1411 } else { 1412 for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ; 1437 } 1438 else if (last_succ_out != old_last_succ) { 1439 for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ; 1413 1440 u = _parent[u]) { 1414 _last_succ[u] = _last_succ[u_out];1441 _last_succ[u] = last_succ_out; 1415 1442 } 1416 1443 } 1417 1444 1418 1445 // Update _succ_num from v_in to join 1419 for ( u = v_in; u != join; u = _parent[u]) {1446 for (int u = v_in; u != join; u = _parent[u]) { 1420 1447 _succ_num[u] += old_succ_num; 1421 1448 } 1422 1449 // Update _succ_num from v_out to join 1423 for ( u = v_out; u != join; u = _parent[u]) {1450 for (int u = v_out; u != join; u = _parent[u]) { 1424 1451 _succ_num[u] -= old_succ_num; 1425 1452 } 1426 1453 } 1427 1454 1428 // Update potentials 1455 // Update potentials in the subtree that has been moved 1429 1456 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 1457 Cost sigma = _pi[v_in] - _pi[u_in] - 1458 _pred_dir[u_in] * _cost[in_arc]; 1434 1459 int end = _thread[_last_succ[u_in]]; 1435 1460 for (int u = u_in; u != end; u = _thread[u]) {
Note: See TracChangeset
for help on using the changeset viewer.